Ê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 de blocs
Résumé
vignette|upright=1.4|Un graphe de blocs.
En théorie des graphes, une branche des mathématiques combinatoires, un graphe de blocs ou arbre de cliques est un graphe non orienté dans lequel chaque composante biconnexe (ou « bloc ») est une clique.
Les graphes de blocs ont été appelés aussi arbres Husimi (d'après Kôdi Husimi), mais ce nom fait plus référence aux graphes cactus, qui sont des graphes dans lesquels chaque composante biconnexe non triviale est un cycle.
Les graphes de blocs peuvent être caractérisés comme les graphes d'intersection des blocs de graphes non orientés quelconques.
Les graphes de blocs sont exactement les graphes pour lesquels, pour tout choix de quatre sommets u, v, x et y, les deux plus grandes des trois distances d ( u, v ) + d ( x, y ), d ( u, x ) + d ( v, y ) et d ( u, y ) + d ( v, x ) sont toujours égales.
Les graphe de blocs ont également une caractérisation par mineurs exclu : ce sont les graphes qui n'ont pas le graphe diamant ou un cycle de longueur au moins quatre comme sous-graphe induit ; ce sont donc les graphes cordaux sans sous-graphe diamant. Ce sont aussi les graphes ptolémaïques ( graphes chordal distance-hereditary ) dans lesquels deux nœuds à distance deux sont connectés par un plus court chemin unique, et les graphes cordaux dans lesquels deux cliques maximales quelconques ont au plus un sommet en commun.
Un graphe G est un graphe de blocs si et seulement si l'intersection de deux sous-ensembles connexes de sommets de G est vide ou connexe. Par conséquent, les sous-ensembles connexes de sommets dans un graphe de blocs connexe forment une géométrie convexe, une propriété qui n'est pas vraie pour les graphes qui ne sont pas des graphes de blocs. Par cette propriété, dans un graphe de blocs connexe, chaque ensemble de sommets a un sur-ensemble connexe minimal unique, qui est sa fermeture dans la géométrie convexe. Les graphes de blocs connexes sont exactement les graphes dans lesquels il existe un chemin induit unique reliant une paire de sommets.
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.