Théorie des graphes : Graphes arbres couvrants énoncés corrigés dut informatique
Télécharger PDFDUT Informatique - Semestre 2
Théorie des Graphes : Parcours et Arbres Couvrants
Mathématiques - Soutien n°3
Exercice 1
Lemme des poignées de mains
1. Peut-il exister un graphe orienté avec des sommets de degrés respectifs (justifier) :
(s)3, 3, 1, 1, 1, 2, 2, 2 (dégrees sortants) et (s)3, 3, 1, 1, 1, 2, 2, 2 (dégrees entrants) ?
Si oui, combien aurait-il d’arcs ?
2. Peut-il exister un graphe non orienté avec des sommets de degrés respectifs :
d(s) = 4, 4, 4, 2, 4, 4, 5 ?
Si oui, combien aurait-il d’arêtes ?
Exercice 2 : Coloriage
Soit G le graphe suivant (description implicite : sommets 1 à 8 avec arêtes entre les paires indiquées) :
1. Combien d’arêtes possède le graphe G ?
2. Donner un coloriage de G avec le moins de couleurs possibles (préciser le nombre de couleurs utilisées).
Exercice 3 : Graphes Eulériens
1. Le graphe G1 suivant est-il Eulerien ? Semi-Eulerien ? Aucun des deux ? Justifier.
2. Le graphe G2 suivant est-il Eulerien ? Semi-Eulerien ? Aucun des deux ? Justifier.
Exercice 4 : Listes d’Adjacence
1. Calculer les listes d’adjacence et la taille du graphe G1 suivant (description implicite : sommets 1 à 10 avec arêtes entre les paires indiquées).
2. Soit G2 le graphe ayant pour listes d’adjacence :
LS = {4, 6, 1}, {3, 1, 6}, {2, 1, 4, 5}, {1, 6, 2}, {1, 4}, {2, 1, 3, 5, 7, 8}, {10, 1, 11}, {9, 10, 11}.
T = {1, 3, 5, 7, 8, 10}.
Donner son ordre et sa taille.
Dessiner le graphe de telle sorte qu’il soit planaire.
Exercice 5 : Arbres et Parcours
1. Dessiner l’arbre G1 ayant pour liste de prédécesseurs P = {4, 0, 4, 2, 3, 7, 2, 9, 2, 9} (pour sommets 1 à 10).
2. Faire le parcours en largeur du graphe G3 suivant (description implicite : sommets 1 à 10 avec arêtes entre les paires indiquées), depuis le sommet 7 dans l’ordre croissant des sommets.
Dessiner l’arborescence du parcours, calculer la liste des prédécesseurs correspondante et aussi la liste numérotation des sommets.
3. Le parcours en profondeur du graphe G2 depuis le sommet 6 a donné l’arbre ci-dessous (description implicite : sommets 1 à 10 avec arêtes entre les paires indiquées), calculer les numérotations préfixe (pref) et suffixe (suff) correspondantes.
Exercice 6 : Décomposition en Niveaux
1. Faire la décomposition en niveaux du graphe G suivant (description implicite : sommets 1 à 10 avec arêtes entre les paires indiquées).
Exercice 7 : Arbre Couvrant Optimal
Donner un arbre couvrant de poids maximal du graphe G suivant (description implicite : sommets 1 à 10 avec arêtes et poids indiqués).
Bien faire apparaître l’arbre couvrant sur le graphe, son poids total et faire le tableau avec les étapes de l’algorithme.
FAQ
1. Qu’est-ce que le lemme des poignées de mains ?
Le lemme des poignées de mains stipule que dans tout graphe non orienté, la somme des degrés de tous les sommets est égale à deux fois le nombre d’arêtes (2E = Σd(s)). Pour un graphe orienté, la somme des degrés sortants est égale à la somme des degrés entrants et à la taille du graphe (nombre d’arcs).
2. Comment déterminer si un graphe est Eulerien ou semi-Eulerien ?
Un graphe est Eulerien si tous ses sommets ont un degré pair. Il est semi-Eulerien s’il possède exactement deux sommets de degré impair. Ces propriétés sont vérifiées après avoir calculé les degrés de chaque sommet.
3. À quoi sert un arbre couvrant optimal ?
Un arbre couvrant optimal permet de connecter tous les sommets d’un graphe avec le moins (ou le plus) de poids possible, selon que l’on cherche un arbre couvrant de poids minimal ou maximal. Cela est utile en optimisation de réseaux et en algorithmes de cheminement.