Line graph
En théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960[1]. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943[2],[3]. Il est également appelé graphe adjoint[4].
Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes[2].
Définition formelle
modifierÉtant donné un graphe G, son line graph L(G) est le graphe défini de la façon suivante :
- Chaque sommet de L(G) représente une arête de G;
- Deux sommets de L(G) sont adjacents si et seulement si les arêtes correspondantes partagent une extrémité commune dans G (on dit alors qu'elles sont adjacentes).
Exemples
modifierExemple de construction
modifierLa figure suivante illustre un graphe (à gauche, avec des sommets bleus) et son line graph (à droite, avec des sommets verts). Chaque sommet du line graph est étiqueté avec les extrémités de l'arête correspondante dans le graphe d'origine.
-
Graphe G -
Sommets de L(G) construits à partir des arêtes de G -
Ajout des arêtes de L(G) -
Le line graph L(G)
Quelques line graphs
modifier- Le graphe de Petersen est le graphe complémentaire du line graph du graphe complet .
- Le line graph du graphe tétraédrique est le graphe octaédrique.
- Le line graph du graphe hexaédrique est le graphe cuboctaédrique.
- Le line graph du graphe dodécaédrique est le graphe icosidodécaédrique.
Propriétés
modifierPropriétés élémentaires
modifierLes propriétés d'un graphe G dépendant uniquement de l'adjacence entre arêtes peuvent être traduites sur L(G) en propriétés équivalentes dépendant de l'adjacence entre sommets. Par exemple, un couplage dans G, c'est-à-dire un ensemble d'arêtes qui n'ont pas de sommet en commun, correspond à un ensemble de sommets deux à deux non adjacents dans L(G), donc à un stable de L(G).
En conséquence, on a les propriétés suivantes :
- Le line graph d'un graphe connexe est connexe. La réciproque n'est cependant pas vraie. Un graphe G ayant des sommets isolés peut avoir un line graph connexe.
- Un ensemble stable de poids maximal dans un line graph L(G) correspond à un couplage maximum dans G. Comme un couplage maximum peut être trouvé en temps polynomial, la recherche d'un ensemble stable de poids maximal se fait également en temps polynomial dans un line graph, même s'il s'agit dans le cas général d'un problème NP-complet au sens de la théorie de la complexité.
- L'indice chromatique d'un graphe G est égal au nombre chromatique de son line graph L(G). En effet, colorer les arêtes d'un graphe équivaut à colorer les sommets de son line graph.
- Le line graph d'un graphe sommet-transitif est un graphe arête-transitif.
- Si un graphe G a un cycle eulérien, c'est-à-dire si G est connexe et que tous ses sommets sont de degré pair, alors le line graph L(G) est un graphe hamiltonien. Il peut exister cependant des cycles hamiltoniens dans L(G) qui ne proviennent pas de cycles eulériens dans G.
Relations avec d'autres familles de graphes
modifierLes line graphs sont des graphes sans griffe, c'est-à-dire des graphes qui n'admettent pas le graphe griffe comme sous-graphe induit.
Le line graph d'un graphe biparti est un graphe parfait (voir le théorème de König). Les line graphs des graphes bipartis sont utilisés dans la preuve du théorème des graphes parfaits.
Caractérisation des line graphs
modifier
Un graphe G est le line graph d'un autre graphe, si et seulement s'il est possible de trouver un ensemble de cliques dans G qui partitionne les arêtes de G tel que chaque sommet de G appartienne exactement à deux des cliques. Certaines de ces cliques peuvent être réduites à un seul sommet.
Par un résultat de Hassler Whitney[2], si G n'est pas un triangle, alors il ne peut y avoir qu'une seule partition de ce type. Si une telle partition existe, il est possible de retrouver le graphe d'origine dont G est le line graph. Pour cela, il suffit de créer un sommet pour chaque clique et de relier par des arêtes les couples de cliques qui partagent un sommet en commun dans G. Roussopoulos utilisa en 1973 ce résultat comme base pour construire une algorithme permettant d'identifier les 'line graphs en temps linéaire[5].
Un corollaire de ce résultat est que, exception faite des cas du graphe complet et du graphe biparti complet , si les line graphs L(G) et L(H) de deux graphes G et H sont isomorphes, alors les graphes G et H sont isomorphes.
Une autre caractérisation des line graphs fut proposée par Beineke en 1968[6] (puis prouvée en 1970[7]). Il montra qu'il existait neuf graphes minimaux qui n'étaient pas des line graphs tel que tout graphe n'étant pas un line graph avait pour sous-graphe induit au moins un de ces graphes minimaux.
Itération de l'opérateur line graph
modifierEn 1965, van Rooij et Wilf s'intéressent à l'itération de l'opérateur line graph[8]. Considérons la séquence suivante :
Alors, si G est un graphe connexe fini, seuls quatre comportements différents sont possibles pour cette séquence :
- Si G est un graphe cycle alors L(G) ainsi que chaque graphe de la séquence est un graphe isomorphe à G lui-même. Les graphes cycles sont les seuls graphes connexes à être isomorphes à leur line graph.
- Si G est le graphe griffe K1,3, alors L(G) et tous les graphes qui suivent dans la séquence sont des graphes triangles (donc des graphes cycles de longueur 3).
- Si G est un graphe chemin, alors chaque graphe qui suit dans la séquence est un chemin plus court jusqu'à terminer avec le graphe singleton et enfin le graphe nul.
- Dans tous les autres cas, la taille des graphes de la séquence augmente sans être bornée.
Si G n'est pas connexe, alors cette classification s'applique séparément à chaque composante connexe de G.
Applications et utilisations
modifierLe concept de line graph est notamment utilisé en théorie du calcul distribué, par exemple dans la borne inférieure de Nati Linial pour la coloration dans le modèle local[9].
Notes et références
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Line graph » (voir la liste des auteurs).
- (en) F. Harary et R. Z. Norman, « Some properties of line digraphs », Rendiconti del Circulo Mathematico di Palermo, vol. 9, , p. 161–169 (DOI 10.1007/BF02854581).
- (en) H. Whitney, « Congruent graphs and the connectivity of graphs », American Journal of Mathematics, vol. 54, no 1, , p. 150–168 (DOI 10.2307/2371086, lire en ligne).
- (en) J. Krausz, « Démonstration nouvelle d'un théorème de Whitney sur les réseaux », Mat. Fiz. Lapok, vol. 50, , p. 75–85.
- Didier Müller. Introduction à la théorie des graphes. Cahiers de la CRM numéro 6, Commission Romande de Mathématiques, 2012 [1].
- (en) N. D. Roussopoulos, « A max {m,n} algorithm for determining the graph H from its line graph G », Information Processing Letters, vol. 2, no 4, , p. 108–112 (DOI 10.1016/0020-0190(73)90029-X).
- (en) L. W. Beineke, Beiträge zur Graphentheorie, Leipzig, Teubner, , 17–33 p..
- (en) L. W. Beineke, « Characterizations of derived graphs », Journal of Combinatorial Theory, vol. 9, , p. 129–135 (DOI 10.1016/S0021-9800(70)80019-9).
- (en) A. C. M. van Rooij et H. S. Wilf, « The interchange graph of a finite graph », Acta Mathematica Hungarica, vol. 16, nos 3–4, , p. 263–269 (DOI 10.1007/BF01904834).
- (en) Nathan Linial, « Locality in Distributed Graph Algorithms », SIAM Journal on Computing, vol. 21, no 1, , p. 193-201.
