Graphe de blocs

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.

À 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.

Publications associées (6)

Concepts associés (12)

Graphe ptolémaïque

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.

Graphe à distance héréditaire

vignette| Exemple d'un graphe à distance héréditaire. En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits.

Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.

D-Cliques: Compensating for Data Heterogeneity with Topology in Decentralized Federated Learning

Anne-Marie Kermarrec, Erick Lavoie

The convergence speed of machine learning models trained with Federated Learning is significantly affected by non-independent and identically distributed (non-IID) data partitions, even more so in a fully decentralized setting without a central server. In ...

2022

Graph Drawing

Radoslav Fulek, Fabrizio Frati

In this paper we study the page number of upward planar directed acyclic graphs. We prove that the page number of any upward planar directed acyclic graph G is a function of the page number of a four-connected subgraph of G; further, we provide an upper bo ...

Springer Berlin Heidelberg2012

Joint Sink Mobility and Routing to Maximize the Lifetime of Wireless Sensor Networks: The Case of Constrained Mobility

Jean-Pierre Hubaux, Jun Luo

The longevity of wireless sensor networks (WSNs) is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged ...

2010