Graphe Dual
- Graphe Dual
-
Graphe dual
Le graphe dual d'un graphe n'est défini que pour les graphes planaires. De plus, le graphe dual d'un graphe planaire G est défini à partir d'un plongement de G sur une surface. A partir d'un tel plongement de G, on peut définir les faces de G (car en fait G est alors en bijection avec un polyèdre).
Le graphe dual de G est alors le graphe dont les sommets correspondent aux faces de G et où deux sommets sont adjacents s'ils correspondent à deux faces adjacentes. Par-exemple, le graphe complet sur quatre sommets est isomorphe à son dual (on dit d'un tel graphe qu'il est auto-dual).
Le concept de dualité en théorie des graphes est une généralisation du concept de dualité d'un polyèdre.
voir aussi
Portail des mathématiques
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Graphe Dual de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Graphe dual — Pour les articles homonymes, voir Dualité (mathématiques) pour les autres notions de dualité en mathématiques. En théorie des graphes, le graphe dual d un graphe plongé à l intérieur d une surface est défini à l aide des composantes du… … Wikipédia en Français
Graphe de Nauru — Représentation du graphe de Nauru. Notation F24A Nombre de sommets 24 Nombre d arêtes 36 Distribution des degrés 3 régulier … Wikipédia en Français
Graphe roue — Quelques exemples de graphe roue. Notation Wn Nombre de sommets n Nombre d arêtes 2(n … Wikipédia en Français
Graphe hexaédrique — Représentation du graphe hexaédrique. Nombre de sommets 8 Nombre d arêtes 12 Distribution des degrés 3 régulier Rayon 3 … Wikipédia en Français
Graphe octaédrique — Représentation du graphe octaédrique. Nombre de sommets 6 Nombre d arêtes 12 Distribution des degrés 4 régulier Rayon … Wikipédia en Français
Graphe autodual — Pour les articles homonymes, voir autodual pour les autres notions d autodualité. En théorie des graphes, un graphe autodual est son propre graphe dual[1]. Le graphe dual d un graphe G est défini à partir d un plongement de G sur une surface. À… … Wikipédia en Français
Graphe planaire extérieur — Un graphe planaire extérieur maximal, muni d un 3 coloriage. En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l anglais, outer planar) s il peut être dessiné dans… … Wikipédia en Français
Graphe cuboctaédrique — Représentation du graphe cuboctaédrique. Nombre de sommets 12 Nombre d arêtes 24 Distribution des degrés 4 régulier Rayon … Wikipédia en Français
Dual topologique — Pour les articles homonymes, voir Dualité (mathématiques) et Dualité. Sommaire 1 Définition 2 Topologies duales 2.1 … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
