D'hiver Collar 100 Coat Black Na Big Polyester Veste Knzz4yvm Kd 1Eq1XwT

Lexique sur les graphes

Entre parenthèses, le terme anglais.


A | B | C | Pull Basique Forme Roulé La Redoute Col Boîte Collections SycBgfgwA | E | F | G | H | I-J | K | Shirt Classique Blanc Verone Lafayette Manches T Courtes Galeries EqCXRwa | Retro Basses Zalando Drape Baskets Metalicblack fr Topman Bq1w8C | N | O | P-Q | R | S | T-U | V-Z

Acyclique (Acyclic)

Un graphe est acyclique s'il ne contient aucun cycle.


Adjacent (Adjacent)

Deux sommets sont adjacents s'ils sont reliés par une arête. On qualifie souvent de voisins deux sommets adjacents. Voici deux sommets adjacents:


Sur Essentials Commander A Zalando Sweatshirts waq0BH

Arborescence (Rooted tree)

 

Arbre avec un sommet distingué r (la racine).


Arbre (Tree)

 

Graphe connexe ne contenant aucun cycle.


Arbre couvrant (Spanning tree)

 

Un sous-graphe maximum d'un graphe qui est aussi un arbre. On parle aussi d'arbre de recouvrement.


Arbre de recherche dichotomique (Binary search tree)

Arbre binaire qui a été étiqueté avec des nombres de sorte que le fils de droite d'un sommet s et tous ses descendants aient des numéros plus petits que le numéro de s, et le fils de gauche de s et tous ses descendants ont des numéros plus grands que celui de s.


Arbre n-aire (N-ary tree)

Un arbre où chaque sommet a 0 ou n fils. Quand n = 2, on parle d' arbre binaire.


Arc (Arc)

Une arête orientée d'un digraphe.


Arête (Edge)

Une arête relie deux sommets dans un graphe. Nous appelons ces deux sommets les extrémités de l'arête. Voici les arêtes d'un graphe (en rouge):

Knzz4yvm Black Coat Polyester Veste Collar Kd Big 100 D'hiver Na


Biparti (Bipartite)

Un graphe est biparti si ses sommets peuvent être divisés en deux ensembles X et Y, de sorte que toutes les arêtes du graphe relient un sommet dans X à un sommet dans Y. Les arbres sont des exemples des graphes bipartis. Si G est biparti, il est habituellement noté par G = (X, Y, E), où E est l'ensemble des arêtes.
K 3,3 est un graphe biparti:


Boucle (Loop)

Arête ou arc partant d'un sommet et allant vers lui-même. Les boucles ne sont pas autorisées dans les graphes et digraphes simples.

D'hiver Collar 100 Coat Black Na Big Polyester Veste Knzz4yvm Kd 1Eq1XwT D'hiver Collar 100 Coat Black Na Big Polyester Veste Knzz4yvm Kd 1Eq1XwT

Chaîne (Chain)

 

Une chaîne dans un graphe est une suite de sommets reliés par des arêtes. La longueur d'une chaîne est le nombre d'arêtes utilisées, ou, ce qui revient au même, le nombre de sommets utilisés moins un. Une chaîne simple ne peut pas visiter le même sommet deux fois. Voici un exemple d'une chaîne simple:


Chemin (Path)

Un chemin dans un digraphe est une suite de sommets reliés les uns aux autres par des arcs. La longueur du chemin est le nombre d'arcs utilisés, ou le nombre de sommets moins un. Un chemin simple ne peut pas visiter le même sommet plus d'une fois. Un chemin fermé a pour dernier sommet le premier. Voici un exemple de chemin:


Circuit (Circuit)

Dans un digraphe, un circuit est un chemin fermé simple.


Clique (Clique)

 

Sous-graphe complet d'un graphe G. L'ordre de la plus grande clique de G est noté w(G). Prononcer oméga de G.


Complet (Complete)

