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). Consultado em Jan. de 2014  Verifique data em: |acessodata=, |data= (ajuda)
  2. Barile, Margherita (2014). «Finite Graph». MathWorld--A Wolfram Web Resource. Consultado em jan. 2014  Verifique data em: |acessodata= (ajuda)
  3. 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)
  4. Carsten Thomassen (1981). «Kuratowski's Theorem» (PDF). University of Denmark. Consultado em Jan. 2014  Verifique data em: |acessodata= (ajuda)
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.