Famílias de grafos

Nesta secção, consideramos apenas grafos. Recorde que um grafo ${\cal{G}}$ é um par ordenado $({\cal{V}},{\cal{A}})$, onde ${\cal{V}}$ é um conjunto não vazio finito e ${\cal{A}}$ é um subconjunto de $\left\{\left\{U,V\right\}:U,V\in {\cal{V}}\right\}$.

Os grafos ${\cal{G}}$ e ${\cal{H}}$ são isomorfos, ${\cal{G}}\cong {\cal{H}}$ se exitir uma bijecção $f:V_{\cal{G}}\rightarrow V_{\cal{H}}$ tal que $u \leftrightarrow v \Leftrightarrow f(u)\leftrightarrow f(v)$. Ou seja, existe uma bijecção entre o conjunto dos vértices dos dois grafos de tal forma que a incidência é preservada. Na prática, significa que se toma outra indexação para os vértices. Se $\varphi$ for o isomorfismo, então escrever-se-á ${\cal{G}}\displaystyle\cong_\varphi {\cal{H}}$.

Proposição 4.1   Se ${\cal{G}}\cong_\varphi {\cal{H}}$ então

1. $\char93 {\cal{V}}_{\cal{G}}= \char93 {\cal{V}}_{\cal{H}}$
2. $\char93 A_{\cal{G}}=\char93 {\cal{A}}_{\cal{H}}$
3. para $v\in {\cal{V}}_{\cal{G}}$, $deg(v)=deg(\varphi(v))$.

Dados dois grafos, uma forma possível de se testar o isomorfismo é percorrer todas as bijecções entre os dois conjuntos de vértices (repare que por (1) da proposição estes são necessariamente equipotentes) até se encontrar uma que preserva a vizinhança. Suponha que $\char93 {\cal{V}}_{\cal{G}}=\char93 {\cal{V}}_{\cal{H}}=n$. Então existem $n!$ bijecções possíveis, o que se para grafos com poucos vértices é realizável, torna-se num algoritmo pouco prático para outros grafos. Tal suscita o chamado Problema do Isomorfismo de Grafos, que pode ser exposto, de uma forma ingénua assim:

• apresentar um algoritmo que, de forma ``prática", encontra o isomorfismo ou mostra que tão isomorfismo não existe;
• em alternativa ao ponto anterior, mostrar que tal algoritmo ``prático não existe.

Existem formas imediatas de teste de não isomorfismo, nomeadamente fazendo uso da proposição anterior. Em primeiro lugar, existe a condição de equipotência tratada nos pontos (1) e (2) da proposição. Por exemplo, não são isomorfos

$$\xymatrix{ & \bullet \ar@{-}[ld] \ar@{-}[rd] &\\ \bullet \ar@{-}... ...et } \hspace*{3cm} \xymatrix{ \bullet \ar@{-}[r] & \bullet\ar@{-}[r]& \bullet}$$

O facto de (1) e (2) da proposição serem satisfeitos não implica que os grafos sejam isomorfos. Mostre por que não são isomorfos, usando (3) da proposição,

$$\xymatrix{ \bullet\ar@{-}[r] &\bullet\ar@{-}[r]\ar@{-}[d] &\bulle... ... &\bullet\ar@{-}[r]\ar@{-}[d] &\bullet\ar@{-}[r] &\bullet\\ & & \bullet & & }$$

Vejamos como se relacionam as matrizes de adjacência de dois grafos isomorfos. Para tal, dizemos que duas matrizes $A,B$, quadradas com a mesma ordem, são permutacionalmente semelhantes, $A\displaystyle\approx_{per} B$, se existir uma matriz permutação $P$ (ou seja, é obtida da matriz identidade fazendo trocas de linhas) tal que $A=PBP^T$.

Proposição 4.2   Sejam $A_{\cal{G}}$ e $A_{\cal{H}}$ matrizes de adjacência dos grafos ${\cal{G}}$ e ${\cal{H}}$, respectivamente. Então

$${\cal{G}}\cong {\cal{H}}\Leftrightarrow A_{\cal{G}}\displaystyle\approx_{per} A_{\cal{H}}.$$

Um grafo ${\cal{G}}$ está contido num grafo ${\cal{H}}$, ${\cal{G}}\subseteq {\cal{H}}$, se ${\cal{V}}_{\cal{G}}\subseteq {\cal{V}}_{\cal{H}}$ e ${\cal{A}}_{\cal{G}}\subseteq {\cal{A}}_{\cal{H}}$. ${\cal{G}}'$ é subgrafo de ${\cal{G}}$ se ${\cal{G}}'\subseteq {\cal{G}}$.

