Grafos, percursos e isomorfismos

Um grafo representa objetos e ligações entre eles. Os vértices podem ser cidades e as arestas podem ser estradas. Para uma estrada de dois sentidos usamos um par não ordenado; para uma ligação de sentido único usamos um par ordenado, como nas relações. Neste capítulo, os grafos são finitos.

Vértices e arestas

Um grafo não dirigido simples é $G=(V,E)$, onde $V$ é o conjunto de vértices e $E$ contém pares de vértices distintos:

$$E\subseteq\{\{u,v\}:u,v\in V,\ u\ne v\}.$$

Não há laços nem arestas repetidas. Um grafo dirigido, ou dígrafo, usa $E\subseteq V\times V$. Neste caso $(u,v)$ e $(v,u)$ são ligações diferentes e podem existir laços. Um multigrafo admite várias arestas entre o mesmo par e tem de as distinguir.

Dois vértices ligados por uma aresta são adjacentes, ou vizinhos. Uma aresta é incidente nos seus extremos. Uma representação no papel pode ter cruzamentos que não são vértices; só contam os vértices declarados.

Um subgrafo escolhe vértices e algumas arestas do grafo original, conservando os extremos das arestas escolhidas. O subgrafo induzido por $U\subseteq V$ conserva todas as arestas com ambos os extremos em $U$. O complemento de um grafo simples, no mesmo conjunto de vértices, contém exatamente os pares distintos que não eram arestas.

Subgrafos de um bipartido completo

Em K_{2,3\}, com partes $\{a,b\}$ e $\{1,2,3\}$, cada letra liga-se a cada número. Retirar apenas a aresta $\{a,1\}$ dá um subgrafo ainda bipartido, mas já não completo bipartido: na bipartição original falta uma ligação entre partes.

Para excluir também uma bipartição alternativa, observa que o subgrafo continua conexo. Numa componente conexa, escolher a parte de um vértice determina as restantes ao alternar pelas arestas. Aqui, o caminho $a,2,b,1$ obriga $a$ e 1 a partes opostas, embora não haja aresta entre eles. Logo nenhuma bipartição o torna completo.

Um subgrafo induzido funciona de outra forma. Se conservamos $\{a,b,1,2\}$, ficam todas as quatro arestas entre as partes, dando $K_{2,2}$. Em geral, um subconjunto $U$ dos vértices de $K_{m,n}$ induz $K_{|U\cap V_1|,|U\cap V_2|}$, porque não pode apagar arestas entre vértices conservados. Quando só conserva vértices de uma parte, esse índice é zero e não há arestas. Apagar uma aresta e escolher um subconjunto de vértices são assim operações diferentes: a primeira pode destruir completude mantendo bipartição, a segunda conserva todas as arestas entre os vértices que ficam.

Famílias de grafos

Grafo	Vértices e arestas
$N_n$, vazio	$n$ vértices, nenhuma aresta.
$K_n$, completo	Todas as ligações entre vértices distintos; $n(n-1)/2$ arestas.
$P_n$, caminho	$n$ vértices em sequência; $n-1$ arestas.
$C_n$, ciclo, $n\ge3$	A sequência fecha-se; $n$ arestas.
$K_{m,n}$, bipartido completo	Duas partes de tamanhos $m,n$, todas as ligações entre partes; $mn$ arestas.
$S_n$, estrela	Um centro e $n-1$ folhas; é $K_{1,n-1}$.
$W_n$, roda	Um ciclo $C_n$ e um vértice extra ligado a todos; $n+1$ vértices e $2n$ arestas.

As convenções de $W_n$ e $S_n$ variam entre textos. Aqui, o índice da roda conta os vértices do ciclo e o índice da estrela conta todos os seus vértices.

Graus e matrizes

O grau $\deg(v)$ é o número de arestas incidentes num vértice de um grafo simples não dirigido. Um vértice de grau zero é isolado. Num grafo regular, todos os vértices têm o mesmo grau.

Cada aresta contribui 1 para o grau de cada extremo, logo:

$$\sum_{v\in V}\deg(v)=2|E|.$$

