Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos - Coggle Diagram

- - - - Exemplo: Aresta (u,v) direcionada do vértice u (Tail) para o vértice v (Head)
        
        Sai de u e chega em v
  - - - Kv
  - - - Várias peças conectadas
        
        Componentes Conexos (máximo subgrafo conectado)
  - - - Peça única
- - - - Peso da aresta do i-ésimo vértice para o j-ésimo vértice se houver tal aresta, e um símbolo especial se não houver
- - - - Elementos i x j
        
        1 se tem uma aresta do vértice i para o j
        
        0 se não tem aresta do vértice i para o j
    - - A[i,j]=A[j,i]
        
        i>=0
        
        j<=n-1
  - - - Contém os vértices adjacentes
    - - Vértice que está sendo comparado
  - - - Lista de adjacência usa menos espaço que a matriz de adjacência
    - - Matriz de adjacência usa menos espaço que a lista de adjacência
- - - - Se todos os vértices são distintos o caminho é simples
    - - Número de vértices do caminho-1
      - Número de arestas
    - - Caminho Direcionado
        
        Sequência de vértices em que cada par consecutivo é conectado por uma aresta direcionada
- - - - A cada iteração o algoritmo processa para um vértice não visitado que é adjacente do vértice atual (Se tiver mais de um, escolhe-se arbitrariamente)
        
        Dead End
        
        Um vértice sem vértices adjacentes não visitados
        
        Quando chega nele, ele volta para o vértice anterior para tentar visitar os outros vértices não visitados
    - - Os vértices do mesmo componente devem ter sido visitados
      - Se houver vértices não visitados o DFS deve ser reiniciado em algum deles
    - - Coloca o vértice na pilha quando ele for visitado pela primeira vez
      - Retira vértice da pilha quando ele for um dead end
    - - Vértice de início de travessia serve como raiz da primeira árvore da floresta
      - Sempre que um vértice não visitado é encontrado, ele é anexado como filho do vértice que está sendo visitado
        
        Aresta usada é chamada de aresta de árvore
        
        Conjunto de todas essas arestas forma uma floresta
      - Aresta Traseira (Back Edges)
        
        Conecta um vértice ao seu ancestral diferente do seu pai
      - Aresta de Árvore
        
        Usadas para alcançar vértices não visitados anteriormente
        
        Considerando apenas as arestas nessa classe, obtém-se uma floresta
    - - Depende da estrutura de dados usada para representar o grafo
        
        Matriz de Adjacência
        
        Θ(|V|^2)
        
        Lista de Adjacência
        
        Θ (|V|+|E|)
    - - Verificar a presença de ciclo
        
        Aproveitar a floresta DFS
        
        Sem aresta traseira
        
        Acíclico
        
        Se houver aresta traseira
        
        Possui ciclo
      - Verificação de conectividade
        
        Inicia o percurso em vértice arbitrário
        
        Se visitou todos os vértices
        
        Grafo conexo
        
        Se não visitou todos os vértices
        
        Grafo não conexo
  - - - Fila iniciada com o vértice inicial da travessia
        
        A cada iteração o algoritmo identifica todos os vértices não visitados e adjacentes ao vértice frontal e adicionam a fila
        
        Depois disso o vértice frontal é removido da fila
    - - Aresta de árvore
        
        Vértice inicial da travessia serve como raiz da primeira árvore na floresta
        
        A cada novo vértice não visitado alcançado pela primeira vez, o vértice é anexado como filho
        
        Usado para alcançar vértices não visitados anteriormente
      - Aresta Cruzada (Cross Edge)
        
        Leva a um vértice visitado diferente de seu predecesssor imediato(pai)
    - - Matriz de Adjacência
        
        Θ(|V|^2)
      - Lista de Adjacência
        
        Θ(|V|+|E|)
    - - Dicionário FIFO
        
        Mesma ordem que é adicionado é retirado
    - - Verificar conectividade e presença de ciclo
      - Encontrar menor caminho entre 2 vértices
- - - - Sem ciclo dirigido
      - Necessário e suficiente para que a ordenação topológica seja possível
      - 2 algoritmos para verificar se o dígrafo é um dag e se for produz uma ordenação topológica
        
        1° Algoritmo
        
        Aplicação de DFS e observa a ordem que os vértices são dead end
        
        Tendo essa ordem invertida resulta numa solução de ordenação topológica
        
        Desde que não tenha sido encontrada nenhuma aresta traseira
        
        2° Algoritmo
        
        Identificar repetidamente uma fonte (vértice sem arestas de entradas) e excluir junto com as arestas de sáida dele
        
        Caso haja várias fontes, escolhe-se uma arbitrariamente
        
        Se não houver fonte o problema não pode ser resolvido
        
        A ordem de exclusão dos vértices produz uma solução para a ordenação topológica
        
        Solução do primeiro e do segundo algoritmo podem ser diferentes
        
        Ambas corretas
        
        Ordenação topológica tem várias soluções alternativas