Grafo planar

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo plano K4

Em Teoria dos Grafos, um grafo planar é um grafo que pode ser imerso no plano de tal forma que suas arestas não se cruzem, esta é uma idealização abstrata de um grafo plano, um grafo plano é um grafo planar que foi desenhado no plano sem o cruzamento de arestas.[1]

Aparentemente o estudo da planaridade de um grafo é uma questão topológica que se baseia em resultados como o Teorema da Curva de Jordan que de forma simplificada diz que uma curva fechada simples no plano divide-o em duas partes, apesar deste ser um critério muito importante, é natural o questionamento se há algum resultado combinatório que caracterize um grafo plano.

Observe os dois exemplos, ambos isomorfos entre si, ambos planares, porém apenas o que é desenhado sem cruzamento de arestas é um grafo plano.

Grafo planar K4

Histórico[editar | editar código-fonte]

Uma das motivações mais antigas para o estudo da planaridade de um grafo é o famoso problema das três casas. Este problema foi proposto por Henry Dudeney em 1913.[2] E pode ser enunciado matematicamente na seguinte forma, dado um grafo K3,3 , sabemos que este é um grafo bipartido, completo, gostaríamos de saber se este grafo pode ser desenhado no plano de forma que nenhuma aresta cruze outra. É possível tal desenho?

Teorema de Kuratowski[editar | editar código-fonte]

Segundo o Teorema de Kuratowski, um grafo planar não pode apresentar nem o grafo completo K5 nem o grafo bipartido K3,3 como subgrafos. A prova de que o K3,3 não é planar pode ser feita de duas formas: por indução e por construção, enquanto a do K5 é feita apenas por construção.

Não é possível redesenhar estes grafos sem que suas arestas se cruzem.

Ver também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  1. Bondy, John Adrian. Graph theory with application. [S.l.: s.n.], 1979. ISBN 0-444-19451-7
  2. Britannica - Dudeney Henry Gas Water Electricity Problem. Visitado em 22/05/2015.