Teorema de Kuratowski
Na teoria dos grafos, o teorema de Kuratowski é uma caracterização gráfica matemática proibida[1] de grafos planares, em homenagem a Kazimierz Kuratowski. O teorema declara que um grafo finito[2] é planar se, e somente se, ele não contém um subgrafo[3] que é uma subdivisão da K5 (o grafo completo em cinco vértices) ou de K3 (grafo bipartido completo em seis vértices, três dos quais se conectam a cada um dos outros três), também conhecido como o gráfico de utilidade[4].
Ver tambémEditar
Referências
- ↑ Michael D. Barrus, Mohit Kumbhat e Stephen G. Hartke ((online) 15 de Nov. de 2007). «Graph Classes Characterized Both by Forbidden Subgraphs and Degree Sequences» (PDF). Wiley InterScience(www.interscience.wiley.com). Consultado em Jan. de 2014 Verifique data em:
|acessodata=, |data=(ajuda) - ↑ Barile, Margherita (2014). «Finite Graph». MathWorld--A Wolfram Web Resource. Consultado em jan. 2014 Verifique data em:
|acessodata=(ajuda) - ↑ Jim Nastos (2008). «Graphs and subgraphs» (PDF). Department of Mathematical and Statistical Sciences of University of Alberta. Consultado em Jan. 2014 Verifique data em:
|acessodata=(ajuda) - ↑ Carsten Thomassen (1981). «Kuratowski's Theorem» (PDF). University of Denmark. Consultado em Jan. 2014 Verifique data em:
|acessodata=(ajuda)