A soma dos graus é par. Como a soma dos graus pares já é par, tem de haver um número par de vértices de grau ímpar. Esta condição é necessária, mas não suficiente para uma lista ser realizável por um grafo simples. Com $n$ vértices, também nenhum grau pode exceder $n-1$.

Num dígrafo, o grau de entrada conta as arestas $(u,v)$ e o grau de saída conta as arestas $(v,u)$. Cada aresta acrescenta uma entrada e uma saída, por isso ambas as somas são $|E|$.

A matriz de adjacência tem $M[u,v]=1$ quando há aresta de $u$ para $v$. Num grafo não dirigido simples, é simétrica e tem diagonal zero. A soma da linha dá o grau. Num dígrafo, a soma da linha dá o grau de saída e a soma da coluna dá o de entrada.

Passeios, trilhos, caminhos e ciclos

Seguimos a terminologia dos slides: walk, trail, path, circuit e cycle distinguem-se pelas repetições permitidas.

Percurso	Repetições permitidas
Passeio, walk	Pode repetir vértices e arestas.
Trilho, trail	Não repete arestas; pode repetir vértices.
Caminho, path	Não repete vértices, logo também não repete arestas.
Circuito, circuit	Trilho fechado, com o mesmo início e fim.
Ciclo, cycle	Caminho fechado; só repete o vértice inicial no fim.

No triângulo com arestas $\{1,2\},\{2,3\},\{3,1\}$, seguimos três sequências:

Sequência	Repetições e tipo
$1,2,3,1,2$	Repete a aresta $\{1,2\}$ e os vértices 1 e 2: passeio, não trilho.
$1,2,3,1$	Repete só a origem no fim: circuito e ciclo, não caminho aberto.
$1,2,3$	Sem repetições: caminho, também trilho e passeio.

As categorias não são exclusivas. Todo o caminho é um trilho e todo o trilho é um passeio. «Caminho fechado» na definição de ciclo permite apenas a repetição final da origem.

O comprimento conta arestas, não vértices. Num ciclo não dirigido simples, o comprimento é pelo menos 3. No caminho $a,b,c,d$, o comprimento é 3. Num dígrafo, cada passo tem de respeitar o sentido da aresta.

Alguns enunciados usam “caminho de Euler” para um trilho de Euler. Confere a condição escrita, porque Euler exige não repetir arestas e não exige não repetir vértices.

Conectividade e componentes

Um grafo não dirigido é conexo se existe um caminho entre qualquer par de vértices. Uma componente conexa é um subgrafo conexo maximal. Vértices isolados também são componentes, com um só vértice.

Um dígrafo é fortemente conexo se, para cada par $u,v$, existe caminho dirigido de $u$ para $v$. É fracamente conexo se se torna conexo ao ignorar as direções.

O dígrafo é fracamente conexo. As componentes fortemente conexas são $\{a,b\}$, $\{c,d\}$ e $\{e\}$. Há caminho de $a$ para $e$, mas não de $e$ para $a$. Uma componente com um só vértice é fortemente conexa pelo caminho de comprimento zero, mesmo sem laço.

Árvores e florestas

Uma árvore é um grafo não dirigido conexo e sem ciclos. Uma floresta é um grafo sem ciclos; cada componente não vazia é uma árvore.

Numa árvore existe exatamente um caminho entre dois vértices. Se existissem dois, a parte em que divergem e voltam a encontrar-se formaria um ciclo. Retirar qualquer aresta separa a árvore; acrescentar uma aresta entre dois vértices já existentes cria um ciclo.

Uma árvore com $n\ge1$ vértices tem $n-1$ arestas. A ideia é retirar folhas sucessivamente: uma árvore com pelo menos dois vértices tem um vértice de grau 1. Para ver porquê, toma um caminho de comprimento máximo; um extremo não pode ter outro vizinho fora do caminho, pois o prolongaria, nem um vizinho adicional dentro dele, pois criaria um ciclo. Retirar essa folha e a sua aresta deixa uma árvore com menos um vértice e menos uma aresta.

Podemos fechar o argumento por indução em $n$. A árvore com um vértice tem $0=1-1$ arestas. Para $n\ge2$, a árvore que resta após retirar a folha tem $n-1$ vértices e, pela hipótese, $(n-1)-1=n-2$ arestas. Repor a folha acrescenta uma aresta, dando $n-1$. A remoção conserva conectividade entre os restantes vértices, porque um caminho entre eles não precisa de passar por uma folha, e não pode criar ciclos.

