AccueilđŸ‡«đŸ‡·Chercher

Lexique de la théorie des graphes

Sommaire : Haut - A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

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

Graphe
structure composĂ©e d'abstractions mathĂ©matiques appelĂ©es objets (ou sommets ou nƓuds ou points) dans laquelle certaines paires d'objets sont en relation par des arĂȘtes (ou liens ou lignes).
Grille
graphe en forme de grille

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

  1. 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
  2. (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.
  3. « ray Â» en anglais.
  4. (en) D. DjokovÏc - Distance preserving subgraphs of hypercubes, Journal of Combin. Theory. Ser. B, numéro 14, pages 263-267, 1973.
  5. (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.