Graphe de blocs
En théorie des graphes, une branche des mathématiques combinatoires, un graphe de blocs ou arbre de cliques[1] est un graphe non orienté dans lequel chaque composante biconnexe (ou « bloc ») est une clique.
Caractérisations
modifierLes graphes de blocs ont été appelés aussi arbres Husimi (d'après Kôdi Husimi)[2], 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[3].
Les graphes de blocs peuvent être caractérisés comme les graphes d'intersection des blocs de graphes non orientés quelconques[4]. 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[2],[5].
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[5]. 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[2], et les graphes cordaux dans lesquels deux cliques maximales quelconques ont au plus un sommet en commun[2].
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[6]. 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[1].
Classes associées
modifierLes graphes de blocs sont chordaux, à distance héréditaire et geodétiques (en). Les graphes à distance héréditaire sont les graphes dans lesquels deux chemins induits quelconques entre les mêmes deux sommets ont la même longueur, ce qui est une condition plus faible que la caractérisation des graphes de blocs comme ayant au plus un chemin induit entre deux sommets. Étant donné que les graphes cordaux et les graphes à distance héréditaire sont des sous-classes des graphes parfaits, les graphes en blocs sont parfaits.
Tout arbre, tout graphe cluster (en), tout graphe moulin est un graphe de blocs.
Tout graphe de blocs a une boxicité (en) au plus égale à deux[7]
Les graphes de blocs sont des exemples des graphes pseudo-médians : pour trois sommets quelconques, soit il existe un unique sommet qui appartient à la plus courte chaîne entre les trois sommets, soit il existe un unique triangle dont les arêtes se trouvent sur ces trois plus courtes chaînes[7]
Les line graphs des arbres sont exactement les graphes de blocs dans lesquels chaque point d'articulation est incident à au plus deux blocs, ou de manière équivalente les graphes de blocs sans griffes. Les line graphs d'arbres ont été utilisés pour trouver des graphes avec un nombre donné d'arêtes et de sommets dans lesquels le plus grand sous-graphe induit qui est un arbre est aussi petit que possible[8].
Les graphes de blocs dans lesquels chaque bloc a une taille au plus égale à trois sont un cas particulier des graphes cactus, à savoir les cactus triangulaire. Le plus grand cactus triangulaire dans un graphe peut être trouvé en temps polynomial en utilisant un algorithme pour le problème de parité de matroïde (en). Étant donné que les graphes cactus triangulaires sont planaires, le plus grand cactus triangulaire peut être utilisé comme approximation du plus grand sous-graphe planaire, un sous-problème important en planarisation (en). Comme algorithme d'approximation, cette méthode a un rapport d'approximation égal à 4/9, le meilleur rapport connu pour le problème du sous-graphe planaire maximum[9].
Graphes de blocs de graphes
modifierPour est un graphe non orienté G, le graphe de blocs de G, noté B(G), est le graphe d'intersection des blocs de G : ainsi, B(G) a un sommet pour chaque composante biconnexe de G, et deux sommets de B(G) sont adjacents si les deux blocs correspondants se rencontrent en un sommet d'articulation. Si K1 dénote le graphe singleton (à un somme, alors B(K1) est par convention le graphe nul. Le graphe B(G) est nécessairement un graphe de blocs : il a une composante biconnexe pour chaque sommet d'articulation de G, et chaque composante biconnexe ainsi formée doit être une clique. Inversement, chaque graphe de bloc est le graphe B(G) pour un graphe G[4]. Si G est un arbre, alors B(G) coïncide avec le line graph de G.
Le graphe B(B(G)) a un sommet pour chaque point d'articulation de G ; deux sommets sont adjacents dans B(B(G)) s'ils appartiennent au même bloc dans G.
Notes et références
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Block graph » (voir la liste des auteurs).
- Kristina Vušković, « Even-hole-free graphs: A survey », Applicable Analysis and Discrete Mathematics, vol. 4, no 2, , p. 219–240 (DOI 10.2298/AADM100812027V, lire en ligne).
- Edward Howorka, « On metric properties of certain clique graphs », Journal of Combinatorial Theory, Series B, vol. 27, no 1, , p. 67–74 (DOI 10.1016/0095-8956(79)90069-8).
- Un compte-rendu, par Robert E. Jamison, d'un article pour Math Reviewslien Math Reviews attribue cette confusion à une erreur dans un livre de Mehdi Behzad et Gary Chartrand.
- Frank Harary, « A characterization of block-graphs », Canadian Mathematical Bulletin, vol. 6, no 1, , p. 1–6 (DOI 10.4153/cmb-1963-001-x, hdl 10338.dmlcz/101399).
- Hans-Jürgen Bandelt et Henry Martyn Mulder, « Distance-hereditary graphs », Journal of Combinatorial Theory, Series B, vol. 41, no 2, , p. 182–208 (DOI 10.1016/0095-8956(86)90043-2).
- Paul H. Edelman et Robert E. Jamison, « The theory of convex geometries », Geometriae Dedicata, vol. 19, no 3, , p. 247–270 (DOI 10.1007/BF00149365, S2CID 123491343).
- Block graphs, Information System on Graph Class Inclusions.
- Paul Erdős, Michael Saks et Vera T. Sós, « Maximum induced trees in graphs », Journal of Combinatorial Theory, Series B, vol. 41, no 1, , p. 61–79 (DOI 10.1016/0095-8956(86)90028-6, lire en ligne
).
- Gruia Călinescu, Cristina G Fernandes, Ulrich Finkler et Howard Karloff, « A Better Approximation Algorithm for Finding Planar Subgraphs », Journal of Algorithms, Series 2, vol. 27, no 2, , p. 269–302 (DOI 10.1006/jagm.1997.0920, S2CID 8329680)
