Teorema de Kuratowski

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

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, 3 (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]

  1. 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). Consult. Jan. de 2014. 
  2. Barile, Margherita (2014). "Finite Graph". MathWorld--A Wolfram Web Resource. Consult. jan. 2014. 
  3. Jim Nastos (2008). "Graphs and subgraphs" (PDF). Department of Mathematical and Statistical Sciences of University of Alberta. Consult. Jan. 2014. 
  4. Carsten Thomassen (1981). "Kuratowski's Theorem" (PDF). University of Denmark. Consult. Jan. 2014. 
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.