Grafo planar

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

Na teoria dos grafos, um grafo planar é um grafo que pode ser representado no plano de tal forma que suas arestas não se cruzem. Por exemplo, os dois grafos seguintes são planares:

6n-graf.svg         Grafo k4 plano.PNG

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.

Teorema das quatro cores[editar | editar código-fonte]

O teorema das quatro cores afirma que qualquer grafo planar é 4-colorível (ou 4-partível).

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