Devoir sur les graphes

Un soin particulier sera apporté à la clarté de la rédaction et des justifications.

L'usage de la calculatrice est autorisé.

Durée : strictement moins d'une heure.

Exercice 1

Un guide de randonnée en montagne décrit les itinéraires possibles autour d'un pic rocheux. La description des itinéraires est donnée par le graphe ci-dessous.

1. a. Dresser un tableau décrivant les degrés de chaque sommet du graphe.

   b. En déduire le nombre d'arêtes de ce graphe.

   Corrigé

   a.

   Sommet	1	2	3	4	5	6	7	8	9	10
   Degré	3	4	4	4	4	4	4	4	4	3

   b.

   La somme des degrès donne \(38\), il y a donc \(\dfrac{38}{2}=19\) arêtes.

2. Donner un itinéraire allant de \(\text{D}\) à \(\text{A}\) passant par tous les sommets du graphe une seule fois mais n'empruntant pas forcément tous les sentiers.

   Corrigé

   Par exemple \(1\) - \(3\) - \(2\) - \(4\) - \(5\) - \(6\) - \(9\) - \(7\) - \(8\) - \(10\)

3. Donner un itinéraire allant de \(\text{D}\) à \(\text{A}\) passant une seule fois par tous les sentiers.

   Corrigé

   Par exemple \(1\) - \(2\) - \(3\) - \(6\) - \(5\) - \(7\) - \(8\) - \(10\) - \(9\) - \(4\) - \(5\) - \(2\) - \(4\) - \(1\) - \(3\) - \(8\) - \(6\) - \(9\) - \(7\) - \(10\)

4. a. Donner la matrice d'adjacence \(\text{M}\) de ce graphe (dans l'ordre croissant des sommets).

   b. En déduire le nombre d'itinéraires allant de \(\text{D}\) à \(\text{A}\) en empruntant cinq sentiers.

   Citer un tel itinéraire passant par le Pic rouge.

   Corrigé

   a.

   \[M = \left( \begin{array}{cccccccccc}0&1&1&1&0&0&0&0&0&0\\ 1&0&1&1&1&0&0&0&0&0\\1&1&0&0&0&1&0&1&0&0\\1&1&0&0&1&0&0&0&1&0\\0&1&0&1&0&1&1&0&0&0\\0&0&1&0&1&0&0&1&1&0\\0&0&0&0&1&0&0&1&1&1\\0&0&1&0&0&1&1&0&0&1\\0&0&0&1&0&1&1&0&0&1\\0&0&0&0&0&0&1&1&1&0\\ \end{array} \right)\]

   b.

   On calcule \(M^5\) sur la calculatrice et on regarde le coefficient (1,10) ou (10,1), il vaut \(47\).

   \[M^5 = \left( \begin{array}{cccccccccc}58&81&78&88&65&79&69&51&50&47\\ 81&92&102&95&108&79&70&81&87&58\\78&102&80&87&88&99&85&89&84&61\\88&95&87&72&121&66&58&103&112&51\\65&108&88&121&62&134&122&66&56&79\\79&79&99&66&134&62&65&121&131&65\\69&70&85&58&122&65&70&118&126&70\\51&81&89&103&66&121&118&72&64&88\\50&87&84&112&56&131&126&64&54&89\\47&58&61&51&79&65&70&88&89&58\\ \end{array} \right)\]

   On peut trouver comme itinéraire qui passe par 5: \(1\) - \(2\) - \(5\) - \(7\) - \(8\) - \(10\).

Exercice 2

Partie A : Étude du problème

Colorier un graphe, c'est affecter une couleur à chaque sommet, de sorte que deux sommets adjacents ne portent pas la même couleur.

Le nombre chromatique, noté \(\gamma\), est le plus petit nombre de couleurs nécessaires pour colorier un graphe.

Considérons un graphe \(\text{G}\).

Un sous-graphe de \(\text{G}\) est un graphe G' composé de certains sommets de \(\text{G}\) et de toutes les arêtes reliant ces sommets.

Notons \(m\) l'ordre du plus grand des sous-graphes complets de \(\text{G}\) et \(\Delta\) le plus grand degré des sommets de \(\text{G}\). Alors \(m \leqslant \gamma \leqslant \Delta+1\).