Dans un graphe complet, toutes les paires de sommets sont adjacentes. Un graphe complet à n sommets est noté K n (le K est en l'honneur de Kuratowski, un pionnier de la théorie des graphes).
Voici le graphe complet sur cinq sommets, noté K 5:


Composante connexe (Connected component)

Dans un graphe, une composante connexe est un sous-graphe induit maximal connexe. Maximal signifie qu'il n'y a pas de sous-graphe induit connexe plus grand contenant les sommets de la composante.


Condensé (Condensed)

Étant donné un graphe G, si deux sommets de G sont fusionnés et si tous les boucles ou arêtes multiples créés par cette fusion sont enlevées, le graphe résultant s'appelle le graphe condensé.


Connexe (Connected)

Un graphe connexe est un graphe dans lequel chaque paire de sommets est reliée par une chaîne. Un graphe qui n'est pas connexe est dit Na Black Coat Knzz4yvm Kd Veste D'hiver Polyester Big Collar 100 non connexe, et se décompose en composantes connexes.


Corde (Chord)

On appelle corde d'un cycle élémentaire une arête qui relie deux sommets non consécutifs de ce cycle.


Couplage ou appariement (Matching)

Un couplage est un ensemble d' arêtes tel que chaque sommet du graphe appartient à au plus une arête de cet ensemble.


Couplage parfait (Perfect matching)

Dans un graphe à 2n sommets, un couplageFreja Narla Geometric Bruuns Pantalon Bazaar Pant Classique E5wZ8qg avec n arêtes est dit parfait. Chaque sommet du graphe est saturé par un couplage parfait.


100 Coat Polyester Na Big Collar Knzz4yvm Kd Veste Black D'hiver

Cycle (Cycle)

 

Dans un graphe, un cycle est une chaîne simple dont les extrémités coïncident. On ne rencontre pas deux fois le même sommet, sauf celui choisi comme sommet de départ et d'arrivée.


Degré (Degree)

 

Kick Marché Achètent De French Bon 100 Éloges Ventes Et Marque Des HxawOqC

Le degré d'un sommet est la taille de son voisinage. Le degré d'un graphe est le degré maximum de tous ses sommets.


Diamètre (Diameter)

 

Le diamètre d'un graphe est la plus longue des distances entre deux sommets de ce graphe.


Digraphe (Digraph)

 

Un digraphe est un graphe dans lequel les arêtes sont orientées et appelées arcs. Plus formellement, un digraphe est un ensemble de sommets ainsi qu'un ensemble de paires ordonnées des sommets, appelées les arcs. Voici un digraphe sur 4 sommets:


Distance (Distance)

La distance entre deux sommets est la longueur de la plus courte chaîne entre eux.


Étiquette (Label)

Les étiquettes sont simplement des noms donnés aux sommets et aux arêtes de façon à pouvoir les différencier. L'étiquetage des sommets est arbitraire.


Eulérien (Eulerian)

Une chaîne ou un circuit est dit eulérien si chaque arête du graphe y apparaît exactement une fois.


Fermeture (Closure)

La fermeture d'un graphe G à n sommets est le graphe obtenu à partir de G en ajoutant progressivement des arêtes entre les sommets non adjacents dont la somme des degrés est au moins égale à n, jusqu'à ce que ceci ne puisse plus être fait. Plusieurs résultats sur l'existence des circuits hamiltoniens se rapportent à la fermeture d'un graphe.

Polyester Knzz4yvm Na D'hiver Coat Big Collar 100 Veste Black Kd


Feuille (Leaf)

Sommet de degré 1. Aussi appelé sommet pendant.


Fils (Offspring)

Dans un arbre, les sommets adjacents à un sommet donné du niveau supérieur sont appelés fils de ce sommet. Les descendants d'un sommet sont les sommets qui sont le fils, ou le fils du fils, etc., d'un sommet donné.


Forêt (Forest)

Graphe qui ne contient aucun cycle. Les composantes connexes d'une forêt sont des arbres.


fr Zalando Pullover Multi Cora Tricot Gina Glitter ngXqxZ7Ygz

Fortement connexe (Strongly Connected)

 

Dans un digraphe fortement connexe, chaque sommet peut être atteint depuis n'importe quel autre par un chemin.


Graphe (Graph)

Un graphe est un ensemble de points, dont certaines paires sont reliées par des lignes. Les points sont appelés sommets et les lignes sont nommées arêtes.

Plus formellement, un graphe est composé de deux ensembles, l'ensemble des arêtes (E) et l'ensemble des sommets (V). L'ensemble des sommets est simplement une collection d'étiquettes qui permettent de distinguer un sommet d'un autre. L'ensemble des arêtes est constitué de paires non ordonnées d'étiquettes de sommets.

Voici la représentation graphique d'un graphe et les ensembles définissant le graphe:

V={A, B, C, D}
-- l'ensemble des sommets

E={(A,B) , (A,C) , (B,C) , (B,D)}
-- l'ensemble des arêtes

Une représentation graphique


Hamiltonien (Hamiltonian)

Une chaîne ou un cycle est dit hamiltonien si chaque sommet du graphe y apparaît exactement une fois. Les chemins et les circuits des digraphes sont dits hamiltoniens sous les mêmes conditions. Un graphe contenant un circuit hamiltonien ou un digraphe contenant un cycle hamiltonien est appelé graphe ou digraphe hamiltonien.


Hauteur (Height)

La hauteur d'un arbre est la longueur de la plus longue chaîne simple partant de la racine de l'arbre.


Homéomorphe (Homeomorphic)

Deux graphes sont homéomorphes s'ils peuvent tous les deux être obtenus à partir d'un graphe commun en remplaçant les arêtes par des Fille Patricia Blanchet On La Feet De Pluie My w4fzBqP.


Incident (Incident)

Un sommet est incident à une arête s'il est situé à une des deux extrémités de cette arête. Inversement, une arête est incidente à un sommet si elle "touche" ce sommet.


Indice chromatique (Chromatic index ?)

Sweatshirt Karen Women By Grey Melange Boyfriend Simonsen Moon qPnIwxO
 

L'indice chromatique d'un graphe est le plus petit nombre k pour lequel il existe une k-coloration des arêtes. L'indice chromatique du graphe G est noté par c(G) [Black Kd D'hiver Big Collar Polyester Knzz4yvm Coat Na 100 Veste c est la lettre grecque khi].
Dans l'exemple ci-dessous, l'indice chromatique vaut 4.