Um subgrafo ${\cal{G}}'$ de ${\cal{G}}$ é gerador se ${\cal{V}}_{G'}={\cal{V}}_G$. Ou seja, tem exactamente o mesmo conjunto de vértices.

Para $S\subseteq {\cal{V}}_{\cal{G}}$, o subgrafo induzido por $S$, $\langle S\rangle$, é o subgrafo maximal ${\cal{G}}'$ de ${\cal{G}}$ com ${\cal{V}}_{{\cal{G}}'}=S$. Este subgrafo é denotado por ${\cal{G}}_S$.

A proposição seguinte dá-nos outra forma de mostrar o não isomorfismo entre grafos (ou seja, fornece mais uma condição necessária do isomorfismo de grafos).

Proposição 4.3   Se ${\cal{G}}\cong_\varphi {\cal{H}}$ e $S\subseteq {\cal{V}}_{\cal{G}}$ então

$${\cal{G}}_S \cong {\cal{H}}_{\varphi(S)}.$$

Exercício.

Mostremos o não isomorfismo entre os grafos seguintes, denotados respectivamente por ${\cal{G}}$ e ${\cal{H}}$:

$$\xymatrix{ 1 \ar@{-}[rrr] & & &2 \ar@{-}[ld] \ar@{-}[ddd]\\ & 5\... ...& h \ar@{-}[r]\ar@{-}[ld] & g \ar@{-}[rd]&\\ d \ar@{-}[rrr]\ar@{-}[uuu]& & &c}$$

Suponha, por absurdo, que tal isomorfismo $\varphi$ existe. Os vértices de grau 3 são 2,4,6 e 8 do primeiro grafo e $c,d,g$ e $h$ do segundo. Portanto, e como os graus são preservados, $\varphi$ aplica $\left\{2,4,6, 8\right\}$ de alguma forma em $\left\{c,d,g,h\right\}$; ou seja, $\varphi\left(\left\{2,4,6, 8\right\} \right)=\left\{c,d,g,h\right\}$. Fazendo uso da proposição anterior, segue que

$${\cal{G}}_{\left\{2,4,6, 8\right\}} \cong_\varphi {\cal{H}}_{\left\{c,d,g,h\right\}}.$$

Mas tal não é verdade, já que se representam, respectivamente, por

$$\xymatrix{ 4 \ar@{-}[r] & 8 & 6\ar@{-}[r] &2} \hspace*{3cm} \xymatrix{ h\ar@{-}[d]\ar@{-}[r] & g\ar@{-}[d]\\ d\ar@{-}[r] & c}$$

Um problema que se coloca é, de alguma forma, o recíproco da proposição. Por outras palavras, se certo tipo de subgrafos induzidos são isomorfos então serão os grafos isomorfos? Vejamos que tipo de subgrafos induzidos nos interessam.

Para $v_i \in {\cal{V}}_{\cal{G}}$, ${\cal{G}}-v_i$ é o subgrafo de ${\cal{G}}$ induzido por ${\cal{V}}_G \setminus \left\{v_i \right\}$. Ou seja, ${\cal{G}}-v_i$ denota ${\cal{G}}_{{\cal{V}}_{\cal{G}}\setminus\left\{v_i \right\}}$. A lista de subgrafos de vértice eliminado é a representação dos subgrafos ${\cal{G}}-v_i$, onde $v_i$ percorre o conjunto dos vértices. Por exemplo, o grafo

$$\xymatrix{ & u \ar@{-}[ld] \ar@{-}[ldd]\ar@{-}[rdd] \ar@{-}[rd] & \\ y \ar@{-}[d] \ar@{-}[rrd] && v\ar@{-}[d]\ar@{-}[lld]\\ x \ar@{-}[rr] && w}$$

a que voltaremos um pouco mais adiante, tem a seguinte lista de subgrafos de vértice eliminado:

