Grafos

Grafos

1. Conjuntos de vértices e arestas e suas conexões.

   • O grau de um vértice é o número de arestas incidentes nele.

2. Irregulares (p. 25)

   • Os graus de todos os vértices são diferentes entre si.
   • Não existem grafos irregulares de ordem maior ou igual a 2.
   • Para todo inteiro maior que 2, existem dois grafos quase irregulares, ou seja, os graus de apenas dois vértices são iguais entre si. (p. 27)
     • Esses dois grafos são únicos e complementares.

3. Regulares (p. 33)

   • Todo vértice do grafo possui o mesmo grau r. Chamamos o grafo de "r-regular".
   • Dados quaisquer dois inteiros r e n, com r entre (inclusive) 0 e n-1, existe um grafo r-regular de ordem n. (p. 34)