Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Graphe ptolémaïque
Résumé
vignette| Un graphe ptolémaïque.
vignette| Le graphe gemme ou 3-fan n'est pas ptolémaïque.
vignette|upright=1.4|Un graphe en bloc est un cas particulier d'un graphe ptolémaïque
vignette|upright=1.4| 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.
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 , et vérifient l'inégalité
Par exemple, le graphe gemme de l'illustration n'est pas ptolémaïque, car dans ce graphe
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 uvy et wxy ne sont pas séparées par leur intersection y, car l'arête vw relie les cliques et évite l'intersection.
Tout cycle à k sommets a au moins 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 uvwx, la distance de u à x est de 3, et est donc supérieure à la distance entre les mêmes sommets dans le graphe entier.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.