Prouver cette inégalité.

Corrigé

Partie A

Pour chaque sommet du graphe on peut tenir le raisonnement suivant : ce sommet est adjacent à \(r\) sommets au plus, et le nombre de couleurs déjà utilisées pour colorer ces sommets est donc inférieur ou égal à \(r\). Il reste donc au moins une couleur non utilisée dans la palette, avec laquelle nous pouvons colorer notre sommet.

Puisque, par définition, dans un sous-graphe complet d'ordre \(m\), tous les sommets sont adjacents entre eux, il faudra \(m\) couleurs. Donc, il faudra au moins ω(G) couleurs pour colorer le graphe G.

Partie B : Algorithme de Welsh-Powell

Pour colorier un graphe, on utilise la palette Rouge, Bleu, Vert, Jaune, Noir, Blanc dans cet ordre et l'algorithme suivant:

• Étape 1: Lister les sommets par ordre de degré décroissant.

• Étape 2: Attribuer une couleur parmi les couleurs de la palette au premier sommet de la liste.

• Étape 3: Attribuer cette même couleur à tous les sommets qui ne sont pas adjacents avec le premier sommet de la liste et qui ne sont pas adjacents entre eux.

• Étape 4: Répéter les étapes 2 et 3 tant que tous les sommets ne sont pas coloriés.

Colorier le graphe ci-dessous à l'aide de cet algorithme.

Corrigé

Partie B

Sommet	Degré
B	4
C	4
D	4
A	3
E	3
F	3
H	3
G	2
I	2
J	2

Avec Welsh-Powell, on trouve par exemple la coloration:

Sommet	Couleur
B	Rouge
C	Bleu
D	Vert
A	Rouge
E	Bleu
F	Vert
H	Jaune
G	Rouge
I	Rouge
J	Bleu

Partie C: Application

Camille est éducatrice de chiens: elle donne des leçons de dressage le samedi après-midi.

Neuf chiots sont présents: Aéro, Banjo, Carrousel, Dirka, Erald, Farore, Gipsy, Hyacinthe et Igor.

Camille souhaite réaliser des exercices d'apprentissage par petits groupes de deux ou trois chiens.

Farore ne pense qu'à jouer si elle est trop proche de Banjo, Carousel ou Erald.

De même, Dirka est très distraite si Banjo ou Farore sont à proximité !

Igor ne supporte pas le caractère trop fougueux de Gipsy.

Enfin, le turbulent Aéro ne supporte la présence d'aucun autre chiot, sauf Erald et Hyacinthe.

1. Représenter cette situation à l'aide d'un graphe \(\text{G}\), dont les sommets sont les noms des chiots et relier entre eux les chiots que l'on ne peut pas mettre ensemble pour ce travail de groupe.

   Corrigé

   

2. Le graphe \(\text{G}\) est-il connexe ? Justifier.

   Corrigé

   Non, le graphe n'est pas connexe, il a un sommet isolé, H.

3. a. Déterminer un sous-graphe complet d'ordre maximal du graphe \(\text{G}\).

   Corrigé

   F - D - B - A est le plus grand sous-graphe complet du graphe \(\text{G}\). Il est d'ordre 4.

   b. Que peut-on en déduire pour le nombre chromatique du graphe \(\text{G}\) ?

   Corrigé

   D'après la partie A, le nombre chromatique est donc supérieur ou égal à 4.

4. Donner la valeur du nombre chromatique du graphe \(\text{G}\).

   Corrigé

   

   On a colorié le graphe avec l'algorithme de Welsh-Powell au-dessus, il y a d'autres colorations possibles.

   La valeur du nombre chromatique est 4.

5. Peut-on proposer une répartition des chiots en groupes de deux à trois chiots pouvant travailler ensemble ?

   Corrigé

   Avec la coloration obtenue à la question précédente, on s'aperçoit que l'on peut constituer des groupes de deux à trois chiots en rassemblant D et H car ce dernier est isolé. On évite alors un groupe de 1 chiot.

   On obtiendrait alors:

   Groupe 1 : A - E

   Groupe 2 : B - C - I

   Groupe 3 : F - G

   Groupe 4 : D - H