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