$\xymatrix{ \bullet \ar@{-}[r]\ar@{-}[rd]\ar@{-}[d] & \bullet \ar@{-}[d]\\ \bullet\ar@{-}[r] & \bullet}$	$\xymatrix{ \bullet \ar@{-}[r]\ar@{-}[d]\ar@{-}[rd] & \bullet \ar@{-}[d]\ar@{-}[ld]\\ \bullet\ar@{-}[r] & \bullet}$	$\xymatrix{ \bullet \ar@{-}[r]\ar@{-}[d]\ar@{-}[rd] & \bullet \ar@{-}[d]\\ \bullet\ar@{-}[r] & \bullet}$	$\xymatrix{ \bullet \ar@{-}[r]\ar@{-}[d]\ar@{-}[rd] & \bullet \ar@{-}[d]\\ \bullet\ar@{-}[r] & \bullet}$	$\xymatrix{ \bullet \ar@{-}[r]\ar@{-}[d]\ar@{-}[rd] & \bullet \ar@{-}[d]\ar@{-}[ld]\\ \bullet\ar@{-}[r] & \bullet}$
${\cal{G}}-u$	${\cal{G}}-v$	${\cal{G}}-w$	${\cal{G}}-x$	${\cal{G}}-y$

O Problema da Reconstrução do Grafo consiste em decidir se dois grafos não isomorfos com 3 ou mais vértices podem ter a mesma lista de subgrafos de vértice eliminado.

Conjectura 4.4 (P.J. Kelly & S.M. Ulam (1941))   Sejam ${\cal{G}},{\cal{H}}$ grafos com

$${\cal{V}}_{\cal{G}}=\{v_1, \dots, v_n\}, {\cal{V}}_{\cal{H}}=\{u_1,\dots,u_n\}, n\ge 3.$$

Sejam ainda

$${\cal{G}}_i={\cal{G}}-v_i, {\cal{H}}_i={\cal{H}}-u_i .$$

Se, para $i=1, \dots, n$,

$${\cal{G}}_i \cong {\cal{H}}_i,$$

então

$${\cal{G}}\cong {\cal{H}}.$$

Acrescente-se que, de forma independente, em 1977 foi mostrado por B. McKay e por A. Nijenhuis, recorrendo a computadores, que um possível contra-exemplo da conjectura teria que ter, pelo menos, 10 vértices.

Recorde a definição de digrafo completo. Ao se considerarem grafos (ou seja, digrafos simétricos), a noção de grafo completo é a induzida pelo digrafo, com a nuance de se assumir que o digrafo é simples. Ou seja, um grafo simples (isto é, sem lacetes), diz-se completo de quaisquer dois vértices são vizinhos um do outro. Um $n$-grafo completo é denotado por ${\cal{K}}_n$.

$\bullet$	$\xymatrix{ \bullet\ar@{-}[d]\\ \bullet}$	$\xymatrix{ & \ar@{-}[ld]\bullet \ar@{-}[rd] &\\ \bullet \ar@{-}[rr] && \bullet }$	$\xymatrix{ & \bullet \ar@{-}[ldd] \ar@{-}[d] \ar@{-}[rdd]& \\ & \bullet\ar@{-}[ld]\ar@{-}[rd] & \\ \bullet \ar@{-}[rr] & & \bullet}$	$\xymatrix{ & \bullet \ar@{-}[ld] \ar@{-}[ldd]\ar@{-}[rdd] \ar@{-}[rd] & \\ \b... ...ar@{-}[rrd] && \bullet\ar@{-}[d]\ar@{-}[lld]\\ \bullet \ar@{-}[rr] && \bullet}$
${\cal{K}}_1$	${\cal{K}}_2$	${\cal{K}}_3$	${\cal{K}}_4$	${\cal{K}}_5$

Um bigrafo ou grafo bipartido ${\cal{G}}=({\cal{V}},{\cal{A}})$ é tal que ${\cal{V}}_G=V_1 \cup V_2$, com $V_1,V_2 \ne \emptyset$ mas $V_1\cap V_2=\emptyset$, e $\forall_{x\in {\cal{A}}_{\cal{G}}} x\subseteq V_1 \cup V_2$. Ou seja, toda a aresta é incidente com um vértice de $V_1$ e um vértice de $V_2$. Portanto, existe uma partição do conjunto dos vértices de tal forma que dois vértices na mesma componente da partição não são vizinhos.

Proposição 4.5   Todo o grafo bipartido é simples.

Um bigrafo é completo se tiver todas as arestas possíveis incidentes com um vértice de $V_1$ e um de $V_2$. De outra forma,

$$\left(\left( v_1\in V_1 \wedge v_2 \in V_2 \right) \vee \left( v_1\in V_2 \wedge v_2 \in V_1 \right) \right) \Leftrightarrow \{v_1,v_2\} \in A_G.$$

