est un graphe orienté (simple). E est l'ensemble des sommets de G. R est l’ensemble des arcs de G.Notation< x, y > R xRy x→y (x est le prédécesseur de y, y est le successeur de x)R(x) = { y | < x, y > R } est l’ensemble des successeurs de x-1R (y) = { x | < x, y > R } est l’ensemble des prédécesseurs de yy x-1x y x yR(x) R (y)y xExemple31 2 57 46E = { 1, 2, 3, 4, 5, 6 , 7 }R = { < 1, 3 >, < 1, 6 >, < 3, 1 >, < 3, 7 >, < 4, 5 >, < 5, 5 > < 6, 1 >, < 6, 3 >, < 6, 7 > }R(1) = { 3, 6 } R(2) = Ø R(3) = { 1, 7 } … R(6) = { 1, 3, 7 } R(7) = Ø-1 -1 -1 -1 -1R (1) = { 3, 6 } R (2) = Ø R (3) = { 1, 6 } … R (6) = { 1 } R (7) = { 3, 6 }Définition 2 : demi-degrés et degré d’un sommetSoit G = < E, R > et x E.-1d (x) = |R (x)| est le demi-degré intérieur de x.id (x) = |R(x)| est le demi-degré extérieur de x.ed(x) = d (x) + d (x) est le degré de x (la somme des demi-degrés intérieur et extérieur).i eDéfinition 3 : sous-grapheSoit G = < E, R > et A E. Le sous-graphe engendré par A est le graphe G = < A, R > tel A Aque R = R { A x A } i.e. les sommets de E - A et les arcs associés sont supprimés.AExemple avec le graphe précédent et A = { 1, 2, 3, 5, 7 }31 2 57M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes ...
est un
graphe orienté (simple). E est l'ensemble des sommets de G. R est l’ensemble des arcs de G.
Notation
< x, y > R xRy x→y (x est le prédécesseur de y, y est le successeur de x)
R(x) = { y | < x, y > R } est l’ensemble des successeurs de x
-1R (y) = { x | < x, y > R } est l’ensemble des prédécesseurs de y
y x
-1x y x yR(x) R (y)
y x
Exemple
3
1 2 5
7 46
E = { 1, 2, 3, 4, 5, 6 , 7 }
R = { < 1, 3 >, < 1, 6 >, < 3, 1 >, < 3, 7 >, < 4, 5 >, < 5, 5 > < 6, 1 >, < 6, 3 >, < 6, 7 > }
R(1) = { 3, 6 } R(2) = Ø R(3) = { 1, 7 } … R(6) = { 1, 3, 7 } R(7) = Ø
-1 -1 -1 -1 -1R (1) = { 3, 6 } R (2) = Ø R (3) = { 1, 6 } … R (6) = { 1 } R (7) = { 3, 6 }
Définition 2 : demi-degrés et degré d’un sommet
Soit G = < E, R > et x E.
-1d (x) = |R (x)| est le demi-degré intérieur de x.i
d (x) = |R(x)| est le demi-degré extérieur de x.e
d(x) = d (x) + d (x) est le degré de x (la somme des demi-degrés intérieur et extérieur).i e
Définition 3 : sous-graphe
Soit G = < E, R > et A E. Le sous-graphe engendré par A est le graphe G = < A, R > tel A A
que R = R { A x A } i.e. les sommets de E - A et les arcs associés sont supprimés.A
Exemple avec le graphe précédent et A = { 1, 2, 3, 5, 7 }
3
1 2 5
7
M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 1<|
<}
„
<{
‰
‰
„
et L R, le graphe partiel engendré par L (sous-ensemble d'arcs)
Lest le graphe G = < E, L >
Exemple avec L = { < 1, 3 > , < 1, 6 > , < 5, 5 > , < 6, 1 > , < 6, 7 > }
3
1 2 5
7 46
Définition 5 : chemin
Un chemin de longueur k ≥ 0 est une suite d'arcs ( α , α , … ,α ) telle que1 2 k
α ( 1 ≤ i ≤ k - 1 ), l'extrémité de α est l'origine de α .i i i+1
!! ! k1 2 x xx x x k-1 k0 1 2
Remarques
• Si α ≠ α pour i ≠ j alors le chemin est simple (élémentaire)i j
• Pour k > 0, le chemin peut-être codé par la suite des sommets ( x , x , … , x ) telle que0 1 k
α = ( x , x )i i-1 i
Définition 6 : cycle (ou circuit)
Un chemin non vide codé par ( x , x , … , x ) est un cycle (ou circuit) si x = x . Si x ≠ x 0 1 k 0 k i j
pour ( i, j ) ≠ ( 0, k ) alors le cycle est élémentaire (chaque sommet n’apparaît qu’une fois).
Définition 7 : circuit hamiltonien
Un cycle élémentaire d’un graphe G est dit hamiltonien s’il contient tous les sommets de G.
Remarque — TSP (Traveling Salesman Problem) — Etant donné un graphe G, déterminer
parmi tous les circuits hamiltoniens, un circuit particulier qui minimise un coût (distance).
Définition 8 : fermeture transitive
+ +La fermeture transitive de G = < E, R > est le graphe G = < E, R > tel que
+ + + i xR y R un chemin non vide de x à y R = R
2 i i ≥ 1 xRy xR y … xR y …
R R1 2 +i.e. si x z y alors ! R
Rappel
Soit R et R deux relations binaires sur l’ensemble E,1 2
le produit R1·R2 = { < x, y > | z tel que < x, z > R et < z, y > R }1 2
2Si R = R = R alors on note R·R par R .1 2
M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 2<}
<{
‰
<}
‰
‰
Exemple
+ +G R
3
1 2 5 +<1,7>!R ? oui
+<3,6>!R ? oui
7 46 + 2R = R " R
+R = R " {<1,7>, <3,6>, <1,1>, <6,6>, <3,3> }
Définition 9 : fermeture transitive réflexive
* *La fermeture transitive réflexive de G est G = < E, R > telle que
*xR y x = y ou un chemin non vide de x à y
Définition 10 : équivalence
Soit G = < E, R > x, y E
⎧∃ un chemin de x à y
x et y sont équivalents si x = y ou ⎨
∃ un chemin de y à x⎪⎩
Exemple
1 et 6 sont équivalents. {1, 3, 6} est une classe d’équivalence.
Définition 11 : forte connectivité
Une composante fortement connexe de G est un sous-graphe de G engendré par une classe
d’équivalence.
Remarque
un chemin entre 2 sommets quelconques d’une composante fortement connexe.
Définition 12 : graphe non orienté
Soit E un ensemble fini.
Si R = { {x, y} | x E et y E } alors G = < E, R > est un graphe non orienté.
E : ensemble de sommets
R : ensemble d’arêtes
Exemple
3
1 2 5
7 46
Définition 13 : graphe valué
Soit G = < E, R > un graphe orienté (ou non orienté), V et V deux ensembles,s a
une valuation des sommets caractérisée par la fonction v : E → Vs s
une valuation des arcs (ou des arêtes) caractérisée par la fonction v : E → Va a
alors G = < E, R, V , V , v , v > est un graphe valué (pondéré).s a s a
M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 3<|
ˆ
<}
‰
‡
un graphe. Si une partition de E en E et en E ( E E = Ø et E E = E ) 1 2 1 2 1 2
telle que x, y E ( i = 1, 2 ) ( x et y ne sont pas incidents / adjacents dans Ei - {x, y} R )i
alors G est un graphe bipartite.
E1
E2
Définition 15 : isomorphisme
G = < E, R > et G’ = < E’, R’ > sont isomorphes si une bijection f : E → E’ telle que :
(u, v) R (f(u), f(v)) R’
Exemple
21
f 1 2 3 4 5 6
u v w x y z3 u v w x y z6
5 4
Définition 16 : graphe complet (clique)
G = < E, R > est un graphe complet si et seulement si x, y E, x≠y {x, y} R
Remarque — Problème MaxClique — Etant donné un graphe G = < E, R >, déterminer le
sous-graphe complet (clique) de taille maximum.
Exemple
MaxClique
M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 4 est un hypergraphe, E : ensemble des sommets, F : ensemble des arêtes.
Exemple
⎧ ⎫s1,s2,s3,s4 s1,s2,s3 s2,s3 s1,s4 s4{ } { } { } { } { }⎪ ⎪
, , , ,⎨ ⎬
E E1 E2 E3 E4⎪ ⎪⎩ ⎭
s3
s2
s1
s4
Définition 19 : arbre
Un arbre est un graphe sans cycle.
M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 5‰
un graphe, le graphe complémentaire de G est le graphe G = < E, R > tel que
∀ u,v∈E, (u,v)∉R⇔ (u,v)∈R
s s1 1G GG G
s s s s ss s s2 3 3 3 32 2 2
s s s s ss s s4 4 4 1 45 5 1
Définition 23 : ensemble indépendant
Soit G = < E, R > un graphe, un ensemble indépendant S de G est un sous-ensemble de E tel
que u, v S, (u, v) R
Définition 24 : clique
Soit G = < E, R > une clique de G est un sous-graphe complet de G.
Théorème
Soit G’= < E’, R’> une clique du graphe G alors E’ est un ensemble indépendant de G.
M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 6<{
Cas particuliers de la coloration
• Graphe planaire (théorème de 4 couleurs, 1974) : tout graphe planaire peut être colorié
avec au maximum 4 couleurs.
• Graphe complet (clique) : le nombre chromatique d’une clique de taille n est égal à n.
K KK3 54
• Graphe bipartite : χ = 2
PVC (Problème du Voyageur de Commerce) — TSP (Traveling Salesman Problem)
Etant donné un graphe valué sur les arêtes (arcs) représentant les distances ( ≥ 0 ), déterminer
un circuit hamiltonien de longueur minimum.
Remarque
1. « Très difficile »
2. Par contre, le plus court chemin entre 2 sommets (distincts) est facile.
Représentation des graphes
1. Matrice d’adjacence
Soit G = < E, R >, on utilise une matrice T de |E| × |E| telle que T[i, j] = 1 x Rxi j
x x x x1 2 3 4
x x1 2 ! $x 0 1 1 01 # &T = x 1 0 0 12 # &
# &x 0 1 0 03 # &x x3 4 x 0 0 0 0# &" %4
Remarque
1. Si le graphe est non orienté, la matrice est triangulaire
2. Si le graphe est valué (sur les arcs/arêtes), les valeurs de T sont les valuations
3. Cette représentation est particulièrement intéressante quand le graphe est dense.
2. Liste d’adjacence
Un graphe est représenté par un tableau dont chaque élément correspond à un sommet as-
socié à une liste chaînée comprenant les sommets adjacents.
x xx 2 31
x xx 1 42
xx 23
x4
M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 7‰