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 $V$
  • O valor de $|V|=n$
  • Ou seja, o número total de vértices que um grafo possui
• Tamanho do grafo ou cardinalidade de $E$
  • O valor de $|E|=m$
  • 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 $m$ for igual a 0.

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

1. Se $G=(V,E)$ é um grafo simples, então

$$|E|\le \frac{n\cdot (n-1)}{2}=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$$

Onde $n=|V|$, temos

• $n$ representa todos os vértices do grafo e para cada vértice $u\in V$ existem no máximo $(n-1)$ arestas incidentes em $u$.
• $\frac{\dots }{2}$ elimina a redundância ao contabilizar as arestas simétricas, pois as arestas $\{v_0,v_1\}$ e $\{v_1,v_0\}$ são idênticas em grafos não orientados.

2. Se $D=(V,E)$ é um digrafo, então

$$|E|\le n\cdot (n-1)$$

Onde $n=|V|$, temos

• Todo par ordenado de vértices distintos é um arco, então, para cada vértices $u\in V$, existem no máximo $n-1$ arcos incidentes em $u$.

Referências

---

Teoria dos grafos - Conceitos iniciais