===== Grafos Planares: Introdução ===== Quando desenhamos um grafo em um pedaço de papel, naturalmente tentamos fazer isso da forma mais transparente possível. Uma maneira óbvia de limitar a confusão criada por todas as linhas é evitar interseções. Por exemplo, podemos perguntar se podemos desenhar o grafo de forma que duas arestas não se encontrem em um ponto que não seja uma extremidade comum. Os grafos desenhados dessa maneira são chamados de **//grafos planos//**; os grafos abstratos que podem ser desenhados dessa maneira são chamados de **planares**. A noção tradicional de desenho de um grafo é que seus vértices são representados por pontos no plano euclidiano, suas arestas são representadas por curvas entre esses pontos, e diferentes curvas se encontram apenas em pontos finais comuns. Para evitar complicações [[.pretopology |topológicas]] desnecessárias, no entanto, consideraremos apenas curvas que são lineares por partes; não é difícil mostrar que qualquer desenho pode ser endireitado dessa maneira, de modo que as duas noções dão na mesma. ==== Grafos Planos ==== === Definição === //Um grafo plano é um par $(V,E)$ de conjuntos finitos com as seguintes propriedades (os elementos de $V$ são novamente chamados de vértices, os de $E$ arestas):// $(i)$ $V \subseteq \mathbb{R}^2$; $(ii)$ //toda aresta é um [[.pretopology |arco]] entre dois vértices;// $(iii)$ //diferentes arestas têm diferentes conjuntos de extremidades;// $(iv)$ //o interior de uma aresta não contém nenhum vértice e nenhum ponto de qualquer outra aresta.// Um grafo plano $(V,E)$ define um grafo $G$ sobre $V$ de forma natural. Desde que não haja confusão, usaremos o nome $G$ deste grafo abstrato também para o grafo plano $(V,E)$, ou para o conjunto de pontos $V \cup \bigcup E$; convenções de notação semelhantes serão usadas para arestas abstratas Vs. arestas planas, para [[.subgrafos| subgrafos]] e assim por diante (no entanto, continuaremos a usar $\setminus$ para diferenças de conjuntos de pontos e $-$ para diferenças de grafos,o que podem ajudar um pouco a manter os dois separados). Quando $G$ é um grafo plano, chamamos as regiões de $\mathbb{R}^2 \setminus G$ de **faces** de $G$. Esses são subconjuntos abertos de $\mathbb{R}^2$ e, portanto, têm suas fronteiras em $G$. Como $G$ é limitado, ou seja, está dentro de algum disco $D$ suficientemente grande, exatamente uma das suas faces são ilimitadas, a face que contém $\mathbb{R}^2 \setminus D$. Esta face é a **//face externa//** de $G$; as outras faces são suas **//faces internas//**. Denotamos o conjunto das faces de $G$ por $F(G)$. As faces dos grafos planos e seus subgrafos estão relacionados da segui nte maneira: === Lema 1 === //Seja $G$ um grafo plano , $f \in F(G)$ uma face e $H \subseteq G$ um sugrafo.// $(i)$ //$H$ tem uma face $f'$ contendo $f$;// $(ii)$ //Se a fronteira de $f$ está em $H$, então $f' = f$.// **//Demonstração://** $(i)$ Claramente, os pontos em $f$ são equivalentes também em $\mathbb{R}^2 \setminus H$; seja $f'$ a classe de equivalência de $\mathbb{R}^2 \setminus H$ que os contém. $(ii)$ Qualquer arco entre $f$ e $f' \setminus f$ encontra a fronteira $X$ de $f$. Se $f' \setminus f \neq \emptyset$ então existe tal arco dentro de $f'$, cujos pontos em $X$ não estão em $H$. Daí $X \not \subseteq H$. $\square$ ---- A fim de lançar as bases para a introdução (fácil, mas) rigorosa aos grafos planos, vamos descer mais uma vez ao reino da topologia verdadeiramente elementar do plano e provar o que parece totalmente óbvio: que a fronteira de uma face de um grafo plano $G$ é sempre um subgrafo de $G$, não, digamos, meia aresta. O lema a seguir afirma isso formalmente, juntamente com duas propriedades 'óbvias' semelhantes de grafos planos: === Lema 2 === //Seja $G$ um grafo plano e $e$ uma aresta de $G$.// $(i)$ //Se $X$ é a fronteira de uma face de $G$, então $e \subseteq X$ ou $X \cap \dot e = \emptyset$;// $(ii)$ //Se $e$ está em um ciclo $C \subseteq G$, então $e$ está na fronteira de exatamente duas faces de $G$, e estas estão contidas em faces distintas de $C$.// $(iii)$ //Se $e$ não pertence a nenhum ciclo, então $e$ está na fronteira de exatamente uma face de $G$.// //**Demonstração:**// Provamos todas as três afirmações juntas. Comecemos considerando um ponto $x_0 \in \dot e$. Mostramos que $x_0$ está na fronteira de exatamente duas faces ou exatamente de uma, conforme $e$ esteja ou não em um ciclo em $G$. Mostramos então que todos os outros pontos em $\dot e$ estão na fronteira exatamente das mesmas faces que $x_0$. Então as extremidades de $e$ também estarão na fronteira dessas faces, simplesmente porque cada vizinhança de uma extremidade de $e$ é também a vizinhança de um ponto interno de $e$. Como $G \setminus \dot e$ é compacto, podemos encontrar em torno de cada ponto $x \in \dot e$ um disco aberto $D_{x}$ que encontra $G$ apenas naqueles (um ou dois) segmentos de reta que contêm $x$. Vamos pegar um ponto interno $x_0$ de um segmento de reta $S \subseteq e$. Então $D_{x_0} \cap G = D_{x_0} \cap S$, logo $D_{x_0} \setminus G$ é a união de dois semi-discos abertos. Como esses meios-discos não encontram $G$, cada um deles está em uma face de $G$. Vamos denotar essas faces por $f_1$ e $f_2$; são as únicas faces de $G$ com $x_0$ em sua fronteira e podem coincidir. {{ :grafos:graph100.png?400 |}} Se $e$ pertence a um ciclo $C \subseteq G$, então $D_{x_0}$ encontra ambas as faces de $C$, pelo [[grafos:pretopology#teorema_da_curva_de_jordan_para_poligonos | Teorema da curva de Jordan para polígonos]]. Como $f_1$ e $f_2$ estão contidos nas faces de $C$ pelo Lema $1$ acima, isso implica $f_1 \neq f_2$. Se $e$ não pertence a nenhum ciclo, então $e$ é uma ponte e, portanto, liga dois conjuntos de pontos disjuntos $X_1, X_2$ como no [[grafos:pretopology#lema_2 | Lema ]]da seção anterior, com $X_1 \cup X_2 = G \setminus \dot e$. Claramente, $f_1 \cup \dot e \cup f_2$ é o subconjunto de uma face $f$ de $G-e$. Pelo mesmo [[grafos:pretopology#lema_2 | Lema ]], $f \setminus \dot e$ é uma face de $G$, enquanto $f_1, f_2 \subseteq f \setminus \dot e$ por definição de $f$. Como $f_1$ e $f_2$ também são faces de $G$, isso implica $f_1 = f \setminus \dot e = f_2$. Agora considere qualquer outro ponto $x_1 \in \dot e$. Seja $P$ um arco de $x_0$ a $x_1$ contido em $e$. Como $P$ é compacto, muitos dos discos $D_{x}$ com $x \in P$ cobrem $P$. Vamos enumerar esses discos como $D_0, \dots , D_{n}$ na ordem natural de seus centros ao longo de $P$; adicionando $D_{x_0}$ ou $D_{x_1}$ conforme necessário, podemos assumir que $D_0 = D_{x_0}$ e $D_{n} = D_{x_1}$. Por indução em $n$, prova-se facilmente que todo ponto $y \in D_{n} \setminus e$ pode ser ligado por um arco dentro de $(D_0 \cup \dots \cup D_{n}) \setminus e$ a um ponto $z \in D_0 \setminus e$: {{ :grafos:graph101.png?400 |}} Então $y$ e $z$ são equivalentes em $\mathbb{R}^2 \setminus G$. Portanto, todo ponto de $D_{n} \setminus e$ está em $f_1$ ou em $f_2$, então $x_1$ não pode estar na fronteira de qualquer outra face de $G$. Uma vez que ambos os meios discos de $D_0 \setminus e$ podem ser ligados a $D_{n} \setminus e$ neste caminho (trocar os papéis de $D_0$ e $D_{n}$), descobrimos que $x_1$ está na fronteira de $f_1$ e $f_2$. $\square$ ---- === Referências === * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch4.pdf |“Graph Theory”]] .5th Electronic Edition 2016, pp. 92-94. Acesso em 10/04/2024.