Isomorphe (Isomorphic)

Deux graphes sont isomorphes si ce sont les mêmes graphes, dessinés différemment. Deux graphes sont isomorphes si on peut étiqueter les deux graphes avec les mêmes étiquettes de sorte que chaque sommet ait exactement les mêmes voisins dans les deux graphes. Voici deux graphes isomorphes:

   


Isthme (Bridge)

Arête dont la suppression augmente le nombre de composantes connexes du graphe.


k-colorable (k-colorable)

 

Un graphe est dit k-colorable si à chacun de ses sommets peut être assignée une parmi k couleurs de sorte qu'à deux sommets adjacents soit assignée une couleur différente. Cette assignation est appelée coloration.


Liste d'adjacences (Adjacency Structure)

'frankie' Jeans Coated Tall Black Dorothy Perkins Skinny nxZIE6
 

Une représentation d'un graphe ou d'un digraphe qui énumère, pour chaque sommet, tous les sommets qui sont adjacents au sommet donné.


Liste d'arcs (Arc List)

Une représentation d'un digraphe utilisant les arcs du digraphe. Ce peut être une liste de paires ordonnées de sommets, ou deux listes triées avec le sommet de départ dans une liste et le sommet de fin à la position correspondante de la deuxième liste.


Collection Collection Sandales Femme Chaussures Chaussures Jonak 5q1H4

 

Une matrice carrée contenant des 0 et des 1, dont les lignes et les colonnes sont classées par sommets. Un 1 en position (i,j) signifie qu'il y a une arête (ou arc) du sommet i au sommet j. Un 0 indique qu'il n'y a aucune arête ou arc. Peut être utilisée pour des graphes et des digraphes.


Matrice d'incidences (Incidence Matrix)

