Théorie des graphes : Graphes nadia brauner uga
Télécharger PDFExercices de Graphe
Nadia Brauner
Université Grenoble Alpes
Table des matières
1. Graphes
2. Chemins et cycles
3. Arbres
4. Plus courts chemins
5. Coloration
6. Couplage
7. Flots
8. Dessins de graphes
1. Graphes
Modélisation
Exercice 1 : Qui a tué le Duc de Dunsmore ? (d’après Claude Berge)
Un jour, Sherlock Holmes reçoit la visite de son ami Watson, chargé d’enquêter sur un assassinat mystérieux datant de plus de 10 ans. À l’époque, le Duc de Graphistan avait été tué par l’explosion d’une bombe, qui avait également détruit le château de Graphistan où il s’était retiré. Les journaux d’alors relataient que le testament, détruit lui aussi par l’explosion, avait tout pour déplaire à l’une de ses 7 ex-femmes. Or, avant sa mort, le Duc les avait toutes invitées à passer quelques jours dans sa retraite écossaise.
Holmes : Je me souviens de l’affaire ; ce qui est étrange, c’est que la bombe avait été fabriquée spécialement pour être cachée dans l’armure de la chambre à coucher, ce qui suppose que l’assassin a nécessairement effectué plusieurs visites au château !
Watson : Certes, et pour cette raison, j’ai interrogé chacune des ex-épouses : Ann, Betty, Charlotte, Edith, Félicia, Georgia et Helen. Elles ont toutes juré qu’elles n’avaient été au château de Graphistan qu’une seule fois dans leur vie.
Holmes : Hum ! Leur avez-vous demandé à quelle période ont eu lieu leurs séjours respectifs ?
Watson : Hélas, aucune ne se rappelait les dates exactes, après 10 ans ! Néanmoins, je leur ai demandé qui elles y avaient rencontré :
— Ann a déclaré y avoir rencontré Betty, Charlotte, Félicia, Georgia ;
— Betty a déclaré y avoir rencontré Ann, Charlotte, Edith, Félicia, Helen ;
— Charlotte a déclaré y avoir rencontré Ann, Betty, Edith ;
— Edith a déclaré y avoir rencontré Betty, Charlotte, Félicia ;
— Félicia a déclaré y avoir rencontré Ann, Betty, Edith, Helen ;
— Georgia a déclaré y avoir rencontré Ann, Helen ;
— Helen a déclaré y avoir rencontré Betty, Félicia, Georgia.
Vous voyez, mon cher Holmes, ces réponses sont concordantes !
Question : Mais qui donc est l’assassin ?
Exercice 2 : Échange de cavaliers (Jean-Paul Davalan)
Pour résoudre ce casse-tête, vous devez échanger les positions des deux cavaliers blancs avec celles des deux noirs, en respectant les règles du déplacement du cavalier sur un échiquier et en n’utilisant que les dix cases dessinées.
Question 1 : Modéliser le problème à l’aide d’un graphe.
Question 2 : Utiliser cette modélisation pour résoudre ce casse-tête.
Question 3 : Y a-t-il des cases inutiles ?
Exercice 3 : Durée minimum d’un tournoi d’échecs
Dans un tournoi d’échecs, chaque participant doit rencontrer tous les autres. Chaque partie dure une heure. Déterminer la durée minimum du tournoi dans le cas où le nombre de participants est 3, 4, 5 ou 6.
Exercice 4 : Missionnaires et cannibales
Trois missionnaires et trois cannibales veulent traverser une rivière en utilisant une barque qui ne peut transporter que deux personnes à la fois. Si les missionnaires sont en infériorité numérique par rapport aux cannibales, ces derniers les mangent.
Question : Modéliser le problème à l’aide d’un graphe. Tout le monde peut-il traverser sans qu’aucun missionnaire ne soit mangé ?
Notions de base
Exercice 5 : Graphes à 3 et 4 sommets
Dessiner tous les graphes à 3 et 4 sommets, à isomorphisme près.
Exercice 6 : Graphes auto-complémentaires
Déterminer tous les graphes auto-complémentaires à 1, 2, 3, 4, 5, 6 et 7 sommets. Pour les courageux : il y a 10 graphes auto-complémentaires à 8 sommets. Les trouver.
Exercice 7 : Propriété des graphes auto-complémentaires
Montrer qu’un graphe auto-complémentaire possède 4a ou 4a + 1 sommets. Réciproquement, montrer que pour tout entier a, il existe un graphe auto-complémentaire sur 4a sommets et un graphe auto-complémentaire sur 4a + 1 sommets.
Exercice 8 : Organisation d’une ligue de football
Une ligue de football contient 15 clubs. Pour des raisons de temps, on décide que chaque club ne jouera que la moitié des matchs possibles. Comment organiser le tournoi ? (On pourra commencer par étudier le cas de 7 clubs.)
Exercice 9 : Séquence de degrés
On dit qu’une séquence de nombres entiers est réalisable s’il existe un graphe dont les sommets ont exactement les degrés de la séquence.
Question 1 : Pour chaque séquence suivante, dire si elle est réalisable ou non. Si oui, dessiner un tel graphe et dire s’il est unique (à isomorphisme près) ; sinon, justifier pourquoi il n’y a pas de tel graphe.
a. (1, 2, 2, 4, 5, 5)
b. (2, 2, 2, 2, 2, 2)
c. (1, 1, 1, 1, 1, 1)
d. (3, 3, 3, 3, 3, 5)
e. (2, 2, 2, 3, 3, 3)
f. (0, 2, 2, 3, 4, 5)
g. (5, 5, 5, 5, 2, 2)
Question 2 : Donner des conditions nécessaires pour qu’une séquence soit réalisable. Sont-elles suffisantes ?
Exercice 10 : Théorème d’Havel-Hakimi
Soit G un graphe et d₁ ≤ d₂ ≤ ... ≤ dₙ les degrés des sommets de G.
Question 1 : Montrer qu’il existe un graphe H sur V = {v₁, ..., vₙ} tel que N(H)(vₙ) = {vₙ₋₁, ..., vₙ₋₁} et pour tout 1 ≤ i ≤ n, deg(vᵢ) = dᵢ.
Question 2 : Montrer qu’une suite d’entiers (d₁, ..., dₙ) telle que d₁ ≤ d₂ ≤ ... ≤ dₙ est une séquence de degrés si et seulement si ou bien S = (0) ou bien la suite S′ définie ci-dessous est une séquence de degrés : S′ = (d′₁, ..., d′ₙ₋₁) avec d′ᵢ = dᵢ si 1 ≤ i ≤ n - dₙ - 1 et d′ᵢ = dᵢ - 1 si n - dₙ ≤ i ≤ n - 1.
Exercice 11 : Jeux de mains
Le tout-Grenoble se retrouve lors du vernissage d’une exposition dans une galerie d’art contemporaine locale. Certaines des personnes présentes se connaissent, d’autres pas. La plus élémentaire des politesses veut que les personnes qui se connaissent se serrent la main.
Question : Démontrer qu’il existe au moins deux personnes qui ont serré le même nombre de mains.
Exercice 12 : Le professeur McBrain
Le professeur McBrain et son épouse Muriel donnent une surprise-partie à laquelle ils invitent 4 autres couples mariés. À l’arrivée, certaines paires de personnes se sont serrées la main (aucun couple marié ne se serre la main). À la fin de la soirée, le professeur demande à chacune des 9 personnes combien de personnes elles ont serré la main et obtient 9 réponses différentes.
Question : À combien de personnes Muriel a-t-elle serré la main ?
Exercice 13 : Graphe 3-régulier non complet
Dessiner un graphe 3-régulier qui ne soit pas le graphe complet K₄.
Exercice 14 : Conseil municipal
Le conseil municipal d’une ville comprend 7 commissions, qui obéissent aux règles suivantes :
— Règle 1 : tout conseiller municipal fait partie de 2 commissions exactement ;
— Règle 2 : deux commissions quelconques ont exactement un conseiller en commun.
Question : Combien y a-t-il de membres dans le conseil municipal ?
Exercice 15 : Étudiants et cartes postales
Sept étudiants partent en vacances. Ils décident que chacun enverra une carte à trois autres. Est-il possible que chaque étudiant reçoive des cartes postales précisément de la part des trois personnes auxquelles il en a envoyé ?
Exercice 16 : Connexion des PCs et imprimantes
On a 13 PCs, mais seulement 6 imprimantes. On doit connecter directement les PCs aux imprimantes de sorte que les utilisateurs de 6 PCs quelconques (parmi les 13) puissent utiliser les 6 imprimantes simultanément. Le nombre minimum de liaisons nécessaires est-il 78 ? Justifier ce minimum et donner une réalisation.
Généralisation : On a p PCs et q imprimantes (p ≥ q). Trouver une architecture minimale (avec la propriété : q PCs quelconques peuvent utiliser les q imprimantes simultanément).
Représentations des graphes
Exercice 17 : Matrices d’adjacence et d’incidence
Question 1 : Représenter le graphe correspondant à la matrice d’adjacence suivante :
0 1 0 0 1
1 0 1 1 0
0 1 0 0 0
0 1 0 0 1
1 0 0 1 0
Question 2 : Les matrices suivantes sont-elles les matrices d’incidence d’un graphe simple non orienté ? Si oui, représenter ce graphe ; sinon, donner la raison.
M₁ =
1 1 0 0
1 0 0 1
0 1 0 1
M₂ =
0 1 0 1
1 0 1 1
1 1 1 0
M₃ =
0 1 1 1
1 1 0 1
1 0 1 0
M₄ =
0 1 1 0
1 1 1 1
1 0 1 1
Exercice 18 : Identification des matrices de graphe
Dans chacun des exemples suivants, dire si la matrice utilisée peut être une matrice d’adjacence, d’incidence ou ne pas représenter un graphe. Dans les deux premiers cas, dessiner un graphe correspondant ; dans le dernier cas, justifier pourquoi.
M₁ =
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
M₂ =
0 1 1 0 1
0 1 0 1 0
1 0 1 1 0
0 1 1 0 1
1 0 1 0 0
M₃ =
0 1 0 0 1 0
1 0 1 0 0 1
0 1 0 1 0 1
0 0 1 0 1 0
1 0 1 1 0 0
0 1 0 0 0 1
M₄ =
0 1 1 0 0 1 0
1 0 0 1 0 0 1
1 0 0 0 1 0 1
0 1 0 0 0 1 0
0 0 1 0 0 0 1
1 0 0 1 0 0 0
0 1 1 0 1 0 0
Exercice 19 : Algorithmes pour voisins communs
Question 1 : Pour les deux représentations (matrice d’adjacence et listes d’adjacence), donner un algorithme permettant de déterminer si deux sommets donnés i, j ont au moins un voisin commun (autre que i et j, si i et j sont voisins).
Question 2 : Donner le temps de calcul de chacun de ces algorithmes. Discuter des cas où l’un est meilleur que l’autre.
Exercice 20 : Analyse de représentations graphiques
Chaque colonne du tableau suivant représente un graphe différent, avec une représentation différente.
Pour chaque cas, répondre aux questions suivantes (sans passer par une autre représentation) :
1. Quelle représentation du graphe a-t-on ?
2. Quels sont les voisins du sommet 1 ?
3. Quel est le nombre de voisins du sommet 4 ?
4. Est-ce que le sommet 5 est isolé ?
5. Combien y a-t-il d’arêtes dans le graphe ?
6. Les sommets 3 et 4 sont-ils adjacents ?
Exercice 21 : Compléter un tableau de représentations
Compléter le tableau suivant :
Définition ensembliste | Représentation graphique | Matrice d’adjacence | Matrice d’incidence | Liste d’adjacence
V = {1, 2, 3, 4, 5} | E = {12, 45, 34, 14, 35}
—1 : [2, 3, 5]
—2 : [1, 4]
—3 : [1, 5]
—4 : [2, 5]
—5 : [1, 3, 4]