Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 11 - Coggle Diagram

- - - - Caso o algoritmo volte para o vértice inicial e ele não tenha vértices adjecentes não-vistos, mas mesmo assim ainda tenha vértices não vistos no grafo, o algoritmo recomeça a partir de um vértice não-visto arbitrário
- - - - Se o grafo for não-direcionado ((u, v) = (v, u))
        
        Os vértices u e v são considerados adjecentes entre si, e são ligados por uma aresta não-direcionada
        
        Dizemos que os vértices u e v são tanto incidentes da aresta (u, v), como seus endpoints
        
        Um grafo só é não direcionado se todas as arestas forem não-direcionadas
      - Se o grafo for direcionado
        ((u, v) ≠ (v, u))
        
        Dizemos que a aresta (u, v) é direcionada de u (cauda da aresta) para v (cabeça da aresta)
        
        Um grafo só é direcionado se todas as arestas forem direcionadas
        
        Também chamado de dígrafo
        
        Quando o grafo possui duas arestas, (u, v) e (v, u), temos um loop
  - - - Dado um grafo G com n vértices, a matriz de incidência M terá dimensões nxn, onde cada linha e coluna representará um vértice de G, se houver uma ligação entre do vértice da coluna i para o da linha j, então o elemento M[i][j] será 1, caso contrário, será 0
      - A matriz de um grafo não-direcionado será sempre simétrico
    - - É basicamente um conjunto de listas ligadas, o header de cada lista é um vértice do grafo, e os próximos elementos dessas listas são os vértices nos quais o vértice do header é ligado, no grafo
  - - - Matriz de incidência
        (Matriz ponderada)
        
        Cada elemento da matriz vai indicar o peso da ligação do vértice da coluna i para o vértice da linha j
        
        Se não houver uma aresta do vértice u para o v, ao invés de 0, se usa um caractere especial qualquer (tipo ∅ ou ∞)
      - Listas de incidência
        
        Cada item da lista, representando as ligações do header, terão: o vértice para o qual é incidente e o peso dessa ligação
  - - - Se o caminho não apresentar vértices repetidos, ele é um caminho simples
      - Se o caminho começar e terminar no mesmo vértice, ele é um ciclo
        
        Se um grafo não possuir ciclos, então ele é considerado acíclico
      - O tamanho de um caminho/ciclo será igual ao número de vértices que está definindo o caminho
      - Se as arestas que ligam os vétices do caminho forem direcionadas, então o caminho é um caminho direcionado
- - - - Caso isso aconteça e se verifique que ainda faltam vértices a serem vistos, o algoritmo recomeça de um vértice não-visto qualquer
- - - - Se em algum momento tiver mais de uma fonte, então a fonte escolhida para retirada será escolhida a critério do programador