Lexique de la théorie des graphes
Pour un article plus général, voir 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 i{displaystyle i}
-ème élément correspond à la liste des voisins du i{displaystyle i}
Adjacence- une matrice d'adjacence est une matrice carrée usuellement notée A{displaystyle A}
, de dimensions |V|×|V|{displaystyle |V|times |V|}
, dont chaque élément Aij{displaystyle A_{ij}}
est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices i{displaystyle i}
(pour un graphe simple non pondéré, Aij∈{0,1}{displaystyle A_{ij}in {0,1}}
). 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 à n{displaystyle n}
sommets et n−1{displaystyle n-1}
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 e1=u1v1,e2=u2v2∈G{displaystyle e_{1}=u_{1}v_{1},e_{2}=u_{2}v_{2}in G}
, il existe deux automorphismes (fV,fE):G→G{displaystyle (f_{V},f_{E}):Grightarrow G}
et (gV,gE):G→G{displaystyle (g_{V},g_{E}):Grightarrow G}
tels que fE(e1)=e2{displaystyle f_{E}(e_{1})=e_{2}}
, gE(e1)=e2{displaystyle g_{E}(e_{1})=e_{2}}
, et fV(u1)=u2{displaystyle f_{V}(u_{1})=u_{2}}
, fV(v1)=v2{displaystyle f_{V}(v_{1})=v_{2}}
, gV(u1)=v2{displaystyle g_{V}(u_{1})=v_{2}}
, gV(v1)=u2{displaystyle g_{V}(v_{1})=u_{2}}
.
- Arête
- connexion entre deux sommets A{displaystyle A}
. 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 (A,B){displaystyle (A,B)}
, c'est-à-dire de A{displaystyle A}
, c'est-à-dire de B{displaystyle B}
- 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 U{displaystyle U}
et V{displaystyle V}
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 U{displaystyle U}
le graphe biparti complet tel que |U|=m{displaystyle |U|=m}
et |V|=n{displaystyle |V|=n}
.
Birégulier- un graphe est dit birégulier s'il est biparti et si chacune de ses parties U{displaystyle U}
-régulier si deg(U)=a{displaystyle deg(U)=a}
et deg(V)=b{displaystyle deg(V)=b}
.
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 |
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 non 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 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 soit un arc du graphe ; la suite (un moins en longueur) 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).
- Circonférence
- longueur du plus grand cycle.
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) G¯{displaystyle {bar {G}}}
d'un graphe simple G=(V,E){displaystyle G=(V,E)}
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 G¯=(V,[V]2∖E){displaystyle {bar {G}}=(V,[V]^{2}backslash E)}
.
Complet- dans un graphe complet chaque sommet est relié à tous les autres. On note Kn{displaystyle K_{n}}
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 G{displaystyle G}
contient H{displaystyle H}
si H{displaystyle H}
Contraction- supprime une arête d'un graphe en fusionnant ses deux extrémités. Autrement dit, la contraction G/e{displaystyle G/e}
d'une arête exy{displaystyle e_{xy}}
à un sommet x{displaystyle x}
rend le sommet x{displaystyle x}
.
- Corde
- arête reliant deux sommets non-adjacents d'un cycle.
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.
- 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.
- Couvrant
- un sous-graphe H{displaystyle H}
).
- 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- chaine dont les sommets de départ et de fin sont les mêmes. Autrement dit, soit un chemin dont les arêtes sont E={s0s1,...,sk−2sk−1}{displaystyle E={s_{0}s_{1},...,s_{k-2}s_{k-1}}}
: le cycle est alors défini par E∪{sk−1s0}{displaystyle Ecup {s_{k-1}s_{0}}}
. 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 G=(V,E){displaystyle G=(V,E)}
, où P{displaystyle P}
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é d(s){displaystyle d(s)}
du sommet s{displaystyle s}
est le nombre d'arêtes de s{displaystyle s}
est le nombre d'arcs vers s{displaystyle s}
est le nombre d'arcs sortant de s{displaystyle s}
, et le degré minimal δ(G){displaystyle delta (G)}
. Dans le cas pondéré, le degré d'un sommet est la somme du poids des arêtes incidentes à ce sommet.
Degrés (matrice)- la matrice des degrés d'un graphe G{displaystyle G}
et ∀i,j,i≠j,Dij=0{displaystyle forall i,j,ineq j,D_{ij}=0}
.
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 G=(V,E){displaystyle G=(V,E)}
.
Diamètre- excentricité maximale des sommets, notée D{displaystyle D}
.
- Dilatation
- dans un plongement où f{displaystyle f}
associe des sommets d'un graphe G{displaystyle G}
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 S{displaystyle S}
de G{displaystyle G}
- Distance
- la distance dG(x,y){displaystyle d_{G}(x,y)}
entre x{displaystyle x}
- 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 u,v∈V{displaystyle u,vin V}
, le nombre de sommets voisins de u{displaystyle u}
à distance i{displaystyle i}
à distance j{displaystyle j}
et de la distance d(u,v){displaystyle d(u,v)}
entre u{displaystyle u}
tels que c0=0{displaystyle c_{0}=0}
et ∀i≥1,ci=|N(v)∩Ni−1(u)|,bi=|N(v)∩Ni+1(u)|{displaystyle forall igeq 1,c_{i}=|N(v)cap N_{i-1}(u)|,b_{i}=|N(v)cap N_{i+1}(u)|}
Dominant (ou absorbant)- un ensemble de sommet est dominant si tout sommet en fait partie ou est voisin d'un sommet en faisant partie.
E |
- Espace
- soit un graphe G=(V,E){displaystyle G=(V,E)}
avec comme base {v1,...,vn}{displaystyle {v_{1},...,v_{n}}}
, soit un espace de dimension n{displaystyle n}
, soit un espace de dimension m{displaystyle m}
. Le principe du 0 est 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és 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 H{displaystyle H}
connectés par une arête, et s1{displaystyle s_{1}}
et s2{displaystyle s_{2}}
sont connectés à tous les voisins de s{displaystyle s}
dans G2=(V2,E2){displaystyle G_{2}=(V_{2},E_{2})}
, une expansion a une autre signification : il s'agit du rapport entre la taille des deux graphes, soit |V2||V1|{displaystyle {frac {|V_{2}|}{|V_{1}|}}}
.
F |
- Facteur
- un k{displaystyle k}
-facteur est un sous-graphe couvrant k{displaystyle k}
- 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.
- 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 |
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 G=(V,E){displaystyle G=(V,E)}
dans laquelle l'entrée bij{displaystyle b_{ij}}
vaut 1 si le sommet vi{displaystyle v_{i}}
est une extrémité de l'arête xj{displaystyle x_{j}}
, 2 si xj{displaystyle x_{j}}
si xj{displaystyle x_{j}}
- 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.
- Induit
- un sous-graphe H{displaystyle H}
de sommets de H{displaystyle H}
- 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 s∈V{displaystyle sin V}
jusqu'à distance r{displaystyle r}
par Nr={u∈V|d(u,s)≤r}{displaystyle N_{r}={uin V|d(u,s)leq r}}
, et deux jumeaux s1,s2∈V{displaystyle s_{1},s_{2}in V}
ont alors Ns1=Ns2{displaystyle N_{s_{1}}=N_{s_{2}}}
.
K |
L |
Laplacienne- une matrice laplacienne est une matrice L=D−A{displaystyle L=D-A}
où D{displaystyle D}
par L′=D−1/2LD−1/2=I−D−1/2AD−1/2{displaystyle L'=D^{-1/2}LD^{-1/2}=I-D^{-1/2}AD^{-1/2}}
, où I{displaystyle I}
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 G{displaystyle G}
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 H{displaystyle H}
Morphisme- application entre deux graphes qui respecte la structure de ces graphes.
- 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 G{displaystyle G}
.
- 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 euv{displaystyle e_{uv}}
indique qu'il y a un arc de u{displaystyle u}
- Outer-planar
- voir planaire extérieur.
P |
Parfait- un graphe est parfait si le nombre chromatique de chacun de ses sous-graphes induits H{displaystyle H}
- Partiel
- Un graphe (V,F){displaystyle (V,F)}
est un graphe partiel de (V,E){displaystyle (V,E)}
si F⊆E{displaystyle Fsubseteq E}
. Un sous-graphe partiel de (V,E){displaystyle (V,E)}
, avec W⊆V{displaystyle Wsubseteq V}
et F⊆E{displaystyle Fsubseteq E}
est la restriction de E{displaystyle E}
à W{displaystyle W}
: (x,y)∈F{displaystyle (x,y)in F}
si et seulement si (x,y)∈E{displaystyle (x,y)in E}
et x,y∈F{displaystyle x,yin F}
.
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 G{displaystyle G}
qui vérifie les trois propriétés suivantes : ∀Vi∈Pk,Vi≠∅{displaystyle forall V_{i}in P_{k},V_{i}neq emptyset }
et Vi⊂V{displaystyle V_{i}subset V}
; ∪i=1..kVi=V{displaystyle cup _{i=1..k}V_{i}=V}
; et ∀(Vi,Vj)∈Pk2,i≠j⇒Vi∩Vj=∅{displaystyle forall (V_{i},V_{j})in P_{k}^{2},ineq jRightarrow V_{i}cap V_{j}=emptyset }
.
- 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 K5{displaystyle K_{5}}
et K3,3{displaystyle K_{3,3}}
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 G1=(V1,E1){displaystyle G_{1}=(V_{1},E_{1})}
dans V1{displaystyle V_{1}}
tel que chaque arête de V2{displaystyle V_{2}}
. 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 n’est pas connexe.
Polynôme caractéristique- le polynôme |λI−A|{displaystyle |lambda I-A|}
de la matrice d'adjacence A{displaystyle A}
.
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 p(v){displaystyle p(v)}
(resp. p(i){displaystyle p(i)}
) le poids d'un sommet v{displaystyle v}
(resp. p(i,j){displaystyle p(i,j)}
) le poids d'une arête (v,v′){displaystyle (v,v')}
(resp. (i,j){displaystyle (i,j)}
).
Pont- dans un graphe connexe, un pont est une arête dont la suppression déconnecte le graphe.
- Produit
- le produit de deux graphes G{displaystyle G}
- 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.
Q |
R |
Rayon- excentricité minimale des sommets, notée R{displaystyle R}
.
Régulier- un graphe est k{displaystyle k}
- Relation de Djokovìc-Winkler
- deux arêtes exy{displaystyle e_{xy}}
si on a l'inégalité dG(x,u)+dG(y,v)≠dG(x,v)+dG(y,u){displaystyle d_{G}(x,u)+d_{G}(y,v)neq d_{G}(x,v)+d_{G}(y,u)}
. Cette relation est réflexive et symétrique[3].
Réseau de flot ou réseau de transport- un graphe valué aux arcs modélisant un problème de transport.
S |
Séparateur- C'est un sous-ensemble X{displaystyle X}
de l'ensemble V{displaystyle V}
n’est pas connexe.
Simple- également appelé Schlicht[4]), 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 G=(V,E){displaystyle G=(V,E)}
.
Sous-graphe- graphe contenu dans un autre graphe. Formellement, avec des notations intuitives, un graphe H=(VH,EH){displaystyle H=(V_{H},E_{H})}
est un sous-graphe de G=(VG,EG){displaystyle G=(V_{G},E_{G})}
si VH⊂VG{displaystyle V_{H}subset V_{G}}
et EH⊂EG{displaystyle E_{H}subset E_{G}}
.
- 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 G{displaystyle G}
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 dans 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.
- 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.
U |
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 {b0,b1,...bD,c1,c2,...,cD}{displaystyle {b_{0},b_{1},...b_{D},c_{1},c_{2},...,c_{D}}}
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)
W |
X |
Y |
Z |
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, 2010, 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.
(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 |
.mw-parser-output .autres-projets ul{margin:0;padding:0}.mw-parser-output .autres-projets li{list-style-type:none;list-style-image:none;margin:0.2em 0;text-indent:0;padding-left:24px;min-height:20px;text-align:left}.mw-parser-output .autres-projets .titre{text-align:center;margin:0.2em 0}.mw-parser-output .autres-projets li a{font-style:italic}
Portail des mathématiques 
Portail de l'informatique théorique
