Théorie des graphes et MuPad 1
Stage Graphes et Mupad
Première journée
Théorie des graphes et MuPad 2
Plan de la journée
• Graphes: outils de modélisation• Mathématisation
• Algorithmétisation • Découverte de Mupad
• MuPad et graphes
Théorie des graphes et MuPad 3
Graphes: outils de modélisation
Optimisation combinatoirePlus court chemin…
Recherche opérationnelleOrdonnancement, flot…
Représentation de liens de dépendance Logique, promenades aléatoires…
Comportement de systèmes informatiquesSystèmes distribués…
Problèmes dans des réseaux etc.
Théorie des graphes et MuPad 4
4 villages de Sildavie
Zmrzlina
Kava
Kolac Dort
Théorie des graphes et MuPad 5
25
9
1211 8
9
6
7
Zmrzlina
Kava
Kolac Dort
Réseau routierProblème: organiser la signalisation (routage)
Théorie des graphes et MuPad 6
Problème 2: trouver une tournée pour le postier
25
9
1211 8
9
6
7
Zmrzlina
Kava
Kolac Dort
Théorie des graphes et MuPad 7
Zmrzlina
Kava
Kolac Dort
Une tournée possible du postier
9
1112
9
Théorie des graphes et MuPad 8
Exercice 1Ce circuit est-il le plus court possible?
25
9
1211 8
9
6
7
Zmrzlina
Kava
Kolac Dort
Théorie des graphes et MuPad 9
Matrice aux arcs du graphe
14
23
8
9
12
25
116 7
9
.434241
34.32.
2423.21
.13..
M
Théorie des graphes et MuPad 10
Le produit est remplacé par la concaténation des mots et la somme par l’union, de plus, on ne retient que les chemins sans
circuit (chemins élémentaires).
.423.413432421
324.342341.321
234243.213.241
134.132.
.434241
34.32.
2423.21
.13..
.434241
34.32.
2423.21
.13..
2M
Le produit latin
Théorie des graphes et MuPad 11
.421341324321
...3241.3421
21342413.2341
1324.1342.
.434241
34.32.
2423.21
.13..
.423.413432421
324.342341.321
234243.213.241
134.132.
3M
Proposition: Les puissances r-ièmes successives de M énumèrent les chemins élémentaires d’ordre r du graphe
Théorie des graphes et MuPad 12
.421341324321
...3241.3421
21342413.2341
1324.1342.
3M
On obtient l’ensemble des chemins hamiltoniens (chemins élémentaires passant par tous les points du graphe)
D’où on déduit les circuits hamiltoniens du graphe
Théorie des graphes et MuPad 13
Il y a essentiellement 2 circuits (hamiltoniens):
• 13421 Longueur 11+6+25+8=50
• 13241 Longueur 11+9+12+9=41
13421 est le meilleur!
Théorie des graphes et MuPad 14
Exercice 2Le problème de monsieur Nô
Mr. Nô, personnage mythique japonais, habite la case du coin supérieur gauche d’un carré de 8x8 cases, et se propose de rendre visite à Mr. Gô, lequel habite la case du coin inférieur droit. Mr. Nô se déplace sur l’échiquier en passant d’une case à l’une des cases adjacentes (pas de diagonale). Est-il possible de trouver un parcours qui l’amène chez Mr. Gô , en passant une et une seule fois sur toutes les autres cases de l’échiquier?
Berge (1970)
Théorie des graphes et MuPad 15
Le problème revient à trouver un chemin hamiltonien dans le graphe des déplacements
possibles sur l’échiquier
On peut cependant remarquer que Mr. Nô et Mr. Gô habitent sur des cases blanches, Mr. Nô doit faire 63 sauts,
il aboutira donc nécessairement sur une case noire(absurde)
Théorie des graphes et MuPad 16
Un projet d’adduction d’eau
Zmrzlina
Kolac
Kava
Dort
Théorie des graphes et MuPad 17
Ordonnancement des tâches
Tâche Durée Opérations antérieures
a Cahier des charges 30
b Approbation par Zmrzlina 5 a
c Approbation par Kava 5 a
d Approbation par Kolac 5 a
e Approbation par Dort 5 a
f Lancement des appels d'offres 8 b,c,d,e
g Commande 2 f
h Creuser les tranchées 10 b,c,d,e
i Construire les châteaux 20 g
j Placer les canalisations 5 h
k Installer l'électronique 3 h,g
l Installer les pompes 3 j
m Tester le système 5 h,i,k,l
n Distribution de l'eau au public 6 m
Théorie des graphes et MuPad 18
Graphe d’ordonnancement des tâches
a
c
bh
e
digf
lj
nmk
Théorie des graphes et MuPad 19
Fin de chacune des tâches
30
35
3545
35
35644442
5350
756947
Chemin critique incompressible, si on allonge une durée sur ce chemin c’est la durée totale des travaux qui est allongée.
Théorie des graphes et MuPad 20
Théorie des graphes et MuPad 21
Capacité des canalisations et flot maximal
Zmrzlina
Kava
Kolac Dort
Théorie des graphes et MuPad 22
Débit de chaque château d’eauCapacité des canalisations
A
C
2
1
4
3B
50
50
75
25
100100
7550
E
100
125
225
Consommation maximale de chaque village
S
150
100
50
150
Théorie des graphes et MuPad 23
Flot dans le réseau
• On cherche des réels définissant le flux sur l’arête (a,b)
ba,
a bba,
Théorie des graphes et MuPad 24
Conservation du flux
• Loi de Kirchof:
Le flux entrant est égal au flux sortant dans chaque nœud
4
i
5
3
2
1
54321
Théorie des graphes et MuPad 25
Compatibilité avec la capacité des arêtes
• Compatibilité du flot:
Le flux dans chaque arête est inférieur ou égal à la capacité de l’arête
a bba,
bac ,
bac ,
baca c ,,0
Théorie des graphes et MuPad 26
Le problème du flot maximal
Trouver un flot maximal c’esttrouver un flot compatible qui rend
maximal le flot dans l’arête virtuelle (S,E) dont la capacité est posée infinie
Théorie des graphes et MuPad 27
Premières étapes
• Trouver un flot compatible
Le flot nul convient
• Saturer le flot
Tant qu’il existe un chemin de E vers S sans aucune arête saturée, on augmente le débit
sur ce chemin
jusqu’à saturation d’une arête
Théorie des graphes et MuPad 28
Première étape de la boucle « tant que »
S
A
C
2
1
4
3B
0
0
0E 0
0
0
0 0
0
0
0
4000
0
0
0
(100)
(50)
(150)
Théorie des graphes et MuPad 29
Première étape de la boucle « tant que »
S
A
C
2
1
4
3B
0
0
0E 0
0
50
50 50
0
0
0
40050
0
0
0
(100)(50)
(100)
Théorie des graphes et MuPad 30
Deuxième étape de la boucle « tant que »
S
A
C
2
1
4
3B
0
0E 0
0
50
50
0
0
40050
0
0
0
50
50100
Théorie des graphes et MuPad 31
Au bout d’un certain nombre d’étapes
En fait: au plus le nombre d’arêtes -2 !
Sur notre exemple exactement 8 étapes
Théorie des graphes et MuPad 32
On obtient un flot complet Il n’est pas forcément maximal!
S
A
C
2
1
4
3B
50
50
50
25
50100
2550
E
100
125
175
150
100
50
100
400400
Théorie des graphes et MuPad 33
S
A
C
2
1
4
3B
50
50
50
25
50100
2550
E
100
125
175
150
100
50
100
400400
Montrons qu’il n’est pas maximal
Théorie des graphes et MuPad 34
Equation de conservation du flux
Flux entrant Flux sortant
100+125+100+50+50 = 25+400
Pour le flux entrant, on ne peut pas faire mieux!
Objectif: diminuer le flux sortant
de l’arête (B,3)
Théorie des graphes et MuPad 35
S
C4
3B50
25
2550
E 125
175
50
100
400400
Réduction du débit sur le tuyau (B,3)
(225) (75) (100) (150)
Théorie des graphes et MuPad 36
S
C4
3B
50
E 12550
75
0
50
200125
400400
On peut le réduire à zéro
Théorie des graphes et MuPad 37
Equation de conservation du flux
Flux entrant Flux sortant
100+125+100+50+50 = 0 + 425
Le flux entrant est maximum
Le flot maximum est atteint !
Théorie des graphes et MuPad 38
Conclusion
Le réseau ne permet pas de répondre à une demande maximale des quatre villages!
Il faut construire une nouvelle canalisation de C vers 4 de capacité minimum 25 l/s
Les responsables auraient mieux fait de faire une étude préalable!
Théorie des graphes et MuPad 39
S
A
C
2
1
4
3B
50
50
50
100
50
E
100
125
150
100
500
75
50
200125
400425
Théorie des graphes et MuPad 40
Question
Evaluer le flot maximum du réseau électrique EDF sur toute la France
Algorithme de Ford et Fulkerson
Définition- Correction- Complexité
Théorie des graphes et MuPad 41
Un autre problème: celui du chauffeur de taxi
Zmrzlina
Kava
Kolac Dort
Théorie des graphes et MuPad 42
Graphe de transition
14
23
0.5 0.5
0.50.5
0.2
0.3
0.2
0.20.1
0.2
0.2
0.1 0.5
Théorie des graphes et MuPad 43
Où désigne la probabilité conditionnelle que le taxi aille en j sachant qu’il est en i
Mathématisons la promenade aléatoire du taxi sur notre réseau
ijpM
ijp
Posons:
5.02.01.02.0
3.05.02.00
1.02.05.02.0
05.005.0
M
Théorie des graphes et MuPad 44
Exercice 3
La matrice que nous venons de construire à les propriétés:
n
jijij petp
1
110
Toute matrice qui a ces propriétés est dite stochastique.
Montrer que les matrices stochastiques admettent 1 comme valeur propre.
Théorie des graphes et MuPad 45
Réponse exo 3
• Le vecteur est vecteur propre pour la valeur propre 1
1
1
1
Théorie des graphes et MuPad 46
Posons où désigne la probabilité que le taxi soit en i. Soit V’ le vecteur défini
par: V’=VM
4321 ,,, qqqqV iq 4321 ',',',' qqqq
alors désigne la probabilité conditionnelle que le taxi se trouve après une course dans la ville i sachant la distribution de probabilité initiale V de présence dans chacune des viles
iq'
Théorie des graphes et MuPad 47
Chaîne de Markov
Par récurrence, on définit un processus:
MVV
qqqqV
nn 1
04
03
02
010 ,,,
Où désigne le vecteur « condition initiale » et le vecteur représente la distribution de probabilité de présence du taxi
dans chacune des villes à la fin de la nième course, sachant la condition initiale .
nV0V
0V
Théorie des graphes et MuPad 48
Expérimentation
0,0,0,10 V
On fait l’hypothèse que le chauffeur de taxi part le matin de la ville de Dort (1). Où se trouve-t-il après la
cinquantième course?
Calculons 50V
Théorie des graphes et MuPad 49
Un petit coup de MuPad!
M:=matrix(4,4,[[0.5,0,0.5,0],[0.2,0.5,0.2,0.1], [0,0.2,0.5,0.3],[0.2,0.1,0.2,0.5]]);
0
BBB@
0.5 0 0.5 00.2 0.5 0.2 0.10 0.2 0.5 0.3
0.2 0.1 0.2 0.5
1
CCCA
0
BBB@
0.1818181818 0.1969696969 0.3636363636 0.25757575760.1818181818 0.1969696969 0.3636363636 0.25757575760.1818181818 0.1969696969 0.3636363636 0.25757575760.1818181818 0.1969696969 0.3636363636 0.2575757576
1
CCCA
v:=matrix(1,4,[1,0,0,0]);v*N;
N:=M^50;
¡0.1818181818 0.1969696969 0.3636363636 0.2575757576
¢
Théorie des graphes et MuPad 50
Manifestement au bout d’un certain nombre de courses, la position du taxi devient
« indépendante » de sa position de départ.
© 0.2701562119 0.3701562119 0.4 1.0
ª
432 ,,,1
44332214321 VVVVVMetVVVVV nnnn
linalg::eigenvalues(M);
Les sous espaces propres associés aux valeurs propres de tM sont supplémentaires,
on peut donc décomposer tout vecteur suivant ces 4 sous espaces
On note ces valeurs propres:
La composante est indépendante de la condition initiale, c’est le vecteur limite. On l’appelle la distribution stationnaire du processus, elle est l’unique
solution de l’équation X=XM avec x1+x2+x3+x4=1.
1V
Théorie des graphes et MuPad 51
Exercice 4
Montrer que pour un processus à deux états, ce phénomène arrive toujours, sauf dans deux cas.
Théorie des graphes et MuPad 52
Eliminons le cas où la matrice est l’identité, dans ce cas le processus est stationnaire quelque soit la distribution initiale.
1 21 1
10
01M
Eliminons aussi le cas où -1 est valeur propre, le processus est alors périodique
1 21
1
01
10M
Théorie des graphes et MuPad 53
Supposons que la matrice de transition soit de la forme
1010,101
1
abetbaavec
bb
aa
1 est valeur propre et la trace est la somme des valeurs propres, donc la deuxième valeur propre est l=a+b-1
Elle vérifie la double inégalité: 11 l
On obtient le même phénomène: convergence vers l’unique solution de l’équation XM=X avec x1+x2=1
1 2
1-a
1-ba b
Théorie des graphes et MuPad 54
linalg::eigenvectors(linalg::transpose(M));
2
64
2
641 1
2
64
0B@
b1
a 1ÅÅÅÅ
1
1CA
3
75
3
75
"
a b 1 1
"Ã 11
! ##3
75
abba
V
1,12
1Soit, en normalisant
Résolvons cette équation
Théorie des graphes et MuPad 55
Définition: On dit qu’un processus de Markov est positivement régulier si, quand n tend vers l’infini, la matrice tend vers une matrice composée de r lignes A identiques.
nM
Proposition: dans les conditions de la définition, quelle que soit la distribution initiale la loi limite est rqqqV ,, 210
AV
Proposition: Pour qu’une suite aléatoire de Markov soit positivement régulière, il est nécessaire et suffisant qu’il existe un entier s tel que tous les termes de soient strictement positifs sM
Théorie des graphes et MuPad 56
Exercice 5
Que pensez-vous d’un processus dont le graphe serait le suivant?
Théorie des graphes et MuPad 57
Zone A
Zone B
Zone C
La zone A est transitoire, les zones B et C sont absorbantes, le processus n’est pas positivement régulier.
Question: quelle est la durée moyenne de présence dans la zone A d’un processus, avant de tomber dans l’une des zones absorbantes?
Théorie des graphes et MuPad 58
Pour cela on réunit les deux zones absorbantes en un état absorbant, la réponse pour cette configuration est la même que celle précédente.
Théorie des graphes et MuPad 59
Le soir, le taxi rentre chez lui
Quand le chauffeur décide de rentrer, il utilise la méthode suivante: il continue
à faire des courses jusqu’à ce qu’il soit rendu dans sa ville de Dort (1).
14
23
0.5 0.5
10.5
0.2
0.3
0.2
0.20.1
0.2
0.2
0.1 0.5
Théorie des graphes et MuPad 60
Encore un petit coup de MuPad
M:=matrix(4,4,[[1,0,0,0],[0.2,0.5,0.2,0.1], [0,0.2,0.5,0.3],[0.2,0.1,0.2,0.5]]);
0
BBB@
1 0 0 00.2 0.5 0.2 0.10 0.2 0.5 0.3
0.2 0.1 0.2 0.5
1
CCCA
n:=M^50;0
BBB@
1 0 0 00.9991499134 0.0002442339085 0.0002981942818 0.00030765842020.9988517191 0.0003299065377 0.0004027951879 0.00041557916680.9991499134 0.0002442339085 0.0002981942818 0.0003076584202
1
CCCA
v:=matrix(1,4,[0,1,0,0]): v*n;:¡0.9991499134 0.0002442339085 0.0002981942818 0.0003076584202
¢
Théorie des graphes et MuPad 61
Question: quelle est la probabilité que le chauffeur rentre chez lui?
Posons la probabilité que le chauffeur rentre chez lui, en partant de l’état iiq
Ces probabilités vérifient le système:
43214
43213
43212
1
5.02.01.02.0
3.05.02.00
1.02.05.02.0
1
qqqqq
qqqqq
qqqqq
q
On trouve une unique solution:
14321 qqqq
Ce qui est rassurant!
Théorie des graphes et MuPad 62
Combien de courses fait-il en moyenne avant de rentrer?
Posons le nombre moyen de courses faites en partant de l’état iim
Ces valeurs moyennes vérifient le système
43214
43213
43212
1
5.02.01.02.01
3.05.02.001
1.02.05.02.01
0
mmmmm
mmmmm
mmmmm
m
On trouve une unique solution:
7,9,7,0 4321 mmmm
Ce qui est beaucoup!
Théorie des graphes et MuPad 63
Quelques simulations (10 transitions)
107.552.5
4
3.5
3
2.5
2
1.5
1
x
y
x
y
107.552.5
4
3.5
3
2.5
2
x
y
x
y
107.552.5
2
1.75
1.5
1.25
1
x
y
x
y
107.552.5
2
1.75
1.5
1.25
1
x
y
x
y
Théorie des graphes et MuPad 64
Théorie des graphes et MuPad 65
Mathématisation
Théorie des graphes et MuPad 66
Un graphe (orienté) G est la donnée d’une partie F d’un produit cartésien S×S, où S est
un ensemble
S peut être
Fini, infini dénombrable, infini
Notation: G=(S,F)S est l’ensemble des sommets de G
F est l’ensemble des arcs (arêtes orientées) de G{u,v} est une arête de G si (u,v) ou (v,u), est dans F
Théorie des graphes et MuPad 67
Représentation d’un graphe
1
2
3
4
5
6
S={1,2,3,4,5,6}F={ (1,2) , (1,5) , (2,1) , (2,4) , (2,5) , (4,6) , (6,2) , (6,3) }
Théorie des graphes et MuPad 68
Exercice 6
Construire le graphe des diviseurs pour n=10
Théorie des graphes et MuPad 69
Réponse exercice 6
1
9
8
105
3
6
4
2
7
Théorie des graphes et MuPad 70
Dans ce qui suit S est fini
le graphe G est dit alors fini
L’ordre de G est le cardinal de S
Théorie des graphes et MuPad 71
Vocabulaire de base
• Boucle: arc de la forme (x,x)
X
Théorie des graphes et MuPad 72
• Graphe simple:
Graphe sans boucle
• Graphe complet
Graphe simple avec F maximal
1
3
2
1
32
4
Théorie des graphes et MuPad 73
• Graphe symétrique (ou non orienté)FijFji ),(),(
1
3
2
4
1
3
2
4
Une arête {u,v} est un arc non orienté
Théorie des graphes et MuPad 74
Chemins et chaînes
nsss ...21
nn ssssss ,,...,,,, 13221
Un chemin dans un graphe G est une suite finie d’arcs consécutifs, c’est-à-dire de la forme :
Une chaîne dans un graphe G est une suite finie d’arêtes consécutives:
Notation:
La longueur d’un chemin (resp. d’une chaîne) est le nombre d’arcs (resp. d’arêtes) constituant le chemin (resp. la chaîne)
nn ssssss ,,...,,,, 13221
Théorie des graphes et MuPad 75
Cycles et circuits
• Un circuit (resp. un cycle) est un chemin (resp. une chaîne) dont les extrémités coïncident, et dont les arcs (resp. arêtes) sont tous distincts (resp. toutes distinctes)
Théorie des graphes et MuPad 76
Chemins et circuits Hamiltoniens
Dans un graphe G, on dit qu’un chemin s1s2…sn est hamiltonien s’il passe une et une seule fois par chaque sommet du graphe.
On dit qu’un circuit s1s2…sns1 est hamiltonien s’il passe une et une seule fois par chaque sommet du graphe.
nsss ...21
Théorie des graphes et MuPad 77
Voyage autour du monde (Hamilton)
Trouver un circuit hamiltonien sur le dodécaèdre régulier
Théorie des graphes et MuPad 78
Voyage autour du monde (Hamilton)
Théorie des graphes et MuPad 79
Le graphe de Petersen
Ce graphe n’admet pas de circuit hamiltonien
Théorie des graphes et MuPad 80
Exercice 7
Proposer une méthode pour prouver ce résultat
Théorie des graphes et MuPad 81
Chaînes et cycles eulèriens
Soit G un graphes
On appelle chaîne eulérienne (resp. cycle eulèrien) une chaîne (resp. un cycle) qui
utilise toutes les arêtes du graphe une et une seule fois.
Théorie des graphes et MuPad 82
Les ponts de Kœnigsberg (Euler)
A
B
C
D
Partir de A, passer une seule fois par chacun des ponts, et revenir en A
Théorie des graphes et MuPad 83
Graphe associé
: Tracer les arcs de ce graphe sans lever le crayon
C
DA
B
3
3
3
5
Théorie des graphes et MuPad 84
Théorie des graphes et MuPad 85
Théorie des graphes et MuPad 86
Connexité et forte connexité
Un graphe G = (S,F) est dit connexe (resp. fortement connexe) s’il vérifie la propriété suivante :
pour toute paire de sommet (x,y) de S, il existe une chaîne (resp. un chemin) reliant x à y.
La composante connexe (resp. fortement connexe) d’un sommet x de S est le plus grand sous-graphe connexe (resp. fortement connexe) de G contenant le sommet x.
Théorie des graphes et MuPad 87
Connexité et forte connexité
1
2
3
4 7
5 6
8
9
2 composantes connexes
Théorie des graphes et MuPad 88
Connexité et forte connexité
1
2
3
4 7
5 6
8
9
7 composantes fortement connexes
Théorie des graphes et MuPad 89
Exercice 8
1. Calculez les composantes connexes (resp.fortement connexes) du graphe des diviseurs pour n=10.
Théorie des graphes et MuPad 90
Représentation des graphes Matrices d’adjacence
On identifie l’ensemble S des sommets à {1, 2, …, N }
La matrice d’adjacence du graphe orienté G = (S,F) est la matrice A de MN({0,1}) définie par :
• A[i][j] = 1 si et seulement si (i,j) F
• A[i][j] = 0 si et seulement si (i,j) F
Représentation fondamentalement booléenne des arcs Complexité en espace : O(N2)
Théorie des graphes et MuPad 91
Représentation des graphes Matrices d’adjacence
0 1 00 0 11 1 1
A =
Matrice d’adjacencedu graphe G
1 2
3
Un graphe G
Théorie des graphes et MuPad 92
Représentation des graphes MuPadMatrices d’adjacence
Théorie des graphes et MuPad 93
Représentation des graphes Listes de successeurs
On identifie l’ensemble S des sommets à {1, 2, …, N }.
La liste des successeurs du sommet i d’un graphe orienté G = (S,F) est la liste L[i] définie par :
• L[i] = { j S, (i,j) F }
La donnée de l’ensemble des listes de successeurs est équivalente à celle du graphe G.
Représentation dynamique du graphe
Complexité en espace : O(N+M) où M = |F|
Théorie des graphes et MuPad 94
Représentation des graphes :Listes de successeurs
Listes de successeursdu graphe G
1
2
3
…
L2
3
1 2
3
1 2
3
Un graphe G
Théorie des graphes et MuPad 95
Représentation des graphes MuPadListes de successeurs
Théorie des graphes et MuPad 96
Parcours de graphe :Exploration en profondeur d’abord
Etant donné un graphe orienté G = (S,F), comment parcourir tous les sommets de manière systématique ?
Initialement tous les sommets ne
sont pas marqués
Principe :marquer ou numéroter
les sommets
Théorie des graphes et MuPad 97
Parcours de graphe :Exploration en profondeur d’abord
Etant donné un graphe orienté G = (S,F), comment parcourir tous les sommets de manière systématique ?
-1
-1 -1 -1
Initialement tous les sommets ne
sont pas marqués
Principe :marquer ou numéroter
les sommetsC’est-à-dire sont
tous numérotés à -1
C’est-à-dire sont tous numérotés à -1
Théorie des graphes et MuPad 98
Parcours de graphe :Exploration en profondeur d’abord
Etant donné un graphe orienté G = (S,F), comment parcourir tous les sommets de manière systématique ?
0
-1 -1 -1
Etape 1 : on numérote à 0le sommet initial
Etape 2 :on numérote récursivement les successeurs du sommet
initial
Théorie des graphes et MuPad 99
Parcours de graphe :Exploration en profondeur d’abord
Etant donné un graphe orienté G = (S,F), comment parcourir tous les sommets de manière systématique ?
0
1 -1 -1
si ceux-ci ne sont pas déjà numérotés !
Etape 2 :on numérote récursivement les successeurs du sommet
initial
Un sommet non encore exploré peut en effet avoir été numéroté lors de l’exploration récursive de l’un de ces frères.
Un sommet non encore exploré peut en effet avoir été numéroté lors de l’exploration récursive de l’un de ces frères.
Théorie des graphes et MuPad 100
Exploration en profondeur d’abord
Théorie des graphes et MuPad 101
Exercice 2 :Exploration en profondeur d’abord
Appliquer la méthode d’exploration en profondeur d’abord au graphe donné ci-dessus en commençant l’exploration en 1.
1
2
3
4 7
5 6