Loading AI tools
cas particulier de graphes d'intervalle De Wikipédia, l'encyclopédie libre
Un graphe d'intervalles propre est un graphe d'intervalles possédant une représentation d'intervalles dans laquelle aucun intervalle n'est inclus dans l'autre.
Un graphe d'intervalles propre est nécessairement un graphe sans griffe.
Soit un graphe possédant une griffe comme sous-graphe induit. On appelle les quatre sommets de la griffe d'intervalles respectives ,, et tels que le sommet soit celui relié aux trois autres et que .
Comme la griffe est un graphe induit, , et ne sont pas voisins dans . On a donc .
est voisin de et donc et d'où et . On a donc , d'où . n'est donc pas un graphe d'intervalle propre.
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.