Combinando

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Teorema de Kuratowski ======

<WRAP info>
Dizemos que um grafo $G = (V,A)$ é uma **subdivisão** de um grafo $H = (V',A')$ se $G$ é construído a partir da remoção de uma quantidade finita de arestas de $H$ e a substituição de cada uma dessas arestas por caminhos conectando seus vértices. 
</WRAP>
<WRAP tip>
No exemplo abaixo, o grafo $G$ é uma subdivisão do grafo $H$.
</WRAP>
{{ :lista:exemplosubdivisao.png?400 |}}

**~~#~~** Desenhe um grafo do qual o grafo $H$ acima é uma subdivisão.

**~~#~~** Mostre que um grafo é planar se, e somente se, todas as suas subdivisões são planares.

<WRAP tip>
O **Teorema de Kuratowski** nos diz que um grafo com uma quantidade finita de vértices é planar se, e somente se, não possui uma subdivisão de $K_{3,3}$ ou $K_5$ como subgrafo. Já sabemos que, se tal grafo é planar, não pode conter uma subdivisão de $K_{3,3}$ ou $K_5$ como subgrafo. No roteiro abaixo, concluiremos a recíproca. 
</WRAP>
<WRAP info>
Dado $G=(V,A)$ um grafo conexo, um **vértice de corte** de $G$ é um vértice $v\in V$ tal que o subgrafo induzido a $V\setminus \{v\}$ é desconexo. Isto é, $v$ é um vértice cuja remoção "aumenta" a quantidade de componentes conexas do grafo. Um **bloco** de $G$ é um subgrafo conexo maximal $H$ de $G$ que não possui um vértice de corte, isto é, se $H'$ é um subgrafo conexo de $G$ que não possui vértices de corte e $H$ é subgrafo de $H'$, então $H=H'$.
</WRAP>
<WRAP tip>
No exemplo abaixo, temos um grafo $G$ e seus blocos representados logo abaixo.
</WRAP>
{{ :lista:exemplobloco.png?400 |}}

**~~#~~** Seja $G = (V,A)$ um grafo conexo que não possui vértices de corte e fixe $u,v \in V$. Por indução sobre $d(u,v)$, mostre que existe um ciclo de $G$ contendo $u$ e $v$ como vértices.

**~~#~~** Mostre que todo vértice de um grafo $G$ é vértice de algum bloco de $G$.

**~~#~~** Seja $G$ um grafo e $H$ e $H'$ dois de seus blocos distintos. Mostre que os vértices de $H$ e os vértices de $H'$ se intersectam em no máximo um vértice.

**~~#~~** Seja $G$ um grafo com finitos vértices e pelo menos dois blocos distintos. Considere $C$ o conjunto de seus vértices de corte e $B$ o conjunto de seus blocos. Vamos construir um grafo $T$ com conjunto de vértices $C\cup B$. Uma aresta $\{c,b\}$ existe se, e somente se, $c \in C$, $b \in B$ e o bloco $b$ contém o vértice de corte $c$.

**~~#.#~~** Mostre que $T$ não possui circuitos como subgrafos.

**~~#.#~~** Conclua que $G$ possui um bloco que contém apenas um vértice de corte de $G$.

**~~#~~** Mostre que, se $G$ é um grafo com uma quantidade finita de vértices e todos os seus blocos são planares, então $G$ é planar.

**~~#.#~~** Conclua que $G$ é um grafo planar se, e somente se, todos os seus blocos são planares. 

<WRAP tip>
Agora, o Teorema de Kuratowski se resume a mostrar que, se $G$ é um grafo que não possui vértices de corte e nem subdivisão de $K_{3,3}$ ou $K_5$, então $G$ é planar.
</WRAP>

**~~#~~** Por um momento, suponha que o Teorema de Kuratowski é falso e considere $G = (V,A)$ um grafo com finitos vértices que não possui vértices de corte e nem subdivisão de $K_{3,3}$ ou $K_5$. Podemos supor que $G$ possui a mínima quantidade de vértices com esta propriedade, isto é, qualquer grafo com menos vértices do que $G$ possuirá uma representação planar.

**~~#.#~~** Observe que $\delta(G)\geq 2$. Mostre que, ainda mais, $\delta(G)\geq 3$.

**~~#.#~~** Mostre que existe uma aresta $a \in A$ tal que o grafo $G = (V,A\setminus \{a\})$ também não possui vértices de corte.
Combinando

User Tools

Site Tools

Page Tools
