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 ${\displaystyle K_{5}}$ (o grafo completo com cinco vértices) ou de ${\displaystyle K_{3,3}}$ (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

${\displaystyle K_{5}}$ - O grafo completo com 5 vértices. (Todos os vértices estão ligados entre si).

Enunciado do teorema

O 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 ${\displaystyle K_{5}}$ ou ${\displaystyle K_{3,3}}$;
• se o grafo não tiver nenhum subgrafo que seja uma subidivisão de ${\displaystyle K_{5}}$ ou ${\displaystyle K_{3,3}}$, 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 ${\displaystyle K_{5}}$ ou ${\displaystyle K_{3,3}}$

Algumas definições

${\displaystyle K_{3,3}}$- Grafo bipartido completo com 6 vértices. Existem dois conjuntos de 3 vértices em que cada um dos vértices está ligados a todos os vértices do outro conjunto.

Um grafo planar é um grafo que pode ser desenhado no plano sem que as suas arestas se intersetem. Um subgrafo de um grafo ${\displaystyle G}$ é um grafo cujos vértices e arestas são um subconjunto dos vértices e arestas de ${\displaystyle G}$. 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

O 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

• Grafo planar

Referências

1. 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
2. Barile, Margherita (2014). «Finite Graph». MathWorld--A Wolfram Web Resource. Consultado em 1 jan. 2014
3. Frink, Orrin; Smith, Paul A. (1930), "Irreducible non-planar graphs", Bulletin of the AMS, 36: 214
4. Menger, Karl (1930), "Über plättbare Dreiergraphen und Potenzen nichtplättbarer Graphen", Anzeiger der Akademie der Wissenschaften in Wien, 67: 85–86
5. 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
6. 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
7. 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
8. Kuratowski, Kazimierz (1930), "Sur le problème des courbes gauches en topologie" (PDF), Fund. Math. (in French), 15: 271–283, doi:10.4064/fm-15-1-271-283
9. Barile, Margherita (2014). «Finite Graph». MathWorld--A Wolfram Web Resource. Consultado em 1 jan. 2014

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o. v d e