Grafo

Grafo

1. Vértices V(G)

   • ADJACENTES OU VIZINHOS
     • Dois vértices incidentes em uma mesma aresta são ADJACENTES OU VIZINHOS

2. Arestas E(G)

   • INCIDENTES
     • Os extremos de uma aresta são INCIDENTES e vice e versa
   • Paralelas
     • Ligam os mesmos pares de vértices

3. Laço

   • Aresta com extremos no mesmo vértice

4. Completo

   • é o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo completo de n vértices é frequentemente denotado por Kn. Ele tem n(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).

5. Simples

   • é um grafo não direcionado, sem laços e existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas). Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.

6. Conexo

   • Se possui um único componente

7. Bipartido

   • é o grafo cujos vértices podem ser divididos em dois conjuntos, nos quais não há arestas entre vértices de um mesmo conjunto. Para um grafo ser bipartido ele não pode conter circuitos de comprimento ímpar.
   • Completo
     •  é o grafo bipartido, cujo qualquer vértice do primeiro conjunto é adjacente a todos vértices do segundo conjunto

8. Representação Computacional

   • Matriz de Incidência
     • Analisar quais linhas incidem nas colunas, supondo que as linhas são os vértices e as colunas as arestas
   • Matriz de Adjacência
     • Linhas e colunas são indexadas pelos vértices
     • Grafos Densos
     • Operações com teste de arestas
   • Lista de Adjacência
     • Busca

9. Algoritmos

   • Busca em Largura
   • Busca em Profundidade
   • Dijkstra

10. Dirigido ou Direcionado

11. Não dirigido ou Não direcionao

Images and files in the map

• 
• 
• 
• 
• 
• 
• 
• 
• 
• [ED] Aula 64 - Grafos - Busca em Largura (Embed)
• Busca Em Largura em Grafos (Embed)
•