Uma floresta com $n$ vértices e $c$ componentes não vazias tem $n-c$ arestas, pois cada componente com $n_i$ vértices contribui com $n_i-1$.

Uma árvore abrangente de um grafo conexo mantém todos os vértices e escolhe algumas arestas de forma a ficar conexa e sem ciclos. Pode obter-se retirando uma aresta de cada ciclo enquanto houver ciclos. Todas as árvores abrangentes têm $n-1$ arestas, mas não precisam de ser isomorfas.

Distância e pesos

A distância $d(u,v)$ é o comprimento do caminho mais curto. $d(u,u)=0$; se não há caminho, convencionamos $d(u,v)=\infty$. Num grafo não dirigido, $d(u,v)=d(v,u)$. Num dígrafo, as duas distâncias podem ser diferentes.

A desigualdade triangular $d(u,w)\le d(u,v)+d(v,w)$ vem de concatenar percursos: o caminho mais curto não é maior do que esse percurso possível.

Num grafo com pesos não negativos, o comprimento ponderado soma os pesos das arestas. Uma ligação direta de peso 10 pode ser pior do que duas de pesos 2 e 3. O algoritmo de Dijkstra começa com distância 0 na origem e infinito nos restantes; fixa de cada vez o vértice não fixado com menor distância provisória e melhora as distâncias dos seus vizinhos. A hipótese de pesos não negativos é o que impede descobrir mais tarde um caminho menor para um vértice já fixado.

Por exemplo, num dígrafo com arestas $a\to b$ de peso 2, $a\to c$ de peso 10, $b\to c$ de peso 3, $b\to d$ de peso 8 e $c\to d$ de peso 1:

Vértice acabado de fixar	Distâncias provisórias para $a,b,c,d$
$a$	$0,2,10,\infty$
$b$	$0,2,5,10$
$c$	$0,2,5,6$
$d$	$0,2,5,6$

O caminho mais curto de $a$ para $d$ é $a,b,c,d$, com peso 6. Usa três arestas, enquanto $a,b,d$ usa duas mas pesa 10. As atualizações são comparações: ao fixar $b$, substituímos a distância 10 de $c$ por $2+3=5$; ao fixar $c$, substituímos a de $d$ por $5+1=6$.

Correspondência de vértices

Dois caminhos de três vértices $a-b-c$ e $x-y-z$ são isomorfos por $a \mapsto x$, $b \mapsto y$, $c \mapsto z$: verifica as duas arestas $(a,b) \mapsto (x,y)$ e $(b,c) \mapsto (y,z)$ e confirma que não aparecem arestas novas. Comparar graus filtra candidatos, mas só a bijeção verificada aresta a aresta prova o isomorfismo. Na figura, as linhas tracejadas representam a correspondência proposta, não arestas dos grafos.

Isomorfismos

Dois grafos são isomorfos se existe uma bijeção $f:V\to V'$ que preserva a adjacência nos dois sentidos:

$$\{u,v\}\in E\Longleftrightarrow\{f(u),f(v)\}\in E'.$$

Mudar nomes, rodar o desenho ou deixar as arestas cruzarem-se não muda o grafo. Para provar isomorfismo, apresenta a bijeção e verifica as arestas. Para o refutar, encontra uma propriedade preservada que difira, como número de vértices, de arestas, graus, componentes ou ciclos de certo comprimento.

A sequência de graus não prova isomorfismo por si só. Um ciclo $C_6$ e dois triângulos separados têm seis vértices de grau 2 e seis arestas, mas o primeiro é conexo e o segundo não.

Nenhum caminho liga os triângulos. Uma bijeção que preservasse adjacência transportaria também os caminhos de $C_6$, por isso não pode existir.

Uma verificação útil começa pelos vértices de graus raros. Se só existe um vértice de grau 4 em cada grafo, qualquer isomorfismo tem de os associar. Depois verifica as ligações entre os seus vizinhos.

O vídeo de Rodrigo Dias é um complemento mais amplo sobre grafos e estratégias de algoritmos:

Abrir no YouTube