Théorie des graphes : notions de base

Définition

Graphe

Un ensemble de points appelés sommets, et un ensemble d'arcs entre ces sommets, qui définissent une structure. Objet mathématique noté G=(X,Γ) avec X l'ensemble dénombrable de sommets (x1,x2,...) et Γ l'application multicoque de X dans X.

Arc

u=(xi,xj) avec xi appartenant à X et xj appartenant à X, xj=Γ(xi)

Les sommets et les arcs peuvent être :

matériels : réseau routier (arcs -> rues/routes / sommets -> carrefours)
immatériels : arbre généalogique (arcs -> liens de filiation entre les individus (immatériel) / sommets -> membres de la famille (matériel)

1 - Représentation des graphes

Par correspondance (1)
Sagittale -> la plus courante (arcs et sommets) (2)
pour décrire un prblm mais pas pour les calculs
Par liste de successeurs ou prédécesseurs (3)
Matricielle (4)

2 - Principaux concepts

L'ordre d'un graphe est le cardinal de X -> nombre de sommets du graphe.
Une boucle est un arc reliant un sommet à ce même sommet.
G1 = (X, Γ1) est un graphe partiel de G = (X, Γ) si ∀_xi ∈ X, Γ_1(xi) ⊆ Γ_(xi)
G2 = (E, Γ2) est un sous-graphe de G = (X, Γ) si E ∈ X et si ∀_xi ∈ E, Γ_2(xi) = E ∩ Γ_(xi)
Un chemin est :
une suite de sommets reliés par un arc. -> µ = (x1 .... xk), tel que ∀_i xi+1 ∈ S_(xi).
la suite des arcs qui le compose.
simple s'il ne passe pas 2 fois par le même arc
élémentaire s'il ne passe pas 2 fois par le même sommet
Un circuit est un chemin dont le sommet initial x1 est le même que le sommet extrémal x_k.
La longueur l(µ) est le nombre d'arcs parcourus par le chemin µ.

Chemins et circuits Hamiltoniens

Soit un graphe d'ordre n -> G = (X, Γ) avec |X|= n.

µ = (x1 ...xn) est un chemin Hamiltonien s'il passe une fois et une seule par chaque sommet.
chemin élémentaire de longueur l(µ)=n-1
µ = (xi ...xi) est un circuit Hamiltonien s'il passe une fois et une seule par chaque sommet.
circuit élémentaire de longueur l(µ)=n
Exemple cours p.4

3 - Détermination du nombre de chemins de longueur p joignant 2 sommets

Soit M la matrice booléenne représentative du graphe d'ordre n :

les termes de M sont a_ij.
le terme c_ij de C = M^P donne le nombre de chemins de longueur p joignant le sommet x_i au sommet x_j.

Exemple cours p.4

4 - Décomposition en niveaux d'un graphe sans circuit

Définition

Niveau des sommets d'un graphe

Soit G un graphe sans circuit. Le niveau d'un sommet xi correspond à la longueur du plus long chemin menant à ce sommet xi. Par extension, on désigne comme niveau p de G, l'ensemble des sommets atteints par des chemins de longueur p au plus. Exemple cours p.5

Intérêt : plus lisible

Algorithme n°1 de classement par niveaux

représentation par tableau des prédécesseurs
TD1 exercice 2

Algorithme n°2 de classement par niveaux

représentation matricielle du graphe
permet de déterminer le niveau de chaque sommets du graphe.

Algorithme n°3 de classement par niveaux

représentation matricielle du graphe
utilise le théorème du nombre de chemins de longueur p joignant 2 sommets (3)

5 - Recherche des chemins extrémaux dans un graphe sans circuit

Position du problème

Soit G=(X, U) un graphe sans circuit avec u=(x_ij, x_j) et a_ij=a(u) la longueur de l'arc (x_i, x_j).
Soit µ un chemin de G. La longueur de ce chemin est l(µ) = Σ_(u_∈_µ)a(u)
Le prblm est de trouver dans G les chemins de longueur extrémale entre 2 sommets -> les chemins les plus longs/courts

Théorème

Tout chemin 0-1 extrémal ne peut être formé que de chemins k-i extrémaux.

Algorithme

Le choix de l'algorithme dépend :

de la taille de G,
de l'existence ou pas de circuit dans le graphe,
de ce que l'on cherche à obtenir comme information (longueur, tracé),
si les longueurs aij des arcs sont exclusivement de signe + ou -,
si les sommets origine et extrémité sont fixés indépendamment ou non.

exemple : GPS pour rechercher le chemin le plus court
exemple cours p.10