Loading AI tools
De Wikipédia, l'encyclopédie libre
En théorie des graphes, une branche des mathématiques, deux graphes et sont homéomorphes si l'on peut obtenir un même graphe en subdivisant certaines de leurs arêtes[1].
Deux graphes sont homéomorphes si et seulement si leurs représentations graphiques usuelles (avec des segments de droites reliant les sommets entre eux) sont homéomorphes au sens que ce mot a en topologie.
Il est évident que la subdivision préserve le fait d'être planaire pour un graphe.
Le théorème de Kuratowski affirme :
Théorème — Un graphe fini est planaire si et seulement si il ne contient pas de sous-graphe homéomorphe au graphe complet à 5 sommets ni au graphe biparti complet à 6 sommets .
De fait, un graphe homéomorphe à ou à est appelé un sous-graphe de Kuratowski.
Une généralisation qui découle du théorème de Robertson-Seymour affirme que pour tout nombre entier , il y a un ensemble de graphes « interdits » tels qu'un graphe peut être plongé dans une surface de genre si et seulement si ne contient pas de copie homéomorphe à l'un des graphes . Par exemple, est formé des deux graphes interdits ou à pour les surfaces de genre . est appelé ensemble d'obstruction.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.