Cette page montre quelques exercices corrigés sur la modélisation en graphe et arbres. Le but de ces exercices est d’apprendre à modéliser un problème grâce aux concepts et bases de la théorie des graphes.
Exercice 1
Deux joueurs ont 2 lots d’allumettes ou plus. A chaque tour, le joueur suivant peut retirer un certain nombre d’allumettes d’un lot (selon la règle choisie). Le joueur qui supprime la dernière allumette perd.
Modélisez ce jeu avec un graphe dans le cas où l’on dispose de deux piles contenant chacune trois allumettes, et où un joueur peut retirer une ou deux allumettes chacune.
Quel coup le premier joueur doit jouer pour gagner la partie ?
Solution
Edges are oriented from left to right. If we are in position or we win. Thus, the position verify that, whatever play your adversary, you can reach or
Exercice 2
Le graphique suivant montre les couloirs d’un musée. Un garde placé dans un couloir peut surveiller deux jonctions placées à ses extrémités. Combien de gardes sont nécessaires (et comment les placer) pour que toutes les intersections sont surveillées ?
Si nous plaçons maintenant des gardes aux intersections, en supposant qu’un garde peut surveiller tous les couloirs menant à ce carrefour, combien de gardes sont nécessaires ?
Solution
Chaque garde sera placé sur une arête et pourra surveiller deux intersections (sommets). Le graphe a 11 sommets ; il faudra au moins six gardes. Il faut donc trouver un ensemble (minimum) d’au moins six arêtes, tel que chaque sommet soit incident à au moins une de ces arêtes. Le graphique ci-dessous fournit une solution (arêtes plus épaisses).
Cette fois, les gardes sont aux sommets et surveillent les arêtes. Il doit y avoir un ensemble de sommets tel que chaque arête soit incidente à au moins un de ces sommets. Le graphique ci-dessous fournit une solution utilisant 6 sommets (sommets blancs).
Exercice 3
Skynet est un réseau à 15 sommets. Vous pouvez aller de chaque sommet à au moins sept autres sommets par lien. Peut-on passer par lien d’un sommet X à chacun des autres ?
Solution
Soit A un sommet quelconque. X est lié à au moins 7 villes différentes. Nous avons donc un réseau de 8 sommets reliés par des liens. Dans un sommet, vous pouvez également vous connecter à au moins sept autres sommets ; il y a donc un nouveau réseau de 8 sommets. Il doit y avoir un sommet partagé dans ces réseaux, car sinon le réseau aurait au moins 16 sommets. X est relié à A en au plus deux plans, par ce sommet commun ; il est relié à toutes les autres villes.
Exercice 4
Un réseau est composé de sept usines. Une ville est liée à exactement deux plantes. Deux usines partagent exactement une ville. Combien de villes sont desservies par le réseau ? Démontrer qu’un graphe complet avec sommets a n(n-1)/2 liens.
Solution
Les usines sont les sommets et les villes sont représentées par une arête reliant deux sommets. La règle 2 implique qu’il n’y a pas d’arêtes multiples et que tout couple de sommets est adjacent ; c’est-à-dire que le graphe est complet ; c’est K7, soit 21 liens.
Exercice 5
Considering the following mathematical system:
Où X est 0 ou 1. Déterminer, avec un problème de graphe, une solution qui maximise la fonction objectif (somme des X).
Solution
Un sommet représente une variable. Deux sommets sont connectés s’ils sont dans la même inégalité. Le problème est de trouver un ensemble maximum de sommets où aucun couple de sommets n’a de lien direct.
Modeling with tree
Exercice 6
Soit un graphe non orienté avec des sommets. Démontrer que toutes les propriétés suivantes sont équivalentes :
- est un arbre
- est connecté et si nous supprimons une arête, le graphe n’est plus connecté
- est connecté avec n-1 arêtes
- n’a pas de cycle jusqu’à ce que nous ajoutions une arête
- n’a pas de cycle avec n-1 arête
- un seul chemin entre n’importe quel couple de sommets
Exercise 7
Nous voulons ajouter une batterie dans un réseau. Le graphique suivant montre le coût d’envoi d’énergie entre deux sous-stations du réseau et la quantité d’énergie envoyée par une sous-station. Vous devez placer la batterie dans une sous-station tout en minimisant le coût total.
Solution
Calculez la somme de tous les coûts à chaque sous-station, c’est-à-dire le coût de chaque chemin entre n’importe quelle sous-station et la sous-station choisie (arête * sommet).
FR 
EN 
RU 
ES