Ou ainda, quaisquer dois vértices $v_1\in V_1$ e $v_2\in V_2$ são vizinhos.

Se $\char93 V_1=m,\char93 V_2=n$ então com grafo bipartido completo com $V_1\cup V_2$ como vértices denota-se por ${\cal{K}}_{m,n}$. Por exemplo,

$\xymatrix{ \circ\ar@{-}[r]\ar@{-}[rd]\ar@{-}[rdd] & \bullet\\ \circ\ar@{-}[r... ...-}[r]\ar@{-}[rd] & \bullet\\ \circ\ar@{-}[ru] \ar@{-}[r]\ar@{-}[ruu]& \bullet}$	$\xymatrix{ \circ\ar@{-}[r]\ar@{-}[rd]\ar@{-}[rdd] & \bullet\\ \circ\ar@{-}[ru] \ar@{-}[r]\ar@{-}[rd] & \bullet\\ & \bullet}$	$\xymatrix{ \circ \ar@{-}[r]\ar@{-}[d] & \bullet\\ \bullet\ar@{-}[r] & \circ\ar@{-}[u]}$	$\xymatrix{ & \circ \ar@{-}[d] & \\ \circ \ar@{-}[r] &\bullet\ar@{-}[r]\ar@{-}[d] &\circ\\ & \circ & }$
${\cal{K}}_{3,3}$	${\cal{K}}_{2,3}$	${\cal{K}}_{2,2}$	${\cal{K}}_{1,4}$

O grafo bipartido completo ${\cal{K}}_{1,n}$ chama-se, por razões óbvias, estrela.

Note-se que $\char93 {\cal{A}}_{{\cal{K}}_{m,n}}=mn$.

Teorema 4.6 (Teorema de Euler)   Seja $G$ um $(p,q)$-grafo. Então

$$\sum_{v_i\in V_G} deg(v_i) = 2q.$$

A demonstração é feita por indução sobre o número de arestas.

Prove-se o resultado para grafos $(p,1)$. Ou seja, o grafo tem $p$ vértices e 1 aresta ($p\ge 2$). Tem-se então que existem apenas 2 vértices $v_i,v_j$ incidentes. Ou seja, $deg(v_i)=deg(v_j)=1$ e $deg(v_k)=0$, para $k\ne i,j$. A igualdade do teorema de Euler é satisfeita de forma imediata.

Suponhamos agora que a igualdade é válida para grafos $(p,q)$. Pretende-se que tal é suficiente para a validade da igualdade em grafos $(p,q+1)$. Seja, então, $G$ um grafo com $p$ vértices e $q+1$ arestas. Sejam $x_i$ uma aresta de $G$ fixa arbitrariamente e $G'=(V_G,A_G\setminus \{x_i\})$. Ora $G'$ é um grafo $(p,q)$, pelo que a hipótese de indução mostra que

$$\sum_{v_i \in V_{G'}} deg(v_i) =2q.$$

Ao incluirmos a aresta $x_i$, esta contribui com 2 unidades na soma total dos graus dos vértives de $G$. Logo, e recordando que $V_G=V_{G'}$,

$$\sum_{v_i\in V_G} deg(v_i)=2q+2=2(q+1).$$

Corolário 4.7   O número de vértices de um grafo com grau ímpar é par.

Dado $G$ um grafo simples $(p,q)$, então

$$\forall_{v\in V_G}, 0\le deg(v) \le p-1.$$

Denota-se por

$$\min deg G = \delta (G)=\min_{v\in V_G} deg(v),$$

$$\max deg G = \Delta (G) = \max_{v\in V_G} deg(v).$$

Se $\delta(G)=\Delta(G)=r$, então $deg(v)=r, \forall_{v\in V_G}$. Neste caso, diz-se que o grafo é regular com grau $r$, ou que o grafo é $k$-regular.

Um grafo $G$ regular com $deg(G)=3$ chama-se um grafo cúbico.

Os grafos platónicos são os correspondentes² aos cinco sólidos platónicos³. Saliente-se, no entanto, que um grafo cúbico não é necessariamente o cubo. Como exemplo, repare no grafo de Petersen:

$$\xymatrix{ & & \bullet \ar@{-}[lldd] \ar@{-}[d] \ar@{-}[rrdd] & &... ... \ar@{-}[ld] & & \bullet\ar@{-}[rd] &\\ \bullet \ar@{-}[rrrr] & & & &\bullet }$$

Corolário 4.8   Todo o grafo cúbico tem um número par de vértices.