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ém[editar | editar código-fonte]
Referências
- ↑ Michael D. Barrus, Mohit Kumbhat e Stephen G. Hartke (15 de Nov. de 2007). «Graph Classes Characterized Both by Forbidden Subgraphs and Degree Sequences» (PDF). Wiley InterScience(www.interscience.wiley.com). Consultado em 1 Jan. de 2014
- ↑ Barile, Margherita (2014). «Finite Graph». MathWorld--A Wolfram Web Resource. Consultado em 1 jan. 2014
- ↑ Jim Nastos (2008). «Graphs and subgraphs» (PDF). Department of Mathematical and Statistical Sciences of University of Alberta. Consultado em 1 Jan. 2014
- ↑ Carsten Thomassen (1981). «Kuratowski's Theorem» (PDF). University of Denmark. Consultado em 1 Jan. 2014
