Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs - Coggle Diagram
Graphs
Um
caminho
de u até v pode ser definido como uma sequencia de vértices adjacentes que começam em u e acabam em v.
Se todos os vértices do caminho são distintos, o caminho é
simples
O tamanho de um caminho é o número de vértices da sequência menos 1 (ou seja, o número de arestas)
Em digrafos, um caminho direcionado é uma sequência de vértices que que cada par consecutivos de vértices são ligados por uma aresta direcionada do vértice listado primeiro ao vértice listado depois
Um grafo é dito
conectado
se de todo caminho de u para v existe um caminho de v para u
Um
ciclo
é um caminho de tamanho positivo que começa e acaba no mesmo vértice e não passa pela mesma aresta mais de uma vez
Uma coleção de nós alguns ligados entre si por arestas ou arcos
Normalmente representamos grafos, fora de algoritmos, pelos seus vértices e suas arestas. Ex:
V = {a, b, c, d, e, f }, E = {(a, c), (a, d), (b, c), (b, f ), (c, e), (d, e), (e, f )}.
Formalmente um grafo é definido como um par de dois conjuntos
Um conjunto finito não vazio de itens chamados vértices
Um conjunto E de pares de vértices chamadas de arestas
Se a ordem do par do vértice não importar (ou seja, (u,v) = (v,u)), dizemos que os vertices u e v são adjacentes e são conectados por uma aresta indireta.
Nós chamamos os vértices u e v endpoints da aresta (u,v) e que são pertencentes a esta aresta. Também dizemos que a aresta (u,v) é pertencente a u e v
Um Grafo é chamado indireto se todas as suas arestas são indiretas.
Se a ordem do par do vértice importar (ou seja, (u,v) != (v,u)), dizemos que a aresta (u,v) é
direcionada
do vértice u, chamada de rabo do vértice, até o vértice v, chamado de cabeça do vértice. Também é dito que a aresta (u,v) sai de u e entra em v.
Um grafo que todo vértice é direcionado é chamado direcionado. Grafos direcionados também são chamados de digrafos.
Um grafo com todos os pares de vértices ligados por arestas é chamado de completo.
Um grafo com relativamente poucas arestas possíveis faltando é chamado de
denso
e um com poucas arestas possíveis existentes é chamado de
espaçado
.
É importante saber com qual dos dois tipos de grafos estamos lidando pois pode influenciar na escolha de representação do grafo e consequentemente no running time do algoritmo usado.
Representação de Grafos
Um grafo em algoritmo normalmente é representado em uma das duas maneiras
Matriz de Adjacência: Se um grafo tem n vértices montamos uma matriz booleana nxn com uma linha e uma coluna para cada um dos vértices do grafo. Se o elemento da linha i e coluna j for 1 quer dizer que existe uma aresta que vai da linha i até a coluna j, se o elemento for 0 quer dizer a aresta não existe.
Lista de Adjacência: É uma coleção de linked lists, uma para cada vértice, que contem todos os vértices adjacentes ao vértice de início. Uma lista de adjacência representa uma coluna de uma Matriz de adjacência mas só com os vértices que contém um.
Wheighted Graphs
É um grafo que suas arestas tem pesos.
São muito importantes para a solução de problemas como a do caixeiro viajante.
Sua representação pode ser facilmente a adaptação de uma matriz de adjacência onde em vez de 1 nas conexões onde as arestas existem, o peso seja colocado no lugar.
Buscas em Grafos
Depth-First Search(DFS)