Loading AI tools
De Wikipédia, l'encyclopédie libre
En mathématiques, et plus particulièrement en théorie des graphes, le critère de planarité de Whitney est une caractérisation, en théorie des matroïdes, des graphes planaires ; critère nommée d'après Hassler Whitney[1]. Il affirme qu'un graphe G est planaire si et seulement si son matroïde graphique est également cographique (c'est-à-dire qu'il est le matroïde dual d'un autre matroïde graphique).
En termes de théorie des graphes pures, ce critère énonce comme suit :
Une formulation équivalente du critère de Whitney est :
Un graphe dont le matroïde graphique est le dual du matroïde graphique de G est appelé dual algébrique de G. Ainsi, le critère de planarité de Whitney peut être exprimé simplement comme suit[2] :
Si un graphe G est plongé dans une surface topologique telle que le plan, de sorte que chaque face du plongement est un disque topologique, le dual graphique du plongement est défini comme le graphe (ou dans certains cas le multigraphe) H qui a un sommet pour chaque face du plongement de G et une arête pour chaque paire de faces adjacentes. Selon le critère de Whitney, les conditions suivantes sont équivalentes :
Il est possible de définir des graphes duaux de graphes plongés sur des surfaces non planes telles que le tore, mais ces duaux ne vérifient en général pas la correspondance entre coupes, cycles et arbres couvrant requis par le critère de Whitney.
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.