Graphe allumette
En mathématiques, plus particulièrement en théorie des graphes, un graphe allumette est un graphe connexe qui est à la fois un graphe planaire et un graphe distance-unité[1]. C'est donc un graphe qu'il est possible de représenter sur un plan, avec des arêtes toutes de longueur 1 et tel que deux arêtes ne se croisent jamais.
Le graphe de Harborth est un exemple de graphe allumette.
Exemples
- Tous les cycles ;
- Le graphe roue W7 (c'est le seul graphe roue à être distance-unité) ;
- Le graphe de Harborth.
Références
- Jean-Paul Delahaye, « Les graphes-allumettes », Pour la Science, no 445, (lire en ligne)
Portail des mathématiques 
Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.