Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Pode ser visto como uma coleção de pontos no plano em que alguns deles são conectados por arestas.
É um par de dois conjuntos: um conjunto finito e não vazio de vértices V e um conjunto E de pares desses itens, chamados de arestas.
Se (u, v) e (v, u) são iguais, então v e u são vértices adjacentes.
Um grafo não é dirigido se suas arestas não forem dirigidas.
Para um grafo dirigido (dígrafo), dizemos que a aresta (u, v) é dirigida do vértice u (tail) até o vértice v (head).
Para definições que não permitem múltiplas arestas entre os mesmos vértices, temos a seguinte inequação:
0 <= |E| <= |V|*(|V| - 1)/2
Um grafo completo possui todos os pares de vértices conectados por arestas entre si. Um grafo com poucas arestas em falta é chamado de denso. Um grafo esparso possui várias arestas em falta.
Representações
Matriz de adjacência
1 more item...
Lista de adjacência
1 more item...
Se um grafo é esparso, a representação por lista de adjacência usa menos espaço em relação à matriz de adjacência, exceto pelo armazenamento extra de ponteiros. O contrário ocorre para grafos densos.
1 more item...