Graphe allumette

En mathématiques, plus particulièrement en théorie des graphes, un graphe allumette est un graphe connexe dont il est possible de donner une représentation dans le plan en représentant toutes les arêtes par des segments de même longueur et ne se croisant jamais.

Le graphe de Harborth est un exemple de graphe allumette.

Un graphe allumette est donc à la fois un graphe planaire et un graphe distance-unité[1]. La réciproque est fausse : le graphe de Moser, qui est à la fois un graphe planaire et un graphe distance-unité, n'est pas un graphe allumette.

Exemples

Références

  1. Jean-Paul Delahaye, « Les graphes-allumettes », Pour la Science, no 445, (lire en ligne)
  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons – Attribution – Partage à l’identique. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.