Théorie des graphes
La théorie des graphes est l'étude des structures mathématiques utilisées pour modéliser des relations par paires entre des objets. Un graphe est constitué de sommets qui sont reliés par des arêtes.
Un graphe G est constitué de deux ensembles V et E où
- V est un ensemble fini mais non vide de sommets ;
- E est un ensemble d’arêtes.
Une arête est un ensemble de deux sommets appartenant à V.
Vocabulaire
Les sommets sont appelés aussi des nœuds. En anglais ils sont appelés nodes points ou vertices (sing. vertex).
Les arêtes sont appelés aussi des arcs. En anglais ils sont appelés links, lines ou edges.
V = [A, B, C, D, E, F, G, H, I, J]
E = [{A, B}, {A, C}, {B, C}, {C, D}, {B, E}, {D, F}, {H, I}, {H, J}, {I, J}]
Notation :
L’arête {A, B} pourra être notée A—B ou B—A.
Définitions :
Soit un graphe G = {V , E}.
- L'ordre (order) d'un graphe est le nombre de sommets |V| ;
- La taille (size) d'un graphe est le nombre d'arêtes |E| ;
- deux sommets A, B ∈ V (qui appartiennent à l'ensemble des sommets V) sont adjacents s’ils sont reliés par une arête. Par exemple si A—B ∈ E (l'arête A-B appartient à l'ensemble E des arêtes) ;
- une arête A—B est incidente aux sommets A et B ;
- le degré (degree or valency) d’un sommet est le nombre d’arêtes qui lui sont incidentes.
- le degré d'un graphe ou degré total est la somme des degrés de ses sommets.
Dans notre exemple :
- A et B sont adjacents ;
- l’arête B—C est incidente à B et à C ;
- le degré de A est 2 ;
- le degré de B est 3 ;
- le degré de G est 0 ;
- le degré de E est 1 ;
- L'ordre du graphe est 10.
Le degré total d'un graphe non orienté est égal au double du nombre total d'arêtes. Cette propriété s'appelle le lemme de la poignée de main.
Vide
Un graphe vide contient que des sommets et aucun arête.
Complet
Un graphe est dit complet quand tous les sommets sont adjacents de tous les autres.
Sous-graphes
Soit un graphe G = {V , E}.
Le graphe G' {V', E'} est un sous-graphe de G si les conditions suivantes sont réunies :
- V' ⊆ V et V ≠ ∅ (V' est inclus dans V et non nul) ;
- E' ⊆ E ;
- les sommets composant les arêtes de E' doivent appartenir à V'.
Multigraphes / multigraph
Une paire de sommets peut être connectée par plus d’une arête
Graphes orientés / directed graph, digraph
Un graphe est orienté si ses arêtes, appelées arcs (directed edges, directed links, directed lines, arrows or arcs) dans ce cas, ont un sens de parcours.
- Une arête partant du sommet A et allant au sommet B est dénotée A → B.
- Le degré entrant d’un sommet est le nombre d’arêtes arrivant à ce sommet.
- Le degré sortant d’un sommet est le nombre d’arêtes sortant de ce sommet
Graphes étiqueté
Un graphe est étiqueté si ses arêtes (ou ses arcs dans le cas d'un graphe orienté) sont affectés d'étiquettes (mots, lettres, symboles, nombres, …)
Graphes pondérés
Dans le cas où les étiquettes sont des nombres, le graphe est dit pondéré. Les étiquettes sont appelées les poids entre les sommets.
Le poids d'une chaîne est la somme des poids des arêtes constituant la chaîne.
De manière identique dans un graphe orienté Le poids d'un chemin est la somme des poids des arcs constituant le chemin.
Boucles :
Une boucle c'est lorsqu'une arête a pour extrémités un seul et même sommet. L'incidence est compté double pour le sommet.
Walk, Marche ou Chemin
Dans un graphe non orienté, une marche (en. Walk) est une suite finie non vide d'arête du graphe. Les sommets et les arêtes peuvent apparaître zéro, une ou plusieurs fois dans la chaîne. C'est la notion la plus générale, il n'y a aucune restriction.
On peut :
- revisiter un sommet ;
- réutiliser une arête ;
- revenir en arrière.
La longueur d'une marche est celle de sa suite d'arêtes, soit un de moins que la longueur de la suite de sommets.
Trail, Chaîne
Dans une chaîne, les arêtes ne peuvent apparaître qu'une seule fois.
Circuit
Un circuit est une trail commençant et se terminant au même nœud. Les circuits ne répètent jamais les arêtes. Cependant, ils autorisent les répétitions de sommets dans la séquence.
Avec circuit :
- on revient au point de départ ;
- aucune arête n'est répétée.
Path, Chemin élémentaire
Dans un chemin élémentaire, les sommets et arêtes ne peuvent apparaître qu'une seule fois.
Un chemin est un sous-graphe où le premier et le dernier nœuds ont un degré un, et les autres nœuds ont un degré deux.
Cycle
Un cycle est un path fermé. Un cycle consiste en une séquence de sommets adjacents et distincts dans un graphe. La seule exception est que le premier et le dernier nœuds de la séquence de cycles doivent être le même nœud.
- les sommets v1 , v2 , . . . , vn sont tous distincts,
Cela signifie :
- aucun sommet répété ;
- sauf le premier qui est aussi le dernier.
Définitions
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.
| Parcours | Français | Répétition de sommets | Répétition d'arêtes | Fermé |
|---|---|---|---|---|
| Walk | Marche | Oui | Oui | - |
| Trail | Chaîne | Oui | Non | Circuit |
| Path | Chemin | Non | Non | Cycle |
| Circuit | Oui | Non | Oui | |
| Cycle | Non * | Non | Oui |
Graphes connexes
Un graphe G = {V , E} est connexe si pour toute paire de sommets A, B ∈ V, il existe un chemin à extrémités A et B dans G