Dois grafos podem ter vértices com nomes diferentes mas serem, na essência, exatamente iguais. Imagine um mapa de metrô desenhado de dois jeitos diferentes: as estações têm rótulos distintos no papel, mas as conexões entre elas são as mesmas. Matematicamente, esses dois grafos são isomorfos.
Neste artigo, formalizamos essa noção e também estudamos como representar grafos de forma que computadores possam trabalhar com eles: as matrizes de adjacência e de incidência.
Por Que Isomorfismo e Representação Matricial Importam? #
- Química: duas moléculas podem ser descritas por grafos diferentes (átomos numerados de formas distintas) e ainda assim serem a mesma substância — decidir isso é decidir um isomorfismo de grafos.
- Verificação de circuitos: dois esquemáticos de circuito desenhados de formas diferentes podem representar exatamente a mesma rede de componentes.
- Compiladores e otimização: grafos de fluxo de controle equivalentes, gerados por caminhos de compilação diferentes, precisam ser reconhecidos como “o mesmo grafo” para aplicar as mesmas otimizações.
- Estruturas de dados em software: bibliotecas de grafos precisam escolher
como guardar um grafo na memória. O
networkx, em Python, usa listas de adjacência (dicionários de vizinhos) e gera a matriz de adjacência ou de incidência quando pedida; bibliotecas numéricas trabalham direto com as matrizes. Entender essas representações é entender como o computador realmente “enxerga” um grafo. - Álgebra linear aplicada a redes: autovalores e autovetores da matriz de adjacência (o “espectro” do grafo) são usados em algoritmos como o PageRank e em análise de redes sociais.
Isomorfismo de Grafos #
Mesmo Grafo, Desenhos Diferentes #
Antes de definir isomorfismo formalmente, vale a pena ver o fenômeno na prática: representações geométricas muito diferentes podem corresponder exatamente ao mesmo grafo (mesmo conjunto de vértices, mesmo conjunto de arestas).
Exemplo: duas representações do mesmo grafo
Enunciado: Seja \(G\) o grafo com \(V(G) = \{a,b,c,d,e\}\) e \(E(G) = \{(a,b), (b,c), (a,c), (a,e), (c,d), (e,d)\}\). As duas representações geométricas abaixo mostram o mesmo grafo?
Solução: Sim. As duas figuras têm posições de vértices completamente diferentes, mas descrevem exatamente o mesmo grafo: mesmos vértices, mesmas arestas.
Exemplo: \(K_4\) em três representações
Enunciado: O grafo completo \(K_4\) (vértices \(\{1,2,3,4\}\), todas as \(\binom{4}{2} = 6\) arestas possíveis) pode ser desenhado de formas visualmente muito diferentes. As três figuras abaixo representam o mesmo grafo?
Solução: Sim. As três figuras parecem, à primeira vista, grafos diferentes — mas todas representam \(K_4\).
Desenhos Parecidos, Grafos Diferentes #
O inverso também acontece: dois desenhos podem parecer praticamente iguais e, ainda assim, corresponder a grafos formalmente diferentes.
Exemplo: \(H_1\) e \(H_2\)
Enunciado: Sejam \(H_1\) e \(H_2\) dois grafos com o mesmo conjunto de vértices \(V(H_1) = V(H_2) = \{1,2,a,b\}\), mas
$$E(H_1) = \{(1,a), (1,b), (2,a), (2,b)\}$$$$E(H_2) = \{(1,a), (1,2), (b,a), (b,2)\}$$\(H_1\) e \(H_2\) são o mesmo grafo? São isomorfos?
Solução: Os dois desenhos têm o mesmo padrão visual de cruzamento, mas \(E(H_1) \neq E(H_2)\) como conjuntos de pares com os mesmos rótulos — \(H_1\) e \(H_2\) são grafos formalmente diferentes.
Curiosamente, se renomeamos os vértices de \(H_2\) trocando \(b\) por \(2\) e \(2\) por \(b\), obtemos exatamente \(H_1\). Ou seja, \(H_1\) e \(H_2\) não são o mesmo grafo, mas são isomorfos entre si — essa é precisamente a noção que vamos formalizar a seguir.
O Problema do Isomorfismo #
Os exemplos acima levantam uma pergunta natural: dadas duas representações geométricas de grafos, elas correspondem ao mesmo grafo (a menos de renomear vértices)? Em outras palavras, é possível associar cada ponto de uma representação a um ponto da outra, de modo a preservar as adjacências — ou seja, de modo que as arestas coincidam?
Essa pergunta tem nome: o Problema do Isomorfismo de Grafos. A definição formal abaixo é a resposta precisa a essa pergunta.
Dois grafos \(G_1\) e \(G_2\) são isomorfos, denotado \(G_1 \approx G_2\), quando existe uma função bijetora (injetora e sobrejetora)
$$f: V(G_1) \to V(G_2)$$tal que:
$$(v, w) \in E(G_1) \iff (f(v), f(w)) \in E(G_2)$$Em palavras: \(f\) é uma bijeção entre os vértices que preserva adjacências — dois vértices são adjacentes em \(G_1\) se e somente se suas imagens são adjacentes em \(G_2\). A função \(f\) é chamada de isomorfismo entre \(G_1\) e \(G_2\).
Condições Necessárias (Mas Não Suficientes) #
Da própria definição já conseguimos deduzir consequências obrigatórias de \(G_1 \approx G_2\). Para que \(G_1 \approx G_2\), as seguintes condições são necessárias:
- \(|V(G_1)| = |V(G_2)|\) (mesma quantidade de vértices) — consequência direta de \(f\) ser injetora e sobrejetora.
- \(|E(G_1)| = |E(G_2)|\) (mesma quantidade de arestas) — para cada par \((v,w) \in E(G_1)\) existe um par correspondente \((f(v), f(w)) \in E(G_2)\), e como \(f\) é bijetora essa correspondência é também uma bijeção entre as arestas.
- As sequências de graus de \(G_1\) e \(G_2\) são iguais — como \(f\) preserva adjacências vértice a vértice, o grau de \(v\) em \(G_1\) é igual ao grau de \(f(v)\) em \(G_2\).
As condições acima são necessárias, mas não suficientes. Dois grafos podem satisfazer todas elas e ainda assim não ser isomorfos — veremos um contraexemplo concreto adiante.
O problema de decidir se dois grafos são isomorfos (o Problema do Isomorfismo de Grafos) é um dos grandes problemas abertos da teoria da complexidade computacional — não se sabe se está em P (a classe dos problemas resolvíveis em tempo polinomial), mas também não foi provado ser NP-completo. Um problema é NP-completo quando está entre os mais difíceis da classe NP (sigla de tempo polinomial não determinístico: problemas cuja solução, uma vez encontrada, pode ser verificada rapidamente): todo outro problema de NP pode ser reduzido a ele em tempo polinomial, de modo que, se alguém encontrasse um algoritmo rápido para um problema NP-completo, teria um algoritmo rápido para todos os problemas de NP.
Esse status indefinido é raro entre os problemas naturais de NP, e o isomorfismo de grafos é uma das fronteiras de pesquisa mais vivas da área. Em 2015, László Babai anunciou um algoritmo de tempo quase-polinomial, da ordem de \(2^{O((\log n)^c)}\) para alguma constante \(c\) — bem mais rápido que qualquer algoritmo exponencial, embora ainda não polinomial. Em janeiro de 2017, Harald Helfgott encontrou uma falha na prova; Babai a corrigiu em poucos dias e o resultado se manteve (veja o verbete Graph isomorphism problem).
Quando as Condições Necessárias Não Bastam #
Vale começar pelo caso fácil: quando as condições necessárias já falham, a resposta é imediata.
Exemplo: grafos não isomorfos (caso fácil)
Enunciado: Seja \(G_1\) o caminho \(P_4\), com sequência de graus \((1,1,2,2)\), e \(G_2\) o grafo estrela \(K_{1,3}\), com sequência de graus \((1,1,1,3)\). \(G_1\) e \(G_2\) são isomorfos?
Solução: Não. Ambos têm 4 vértices e 3 arestas, mas as sequências de graus são diferentes. Logo, \(G_1 \not\approx G_2\).
Agora o caso difícil — e a razão pela qual o quadro de aviso acima existe: dois grafos podem satisfazer todas as condições necessárias vistas e ainda assim não serem isomorfos.
Contraexemplo: quando as condições necessárias enganam
Enunciado: Sejam \(G_1\) e \(G_2\) os grafos abaixo.
$$E(G_1) = \{(1,2),(2,3),(3,4),(1,4),(8,7),(7,5),(5,6),(6,8),(1,8),(3,5)\}$$$$V(G_2) = \{a,b,c,d,e,f,g,h\}$$
$$E(G_2) = \{(a,b),(b,c),(c,d),(d,a),(g,h),(h,f),(f,e),(e,g),(a,g),(b,h)\}$$
\(G_1\) e \(G_2\) são isomorfos?
Solução: Primeiro, checamos as condições necessárias: \(|V(G_1)| = |V(G_2)| = 8\), \(|E(G_1)| = |E(G_2)| = 10\), e as sequências de graus de ambos são \((2,2,2,2,3,3,3,3)\) — tudo bate! Somos tentados a concluir que \(G_1 \approx G_2\).
Mas olhando com mais cuidado para como os vértices de grau 3 se conectam entre si:
- Em \(G_1\), o vértice \(1\) (grau 3) é adjacente a \(2\) (grau 2), \(4\) (grau 2) e \(8\) (grau 3) — cada vértice de grau 3 é adjacente a dois vértices de grau 2 e um de grau 3.
- Em \(G_2\), o vértice \(a\) (grau 3) é adjacente a \(b\) (grau 3), \(d\) (grau 2) e \(g\) (grau 3) — cada vértice de grau 3 é adjacente a dois vértices de grau 3 e um de grau 2 — o padrão oposto!
Como essa estrutura local de adjacência é diferente, nenhuma bijeção consegue preservar todas as adjacências simultaneamente. Logo, \(G_1 \not\approx G_2\), apesar de satisfazerem todas as condições necessárias vistas até aqui. É exatamente isso que significa dizer que essas condições não são suficientes.
Provando um Isomorfismo #
Depois de ver que checar as condições necessárias pode enganar, a única forma confiável de garantir que \(G_1 \approx G_2\) é exibir explicitamente uma bijeção \(f\) e verificar que ela preserva todas as adjacências.
Exemplo: provando \(G_1 \approx G_2\)
Enunciado: Sejam \(G_1\) e \(G_2\) os grafos abaixo, dados por sua representação geométrica.
$$E(G_1) = \{(1,2),(2,3),(3,4),(1,4),(5,6),(6,7),(7,8),(5,8),(1,5),(2,6),(3,7),(4,8)\}$$$$V(G_2) = \{a,b,c,d,e,f,g,h\}$$
$$E(G_2) = \{(a,b),(b,h),(h,g),(g,a),(c,d),(d,f),(f,e),(e,c),(a,c),(b,d),(g,e),(h,f)\}$$
\(G_1\) e \(G_2\) são isomorfos?
Solução: Antes de tentar provar que são isomorfos, vale conferir as condições necessárias: \(|V(G_1)| = |V(G_2)| = 8\), \(|E(G_1)| = |E(G_2)| = 12\), e ambos são 3-regulares (todo vértice tem grau 3). As condições batem — mas isso só nos diz que pode existir um isomorfismo, não que existe.
Para provar que existe, exibimos a bijeção \(f: V(G_1) \to V(G_2)\):
| \(v\) | \(f(v)\) |
|---|---|
| 1 | a |
| 2 | c |
| 3 | d |
| 4 | b |
| 5 | g |
| 6 | e |
| 7 | f |
| 8 | h |
Basta conferir que cada uma das 12 arestas de \(G_1\) mapeia para uma aresta real de \(G_2\). Por exemplo: \((1,2) \in E(G_1)\) e \((f(1),f(2)) = (a,c) \in E(G_2)\); \((1,4) \in E(G_1)\) e \((f(1),f(4)) = (a,b) \in E(G_2)\); \((1,5) \in E(G_1)\) e \((f(1),f(5)) = (a,g) \in E(G_2)\); e assim por diante para as demais arestas. Todas se verificam, logo \(G_1 \approx G_2\).
O procedimento mais natural para decidir se dois grafos de \(n\) vértices são isomorfos seria força bruta: examinar cada uma das \(n!\) permutações possíveis de vértices (ou seja, testar cada função bijetora candidata) até encontrar uma que preserve as adjacências, ou esgotar todas sem sucesso. O problema é que \(n!\) cresce absurdamente rápido — para \(n = 20\) já são mais de \(2 \times 10^{18}\) permutações. É por isso que o Problema do Isomorfismo de Grafos é considerado computacionalmente difícil na prática, mesmo sem status definido na teoria da complexidade.
Matriz de Adjacência #
Para que algoritmos de computador possam processar grafos, precisamos de representações numéricas. A mais natural é a matriz de adjacência.
Dado um grafo \(G\) com \(n\) vértices \(V = \{v_1, v_2, \ldots, v_n\}\), a matriz de adjacência \(A = (a_{ij})\) é uma matriz \(n \times n\) onde:
$$a_{ij} = \begin{cases} 1 & \text{se } (v_i, v_j) \in E(G) \\ 0 & \text{caso contrário} \end{cases}$$
Exemplo: matriz de adjacência de um grafo de 5 vértices
Enunciado: Escreva a matriz de adjacência do grafo \(G\) com
$$V(G) = \{v_1, v_2, v_3, v_4, v_5\}$$$$E(G) = \{(v_1,v_2), (v_1,v_3), (v_1,v_5), (v_2,v_3), (v_3,v_4), (v_4,v_5)\}$$
Solução:
$$A = \begin{pmatrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}$$Propriedades da matriz de adjacência de um grafo simples:
- A diagonal principal é toda nula: \(a_{ii} = 0\) (sem laços)
- A matriz é simétrica: \(a_{ij} = a_{ji}\) (pois arestas são pares não ordenados, em grafos não orientados)
- O número de 1’s é igual a \(2m\), onde \(m = |E(G)|\) (cada aresta \((v_i,v_j)\) contribui com um 1 em \(a_{ij}\) e outro em \(a_{ji}\))
- Uma matriz de adjacência caracteriza univocamente um grafo — mas o mesmo grafo pode ter várias matrizes de adjacência diferentes: basta permutar a ordem em que os vértices são listados.
Exemplo: permutando a ordem dos vértices
Enunciado: Reordene os vértices do grafo do exemplo anterior de \((v_1,v_2,v_3,v_4,v_5)\) para \((v_3,v_2,v_5,v_1,v_4)\) e escreva a nova matriz de adjacência.
Solução:
$$A' = \begin{pmatrix} 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \end{pmatrix}$$Visualmente, \(A\) e \(A’\) são matrizes diferentes — mas ambas representam exatamente o mesmo grafo.
A matriz de adjacência guarda mais informação do que parece: o elemento \((A^k)_{ij}\) da \(k\)-ésima potência de \(A\) é igual ao número de passeios de comprimento \(k\) entre \(v_i\) e \(v_j\). É uma das razões pelas quais essa representação é tão usada em algoritmos sobre grafos.
Matriz de Incidência #
Uma representação alternativa é a matriz de incidência, que relaciona vértices com arestas.
Dado um grafo \(G\) com \(n\) vértices e \(m\) arestas, a matriz de incidência \(B = (b_{ij})\) é uma matriz \(n \times m\) onde:
$$b_{ij} = \begin{cases} 1 & \text{se o vértice } v_i \text{ é extremo da aresta } e_j \\ 0 & \text{caso contrário} \end{cases}$$
Exemplo: matriz de incidência do mesmo grafo
Enunciado: Escreva a matriz de incidência do grafo de 5 vértices do exemplo anterior, agora com as arestas rotuladas: \(e_1=(v_1,v_2)\), \(e_2=(v_1,v_3)\), \(e_3=(v_2,v_3)\), \(e_4=(v_3,v_4)\), \(e_5=(v_4,v_5)\), \(e_6=(v_1,v_5)\).
Solução:
$$B = \begin{array}{c|cccccc} & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 \\ \hline v_1 & 1 & 1 & 0 & 0 & 0 & 1 \\ v_2 & 1 & 0 & 1 & 0 & 0 & 0 \\ v_3 & 0 & 1 & 1 & 1 & 0 & 0 \\ v_4 & 0 & 0 & 0 & 1 & 1 & 0 \\ v_5 & 0 & 0 & 0 & 0 & 1 & 1 \end{array}$$Somas das linhas: \(d(v_1)=3, d(v_2)=2, d(v_3)=3, d(v_4)=2, d(v_5)=2\). Soma total dos elementos: \(12 = 2 \times 6\) arestas.
Propriedades da matriz de incidência de um grafo simples:
- Cada coluna tem exatamente dois 1s (cada aresta tem dois extremos)
- A soma da linha \(i\) é igual a \(d(v_i)\) (grau do vértice)
- A soma de todos os elementos é \(2|E|\) — confirmando o Teorema do Aperto de Mãos
- Uma matriz de incidência caracteriza univocamente um grafo — mas o mesmo grafo pode ter várias matrizes de incidência diferentes: basta permutar a ordem dos vértices e/ou a ordem das arestas.
Exemplo: permutando vértices e arestas
Enunciado: Permute simultaneamente \((v_1,v_2,v_3,v_4,v_5) \to (v_3,v_5,v_1,v_4,v_2)\) e \((e_1,\ldots,e_6) \to (e_5,e_3,e_2,e_1,e_6,e_4)\) e escreva a nova matriz de incidência.
Solução:
$$B' = \begin{array}{c|cccccc} & e_5 & e_3 & e_2 & e_1 & e_6 & e_4 \\ \hline v_3 & 0 & 1 & 1 & 0 & 0 & 1 \\ v_5 & 1 & 0 & 0 & 0 & 1 & 0 \\ v_1 & 0 & 0 & 1 & 1 & 1 & 0 \\ v_4 & 1 & 0 & 0 & 0 & 0 & 1 \\ v_2 & 0 & 1 & 0 & 1 & 0 & 0 \end{array}$$Linhas e colunas em outra ordem, mas ainda o mesmo grafo — exatamente como aconteceu com a matriz de adjacência.
O Problema do Isomorfismo via Matrizes #
Agora que sabemos representar grafos numericamente, o Problema do Isomorfismo pode ser reformulado em termos de matrizes: dadas duas matrizes de adjacência \(n \times n\) (ou duas matrizes de incidência \(n \times m\)), elas representam o mesmo grafo? É a mesma pergunta do início do artigo — lembra do mapa de metrô redesenhado com rótulos diferentes? — só que agora aplicada às representações numéricas em vez das representações geométricas. E sofre exatamente da mesma dificuldade: não basta comparar as matrizes entrada a entrada, é preciso descobrir se existe alguma permutação de linhas e colunas que transforma uma na outra.
Tabela-Resumo #
A tabela a seguir resume as definições, condições e propriedades centrais apresentadas neste artigo.
| Conceito | Notação / Fórmula | Descrição |
|---|---|---|
| Isomorfismo | \(G_1 \approx G_2\) se \(\exists f: V(G_1) \to V(G_2)\) bijetora com \((v,w) \in E(G_1) \iff (f(v),f(w)) \in E(G_2)\) | \(f\) preserva adjacências |
| Condições necessárias | \(\lvert V(G_1)\rvert = \lvert V(G_2)\rvert\), \(\lvert E(G_1)\rvert = \lvert E(G_2)\rvert\), mesma sequência de graus | Necessárias, não suficientes |
| Matriz de adjacência | \(A = (a_{ij})\), \(n \times n\), \(a_{ij} = 1\) se \((v_i,v_j) \in E\) | Diagonal nula, simétrica, número de 1’s \(= 2m\), não única (permutação de vértices) |
| Matriz de incidência | \(B = (b_{ij})\), \(n \times m\), \(b_{ij} = 1\) se \(v_i\) é extremo de \(e_j\) | Cada coluna com dois 1’s, soma da linha \(i\) \(= d(v_i)\), soma total \(= 2\lvert E\rvert\), não única (permutação de vértices e arestas) |
| Potências da matriz de adjacência | \((A^k)_{ij}\) | Número de passeios de comprimento \(k\) entre \(v_i\) e \(v_j\) |
Comparando as Representações #
Além de saber construir cada matriz, vale comparar diretamente o custo prático de usá-las em um algoritmo:
| Aspecto | Matriz de Adjacência | Matriz de Incidência |
|---|---|---|
| Dimensão | \(n \times n\) | \(n \times m\) |
| Simetria | Simétrica (grafo não orientado) | Não se aplica (matriz não é quadrada) |
| Verificar adjacência | \(O(1)\) | \(O(m)\) |
| Listar vizinhos de \(v\) | \(O(n)\) | \(O(m)\) |
| Uso de memória | \(O(n^2)\) | \(O(nm)\) |
Para grafos densos (muitas arestas), a matriz de adjacência costuma ser mais eficiente. Para grafos esparsos, representações que guardam só os vizinhos de cada vértice (as chamadas listas de adjacência, uma lista por vértice em vez de uma matriz \(n \times n\) cheia de zeros) são preferíveis na prática.
Exercícios #
Exercício 1: Isomorfismo
Os grafos \(G_1\) (triângulo mais um vértice isolado: \(K_3 \cup K_1\)) e \(G_2\) (caminho \(P_4\)) são isomorfos?
Solução: Não. A sequência de graus de \(G_1\) é \((0, 2, 2, 2)\) e de \(G_2\) é \((1, 1, 2, 2)\). Como as sequências são diferentes, \(G_1 \not\approx G_2\). \(\blacksquare\)
Exercício 2: Matriz de adjacência
Escreva a matriz de adjacência do ciclo \(C_5\) com vértices \(\{1, 2, 3, 4, 5\}\) e arestas \((1,2), (2,3), (3,4), (4,5), (5,1)\).
Solução:
$$A = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 \end{pmatrix}$$Todos os vértices têm grau 2 (soma de cada linha = 2), confirmando que \(C_5\) é 2-regular. \(\blacksquare\)
Exercício 3: Matriz de incidência
Seja \(G\) o grafo “triângulo com uma aresta pendente”: \(V(G) = \{p,q,r,s\}\), \(E(G) = \{(p,q), (q,r), (p,r), (r,s)\}\). Escreva a matriz de incidência \(B\) de \(G\) e confirme que a soma de cada linha bate com o grau do vértice correspondente.
Solução: Rotulando \(e_1=(p,q)\), \(e_2=(q,r)\), \(e_3=(p,r)\), \(e_4=(r,s)\):
$$B = \begin{array}{c|cccc} & e_1 & e_2 & e_3 & e_4 \\ \hline p & 1 & 0 & 1 & 0 \\ q & 1 & 1 & 0 & 0 \\ r & 0 & 1 & 1 & 1 \\ s & 0 & 0 & 0 & 1 \end{array}$$Somas das linhas: \(d(p)=2, d(q)=2, d(r)=3, d(s)=1\) — batem exatamente com os graus de cada vértice em \(G\). \(\blacksquare\)
Exercício 4: Isomorfismo via matrizes
As matrizes de adjacência abaixo representam, respectivamente, os grafos \(G_1\) (vértices \(1,2,3,4\)) e \(G_2\) (vértices \(a,b,c,d\)):
$$A_1 = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix} \qquad A_2 = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}$$\(G_1\) e \(G_2\) são isomorfos?
Solução: Sim, embora não sejam o mesmo grafo (os vértices têm nomes diferentes). \(A_1\) descreve o ciclo \(1-2-3-4-1\), e \(A_2\) descreve o ciclo \(a-b-d-c-a\) (confira: \(a\) é adjacente a \(b\) e \(c\); \(b\) é adjacente a \(a\) e \(d\); etc.). A bijeção \(f(1)=a, f(2)=b, f(3)=d, f(4)=c\) preserva todas as adjacências, logo \(G_1 \approx G_2\). \(\blacksquare\)
Próximos Passos #
Isomorfismo e matrizes respondem a uma pergunta específica: dados dois grafos inteiros, eles são “o mesmo”? Mas nenhuma dessas ferramentas nos diz como nos mover dentro de um único grafo — qual é a rota entre dois vértices, quando essa rota forma um ciclo, ou se o grafo inteiro está conectado. Essas são as perguntas do próximo artigo da série: caminhos, ciclos e conexidade.
