Graphe distance-unité

Carte Commune · n° 336457

En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe pouvant être représenté par un ensemble de points du plan euclidien en reliant par une arête uniquement des paires de points distants d'une unité ; s'il existe une représentation où toutes les paires de points à distance 1 sont reliées, on parle de graphe distance-unité strict. Les arêtes peuvent se croiser, si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. Si une représentation est sans croisement entre les arêtes, toutes de longueur 1, alors le graphe est qualifié de graphe-allumettes.

Lire sur Wikipédia · Image Public domain