Lexique de la théorie des graphes
A
- Acyclique
- graphe ne contenant pas de cycle.
- Adjacence
- une liste d'adjacence est une structure de données constituée d'un tableau dont le -Úme élément correspond à la liste des voisins du -Úme sommet.
- Adjacence
- une matrice d'adjacence est une matrice carrĂ©e usuellement notĂ©e , de dimensions , dont chaque Ă©lĂ©ment est Ă©gal au nombre d'arĂȘtes incidentes (ayant pour extrĂ©mitĂ©s) aux sommets d'indices et (pour un graphe simple non pondĂ©rĂ©, ). Dans le cas d'un graphe pondĂ©rĂ©, chaque Ă©lĂ©ment est Ă©gal Ă la somme du poids des arĂȘtes incidentes.
- Adjacence
- une relation d'adjacence propriĂ©tĂ© de deux sommets d'ĂȘtre connectĂ©s par la mĂȘme arĂȘte (dits sommets adjacents) ou propriĂ©tĂ© de deux arĂȘtes de prĂ©senter une extrĂ©mitĂ© commune (dites arĂȘtes adjacentes). Ăgalement appelĂ© relation de voisinage.
- Adjoint
- un graphe adjoint est synonyme de line graph.
- Admittance
- autre nom d'une matrice laplacienne.
- Aléatoire
- un graphe est aléatoire, ou non déterministe, dÚs que sa construction fait intervenir des probabilités.
- Arbre
- graphe connexe et acyclique. Ăquivalent Ă un graphe connexe Ă sommets et arĂȘtes.
- Arbre enraciné ou arborescence
- graphe acyclique orientĂ© oĂč on distingue une racine de degrĂ© entrant nul, et oĂč tous les autres sommets sont de degrĂ© entrant 1.
- Arc
- arĂȘte dans un graphe orientĂ©. Autre formulation : couple (ensemble ordonnĂ© de deux Ă©lĂ©ments) de sommets reliĂ©s par une arĂȘte dans un graphe non orientĂ©.
- Arc-transitif
- un graphe G est arc-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses arcs. Ătant donnĂ© deux arĂȘtes , il existe deux automorphismes et tels que , , et , , , .
- ArĂȘte
- connexion entre deux sommets et . Dans le cas des graphes orientĂ©s on parle d'arc. Le terme « arĂȘte » est alors utilisĂ© pour dĂ©signer l'ensemble des deux arcs , c'est-Ă -dire de vers , et , c'est-Ă -dire de vers . Ne pas confondre avec arĂȘte en gĂ©omĂ©trie.
- ArĂȘte multiple
- ensemble d'arĂȘtes parallĂšles relatif Ă un couple de sommets.
- ArĂȘte parallĂšle
- arĂȘte ayant pour extrĂ©mitĂ©s les mĂȘmes sommets qu'une autre arĂȘte. On parle d'arĂȘtes parallĂšles.
- ArĂȘte-transitif
- un graphe est arĂȘte-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses arĂȘtes. Autre formulation de la condition : pour tout couple d'arĂȘtes, au moins un automorphisme envoie la premiĂšre composante sur la seconde. Toutes les arĂȘtes jouent exactement le mĂȘme rĂŽle Ă l'intĂ©rieur du graphe. Exemple : un graphe complet.
- Automorphisme
- isomorphisme d'un graphe sur lui-mĂȘme. Chaque graphe possĂšde au moins un automorphisme : l'identitĂ©. L'ensemble des automorphismes d'un graphe forme un groupe.
B
- Biconnexe
- un graphe non orienté est dit biconnexe si, en retirant n'importe lequel de ses sommets, il reste connexe. Cela revient à dire que le graphe n'a pas de point d'articulation.
- Biparti
- un graphe est dit biparti s'il existe une partition de son ensemble de sommets en deux sous-ensembles et telle que deux sommets adjacents soient dans deux parties différentes. Cela revient à dire que le graphe est 2-colorable.
- Biparti complet
- un graphe est dit biparti complet s'il est biparti et qu'il existe une arĂȘte entre chaque sommet de et de . On note le graphe biparti complet tel que et .
- Birégulier
- un graphe est dit birĂ©gulier s'il est biparti et si chacune de ses parties et n'a que des sommets de mĂȘme degrĂ©. On le dit -rĂ©gulier si et .
- Blob
- bridgeless component en anglais, ensemble de sommets ne contenant pas d'isthme[1].
- Bloc
- ensemble de sommets ne contenant pas de point d'articulation[1].
- Boucle
- arĂȘte partant d'un sommet et arrivant sur lui-mĂȘme.
C
- Cactus
- un graphe connexe dans lequel deux cycles simples quelconques ont au plus un sommet en commun.
- Centralité
- un indicateur de centralité est une mesure censée capturer la notion d'importance dans un graphe, en identifiant les sommets les plus significatifs.
- ChaĂźne
- dans un graphe non orientĂ©, une chaĂźne est une suite finie non vide de sommets telle que chaque paire de sommets consĂ©cutifs de la suite soit une arĂȘte du graphe ; la suite (un moins en longueur) d'arĂȘtes ainsi obtenue caractĂ©rise aussi la chaĂźne. La notion correspondante dans un graphe orientĂ© est celle d'un chemin. La longueur d'une chaĂźne est celle de sa suite d'arĂȘtes (un moins que la longueur sa suite de sommets). La source de la chaĂźne est son premier sommet, et son but est son dernier sommet. Une chaĂźne est dite Ă©lĂ©mentaire si aucun sommet ne figure plus d'une fois dans la suite, Ă l'exception de la source et le but de la chaĂźne qui peuvent coĂŻncider.
- Chemin
- dans un graphe orienté, un chemin est une suite finie non vide de sommets telle que chaque couple de sommets consécutifs de la suite est un arc du graphe ; la suite d'arcs ainsi obtenue caractérise aussi le chemin. La notion correspondante dans un graphe non orienté est celle d'une chaßne. La longueur d'un chemin est celle de sa suite d'arcs (un moins que la longueur sa suite de sommets). La source du chemin est son premier sommet, et son but est son dernier sommet. Un chemin est dit élémentaire si aucun des sommets ne figure plus d'une fois comme source, ni plus d'une fois comme but d'un arc du chemin (mais source et but du chemin peuvent coïncider).
- Chenille
- c'est un arbre dans lequel tous les sommets sont Ă distance au plus 1 d'un chemin central.
- Circonférence
- longueur du plus grand cycle.
- Nombre chromatique
- nombre minimal de couleurs pour colorier un graphes sans sommets adjacents de mĂȘme couleur.
- Nombre chromatique non répétitif
- nombre minimal de couleurs pour colorier un graphes dont les chaßnes sont sans facteurs de couleurs répétées.
- Clique
- sous-graphe induit complet, c'est-à -dire un sous-ensemble des sommets tels que chacun est connecté à tous les autres. Une clique est un ensemble indépendant (ou stable) du graphe complémentaire.
- Coloration
- fonction associant à tout sommet une couleur, tels que deux sommets adjacents aient une couleur différente (c'est-à -dire partitionne les sommets en ensembles indépendants).
- k-coloration
- coloration d'un graphe en k couleurs distinctes.
- Complémentaire
- le complĂ©mentaire (ou inverse, ou complĂ©ment) d'un graphe simple est un graphe simple qui a les mĂȘmes sommets que G, reliĂ©s si et seulement sâils ne sont pas reliĂ©s dans le graphe d'origine, soit .
- Complet
- dans un graphe complet chaque sommet est relié à tous les autres. On note le graphe complet à n sommets.
- Composante
- une composante d'un graphe est un sous-graphe connexe maximal.
- Connexe
- un graphe est connexe s'il existe un chemin entre tout couple de sommets. Quand on parle de connexité pour un graphe orienté, on considÚre non pas ce graphe mais le graphe non-orienté correspondant. On peut déterminer ceci par exemple avec un algorithme de parcours en profondeur. Un graphe orienté est dit fortement connexe si, pour tout couple de sommets (u,v) du graphe, il existe un chemin de u à v et de v à u.
- k-arĂȘte-connexe
- un graphe est k-arĂȘte-connexe s'il cesse d'ĂȘtre connexe uniquement quand on supprime k arĂȘtes ; ceci peut se vĂ©rifier par la prĂ©sence de k chaĂźnes disjointes (ne partageant aucune arĂȘte) entre chaque sommet.
- k-sommet-connexe (ou k-connexe)
- un graphe est k-sommet-connexe s'il cesse d'ĂȘtre connexe uniquement quand on supprime k sommets.
- Contenir
- un graphe contient si est un sous-graphe induit de .
- Contraction
- supprime une arĂȘte d'un graphe en fusionnant ses deux extrĂ©mitĂ©s. Autrement dit, la contraction d'une arĂȘte Ă un sommet rend le sommet adjacent Ă tous les voisins prĂ©cĂ©dents de .
- Corde
- arĂȘte reliant deux sommets non-adjacents d'un cycle.
- Cospectral
- deux graphes sont cospectraux s'ils ont le mĂȘme spectre. Ce spectre pouvant ĂȘtre basĂ© sur plusieurs matrices, on peut prĂ©ciser A-cospectraux pour le spectre de la matrice d'adjacence et L-cospectraux pour le spectre de la matrice laplacienne.
- Coupe
- partition des sommets en deux sous-ensembles. Peut aussi dĂ©signer lâensemble des arĂȘtes ayant une extrĂ©mitĂ© dans chaque sous-ensemble.
- Couverture par sommets
- Une couverture par sommets ou transversale d'un graphe G est un ensemble C de sommets de G tel que chaque arĂȘte du graphe est incidente Ă au moins un sommet de C.
- Couvrant
- un sous-graphe d'un graphe couvre (on dit aussi qu'il est un sous-graphe couvrant ou un graphe partiel de ) si tous les sommets de sont dans ().
- Creux
- un graphe creux possĂšde un nombre d'arĂȘtes (ou d'arcs) faible par rapport au nombre de sommets.
- Cubique
- graphe 3-régulier.
- Cycle
- chaĂźne dont les sommets de dĂ©part et de fin sont les mĂȘmes. Autrement dit, soit un chemin dont les arĂȘtes sont : le cycle est alors dĂ©fini par . Dans un graphe orientĂ©, on parlera d'un circuit plutĂŽt que d'un cycle, mĂȘme si la terminologie n'est pas tout Ă fait stabilisĂ©e.
- Cyclomatique
- le nombre cyclomatique d'un graphe est , oĂč est le nombre de composantes connexes. C'est Ă©galement la dimension de l'espace des cycles.
D
- Degré
- dans le cas non-orientĂ© et non pondĂ©rĂ©, le degrĂ© du sommet est le nombre d'arĂȘtes de . Dans le cas d'un graphe orientĂ©, le degrĂ© entrant est le nombre d'arcs vers tandis que le degrĂ© sortant est le nombre d'arcs sortant de . Le degrĂ© maximum est notĂ© , et le degrĂ© minimal . Dans le cas pondĂ©rĂ©, le degrĂ© d'un sommet est la somme du poids des arĂȘtes incidentes Ă ce sommet.
- Demi-carré
- le sous-graphe induit sur l'un des deux sous-ensembles de sommets du carré d'un graphe biparti. Se dit aussi moitié bipartie.
- Demi-graphe
- un graphe biparti qui possĂšde environ la moitiĂ© des arĂȘtes d'un graphe biparti complet sur ses sommets.
- Degrés (matrice)
- la matrice des degrés d'un graphe est une matrice carrée de taille telle que et .
- Dense
- un graphe dense possĂšde un nombre d'arĂȘtes (ou d'arcs) proche du nombre maximal.
- Densité
- la densitĂ© d'un graphe est le rapport entre le nombre d'arĂȘtes (ou d'arcs) divisĂ© par le nombre d'arĂȘtes (ou d'arcs) possibles. Dans le cas d'un graphe non orientĂ©, simple et fini , c'est le rapport .
- DiamĂštre
- excentricité maximale des sommets, notée .
- Dilatation
- dans un plongement oĂč associe des sommets d'un graphe Ă ceux d'un graphe , la dilatation est la distance maximale entre les images par de deux sommets adjacents dans . Autrement dit, si deux sommets sont voisins dans un graphe, leurs images peuvent ĂȘtre sĂ©parĂ©es par un chemin qui augmente donc la distance entre eux, et la plus grande augmentation est la dilatation.
- Dimension
- la dimension minimale d'un espace euclidien afin qu'un graphe puisse y ĂȘtre reprĂ©sentĂ© avec des arĂȘtes qui soient toutes de longueur 1.
- Dimension euclidienne ou dimension fidĂšle
- la dimension minimale d'un espace euclidien afin qu'un graphe puisse y ĂȘtre reprĂ©sentĂ© de telle sorte que des sommets soient Ă distance 1 si et seulement s'ils sont reliĂ©s.
- Dimension bipartie
- le nombre minimal de sous-graphes bipartis complets nĂ©cessaires pour couvrir toutes les arĂȘtes d'un graphe.
- Dimension métrique
- le nombre minimal de sommets d'un sous-graphe de tel que tous les autres sommets sont déterminés de façon unique par leur distance aux sommets de .
- Distance
- la distance entre et est la longueur du plus court chemin entre ces sommets ; aussi appelée distance géodésique.
- Distance (matrice de)
- matrice d'éléments aij correspondant a la longueur du plus court chemin (la distance) entre les sommets d'indices i et j.
- Distance-régulier
- un graphe est distance-régulier si pour tous sommets , le nombre de sommets voisins de à distance et le nombre de sommets voisins de à distance ne dépendent que de et de la distance entre et . Formellement, tels que et
- Dominant (ou absorbant)
- un ensemble de sommet est dominant si tout sommet en fait partie ou est voisin d'un sommet en faisant partie.
- Dureté
- la duretĂ© (« toughness » en anglais) est une mesure de la connexitĂ© d'un graphe. Un graphe est dit -dur pour un nombre rĂ©el donnĂ© si, pour tout entier , ne peut pas ĂȘtre divisĂ© en composantes connexes par la suppression de moins de sommets.
E
- Espace
- soit un graphe . L'espace des sommets est l'espace vectoriel sur avec comme base , soit un espace de dimension . De mĂȘme, l'espace des arĂȘtes est l'espace vectoriel sur avec comme base , soit un espace de dimension . Le principe du 0 et du 1 est qu'on obtient 1 pour un sommet (ou arĂȘte) appartenant Ă l'espace et 0 sinon.
- Ătiquetage
- fonction associant chaque sommet Ă une Ă©tiquette, pouvant ĂȘtre dans n'importe quel ensemble (rĂ©els, mots, couleurs...).
- Eulérien
- un chemin eulĂ©rien est un chemin qui passe par toutes les arĂȘtes exactement une fois. Un cycle eulĂ©rien est un chemin eulĂ©rien oĂč les sommets de dĂ©part et d'arrivĂ©e sont les mĂȘmes. Un graphe oĂč l'on peut construire un cycle eulĂ©rien est appelĂ© graphe eulĂ©rien ; si l'on ne peut construire que des chemins eulĂ©riens, alors le graphe est semi-eulĂ©rien. Un graphe est eulĂ©rien si chaque sommet est de degrĂ© pair.
- Excentricité
- l'excentricité d'un sommet est sa distance maximale à tous les autres sommets.
- Expanseur (graphe)
- expander graph en anglais. Soit G = (V, E) un graphe Ă n sommets. Pour un sous-ensemble de sommets W â V, on appelle frontiĂšre de W et on note â(W) lâensemble des arĂȘtes de G partant d'un sommet de W et n'aboutissant pas Ă un sommet de W. G est un graphe expanseur dans le rapport Îł si, pour tout sous-ensemble de sommets W de cardinal |W| †n/2, on a |â(W)| â„ Îł |W|.
- Expansion
- si est un mineur de (c. Ă d. rĂ©sulte d'une sĂ©rie de contractions) alors est une expansion de . Une opĂ©ration d'expansion remplace un sommet par deux sommets connectĂ©s par une arĂȘte, et et sont connectĂ©s Ă tous les voisins de . Dans le cas d'un plongement d'un graphe dans , une expansion a une autre signification : il s'agit du rapport entre la taille des deux graphes, soit .
F
- Facteur
- un -facteur est un sous-graphe couvrant -régulier.
- Feuille
- sommet de degré 1 dans un arbre.
- Fini
- un graphe est fini si le nombre de ses arĂȘtes et de ses sommets est fini. Un graphe infini dont chaque sommet a un degrĂ© fini est dit localement fini.
- Force
- d'un graphe, lâanalogue de la duretĂ© pour les arĂȘtes.
- ForĂȘt
- graphe non-orientĂ© acyclique. Chaque composante connexe d'une forĂȘt forme un arbre.
- FrontiĂšre des arĂȘtes
- les arĂȘtes menant d'une partie d'un graphe au reste du graphe.
- FrontiÚre intérieure des sommets
- les sommets d'une partie d'un graphe reliées au reste du graphe.
- FrontiÚre extérieure des sommets
- les sommets du reste d'un graphe reliées à une partie du graphe.
G
H
- Hamiltonien
- un graphe est hamiltonien s'il a au moins un cycle passant par tous les sommets exactement une fois, et ce cycle est appelĂ© cycle hamiltonien. Un cycle hamiltonien est aussi un cycle Ă©lĂ©mentaire de mĂȘme ordre que le graphe.
- Homéomorphes (graphes)
- deux graphes G et H sont dits homĂ©omorphes si l'on peut arriver au mĂȘme graphe I en subdivisant certaines de leurs arĂȘtes (Ă ne pas confondre avec la notion d'homomorphisme).
- Hypergraphe
- gĂ©nĂ©ralise la notion de graphe en autorisant une arĂȘte Ă relier plus de deux sommets.
I
- Incidence
- la matrice d'incidence d'un graphe est la matrice de dimensions dans laquelle l'entrĂ©e vaut 1 si le sommet est une extrĂ©mitĂ© de l'arĂȘte , 2 si est une boucle sur et 0 sinon. Dans le cas orientĂ©, on a si sort de et 1 si elle y rentre.
- Indépendant
- deux sommets sont indépendants s'ils ne sont pas connectés, c'est-à -dire pas adjacents. Un ensemble de sommets est indépendant (ou stable) s'il n'y a pas deux de ses sommets adjacents.
- Indice chromatique (nombre chromatique des arĂȘtes)
- le nombre minimal de couleurs nĂ©cessaire pour colorer les arĂȘtes d'un graphe ne pas confondre avec le nombre chromatique (des sommets).
- Indice de Hosoya ou indice Z
- nombre de couplages d'un graphe.
- Induit
- un sous-graphe d'un graphe est dit induit lorsque, pour tout couple de sommets de , est connectĂ© Ă dans si et seulement si est connectĂ© Ă dans . Autre formulation de la condition : l'ensemble des arĂȘtes de correspond Ă l'ensemble des arĂȘtes de incidentes Ă deux sommets de .
- Infini
- contraire de fini.
- Intervalle
- un graphe d'intervalle est un graphe G tel que l'on puisse associer Ă chacun de ses sommets un intervalle sur l'ensemble des rĂ©els et tel que pour chaque sommet u et v de G il y a une arĂȘte entre u et v si et seulement si l'intersection entre leurs intervalles associĂ©s n'est pas nulle,
- Invariant
- propriété du graphe dépendant uniquement de sa structure (i.e. indépendante de son étiquetage). Par exemple, le degré moyen du graphe ou son spectre.
- Isolé
- sommet de degré 0, c'est-à -dire n'ayant pas de voisin.
- Isomorphisme
- un isomorphisme de graphes est un morphisme de graphes bijectif (ou inversible).
- Isomorphe
- deux graphes sont isomorphes s'il existe un isomorphisme de graphes de l'un vers l'autre. C'est-Ă -dire s'ils ont exactement la mĂȘme structure. Il suffit de remplacer les Ă©tiquettes des sommets pour qu'un graphe soit la copie conforme de l'autre.
- Isospectral
- voir cospectral.
- Isthme
- arĂȘte d'un graphe dont l'Ă©limination augmente le nombre de composantes connexes du graphe.
J
- Jumeau
- deux sommets sont jumeaux s'ils ont le mĂȘme voisinage. Des vrais jumeaux respectent en plus la contrainte d'ĂȘtre voisins l'un de l'autre, et si cette contrainte n'est pas respectĂ©e alors on parle de faux jumeaux. La notion de voisinage peut ĂȘtre gĂ©nĂ©ralisĂ©e[2] pour une distance supĂ©rieure Ă 1 : on dĂ©finit le voisinage de jusqu'Ă distance par , et deux jumeaux ont alors .
L
- Laplacienne
- une matrice laplacienne est une matrice oĂč est la matrice des degrĂ©s et la matrice d'adjacence ; on obtient sa forme normalisĂ©e par , oĂč dĂ©note la matrice identitĂ©. Est utilisĂ©e dans la thĂ©orie spectrale des graphes.
- Libre d'Ă©chelle
- un graphe est libre d'échelle si la distribution de ses degrés est proche d'une loi de puissance. Cette notion provient de la physique, et les divergences locales ou l'écart de la distribution par rapport à une loi de puissance ne sont pas spécifiés.
- Line graph
- le line graph d'un graphe est le graphe oĂč on inverse sommets et arĂȘtes, c'est-Ă -dire que deux sommets adjacents dans le line graph correspondent Ă deux arĂȘtes incidentes Ă un mĂȘme sommet dans G.
M
- Maille
- girth en anglais, longueur du plus court cycle. Si un graphe est acyclique, sa maille est considérée comme infinie. La maille paire (respectivement maille impaire) est la longueur du plus court cycle de longueur paire (respectivement impaire).
- Mineur
- un graphe est un mineur de s'il est isomorphe Ă un graphe pouvant ĂȘtre obtenu en contractant zĂ©ro ou plus arĂȘtes de .
- Morphisme
- application entre deux graphes qui respecte la structure de ces graphes.
- Moulin
- un graphe moulin est une somme de graphes complets se partageant un sommet central.
- Multigraphe
- graphe dotĂ© d'une ou plusieurs arĂȘtes multiples ou de boucles.
N
- NĆud
- sommet dans un rĂ©seau. Un nĆud interne est un sommet dans un arbre de degrĂ© supĂ©rieur Ă 1, c'est-Ă -dire n'Ă©tant pas une feuille.
- Nombre chromatique
- nombre minimum de couleurs pour colorer un graphe. Le nombre chromatique d'un graphe est noté .
- Noyau
- sous-ensemble de sommets Ă la fois stable et dominant.
- Nul
- un graphe nul est soit un graphe ne contenant aucun sommet, soit un graphe dont tous les sommets sont isolĂ©s (i.e. sans arĂȘtes ni arcs).
O
- Ordre
- nombre de sommets du graphe.
- Orienté
- un graphe est orientĂ© si les arĂȘtes ont un sens, par exemple indique qu'il y a un arc de Ă . Un graphe est non orientĂ© si ses arĂȘtes n'ont pas de sens : indique qu'il y a une arĂȘte entre et .
- Outer-planar
- voir planaire extérieur.
P
- Parfait
- un graphe est parfait si le nombre chromatique de chacun de ses sous-graphes induits est Ă©gal Ă la taille de la clique maximale de .
- Partiel
- Un graphe est un graphe partiel de si . Un sous-graphe partiel de est un graphe , avec et .
- Partition
- séparation des sommets du graphe en des ensembles de sommets disjoints deux à deux et non vides dont l'union permet de retrouver tous les sommets. Formellement, une partition d'un graphe en parties sépare l'ensemble des sommets en un ensemble qui vérifie les trois propriétés suivantes : et ; ; et .
- Petit monde
- un graphe a le phénomÚne du petit-monde si son coefficient de clustering est élevé et la distance moyenne entre deux sommets faible. Cette notion provient de la physique, et il n'y a pas de définition exacte quant à ce qui est élevé et ce qui est faible ; on considÚre la distance moyenne comme faible tant qu'elle n'excÚde pas le logarithme du nombre de sommets.
- Planaire
- un graphe est planaire si on peut le dessiner dans un plan sans croiser deux arĂȘtes. Un graphe est planaire s'il ne contient pas et comme mineurs.
- Planaire extérieur
- dans un graphe planaire, on considĂšre les rĂ©gions (ou faces) entourĂ©es par des arĂȘtes comme internes. L'ensemble du graphe est donc entourĂ© par une rĂ©gion externe. Si tous les sommets sont sur la face externe, alors le graphe est planaire extĂ©rieur.
- Plongement
- soient deux graphes et , un plongement est une fonction injective de dans tel que chaque arĂȘte de corresponde Ă un chemin disjoint de . Un plongement permet de dire qu'on peut utiliser un graphe pour simuler les capacitĂ©s de l'autre en termes de connexion : s'il y a une arĂȘte (i.e. un chemin dĂ©diĂ©) entre deux sommets, alors on la retrouvera dans le graphe simulant sous la forme d'un chemin dĂ©diĂ© (mais pouvant ĂȘtre plus long).
- Point d'articulation
- dans un graphe connexe, un sommet est dit dâarticulation si le sous-graphe obtenu en le supprimant a plus de composantes connexes .
- PolynÎme caractéristique
- le polynÎme de la matrice d'adjacence d'un graphe G est son polynÎme caractéristique, et on le note .
Exemple de graphe pondéré
- Pondéré
- un graphe pondĂ©rĂ© est un graphe auquel on adjoint une fonction de valuation. Un graphe peut ĂȘtre pondĂ©rĂ©/valuĂ© sur ses sommets comme sur ses arĂȘtes. On note (resp. ) le poids d'un sommet (resp. ) et (resp. ) le poids d'une arĂȘte (resp. ).
- Pont
- dans un graphe connexe, un pont est une arĂȘte dont la suppression dĂ©connecte le graphe.
- Produit
- le produit de deux graphes et (remplissant éventuellement certaines conditions) est un troisiÚme graphe obtenu à partir de et de en appliquant certaines rÚgles. On distingue le produit cartésien, le produit tensoriel, le produit lexicographique (en), le produit fort, le produit conormal, le produit modulaire (en), le produit enraciné (en) et le produit zig-zag de graphes.
- Promenade
- également appelé parcours ; voir chemin (considéré en général comme non-élémentaire). Une promenade close (ou parcours fermé) est un circuit.
- Puits
- dans un problÚme de flot, sommet consommant le flot. Généralement de degré sortant nul, mais pas nécessairement.
R
- Racine
- sommet particulier d'une arborescence Ă partir duquel il existe un chemin unique vers tous les autres sommets du graphe.
- Rayon
- excentricité minimale des sommets, notée .
- Rayon[3]
- dans un graphe infini, une chaĂźne simple infinie ; une telle chaĂźne existe si le graphe est connexe et localement fini.
- RĂ©gulier
- un graphe est -régulier si chacun de ses sommets est de degré .
- Relation de DjokovĂŹc-Winkler
- deux arĂȘtes et sont en relation de DjokovĂŹc-Winkler, et on le note si on a l'inĂ©galitĂ© . Cette relation est rĂ©flexive et symĂ©trique[4].
- Réseau de flot ou réseau de transport
- un graphe valué aux arcs modélisant un problÚme de transport.
- Roncier
- Un roncier est une collection de sous-graphes connexes oĂč deux sous-graphes quelconques ont un sommet en commun ou chacun comprend une extrĂ©mitĂ© d'une arĂȘte. L'ordre d'un roncier est la plus petite taille d'un ensemble de sommets qui a une intersection non vide avec tous les sous-graphes. La largeur d'arbre d'un graphe est l'ordre maximum de l'un de ses ronciers.
S
- Scindé
- un graphe est scindĂ© (split graph en anglais) si ses sommets peuvent ĂȘtre partitionnĂ©s en une clique et un stable.
- Seuil
- Un graphe est Ă seuil s'il existe un nombre rĂ©el et, pour chaque sommet , un poids (nombre rĂ©el) tel que pour deux sommets la paire est une arĂȘte si et seulement si .
- SĂ©parateur
- C'est un sous-ensemble de l'ensemble des sommets d'un graphe tel que le sous-graphe induit par nâest pas connexe.
- Simple
- Ă©galement appelĂ© Schlicht[5]), graphe fini, non orientĂ©, sans boucles ni arĂȘtes multiples.
- Sommet
- un graphe est composĂ© de sommets reliĂ©s par des arcs ou des arĂȘtes. Ăgalement appelĂ© nĆud ou plus rarement point.
- Sommet-transitif
- un graphe est sommet-transitif si son groupe d'automorphismes agit transitivement sur l'ensemble de ses sommets. Autre formulation de la condition : pour tout couple de sommets, au moins un automorphisme envoie la premiĂšre composante sur la seconde. Tous les sommets jouent exactement le mĂȘme rĂŽle Ă l'intĂ©rieur du graphe. Un graphe sommet-transitif est ainsi nĂ©cessairement rĂ©gulier.
- Source
- dans un problÚme de flot, sommet produisant le flot. Un tel sommet est généralement de degré entrant nul, mais pas nécessairement.
- Split
- un graphe est split s'il y a une partition de V en deux sous-ensembles S et C tel que S est un ensemble de G et C est une clique de G. On note .
- Sous-graphe
- graphe contenu dans un autre graphe. Formellement, avec des notations intuitives, un graphe est un sous-graphe de si et . Il est induit si .
- Spanner
- sous-graphe couvrant dont on essaye de minimiser le nombre d'arĂȘtes (i.e. la densitĂ©) tout en conservant des bonnes propriĂ©tĂ©s de distance. Dans un spanner additif (respectivement multiplicatif), la distance entre deux sommets peut ĂȘtre augmentĂ©e (respectivement multipliĂ©e) jusqu'Ă un certain facteur appelĂ© le dĂ©lai (respectivement la dilatation).
- Spectre
- ensemble des valeurs propres d'une matrice reprĂ©sentant le graphe. La matrice peut ĂȘtre de Laplace ou d'adjacence. Les relations entre le spectre du graphe et ses propriĂ©tĂ©s font l'objet de la thĂ©orie spectrale des graphes.
- Stable
- un ensemble stable est un ensemble de sommets 2 à 2 indépendants. Synonyme : ensemble indépendant.
- Subdivision
- la subdivision d'un graphe consiste Ă ajouter des sommets sur les arĂȘtes, c'est-Ă -dire Ă remplacer des arĂȘtes par des chemins.
- Subdivision barycentrique
- la subdivision d'un graphe oĂč chaque arĂȘte de a Ă©tĂ© remplacĂ©e par un chemin de longueur deux par insertion d'un sommet dans chaque arĂȘte.
- Symétrique
- un graphe est symĂ©trique s'il est Ă la fois arĂȘte-transitif et sommet-transitif. Cela revient Ă vĂ©rifier que toutes ses arĂȘtes et tous ses sommets sont indistinguables en termes d'isomorphisme de graphe. Exemple : graphe de Petersen.
T
- Taille
- nombre d'arĂȘtes (ou d'arcs) du graphe.
- Technique spectrale
- technique faisant intervenir le spectre du graphe.
- Tournoi
- un graphe orientĂ© obtenu en orientant chaque arĂȘte d'un graphe complet.
- Transposé
- le transposĂ© d'un graphe orientĂ© est le mĂȘme graphe, mais dont les arĂȘtes ont Ă©tĂ© inversĂ©es.
- Transversal
- un transversal (ou couverture nodale, ou support) d'un graphe est un sous-ensemble de sommet T tel que toute arĂȘte du graphe est incidente Ă au-moins un sommet de T. Le complĂ©mentaire d'un transversal est un stable.
- Triangle
- cycle de longueur trois.
- Triangulé
- un graphe est triangulé s'il ne contient pas un cycle de longueur quatre sans corde comme mineur. Les arbres, et les graphes d'intervalles notamment, sont triangulés.
- Triconnexe
- un graphe non orienté est dit triconnexe si, en retirant deux quelconques de ses sommets, il reste connexe. Cela revient à dire que le graphe n'a pas de point d'articulation.
- Trivial
- un graphe est trivial s'il a un seul (graphe singleton) ou aucun sommet (graphe nul). On peut utiliser un graphe trivial pour commencer une preuve par récurrence, mais ils sont implicitement exclus des théorÚmes dont ils constitueraient parfois des contre-exemples inintéressants.
V
- Valuation
- fonction associant un poids Ă chaque arĂȘte et/ou sommet du graphe. On parle alors de graphe valuĂ©. Voir la dĂ©finition de graphe pondĂ©rĂ© plus haut dans cette page.
- Vecteur d'intersection
- séquence d'un graphe distance-régulier.
- Vide
- un graphe vide est un graphe sans arĂȘtes, voir graphe nul.
- Voisinage
- le voisinage d'un sommet v est l'ensemble des sommets adjacents Ă v (et Ă©ventuellement le sous-graphe induit)
Notes et références
- Gambette, Philippe, MĂ©thodes combinatoires de reconstruction de rĂ©seaux phylogĂ©nĂ©tiques (ThĂšse de doctorat), UniversitĂ© Montpellier II â Sciences et Techniques du Languedoc, , p. 16
- (en) IrĂšne Charon, Iiro Honkala, Olivier Hudry et Antoine Lobstein - Structural properties of twin-free graphs, The electronic journal of combinatorics, volume 14, 2007.
- « ray » en anglais.
- (en) D. DjokovÏc - Distance preserving subgraphs of hypercubes, Journal of Combin. Theory. Ser. B, numéro 14, pages 263-267, 1973.
- (en) Dragos M. Cvetkovic et Michael Doob et Horst Sachs - Spectra of Graphs, Heidelberg, Leipzig, 1994, (ISBN 3335004078).
Voir aussi
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent sâappliquer aux fichiers multimĂ©dias.