Please enable JavaScript.

Coggle requires JavaScript to display documents.

Introdução aos Grafos - Coggle Diagram

- - - - Quando tem vértices em comum
    - - Várias aresta conectando o mesmo par de vértices
    - - Quantidade de aresta que sai do vértice
    - - Trajeto
        
        Passeio em que todas as suas arestas são distintas
      - Ciclo
        
        Começa e termina no mesmo vértice
        
        Grafos sem ciclos é chamado de aciclo
      - O caminho (percurso)
        
        k-1 aresta
    - - Quando existe um caminho entre os vértices
        
        Desconexo caso contrario :!!:
  - - - Vértices - trata
    - - Arestas - trata
- - - - que não contém ciclo!
  - - - Conceitos como:
        
        Descendente
        
        Ancestral
    - - vertice = 0
        
        é uma folha
      - Vértice > 1
        
        é um vertice interno, ou sejá existem +2 vertices ligado a ele
- - - - Ordem parcial
- - - - Transposto é quando altera a direção da aresta
- - - - Grafos espersos
        
        |E| é muito menor que |V|²
    - - Dirigidos
        
        |E|
      - Não dirigidos
        
        2.|E|
  - - - Grafo densos
        
        quando |E| está próximo de |V|²
- - - - Começa na raiz e vai explorar todos seus vizinhos, antes de avançar para os vizinhos dos vizinhos.
    - - Constante
    - - Custosa computacionalmente. :red_cross:
        
        Em seu pior caso aumenta exponencialmente.
  - - - Computacionalmente viável
    - - Começa da raiz (ou vértice inicial) e vai o mais fundo possível em um ramo antes de retroceder.