Théorie des graphes : Graphes arbres couvrants énoncés corrigés dut informatique
Télécharger PDFDUT Informatique
semestre 2
Th ́eorie des Graphes
parcours et arbres couvrants
Math ́ematiques
Soutien n◦ 3
Exercice1
Lemme des poign ́ees de mains
1. Peut-il exister un graphe orient ́e avec des sommets de degr ́es respectifs (justifier) :
s1234567d −
(s)3311122d +
(s)1121323
Si oui combien aurait-il d’arcs ?
2. Peut-il exister un graphe non-orient ́e avec des sommets de degr ́es respectifs (justifier) :
s1234567
d(s)4442445
Si oui combien aurait-il d’arˆetes ?
Exercice2 Coloriage1 23 45 67 8
SoitGle graphe ci-contre :
1. Combien d’arˆetes poss`ede le grapheG:
2. Donner un coloriage deGavec le moins
de couleurs possibles (pr ́eciser le nombre
de couleurs utilis ́ees).1 DUT Informatique
semestre 2
Th ́eorie des Graphes
parcours et arbres couvrants
Math ́ematiques
Soutien n◦ 3
Exercice3
Graphes Euleriens
1. Le grapheG1 suivant est-il Eulerien ? Semi-Eulerien ? aucun des deux ? Justifier.1 23 45 67 2. Le grapheG2 suivant est-il Eulerien ? Semi-Eulerien ? aucun des deux ? Justifier.1 23 45 67 82 DUT Informatique
semestre 2
Th ́eorie des Graphes
parcours et arbres couvrants
Math ́ematiques
Soutien n◦ 3
Exercice4
Listes d’Adjacence
1. Calculer les listes d’adjacence et la taille du grapheG1 suivant :1 23 45 67 8LS= T S=
2. SoitG2 le graphe ayant pour listes d’adjacence :
LS=4613162145
T S=135781011
Donner son ordre et sa taille :
Dessiner le graphe de telle sorte qu’il soit planaire :3 DUT Informatique
semestre 2
Th ́eorie des Graphes
parcours et arbres couvrants
Math ́ematiques
Soutien n◦ 3
Exercice5
Arbres et parcours
1. Dessiner l’arbreG1 ayant pour liste de pr ́edesseceursPci-dessous :
P=40423729292. Faire le parcours en
largeur du grapheG 3
suivant, depuis
le sommet 7 dans
l’ordre croissant des
sommets.Dessiner
l’arborescence du par-
cours, calculerPla
liste des pr ́ed ́ecesseurs
correspondanteet
aussi la listenum
de num ́erotation des
sommets :1 23 45 67 89 10P= num=4 DUT Informatique
semestre 2
Th ́eorie des Graphes
parcours et arbres couvrants
Math ́ematiques
Soutien n◦ 3
3. Le parcours en profondeur du grapheG2 depuis le sommet 6 a donn ́e l’arbre ci-dessous,
calculer les num ́erotations pr ́efixe (pref) et suffixe (suf f) correspondantes :1 23 4567 89 10pref= suf f=
Exercice6 d ́ecomposition en niveaux
1. Faire la d ́ecomposition en niveaux du grapheGci-dessous :1 234 5678 910 niveaux=5 DUT Informatique
semestre 2
Th ́eorie des Graphes
parcours et arbres couvrants
Math ́ematiques
Soutien n◦ 3
Exercice7
Arbre couvrant optimal
Donner un arbre couvrant de poids maximal du grapheGci-dessous, bien faire apparaˆıtre l’arbre
couvrant sur le graphe , son poids total, et faire le tableau avec les ́etapes de l’algorithme sur la
feuille :1 234 56 576 1510 3201 1210 sommetsarˆetes sortantespoids
marqu ́esminimum