Grafos planares

Um grafo diz-se planar se for possível desenhá-lo de tal forma que duas arestas não se intersectem à excepção nos vértices inicial e final. Por exemplo, o cubo é um grafo planar já que pode ser desenhado como

$$\xymatrix{ 1 \ar@{-}[rrr]\ar@{-}[rd] & & &2 \ar@{-}[ld] \ar@{-}[d... ... 8 \ar@{-}[r] \ar@{-}[ld] & 7 &\\ 4 \ar@{-}[rrr]\ar@{-}[uuu]& & &3\ar@{-}[lu]}$$

Outro exemplo de grafo planar é $K_4$ (verifique!), e o objectivo desta secção é caracterizar tais grafos. Um resultado relevante no estudo da planaridade de grafos é o Teorema de Kuratowski, que passamos a enunciar:

Um grafo é planar se e só se não tem nenhum subgrafo homeomorfo a $K_5$ ou $K_{3,3}$.

Antes de compreendermos o enunciado, é importante apresentar mais definições e alguns resultados.

Um grafo planar divide o plano em regiões, à custa das suas arestas. Cada uma destas divisões é denominada por face do grafo. Dois pontos do plano estão na mesma face se existir uma curva do plano que os une sem intersectar nenhuma das arestas do grafo. No grafo apresentado atrás, existem 6 faces (a face ``exterior'' é contabilizada! - esta é denominada por face infinita, ou face exterior). A fronteira de uma face, $fr(F)$, é o conjunto das arestas que delimitam a face $F$, ou que estão contidas em $F$.

Teorema 6.1 (Fórmula de Euler)   Dado um grafo planar conexo $(p,q)$ com $f$ faces,

$$p+f=q+2.$$

Se $f=1$ então o grafo é acíclico, e sendo conexo segue que é uma árvore. Como foi provado na secção anterior, $q=p-1$ e a fórmula é válida.

Suponhamos agora que $f>1$; a igualdade é provada por indução sobre o número de arestas.
Se $q=1$ então $p=2$ e $f=1$, ou então $p=1$, e portanto $f=2$. Uma representação destes dois casos é, respectivamente,

$$\xymatrix{ \bullet \ar@{-}[r]& \bullet}\hspace*{2cm} \xymatrix{ \bullet \ar@(ul,ur)}$$

Em qualquer um dos casos, a fórmula é válida quando $q=1$.
Suponhamos agora que $f-q+p=2$ para grafos com mais que 1 face com $q$ arestas. Seja ${\cal{G}}$ um grafo conexo com $q+1$ arestas e mais que uma face. Seja $F$ a face infinita. Existe então um ciclo $\gamma$ contido na fronteira de $F$. Defina-se ${\cal{G}}'$ como o grafo obtido de ${\cal{G}}$ a que se retirou uma aresta $e$ de $\gamma$. Tem-se que, como $e$ é aresta de um ciclo, o grafo ${\cal{G}}'$ é conexo, planar e com $q$ arestas. Sejam $f',q',p'$ o número de faces, arestas e vértices, respectivamente, de ${\cal{G}}'$. As igualdade seguintes são válidas: $p=p',q=q'+1,f=f'+1$. Se $f'>1$, então pela hipótese de indução $f'-q'+p'=2$, e logo $f-q+p=2$. Se $f'=1$ então $f'-q'+p'=2$ pelo que foi visto no início da demonstração, o que implica que $f-q+p=2$.

Vejamos um exemplo:

$$\xymatrix{\bullet \ar@{-}[rrr]\ar@{-}[rrrdd]^{F_2}\ar@{-}[dd] & &... ...et\\ &\bullet\ar@{-}[ld]_{F_1} & & & \\ \bullet\ar@{-}[rrr] & & & \bullet & }$$

O grafo planar acima apresentado tem 3 faces, mas apenas uma delas tem um ciclo como fronteira.

Vejamos algumas consequências da fórmula de Euler:

Corolário 6.2   Dado um $(p,q)$-grafo planar conexo com $f$ faces tal que cada uma tem como fronteira um ciclo de comprimento $n$, então $q=\frac{n(p-2)}{n-2}$.

Visto cada face ter $n$ arestas e cada aresta está em fronteiras de 2 faces distintas, segue que $nf=2q$. Sendo $p-q+f=2$, então $np-nq+nf=2n$. Como $nf=2q$ segue que $q(2-n)=2n-np$.

Um grafo planar diz-se maximal se não for possível acrescentar uma aresta (que não seja lacete) de forma a não se perder a planaridade do grafo.

Corolário 6.3   Se ${\cal{G}}$ é um grafo $(p,q)$ planar maximal então a fronteira de cada face é e $q=3p-6$. Se ${\cal{G}}$ é um grafo $(p,q)$ planar tal que a fronteira de cada face é $C_4$ então $q=2p-4$.

Basta substituir $n$ por 3 e 4, respectivamente.

Visto o número máximo de arestas ocorrer quando a fronteira de cada face é , são válidos os resultados seguintes:

Corolário 6.4   Dado ${\cal{G}}$ um grafo $(p,q)$ planar, com $p\ge 3$, então $q\le 3p-6$. Se ${\cal{G}}$ não tem subgrafos do tipo então $q\le 2p-4$.

Corolário 6.5   Os grafos $K_5$ e $K_{3,3}$ não são planares.

Para $K_5$, $q=10>9=3p-6$, e para $K_{3,3}$, $q=9>8=2p-4$.

Definição 6.6   Seja ${\cal{G}}=({\cal{V}}_{\cal{G}},{\cal{A}}_{\cal{G}})$ um grafo.

1. Se $e=\{u,v\} \in {\cal{A}}_{\cal{G}}$, com $u\ne v$, uma subdivisão de $e$ consiste na inserção de $w$ em ${\cal{V}}_{\cal{G}}$ e na substituição de $e$ por $e'=\{u,w\},e''=\{w,v\}$.
2. Se $e=\{u,w\},e'= \{w,v\}$ e $deg(w)=2$, uma contracção de $w$ consiste na remoção de $w$ de ${\cal{V}}_{\cal{G}}$ e na substituição de $e,e'$ por $e''=\{u,v\}$.
3. Uma subdivisão de ${\cal{G}}$ é um grafo obtido de ${\cal{G}}$ por subdivisão de arestas e/ou contracção de arestas.

Um exemplo de cada um destes conceitos é, respectivamente,

$$\xymatrix{\bullet \ar@{-}[r]_{e} & \bullet} \ \xymatrix{ \bullet \ar@{-}[r]_{e'} & \circ \ar@{-}[r]_{e''} & \bullet }$$

$$\xymatrix{ \bullet \ar@{-}[r]_{e'} & \circ \ar@{-}[r]_{e''} & \bullet } \xymatrix{\bullet \ar@{-}[r]_{e} & \bullet}$$

Definição 6.7   Dois grafos ${\cal{G}},{\cal{H}}$ são homeomorfos se uma subdivisão de ${\cal{G}}$ for isomorfa a uma subdivisão de ${\cal{H}}$.

Os grafos seguintes são homeomorfos mas não são isomorfos:

$$\xymatrix{\bullet \ar@{-}[rd] & & &\\ \circ \ar@{-}[u]\ar@{-}[d]... ...et \ar@{-}[r] &\circ\ar@{-}[r]& \bullet \\ \bullet\ar@{-}[uu] \ar@{-}[ru] &&&}$$

Recordamos, então, o enunciado do Teorema de Kuratowski:

Teorema 6.8 (Teorema de Kuratowski)   Um grafo é planar se e só se não tem nenhum subgrafo homeomorfo a $K_5$ ou $K_{3,3}$.

Uma contracção elementar do grafo ${\cal{G}}$ consiste na substituição de dois vértices$u,v$ adjacentes por um novo vértice $w$, acrescentando-se arestas de tal forma que $w$ seja vizinho de todos os vizinhos de $u,v$.

Por exemplo, considere 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}$$

Vamos remover os vértices $u$ e $v$, assim como as arestas adjacentes a eles, acrescentando um vértice $t$ bem como arestas de forma a que $t$ seja vizinho dos vértices que o eram de $u$ ou de $v$:

$$\xymatrix{ y\ar@{-}[r]\ar@{-}[rd]\ar@{-}[d] & t\ar@{-}[d] \\ x\ar@{-}[r]\ar@{-}[ru] & w}$$

Um grafo ${\cal{G}}$ diz-se contractível num grafo ${\cal{H}}$ se ${\cal{H}}$ puder ser obtido de ${\cal{G}}$ por contracções elementares. Por exemplo, o grafo apresentado atrás é contractível em $K_4$.

O resultado seguinte dá-nos outra forma de caracterizar os grafos planares:

Teorema 6.9 (Teorema de Wagner-Harary-Tutte)   Um grafo é planar se e só se não tiver um subgrafo contractível em $K_5$ ou $K_{3,3}$.