Graphe ptolémaïque

Un graphe ptolémaïque.

Le graphe gemme ou 3-fan n'est pas ptolémaïque.

Un graphe en bloc est un cas particulier d'un graphe ptolémaïque

Trois opérations qui permettent de construire tout graphe distance-héréditaire. Pour les graphes ptolémaïques, les voisins de « faux jumeaux » doivent former une clique, ce qui empêche la construction d'un cycle à 4 sommets, montré ici.

En théorie des graphes, un graphe de Ptolémée ou graphe ptolémaïque est un graphe non orienté dont les distances des plus courts chemins entre sommets les plus courtes obéissent à l'inégalité de Ptolémée, qui à son tour a été nommée d'après l'astronome et mathématicien grec Ptolémée. Les graphes de Ptolémée sont exactement les graphes qui sont à la fois cordaux et à distance héréditaire ; ils incluent les graphes par blocs et sont une sous-classe des graphes parfaits.

Caractérisations

Un graphe est ptolémaïque si et seulement s'il vérifie une des conditions équivalentes suivantes :

• Les distances des chemins les plus courts vérifient l'inégalité de Ptolémée : quatre sommets quelconques $u,v,w$, et $x$ vérifient l'inégalité

$d(u,v)d(w,x)+d(u,x)d(v,w)\ge d(u,w)d(v,x)$

Par exemple, le graphe gemme de l'illustration n'est pas ptolémaïque, car dans ce graphe

$d(u,w)d(v,x)=4>d(u,v)d(w,x)+d(u,x)d(v,w)=3$.

• L'intersection de deux cliques maximales chevauchantes est un séparateur qui sépare les différences des deux cliques. Dans le graphe gemme, ce n'est pas le cas : les cliques Modèle:Mvar et Modèle:Mvar ne sont pas séparées par leur intersection Modèle:Mvar, car l'arête Modèle:Mvar relie les cliques et évite l'intersection.
• Tout cycle à Modèle:Mvar sommets a au moins Modèle:Formule diagonales.
• Le graphe est à la fois cordal (chaque cycle de longueur supérieure à trois a une diagonale) et à distance héréditaire (chaque sous-graphe induit connexe a les mêmes distances que le graphe tout entier). Le graphe gemme ci-dessus est cordal mais n'est pas à distance héréditaire : dans le sous-graphe induit par Modèle:Mvar, la distance de Modèle:Mvar à Modèle:Mvar est de 3, et est donc supérieure à la distance entre les mêmes sommets dans le graphe entier. Comme les graphes cordaux et à distance héréditaire sont des graphes parfaits, les graphes de Ptolémaïque le sont aussi.
• Le graphe est cordal et ne contient pas de graphe gemme induitModèle:,.
• Le graphe est à distance héréditaire ne contient pas de cycle induit de longueur 4.
• Le graphe peut être construit à partir d'un sommet unique par une séquence d'opérations qui ajoutent un nouveau sommet pendant (de degré un) ou qui dupliquent un sommet existant sous réserve que le nouveau sommet dupliqué est adjacent à son jumeau (vrai jumeaux) sauf si les voisins des jumeaux forment une clique. Ces trois opérations, produisent tous les graphe à distance héréditaire. Pour obtenir tous les graphes ptolémaïques, il ne suffit pas d'utiliser des sommets pendants et de vrais jumeaux ; le cas exceptionnel des faux jumeaux est aussi nécessaire.
• Le diagramme de Hasse de la relation d'inclusion des intersections non vides de cliques maximales est un arbre orienté.
• Les sous-ensembles de sommets qui sont convexes (ce sont des ensembles qui contiennent chaque chemin le plus court entre deux sommets du sous-ensemble) forment une géométrie convexe. Cela signifie que tout ensemble convexe peut être obtenu à partir de l'ensemble de sommets tout entier en supprimant à plusieurs reprises un sommet « extrême », c'est-à-dire un sommet qui n'appartient à aucun des chemins les plus courts entre les sommets restants. Dans le graphe gemme, l'ensemble convexe Modèle:Mvar ne peut pas être obtenu de cette manière, car ni Modèle:Mvar ni Modèle:Mvar ne sont des sommets extrêmes.

Complexité de calcul

En vertu de la caractérisation par arbres orientés, les graphes de Ptolémée peuvent être reconnus en temps linéaire.

Énumération

La série génératrice des graphes ptolémaïques peut être décrite par des méthodes de combinatoire analytique ; ceci permet le calcul rapide du nombre de ces graphes. Le nombre de graphes ptolémaïques à Modèle:Mvar sommets étiquetés, pour $n=1,2,3,\dots$, est le suivant :

1, 1, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 1019915376831963, ... Modèle:OEIS

Bibliographie

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.