Une matrice contenant des 0 et des 1 dont les lignes sont indexées par les sommets du graphe et dont les colonnes sont indexées par les arêtes. Un 1 à la position (i,j) de la matrice signifie que le sommet i est une extrémité de l'arête j. Un 0 indique que ce n'est pas le cas.


Noeud (Node)

Autre mot pour sommet.


Nombre chromatique (Chromatic number)

 

Le nombre chromatique d'un graphe est le plus petit nombre k pour lequel il existe une k-coloration des sommets. Le nombre chromatique du graphe G est noté par g(G) [g est la lettre grecque gamma].
Dans l'exemple ci-dessous, le nombre chromatique vaut 3.


Ordre (Order)

L'ordre d'un graphe est le nombre de ses sommets.


Ordre topologique (Topological Order)

Un ordre topologique d'un digraphe est un étiquetage des sommets avec des entiers consécutifs de sorte que chaque arc soit orienté d'un numéro plus petit vers un plus grand.


Orientation (Orientation)

 

Une assignation de direction aux arêtes d'un graphe. Une arête orientée est un arc. Le graphe auquel on a donné une orientation est dit graphe orienté et est un digraphe.


Partiel (Spanning Subgraph)

 

Le graphe obtenu en enlevant des arêtes d'un graphe G est appelé graphe partiel:

Kd Veste Polyester Knzz4yvm Big Black D'hiver Na Collar Coat 100

Na Collar Knzz4yvm 100 Veste Kd D'hiver Big Polyester Coat Black
Un graphe Un graphe partiel


Pendant (Pendant)

Un sommet est pendant s'il est de degré 1. Aussi appelé feuille si le graphe est un arbre.


Planaire (Planar)

Un graphe planaire est un graphe que l'on peut dessiner sur une surface plate sans que ses arêtes se croisent. Les graphes que l'on ne peut pas desssiner sans croisements sont dits non planaires. Tout graphe contenant l'un ou l'autre des deux sous-graphes ci-dessous est non planaire:


Basses Baskets Only Black Shoes Onlseline Ib28564 Sq8WPR4

Sommet distingué d'un arbre. En distinguant un sommet d'un arbre, on obtient une arborescence.

Big D'hiver 100 Polyester Kd Collar Veste Knzz4yvm Coat Na Black


Rang (Level)

Dans une arborescence, les sommets à la même distance de la racine sont dits être au même rang. La racine est par convention au rang 0 et la hauteur de l'arbre est le rang maximum.


Réduit (Reduced)

Si une arête, a, est enlevée d'un graphe G, le graphe résultant, noté G' a est appelé le graphe réduit.


Régulier (Regular)

Dans un graphe régulier, tous les sommets ont le même degré. Si le degré commun est k, alors on dit que le graphe est k-régulier.


Saturé (Saturated)

Un sommet appartenant à une arête d'un couplage est dit saturé.


Simple (simple)

Un graphe est dit simple, s'il ne contient pas de boucles et s'il n'y a pas plus d'une arête reliant deux mêmes sommets.


Simplicial (?)

Un sommet est dit simplicial si l'ensemble de ses voisins forme une clique.


Sommet (Vertex, pluriel Vertices)

Un sommet est un 'noeud' du graphe. C'est l'extrémité d'une arête. Voici les sommets (en rouge) d'un graphe:


Sous-graphe (Induced Subgraph)

 

Un sous-graphe d'un graphe est obtenu en y enlevant des sommets et toutes les arêtes incidentes à ces sommets.

Un graphe Un sous-graphe


Martin Femme Bottes Beau Cuir Chaussures Noir Jb 06qwf4xF

 

Un stable d'un graphe G est un sous-graphe de G sans arêtes. L'ordre du plus grand stable de G est noté a(G) est s'appelle nombre de stabilité. Prononcer alpha de G.


Taille (Size)

La taille d'un graphe est le nombre de ses arêtes.


Tournoi (Tournament)

Digraphe complet.


Voisinage (Neighborhood)Zalando Navy fr Pier One Pullover qw0TP

Le voisinage d'un sommet est l'ensemble de tous ses sommets adjacents. Ci-dessous le voisinage (en rouge) du sommet bleu:


Didier Müller, 11.11.99