Teorema de Kuratowski
Na teoria dos grafos, o teorema de Kuratowski é um teorema que permite caracterizar os grafos planares, publicado em 1930 por Kazimierz Kuratowski[1]. O teorema declara que um grafo finito[2] é planar se, e somente se, ele não contém nenhum subgrafo que seja uma subdivisão de (o grafo completo com cinco vértices) ou de (grafo bipartido completo com 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.
O teorema
editarEnunciado do teorema
editarO teorema apresenta uma condição necessária e suficiente para a planaridade, logo consiste em duas implicações:
- se o grafo for planar, então não tem nenhum subgrafo que seja uma subdivisão de ou ;
- se o grafo não tiver nenhum subgrafo que seja uma subidivisão de ou , então é planar.
Alternativamente, uma versão equivalente é que um grafo é não-planar se e só se contém um subgrafo que é uma subidivsão de ou
Algumas definições
editarUm grafo planar é um grafo que pode ser desenhado no plano sem que as suas arestas se intersetem. Um subgrafo de um grafo é um grafo cujos vértices e arestas são um subconjunto dos vértices e arestas de . Uma subdivisão de um grafo é um novo grafo formado ao subdividir uma aresta desse grafo (basicamente colocar mais vértices numa aresta).
História
editarO teorema foi publicado por Kazimierz Kuratowski em 1930. Também em 1930 foi provado independentemente por Orrin Frink e Paul Smith[3], contudo a sua prova nunca foi publicada. O caso particular de grafos planares cúbicos também foi provado independentemente por Karl Menger em 1930.[4] Desde então, várias novas provas deste teorema têm sido descobertas[5].
Na união soviética, este teorema era conhecido como o teorema de Pontryagin-Kuratowski ou Kuratowski-Pontryagin[6], já que teria sido provado por Lev Pontryagin por volta de 1927[7]. Contudo, como Pontryagin nunca publicou a sua prova, este nome não se espalhou.
Ver também
editarReferências
- ↑ Kuratowski, Casimir (1930). «Sur le problème des courbes gauches en Topologie». Fundamenta Mathematicae (em inglês): 271–283. ISSN 0016-2736. doi:10.4064/fm-15-1-271-283. Consultado em 3 de julho de 2024
- ↑ Barile, Margherita (2014). «Finite Graph». MathWorld--A Wolfram Web Resource. Consultado em 1 jan. 2014
- ↑ Frink, Orrin; Smith, Paul A. (1930), "Irreducible non-planar graphs", Bulletin of the AMS, 36: 214
- ↑ Menger, Karl (1930), "Über plättbare Dreiergraphen und Potenzen nichtplättbarer Graphen", Anzeiger der Akademie der Wissenschaften in Wien, 67: 85–86
- ↑ Thomassen, Carsten (setembro de 1981). «Kuratowski's theorem». Journal of Graph Theory (em inglês) (3): 225–241. ISSN 0364-9024. doi:10.1002/jgt.3190050304. Consultado em 3 de julho de 2024
- ↑ Burstein, Michael (abril de 1978). «Kuratowski-Pontrjagin theorem on planar graphs». Journal of Combinatorial Theory, Series B (em inglês) (2): 228–232. doi:10.1016/0095-8956(78)90024-2. Consultado em 3 de julho de 2024
- ↑ Kennedy, John W; Quintas, Louis V; Sysło, Maciej M (novembro de 1985). «The theorem on planar graphs». Historia Mathematica (em inglês) (4): 356–368. doi:10.1016/0315-0860(85)90045-X. Consultado em 3 de julho de 2024
<ref>
definido em <references>
não tem um atributo de nome.