Conceitos importantes

Conceitos importantes

1. Regular

   • Todos os vértices tem o mesmo grau

2. Completo

   • Uma aresta entre cada par de vértices

3. Bipartido

   • Conjunto de vértices pode ser partido em dois
     • Bipartido completo
       • Todos os vértices de uma partição liga a todos os vértices da outra

4. Rotulado

   • Cada vértice está associado a um rótulo

5. Valorado

   • Existem valores nas arestas

6. Multigrafo

   • Múltiplas arestas entre pares

7. Complementar

   • Grafo complementar de G contém as ligações que não estão em G

8. Subgrafo

   • Conjunto de vértices e arestas contidos no grafo original
     • Abrangente
       • Contém todos os vértices, mas não necessariamente todas as arestas
     • Induzido por vértices
       • Possui apenas parte dos vértices, porém estes têm todas as arestas
     • Induzido por arestas
       • Subconjunto de arestas e seus vértices

9. Cadeia(percurso)

   • Sequência de arestas adjacentes que ligam dois vértices

10. Caminho

    • Cadeia na qual os arcos possuem a mesma orientação

11. Distância

    • Menor comprimento capaz de ligar dois vértices

12. Ciclo

    • Cadeia simples(não repete arestas) e fechada(vértice inicial = final)
      • Ciclo orientado = circuito