Antes de explorar os resultados profundos da teoria dos grafos, precisamos construir um vocabulário preciso. Assim como qualquer área da matemática, a teoria dos grafos tem definições específicas que permitem comunicar ideias de forma clara e sem ambiguidade.
Neste artigo, estabelecemos a linguagem formal que usaremos ao longo de toda a série.
Por que precisar de uma linguagem formal? #
Sem um vocabulário compartilhado, a comunicação em teoria dos grafos seria imprecisa e ambígua. Uma linguagem formal é indispensável por ao menos quatro razões:
- Modelagem: problemas reais — redes de computadores, rotas de entrega, dependências entre tarefas — só podem ser analisados matematicamente depois de traduzidos para um grafo com definições precisas.
- Comunicação: quando dois pesquisadores dizem “vizinhança de \(v\)”, as definições garantem que ambos entendem exatamente o mesmo conjunto.
- Provas: sem definições rigorosas, demonstrações perdem validade; cada passo de uma prova apoia-se na definição exata dos termos usados.
- Implementação: as definições formais guiam diretamente as estruturas de dados (listas de adjacência, matrizes de incidência) que algoritmos em grafos utilizam.
Esses conceitos têm correspondências diretas em computação: a vizinhança \(N(v)\) é exatamente a lista de adjacência usada em algoritmos como Busca em Largura (BFS) e Busca em Profundidade (DFS); cliques são o núcleo de algoritmos de detecção de comunidades em redes sociais; e conjuntos independentes fundamentam o problema de coloração de grafos, em que vértices adjacentes não podem receber a mesma cor — restrição presente em escalonamento de tarefas, alocação de frequências de rádio e muito mais.
Definição Formal de Grafo #
Um grafo simples ou grafo \(G\) é um par \((V, E)\), denotado \(G = (V, E)\), onde \(V\) é um conjunto finito não vazio de elementos denominados vértices (também chamados de nós ou pontos) e \(E\) é um conjunto de pares não ordenados de elementos distintos de \(V\), chamados arestas.
- Vértices = nós = pontos — os três termos são sinônimos.
- Número de vértices de \(G\): \(|V(G)| = n\).
- Número de arestas de \(G\): \(|E(G)| = m\).
- Quando há vários grafos \(G_1, G_2, \ldots, G_k\), denotamos seus conjuntos de vértices e arestas respectivamente por \((V(G_1), E(G_1))\), \((V(G_2), E(G_2))\), …, \((V(G_k), E(G_k))\).
- Grafos = grafos simples — salvo indicação em contrário, “grafo” sempre significa grafo simples nesta série.
Dado um grafo \(G = (V, E)\), cada aresta \(e \in E\) será denotada pelo par \(e = (v, w)\) que a forma, com \(v, w \in V\). Nesse caso, os vértices \(v\) e \(w\) são os extremos da aresta \(e\). A aresta \(e\) é dita incidente aos vértices \(v\) e \(w\).
Exemplo 1
Seja \(G = (V, E)\) com:
$$V = \{a,\ b,\ c,\ d,\ e\}$$$$E = \{(a,b),\ (b,c),\ (a,c),\ (a,e),\ (c,d),\ (e,d)\}$$
Neste grafo:
- \(a\) e \(b\) são adjacentes; \(b\) e \(d\) não são adjacentes
- A aresta \((c,d)\) é incidente em \(c\) e em \(d\); os extremos de \((c,d)\) são \(c\) e \(d\)
- \(n = |V| = 5\) e \(m = |E| = 6\)
A figura abaixo mostra a representação geométrica de \(G\).
Representação Geométrica #
A maneira usual de representar um grafo é geométrica (no plano): cada vértice corresponde a um ponto do plano e cada aresta \((v, w)\) corresponde a uma linha unindo os pontos correspondentes aos vértices \(v\) e \(w\).
Exemplo 2
Seja \(G\) o grafo do Exemplo 1, com \(V = \{a,b,c,d,e\}\) e \(E = \{(a,b),(b,c),(a,c),(a,e),(c,d),(e,d)\}\). Este grafo admite múltiplas representações geométricas válidas: os vértices podem ser dispostos em diferentes posições no plano (por exemplo, em forma de pentágono ou em qualquer outra configuração), desde que as ligações sejam preservadas. A representação geométrica de um grafo não é única.
As duas representações abaixo correspondem ao mesmo grafo \(G\): mesmos vértices, mesmas arestas, posições distintas.
Se relaxarmos a definição de grafo simples de modo a admitir pares não ordenados iguais de elementos distintos de \(V\) — chamados arestas paralelas — e pares de elementos iguais \((v, v)\), chamados laços, obtemos um multigrafo. Nesta série, salvo aviso contrário, trabalhamos apenas com grafos simples.
Exemplo 3
Seja \(G = (V, E)\) com \(V = \{a, b, c, d\}\) e
$$E = \{(a,b),\ (a,b),\ (b,c),\ (c,d),\ (d,a),\ (c,c)\}$$As duas ocorrências de \((a,b)\) são arestas paralelas; \((c,c)\) é um laço.
O multigrafo abaixo ilustra arestas paralelas e um laço.
Vizinhança e Isolamento #
Seja \(G = (V, E)\) um grafo. Os vértices \(v\) e \(w \in V\) são ditos adjacentes ou vizinhos se \((v, w) \in E\). Chamamos de adjacência ou vizinhança de \(v\) em \(G\) o conjunto:
$$N(v) = \{w \in V \mid (v, w) \in E\}$$Quando há mais de um grafo em jogo, escrevemos \(N_G(v)\) para indicar a vizinhança de \(v\) no grafo \(G\).
Exemplo 4
Seja \(G\) o grafo do Exemplo 1. Calculamos a vizinhança de cada vértice:
- \(N(a) = \{b, c, e\}\)
- \(N(b) = \{a, c\}\)
- \(N(c) = \{b, a, d\}\)
- \(N(d) = \{c, e\}\)
- \(N(e) = \{a, d\}\)
A figura a seguir mostra \(G\) com o vértice \(a\) e suas arestas destacados, ilustrando \(N(a) = \{b, c, e\}\).
Um vértice \(v\) com \(N(v) = \emptyset\) é chamado de vértice isolado — ele não está conectado a nenhum outro vértice.
Exemplo 5
Seja \(G = (V, E)\) com \(V = \{1, 2, 3, 4, 5\}\) e
$$E = \{(1,2),\ (2,3),\ (1,3),\ (1,4),\ (3,4)\}$$Calculamos \(N(5) = \emptyset\). Logo, 5 é um vértice isolado em \(G\).
O vértice 5 (em destaque) não possui nenhuma aresta incidente, confirmando \(N(5) = \emptyset\).
Um vértice \(v\) de \(G\) é dito universal quando
$$N(v) = V - \{v\}$$ou seja, \(v\) é adjacente a todos os demais vértices do grafo.
Exemplo 6
Seja \(G = (V, E)\) com \(V = \{1, 2, 3, 4, 5\}\) e
$$E = \{(1,2),\ (1,3),\ (1,4),\ (1,5),\ (2,3),\ (3,4),\ (4,5)\}$$Calculamos \(N(1) = \{2, 3, 4, 5\} = V - \{1\}\). Logo, 1 é um vértice universal em \(G\).
O vértice 1 (em destaque) conecta-se a todos os demais: \(N(1) = V - \{1\}\).
Em um mesmo grafo com pelo menos dois vértices não podemos ter ao mesmo tempo um vértice isolado e um vértice universal: o universal seria vizinho do isolado, que por definição não tem vizinhos. A exceção é o grafo de um único vértice, em que \(N(v) = \emptyset = V - \{v\}\) e o vértice é as duas coisas.
O fluxograma abaixo resume como classificar qualquer vértice \(v\) em isolado, universal ou nenhum dos dois.
flowchart TD
A["Vértice v em G"] --> B{"N(v) = ∅ ?"}
B -- "Sim" --> C["Isolado
sem vizinhos"]
B -- "Não" --> D{"N(v) = V − {v} ?"}
D -- "Sim" --> E["Universal
adjacente a todos"]
D -- "Não" --> F["Nem isolado
nem universal"]
O Grafo Complemento #
O complemento de \(G\), denotado \(\bar{G}\), é o grafo com o mesmo conjunto de vértices \(V(G)\), tal que dois vértices distintos são adjacentes em \(\bar{G}\) se e somente se não são adjacentes em \(G\):
$$V(\bar{G}) = V(G)$$$$E(\bar{G}) = \{(v, w) \mid v, w \in V(G)\ \text{e}\ (v, w) \notin E(G)\}$$
Exemplo 7
Seja \(G\) o grafo do Exemplo 1: \(V = \{a,b,c,d,e\}\) e \(E(G) = \{(a,b),(b,c),(a,c),(a,e),(c,d),(e,d)\}\).
O grafo completo em 5 vértices teria \(\binom{5}{2} = 10\) arestas. Como \(m = 6\), o complemento \(\bar{G}\) tem \(10 - 6 = 4\) arestas — exatamente os pares que não aparecem em \(G\):
$$E(\bar{G}) = \{(a,d),\ (b,d),\ (b,e),\ (c,e)\}$$Os dois grafos abaixo ilustram \(G\) e \(\bar{G}\): note que as arestas presentes em um estão ausentes no outro.
Subgrafos #
Uma das noções mais importantes é a de subgrafo — partes de um grafo obtidas mantendo um subconjunto de seus vértices e arestas.
Sejam os grafos \(G\) e \(H\). \(H\) é dito um subgrafo de \(G\), denotado \(H \subseteq G\), se:
- \(V(H) \subseteq V(G)\)
- \(E(H) \subseteq E(G)\)
Exemplo 8
Sejam \(G\) e \(H\) os seguintes grafos:
\(V(G) = \{a, b, c, d, e\}\),
\(E(G) = \{(a,b),\ (b,c),\ (a,c),\ (c,d),\ (e,d),\ (a,e)\}\)
\(V(H) = \{a, b, c, d\}\), \(E(H) = \{(a,b),\ (b,c)\}\)
Como \(V(H) \subseteq V(G)\) e \(E(H) \subseteq E(G)\), concluímos que \(H\) é um subgrafo de \(G\).
A figura mostra \(G\) à esquerda e \(H\) à direita. Note que \(H\) tem apenas 2 das 6 arestas de \(G\), e o vértice \(d\) fica isolado em \(H\).
Subgrafo Induzido #
Seja \(G\) um grafo e \(A \subseteq V(G)\), ou seja, um subconjunto dos vértices de \(G\). O subgrafo de \(G\) induzido por \(A\), denotado \(G[A]\), é definido por:
$$V(G[A]) = A$$$$E(G[A]) = \{(x, y) \in E(G) \mid x \in A\ \text{e}\ y \in A\}$$
\(G[A]\) herda todas as arestas de \(G\) cujos dois extremos pertencem a \(A\).
Exemplo 9
Considerando o grafo \(G\) do Exemplo 8, seja \(A = \{a, b, c, d\}\) (\(A \subset V(G)\)). O subgrafo \(F = G[A]\) induzido por \(A\) tem:
\(V(F) = \{a, b, c, d\}\)
\(E(F) = \{(a,b),\ (b,c),\ (a,c),\ (c,d)\}\)
Observe que \((a,c)\) e \((c,d)\) pertencem a \(E(F)\) porque ambos os extremos de cada uma dessas arestas pertencem a \(A\) e elas existem em \(E(G)\).
Na figura, os vértices de \(A\) estão destacados em \(G\) (esquerda); à direita, \(F = G[A]\) com todas as 4 arestas herdadas.
O subgrafo \(H\) do Exemplo 8 e o subgrafo \(F\) do Exemplo 9 têm o mesmo conjunto de vértices \(\{a,b,c,d\}\), mas não são iguais:
- \(E(H) = \{(a,b),\ (b,c)\}\) — \(H\) não é subgrafo induzido de \(G\) pelo conjunto \(\{a,b,c,d\}\), pois as arestas \((a,c)\) e \((c,d)\) existem em \(G\) com ambos os extremos em \(\{a,b,c,d\}\), mas foram omitidas de \(H\).
- \(E(F) = \{(a,b),\ (b,c),\ (a,c),\ (c,d)\}\) — \(F\) é subgrafo induzido porque herdou todas as arestas de \(G\) entre os vértices de \(A\).
A comparação a seguir coloca \(G\), \(H\) e \(F\) lado a lado: \(H\) e \(F\) têm o mesmo \(V\), mas \(H\) omite arestas que \(F\) obrigatoriamente herda.
Subgrafo Gerador #
Sejam os grafos \(G\) e \(H\). \(H\) é dito um subgrafo gerador de \(G\) se \(H\) é um subgrafo de \(G\) e \(V(H) = V(G)\) — ou seja, \(H\) contém todos os vértices de \(G\), mas possivelmente menos arestas.
Exemplo 10
Considerando o grafo \(G\) do Exemplo 8, seja \(H\) dado por:
\(V(H) = V(G) = \{a, b, c, d, e\}\), \(E(H) = \{(a,b),\ (a,c),\ (c,d)\}\)
Como \(V(H) = V(G)\) e \(E(H) \subseteq E(G)\), \(H\) é um subgrafo gerador de \(G\).
O subgrafo gerador \(H\) mantém todos os 5 vértices de \(G\), mas preserva apenas 3 das 6 arestas — o vértice \(e\) fica isolado.
O diagrama a seguir sintetiza as relações entre os tipos de subgrafo estudados e seus casos especiais.
flowchart TD
A["Subgrafo H ⊆ G
V(H) ⊆ V(G) e E(H) ⊆ E(G)"] --> B["Subgrafo Induzido G[A]
herda todas as arestas de G
cujos dois extremos estão em A"]
A --> C["Subgrafo Gerador
V(H) = V(G)
possivelmente menos arestas"]
B --> D["Clique A
G[A] é completo (= Kk)"]
B --> E["Conjunto Independente S
G[S] é nulo (= Ns)"]
Grafos Especiais: Completos e Nulos #
Um grafo \(G\) é dito completo se todos os seus pares de vértices distintos são adjacentes. Em outras palavras, todos os seus vértices são universais. Um grafo completo com \(n\) vértices é representado por \(K_n\).
Número de arestas: \(|E(K_n)| = \binom{n}{2} = \dfrac{n(n-1)}{2}\)
Exemplo 11
- \(K_1\): 1 vértice, 0 arestas
- \(K_2\): 2 vértices, 1 aresta
- \(K_3\): 3 vértices, 3 arestas
- \(K_4\): 4 vértices, 6 arestas
- \(K_5\): 5 vértices, 10 arestas
Os cinco primeiros grafos completos são mostrados abaixo.
Clique #
Seja \(G\) um grafo e \(A \subseteq V(G)\) um subconjunto de vértices. \(A\) é uma clique de \(G\) se \(G[A]\) é um grafo completo — todo par de vértices em \(A\) é adjacente.
Exemplo 12
Seja \(G\) um grafo com \(V = \{a,b,c,d,e,f,g,h\}\) e arestas:
$$(a,b),\ (a,c),\ (a,d),\ (b,c),\ (b,d),\ (c,d),\ (c,e),\ (e,f),\ (c,f),\ (c,h),\ (h,g),\ (g,f)$$Os seguintes subconjuntos são cliques de \(G\):
- \(A_1 = \{a, b, c, d\}\) — clique de tamanho 4 (\(G[A_1] = K_4\))
- \(A_2 = \{c, e, f\}\) — clique de tamanho 3 (\(G[A_2] = K_3\))
- \(A_3 = \{g, h\}\) — clique de tamanho 2
Outros \(A_i\) também são possíveis: qualquer subconjunto de \(A_1\) com 2 ou 3 vértices — por exemplo \(\{a,b,c\}\), \(\{a,c,d\}\) — forma uma clique. Uma clique é maximal quando não está contida em nenhuma clique maior, e máxima quando nenhuma clique do grafo tem mais vértices do que ela. \(A_1\), \(A_2\) e \(A_3\) são maximais — assim como \(\{c,h\}\) e \(\{f,g\}\) —, mas só \(A_1\), com 4 vértices, é máxima. Achar uma clique máxima num grafo grande é um problema difícil: não se conhece algoritmo eficiente para o caso geral (veja o verbete Clique problem).
A figura abaixo mostra \(G\) com os vértices coloridos por grupo: \(A_1\) em azul, \(A_2\) em laranja, \(A_3\) em verde; o vértice \(c\) (compartilhado por \(A_1\) e \(A_2\)) aparece destacado.
Grafo Nulo #
O contraponto natural de \(K_n\) é o grafo nulo: em vez de todos os pares adjacentes, nenhum par é adjacente.
Um grafo \(G\) é dito nulo (ou completamente independente) se todos os seus pares de vértices distintos não são adjacentes. Em outras palavras, todos os seus vértices são isolados. Um grafo nulo com \(n\) vértices é denotado por \(N_n\).
Exemplo 13
- \(N_1\): 1 vértice, 0 arestas
- \(N_2\): 2 vértices, 0 arestas
- \(N_3\): 3 vértices, 0 arestas
- \(N_4\): 4 vértices, 0 arestas
- \(N_5\): 5 vértices, 0 arestas
Os cinco primeiros grafos nulos são mostrados abaixo.
Conjunto Independente #
Seja \(G\) um grafo e \(S \subseteq V(G)\) um subconjunto de vértices. \(S\) é um conjunto independente (ou estável) de \(G\) se \(G[S]\) é um grafo nulo — nenhum par de vértices em \(S\) é adjacente.
Exemplo 14
Seja \(G\) o grafo do Exemplo 12. Os seguintes subconjuntos são conjuntos independentes de \(G\):
- \(S_1 = \{a, e, g\}\)
- \(S_2 = \{e, h\}\)
- \(S_3 = \{d, h, f\}\)
A figura mostra \(G\) com o conjunto independente \(S_1 = \{a, e, g\}\) destacado: nenhum par desses vértices compartilha uma aresta.
Se \(A\) é uma clique em \(G\), então \(A\) é um conjunto independente no complemento \(\bar{G}\) — e vice-versa. Isso decorre diretamente das definições: as arestas presentes em \(G[A]\) estão ausentes em \(\bar{G}[A]\), transformando um subgrafo completo em um subgrafo nulo.
Exercícios #
Os exercícios a seguir consolidam os conceitos apresentados — vizinhança, complemento, subgrafos e independência.
Exercício 1 — Vizinhança e vértices especiais
Enunciado:
Dado o grafo \(G = (V, E)\) com \(V = \{1, 2, 3, 4, 5\}\) e
$$E = \{(1,2),\ (1,3),\ (2,4),\ (3,4),\ (4,5)\}$$a) Calcule \(N(v)\) para cada vértice \(v \in V\).
b) Existe algum vértice isolado? E algum vértice universal?
Solução:
a) Percorrendo as arestas para cada vértice:
- \(N(1) = \{2, 3\}\)
- \(N(2) = \{1, 4\}\)
- \(N(3) = \{1, 4\}\)
- \(N(4) = \{2, 3, 5\}\)
- \(N(5) = \{4\}\)
b) Nenhum vértice tem \(N(v) = \emptyset\), logo não há vértice isolado. Nenhum vértice tem \(N(v) = V - \{v\}\) — por exemplo, \(N(1) = \{2,3\} \neq \{2,3,4,5\}\) — logo não há vértice universal.
O grafo \(G\) com todas as vizinhanças anotadas:
Exercício 2 — Grafo complemento
Enunciado:
Seja \(G\) o grafo do Exercício 1. Determine \(\bar{G}\).
Solução:
\(K_5\) tem \(\binom{5}{2} = 10\) arestas. Como \(|E(G)| = 5\), o complemento tem \(10 - 5 = 5\) arestas — os pares que não aparecem em \(G\):
$$E(\bar{G}) = \{(1,4),\ (1,5),\ (2,3),\ (2,5),\ (3,5)\}$$\(G\) e \(\bar{G}\) lado a lado:
Exercício 3 — Subgrafo induzido e conjunto independente
Enunciado:
Seja \(G\) o grafo do Exercício 1 e \(A = \{1, 2, 4\}\).
a) Determine o subgrafo induzido \(G[A]\).
b) \(S = \{1, 5\}\) é um conjunto independente de \(G\)? Justifique.
Solução:
a) \(V(G[A]) = \{1, 2, 4\}\). As arestas de \(G\) com ambos os extremos em \(A\) são \((1,2)\) e \((2,4)\). Portanto:
$$E(G[A]) = \{(1,2),\ (2,4)\}$$b) Sim. O único par em \(S\) é \(\{1, 5\}\), e \((1,5) \notin E(G)\). Logo \(G[S]\) é um grafo nulo e \(S\) é um conjunto independente.
À esquerda: \(G\) com \(A = \{1,2,4\}\) em laranja e arestas de \(G[A]\) destacadas. À direita: \(S = \{1,5\}\) em verde — nenhuma aresta os conecta.
Resumo #
| Conceito | Símbolo/Notação | Descrição |
|---|---|---|
| Grafo simples | \(G = (V, E)\) | Vértices + arestas (pares não ordenados) |
| Aresta | \(e = (v, w)\) | Par não ordenado; \(v\) e \(w\) são os extremos |
| Extremos da aresta | \(v, w\) | Os dois vértices que formam a aresta \((v, w)\) |
| Incidência | — | \(e = (v, w)\) é incidente aos vértices \(v\) e \(w\) |
| Número de vértices | \(n\) | \(n = \lvert V(G) \rvert\) |
| Número de arestas | \(m\) | \(m = \lvert E(G) \rvert\) |
| Vizinhança | \(N(v)\), \(N_G(v)\) | Conjunto de vizinhos de \(v\) em \(G\) |
| Vértice isolado | — | \(N(v) = \emptyset\) |
| Vértice universal | — | \(N(v) = V - \{v\}\) |
| Complemento | \(\bar{G}\) | Mesmo \(V\), arestas complementares |
| Subgrafo | \(H \subseteq G\) | \(V(H) \subseteq V(G)\) e \(E(H) \subseteq E(G)\) |
| Subgrafo induzido | \(G[A]\) | Vértices de \(A\) + todas as arestas herdadas |
| Subgrafo gerador | — | \(V(H) = V(G)\), possivelmente menos arestas |
| Grafo completo | \(K_n\) | Todo par adjacente; \(\binom{n}{2}\) arestas |
| Grafo nulo | \(N_n\) | Sem arestas; todos os vértices isolados |
| Clique | — | \(A \subseteq V(G)\) com \(G[A]\) completo |
| Conjunto independente | — | \(S \subseteq V(G)\) com \(G[S]\) nulo |
Próximos Passos #
Com o vocabulário estabelecido — vértices, arestas, vizinhança, subgrafos e grafos especiais — temos a base para começar a medir propriedades locais de cada vértice. O que ainda falta é quantificar quantas arestas incidem em cada vértice: essa medida, chamada de grau, é o objeto central do próximo artigo, onde também demonstraremos o elegante Teorema do Aperto de Mãos, que relaciona a soma dos graus ao número de arestas do grafo.
