suite
SMI S5
FP Taza
Connexité (1)
• Un graphe non orienté G = (S, A) est dit
connexe si x, y S, il existe une chaîne
entre x et y.
29
Connexité (2)
• Exemple:
e1
1 2
e2
e3
3 4
e4
Graphe connexe
30
Connexité forte (1)
• Un graphe orienté G = (S, A) est dit fortement
connexe si x, y S, il existe un chemin de x
à y et un chemin de y à x.
31
Connexité forte (2)
• Exemple 1:
a d
b c
Graphe fortement connexe
32
Connexité forte (3)
• Exemple 2:
b c a d
e f g h
Graphe non fortement connexe
b c a d
e f g h
Composantes fortement connexes du graphe
33
Graphes Eulériens (1)
• Soit G = (S, A) un graphe orienté (resp. non orienté).
– Un chemin eulérien (resp. une chaîne eulérienne) de G est
un chemin (resp. une chaîne) passant une et une seule fois
par chaque arc (resp. arête) de G.
– Un circuit (resp. cycle) eulérien de G est un circuit (resp.
cycle) passant une et une seule fois par chaque arc (resp.
arête) de G.
– G est dit graphe eulérien s’il possède un circuit (resp.
cycle) eulérien.
• Exemples d’applications:
– Ramassage d’ordures
– Reconstruction de séquences d’ADN
34
Graphes Eulériens (2)
• Exemple (graphe eulérien):
– ((C,D), (D,B), (B,A), (A,C), (C,E), (E,B), (B,C)) est un cycle eulérien.
C D
B A
35
Graphes Eulériens (3)
• Théorème d’Euler (Cas non orienté):
– Soit G = (S, A) un graphe non orienté connexe. G
est eulérien si et seulement si d(x) est pair pour
tout sommet x du graphe G.
36
Graphes Eulériens (4)
• Théorème d’Euler (Cas orienté):
– Soit G = (S, A) un graphe orienté fortement
connexe. G est eulérien si et seulement si d+(x) =
d-(x) pour tout sommet x du graphe G.
37
Graphes Hamiltoniens (1)
• Soit G = (S, A) un graphe orienté (resp. non orienté).
– Un chemin hamiltonien (resp. une chaîne hamiltonienne)
de G est un chemin (resp. une chaîne) passant une et une
seule fois par chaque sommet de G.
– Un circuit (resp. cycle) hamiltonien de G est un circuit
(resp. cycle) passant une et une seule fois par chaque
sommet de G.
– G est dit graphe hamiltonien s’il possède un circuit (resp.
cycle) hamiltonien.
• Exemples d’applications:
– Problème du voyageur de commerce
– Ordonnancement de tâches avec temps de réglage
38
Graphes Hamiltoniens (2)
• Exemple (graphe hamiltonien):
– ((a,d), (d,c), (c,e), (e,b), (b,a)) est un circuit hamiltonien.
a d
b c
39
Graphes Hamiltoniens (3)
• Théorème de Dirac (Cas non orienté):
– Soit G = (S, A) un graphe non orienté simple
d’ordre n ≥ 3. Si d(x) ≥ n/2 pour tout sommet x du
graphe G, alors G est hamiltonien.
40
Graphes Hamiltoniens (4)
• Théorème de Ghouila-Houiri (Cas orienté):
– Soit G = (S, A) un graphe orienté simple et
fortement connexe d’ordre n ≥ 2. Si d(x) ≥ n pour
tout sommet x du graphe G, alors G est
hamiltonien.
41
