Idée générale d’un graphe
Un graphe sert à modéliser des problèmes réels : réseau routier, canalisations, réalisation
de projet, chaîne de fabrication, agriculture, etc.
On résout le problème réel en résolvant le problème sur le graphe avec des méthodes
adaptées.
Un graphe G(X,E) contient :
- X : ensemble fini de sommets, |X| = n est l’ordre du graphe.
- E : ensemble de couples de sommets, |E| = m est la taille du graphe.
Si les couples ne sont pas orientés, on parle d’arêtes et le graphe est non orienté.
Si les couples sont orientés (de x vers y), on parle d’arcs et le graphe est orienté.
Un couple (x,x) est une boucle.
Pour un arc u(x,y) :
- I(u) = x : extrémité initiale.
- T(u) = y : extrémité terminale.
Pour une arête non orientée, x et y sont simplement les extrémités.
---
Types de graphes
Un p-graphe est un graphe orienté où il n’existe jamais plus de p arcs de la forme (i,j) entre
deux sommets i et j pris dans cet ordre.
Un 1-graphe est un graphe orienté avec au plus un arc de i vers j pour tout couple (i,j).
Un multigraphe est un graphe où au moins une paire de sommets est reliée par plus d’une
arête.
Un graphe simple :
- ne contient aucune boucle ;
- ne contient jamais plus d’une arête entre deux sommets quelconques.
---
Chaînes, cycles, chemins, circuits
Une chaîne C d’extrémités x0 et xn est une suite alternée sommets/arêtes telle que chaque
arête relie deux sommets consécutifs.
La longueur d’une chaîne est le nombre d’arêtes qui la composent.
- Chaîne élémentaire : chaque sommet y apparaît au plus une fois.
- Chaîne simple : chaque arête y apparaît au plus une fois.
Un cycle est une chaîne dont le sommet de départ et d’arrivée est le même.
Un cycle élémentaire ne repasse pas deux fois par le même sommet, sauf le départ/arrivée.
Un chemin respecte l’orientation des arcs.
Un chemin élémentaire ne passe qu’une fois par chaque sommet.
Un circuit est un chemin fermé avec arcs distincts.
---
Adjacence et degré
Deux sommets sont adjacents s’ils sont reliés par une arête.
Une arête est incidente aux sommets qu’elle relie.
Dans un graphe orienté :
- d⁻(x) : nombre d’arcs arrivant en x.
- d⁺(x) : nombre d’arcs partant de x.
- d(x) = d⁺(x) + d⁻(x).
Dans un graphe non orienté, d(x) est le nombre d’arêtes incidentes.
Un graphe régulier : tous les sommets ont le même degré.
Un graphe complet : chaque sommet est relié à tous les autres.
---
Théorème sur les degrés
Dans un graphe orienté :
Σ d⁺(x) = Σ d⁻(x) = |E|.
Cas non orienté :
Σ d(x) = 2|E|.
Le nombre de sommets de degré impair est pair.
---
Graphes bipartis et isomorphisme
Un graphe est biparti si ses sommets peuvent être divisés en deux ensembles sans arêtes
internes.
Deux graphes sont isomorphes s’il existe des correspondances entre sommets et arêtes qui
respectent les extrémités.
---
Sous-graphes
- Graphe partiel : même X, sous-ensemble E'.
- Sous-graphe : X' ⊂ X, E'' contient toutes les arêtes internes à X'.
- Sous-graphe partiel : X' et sous-ensemble d’arêtes E'''.
---
Forte connexité et connexité
Une cfc est une classe de sommets reliés par des chemins aller-retour.
Un graphe est fortement connexe s’il n’en possède qu’une.
Une composante connexe (cc) regroupe les sommets reliés par chaînes.
Un graphe non orienté est connexe s’il n’a qu’une cc.
---
Points d’articulation, isthmes et niveaux de connexité
Un point d’articulation est un sommet dont la suppression augmente le nombre de cc.
Un isthme est une arête dont la suppression augmente le nombre de cc.
Connectivité = nombre minimal de sommets à supprimer pour déconnecter.
Arête-connectivité = nombre minimal d’arêtes à supprimer.