Théorie des graphes
Commentaire d'oeuvre : Théorie des graphes. Recherche parmi 298 000+ dissertationsPar LunixMLP • 4 Mai 2015 • Commentaire d'oeuvre • 271 Mots (2 Pages) • 881 Vues
2GRA - Théorie des graphes - TP (4heures)
1.
1.
2.
3.
1.
Première Partie : Parcours Eulériens, Coloration
1.1 Parcours Eulériens
Onconstatequenoussommesenfaced’ungrapheorientés,carsiilauraitétécompletil aurait fallu que chaque paire de sommet soit reliée entre elle .On constate que non. Cependant il est connexe puisque aucun sommet est isolé et il existe toujours une chaine pour relier deux points.
NonavonsuncircuitEulérien
Par exemple le circuit E-B-A-D-H-F les deux sommets impaires sont Positionnées au début et à la fin
SinousavonsuncircuitEulérienforcémentilendécouledescheminsEulériens
1.2 Coloration
Pourtrouverlamajorationd’ungrapheoncherchelesommetdeplushautdegrés.Le plus haut degrés est 4 par conséquent on aura au maximum 5 couleurs.
Et la minoration, on observe les sous-graphes hamiltonien. Ici on peut donc minorer à 3. Par exemple B-C-E.
2.
A
C
E
G
B
F
D
H
2.
1.
2.
Deuxième Partie : Plus cours chemins, Arbres Couvrants 2.1 Plus Courts Chemins
Afin de calculer le plus court chemin entre un sommet fixé et les autres sommets, on utilise l’algorithme de Dijkstra.
Pour commencer on part de A puis en suivant:
3. Le nombre chromatique de ce graphe est 3.
M
LA
LB
LC
LD
LE
LF
LG
LH
PA
PB
PC
PD
PE
PF
PG
PH
A
0
400
/
600
/
/
/
/
A
A
A
B
0
400
1000
600
800
/
/
/
A
A
B
A
B
E
0
400
1000
600
800
/
1000
/
A
A
B
A
B
E
D
0
400
1000
600
800
/
...