Graphe-allumettes

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

Un graphe-allumettes est un graphe à la fois distance-unité (au sens large) et planaire ; la réciproque est fausse comme le montrent les exemples du graphe prisme triangulaire et du graphe de Moser qui possèdent une représentation distance-unité et une représentation planaire mais pas de représentation ayant les deux propriétés simultanément.

• 
  Représentation "distance-unité" du graphe prisme triangulaire.
• 
  Représentation planaire du même graphe.
• 
  Représentation "distance-unité" du graphe de Moser.
• 
  Représentation planaire du même graphe.

• Les graphes chaine, les graphes grille, les graphes cycle, les graphes étoile.
• Le graphe de Harborth.
• Les graphes planaires connexes ayant une représentation où les faces sont des triangles équilatéraux identiques, comme le graphe triangle, le graphe diamant, le graphe papillon, le graphe roue W₇ (qui est le seul graphe roue à être distance-unité).
• Les graphes planaires connexes ayant une représentation où les faces sont des losanges identiques, comme les graphes de Jahangir, les rosaces rhombiques ou certains pavages de Penrose.
  • 
    Graphe rhombique.
  • 
    Graphe de Jahangir.
  • 
    Rosace rhombique.
  • 
    Pavage de Penrose.

Le nombre ${\displaystyle a(n)}$ de graphes-allumettes à ${\displaystyle n}$ arêtes à isomorphisme près est donné par la suite A066951 de l'OEIS^{[1] [2]}.

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10
${\displaystyle a(n)}$	1	1	3	5	12	28	74	207	633	2008

Par exemple, les trois graphes-allumettes à trois arêtes sont le graphe chaine, le graphe étoile ${\displaystyle S_{3}}$, et le graphe triangle.

Le nombre ${\displaystyle b(n)}$ de graphes-allumettes à ${\displaystyle n}$ arêtes à homéomorphisme près est donné par la suite A003055 de l'OEIS^{[1] [2]}.

${\displaystyle n}$	1	2	3	4	5	6	7	8	9	10
${\displaystyle b(n)}$	1	1	3	5	10	19	39	84	196	479

Le nombre ${\displaystyle c(n)}$ de graphes-allumettes à ${\displaystyle n}$ sommets à isomorphisme près est donné par la suite A303792 de l'OEIS^[3].

${\displaystyle n}$	1	2	3	4	5	6
${\displaystyle c(n)}$	1	1	2	5	13	50

• Graphe distance-unité
• Théorème de Fáry (tout graphe planaire peut être tracé avec des arêtes rectilignes, mais pas forcément de même longueur)

• Portail des mathématiques
• Portail de l'informatique théorique