Ê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
Line graph
Résumé
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. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint.
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.
É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).
La 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.
File:Line graph construction 1.svg|Graphe ''G''
File:Line graph construction 2.svg|Sommets de ''L''(''G'') construits à partir des arêtes de ''G''
File:Line graph construction 3.svg|Ajout des arêtes de ''L''(''G'')
File:Line graph construction 4.svg|Le ''line graph'' ''L''(''G'')
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 icosaédrique.
Les 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).
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.
Proximité ontologique
Cours associés (32)
PHYS-512: Statistical physics of computation
This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and
EE-548: Audio engineering
This lecture is oriented towards the study of audio engineering, with a special focus on room acoustics applications. The learning outcomes will be the techniques for microphones and loudspeaker desig
ME-427: Networked control systems
This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun