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