Utilisateur:Tartetatindu03/Théorème de Kuratowski
Ne doit pas être confondu avec Théorème de fermeture/complémentaire de Kuratowski.
En théorie des graphes, le théorème de Kuratowski est une caractérisation des graphes planaires, du nom de Kazimierz Kuratowski. Il indique qu'un graphe fini est planaire si et seulement s'il ne contient pas de sous-graphe qui est une subdivision de K5 (le graphe complet à cinq sommets) ou de K3,3 [1](le graphe biparti complet constitué de deux sous ensembles de trois sommets, et tels que chaque sommet d'une partie soit relié à tous les sommets de l'autre).
Énoncé du théorème[modifier | modifier le code]
Un graphe planaire est un graphe dont les sommets peuvent être représentés par des points dans le plan euclidien, et dont les arêtes peuvent être représentées par des courbes simples dans le même plan reliant leurs extrémités, de sorte qu'aucune courbe ne se croise sauf à une extrémité commune[1]. D'après le théorème de Fary[2], tout graphe planaire admet une représentation dans le plan pour laquelle les arêtes sont des segments de droite.
Une subdivision d'un graphe est un graphe construit à partir d'un autre en ajoutant des sommets (de degré 2) sur ses arêtes. Le théorème de Kuratowski affirme qu'un graphe G est planaire, si et seulement s'il n'est pas possible de subdiviser les arêtes de K5 ou K3,3, puis d'ajouter éventuellement des arêtes et des sommets supplémentaires, pour former un graphe isomorphe à G. De manière équivalente, un graphe est plan si et seulement s'il ne contient pas de sous-graphe homéomorphe à K5 ou K3,3 .
Sous-graphes de Kuratowski[modifier | modifier le code]
Si G est un graphe contenant un sous-graphe H qui est une subdivision de K5 ou K3,3, alors H est appelé sous-graphe de Kuratowski de G[3]. Avec cette notation, le théorème de Kuratowski peut être énoncé succinctement: un graphe est planaire si et seulement s'il n'a pas de sous-graphe de Kuratowski.
Les deux graphes K5 et K3,3 sont non planaires, comme le montrent soit une analyse de cas, soit un argument faisant intervenir la formule d'Euler. De plus, si une subdivision d'un graphe G a une représentation dans le plan, les subdivisions des arêtes forment des courbes simples, et donc une représentation de lui même. Par conséquent, un graphe qui contient un sous-graphe de Kuratowski ne peut pas être planaire. Le sens le plus difficil pour démontrer le théorème de Kuratowski est de prouverr que, si un graphe est non planaire, alors il contient un sous-graphe de Kuratowski.
Histoire[modifier | modifier le code]
Kazimierz Kuratowski a publié son théorème en 1930[4]. Le résultat a aussi été prouvé indépendamment par Orrin Frink et Paul Smith, également en 1930[5] mais leur démonstration n'a jamais été publiée. Le cas particulier des graphes cubiques planaires (pour lesquels les seuls sous-graphes exclus sont les subdivisions de K3,3) a également été montré de façon indépendante par Karl Menger en 1930[6].
Articles connexes[modifier | modifier le code]
Références[modifier | modifier le code]
- Mohar, Bojan, 1956-, Graphs on surfaces, Johns Hopkins University Press, (ISBN 0-8018-6689-8 et 978-0-8018-6689-0, OCLC 45102952, lire en ligne)
- (en) István Fáry, « On straight-line representation of planar graphs », Acta Sci. Math. (Szeged), , p. 229-233
- S. G. Williamson, « Depth-First Search and Kuratowski Subgraphs », Journal of the ACM, vol. 31, no 4, , p. 681–693 (ISSN 0004-5411, DOI 10.1145/1634.322451, lire en ligne, consulté le )
- Mehlhorn, Kurt., LEDA : a platform for combinatorial and geometric computing., Cambridge Univ. Press, (ISBN 978-0-521-12956-5 et 0-521-12956-7, OCLC 772970562, lire en ligne)
- Markus Chimani, Petra Mutzel et Jens M. Schmidt, « Efficient Extraction of Multiple Kuratowski Subdivisions », dans Graph Drawing, Springer Berlin Heidelberg (ISBN 978-3-540-77536-2, lire en ligne), p. 159–170
- Casimir Kuratowski, « Sur le problème des courbes gauches en Topologie », Fundamenta Mathematicae, vol. 15, , p. 271–283 (ISSN 0016-2736 et 1730-6329, DOI 10.4064/fm-15-1-271-283, lire en ligne, consulté le )