Grafo simples §

---

Grafos simples são grafos que não possuem laços e nem arestas múltiplas.

Abaixo algumas características de um grafo simples:

• Ordem do grafo ou cardinalidade de
  • O valor de
  • Ou seja, o número total de vértices que um grafo possui
• Tamanho do grafo ou cardinalidade de
  • O valor de
  • Em outras palavras, o número total de arestas que um grafo possui.

Note

Um grafo simples é dito como grafo trivial quando o número total de arestas for igual a 0.

Com base nessas definições sobre um grafo simples, podemos desenvolver as seguintes proposições:

1. Se é um grafo simples, então

Onde , temos

• representa todos os vértices do grafo e para cada vértice existem no máximo arestas incidentes em .
• elimina a redundância ao contabilizar as arestas simétricas, pois as arestas e são idênticas em grafos não orientados.

2. Se é um digrafo, então

Onde , temos

• Todo par ordenado de vértices distintos é um arco, então, para cada vértices , existem no máximo arcos incidentes em .

Referências §

---

Teoria dos grafos - Conceitos iniciais