Aula 2

Aula 2

1. Índice de Wiener

   • Soma das distâncias entre todos os pares de vértices, dividido por 2.
   • pode também ser aplicado aos grafos ponderados...
   • Transitividade
     • atingibilidade: de um ponto a outro
     • Fecho Transitivo
       • direto (sucessores)
         • R +
       • inverso (antecessores)
         • R -

2. Grafo Conexo

   • há pelo menos uma cadeia ligando cada par de vértices
   • Chegar em todos os pontos sem ser necessário ordem
   • Relações através das vértices

3. Grafo Desconexo

   • Que não tem ligação

4. Conexidade em grafos direcionados

   • Existem cadeias entre todos os pares de vértices
   • Tipos
     • Grafo semi-fortemente conexo (sf-conexo) = Para cada par de vértices (v1,v2), existe um caminho de v1 para v2, ou de v2 para v1
       • Grafo fortemente conexo (f-conexo) = cada vértice pode ser alcançável partindo-se de qualquer outro vértice do grafo (considerando a orientação).
         • GRAFO FORTEMENTE CONEXO : se todo par de vértices está ligado por pelo menos um caminho em cada sentido, ou seja, se cada par de vértices participa de um circuito.

5. Algoritmo de Malgrange

   • Passo 1: Tabela para visualizar ligações
     • Passo 2: R+(x)
       • Passo 3: R- (x)
         • Passo 4: R+∩R-

6. Vértice de corte

   • vértice cuja remoção altera a conexidade do grafo original

7. Ponte

   • aresta cuja remoção provoca um redução na conexidade do grafo

8. Isomorfismo

   • existe uma relação de equivalência entre vértices e arestas de um e outro grafo

9. Árvore:

   • é um grafo conexo sem ciclos.

10. Arborescência

    • árvore que possui uma raiz.

11. Floresta

    • grafo cujas componentes conexas são árvores.

12. Busca em grafo

    • Largura e profundidade

13. Algoritmo de Floyd - Warshall

    • Permite definir a distância de cada vértice a todos os outros
    • Permite trabalhar com valores negativos
    • matriz de custos