Théorie des graphes : Exercices d'examen sur les graphes niveau l3 avec corriges
Télécharger PDFExercices d’examen sur les graphes (niveau L3) avec corrigés
1) Exploration d’un graphe
Pour ce graphe non orienté à 14 sommets, les voisins de chaque sommet sont supposés écrits dans l’ordre croissant de leurs numéros. Ainsi : - 0 a pour voisins 1, 4, 7, 8 ; - 1 a pour voisins 0, 5, 7 ; - 2 a pour voisins 5, 10, 12, 13 ; - etc.
1) En partant du sommet 0, réaliser une exploration en profondeur (DFS) de ce graphe en utilisant l’ordre des voisins défini. Dessiner l’arbre couvrant obtenu.
2) Toujours en partant du sommet 0, effectuer une exploration en largeur (BFS) du graphe. Utiliser une file pour suivre l’évolution et dessiner l’arbre final de l’exploration.
2) Chemins hamiltoniens
Ce graphe à cinq sommets est tel que deux sommets quelconques sont reliés par un arc unique, dans un sens ou dans l’autre. Ce type de graphe possède un nombre impair de chemins hamiltoniens (avec le sommet final différent du sommet initial) lorsque l’on considère les cinq points de départ possibles.
1) Déterminer tous les chemins hamiltoniens partant de chacun des 5 sommets (0, 1, 2, 3, puis 4) et se terminant en un sommet différent du point de départ. Dessiner ces chemins dans chacun des cinq cas. Combien en existe-t-il ?
2) Vérifier que pour chacun des points de départ, un des chemins hamiltoniens peut être prolongé pour former un cycle hamiltonien. Les cinq cycles obtenus représentent le même cycle si l’on ignore le point de départ.
3) Cycles eulériens
Considérons ce graphe non orienté à 6 sommets numérotés de 0 à 5.
1) Expliquer pourquoi ce graphe possède des cycles eulériens.
2) Déterminer tous les cycles eulériens qui commencent par la succession des sommets 0, 1, 2.
4) Chemins eulériens
On dispose de trois îles A, B, C sur une rivière dont les rives sont notées D et E, avec 7 ponts reliant ces éléments selon un schéma donné.
1) Construire le graphe correspondant à ce schéma.
2) Montrer que ce graphe possède des chemins eulériens mais pas de cycles eulériens. Autrement dit, en partant d’un sommet précis, une personne peut traverser chaque pont une fois et une seule, mais sans revenir à son point de départ.
3) Donner un exemple de chemin eulérien.
5) Arbre couvrant minimal
On considère un graphe non orienté pondéré à 12 sommets (numérotés de 0 à 11), où les poids sont indiqués sur les arêtes correspondantes.
1) En prenant comme point de départ le sommet 0, construire l’arbre couvrant minimal en appliquant l’algorithme de Prim.
6) Plus courts chemins
Ce graphe orienté pondéré possède 5 sommets et 11 arcs.
1) Écrire la matrice d’adjacence de ce graphe.
2) Utiliser l’algorithme de Floyd pour déterminer les longueurs des plus courts chemins entre n’importe quel sommet et n’importe quel autre sommet.
7) Programmation d’un cheminement
Dans un quadrillage de pas unité, on dessine des chemins montants à partir d’un point du quadrillage. Seules trois directions sont autorisées à chaque pas : vers le haut, la droite ou la gauche. Aucun retour n’est permis sur un segment déjà parcouru. Le premier pas est toujours vertical.
1) En continuant l’arborescence, déterminer le nombre de chemins de longueur N = 4.
2) Écrire un programme récursif qui calcule le nombre de chemins de longueur N, en utilisant une fonction récursive arbre(i, n) où i est le numéro du pas actuel et n la longueur du chemin en cours de construction.
3) On admet que le nombre de chemins de longueur N, noté u(N), suit la relation de récurrence : u(n+2) = 2u(n+1) + u(n), avec u(0) = 1 et u(1) = 1. Faire un programme itératif qui calcule u(N) en utilisant seulement trois variables.
8) Programmation : des sommets aux arêtes d’un graphe
Un graphe non orienté à NS sommets (numérotés de 0 à NS – 1) est enregistré par les listes d’adjacence de ses sommets. Pour chaque sommet i, on connaît ses voisins v[i][j] et leur nombre nbv[i] (j allant de 0 à nbv[i] – 1).
1) Faire un programme qui donne les arêtes du graphe et leur nombre NA. Chaque arête k sera enregistrée par ses deux extrémités e1[k] et e2[k], avec e1[k] < e2[k].
FAQ
Qu’est-ce qu’un chemin hamiltonien ? Un chemin hamiltonien est un chemin dans un graphe qui visite chaque sommet exactement une fois.
Comment différencier un chemin eulérien d’un cycle eulérien ? Un chemin eulérien traverse chaque arête une fois sans nécessairement revenir au sommet de départ, tandis qu’un cycle eulérien fait cela en formant un circuit fermé.
À quoi sert l’algorithme de Prim ? L’algorithme de Prim permet de construire un arbre couvrant minimal pour un graphe pondéré, c’est-à-dire un sous-graphe connecté sans cycles et dont la somme des poids est minimale.