Théorie des graphes : Td1 theorie des graphes m2 iup miage f12 fe2
Télécharger PDFTD no 1 – Théorie des graphes
1. Un graphe G d’ordre 7, à 10 arêtes, a six sommets de degré 2 et un sommet de degré 4. Que vaut b ?
De plus, si l’on considère que G est simple, que vaut b ?
2. Soit G un graphe d’ordre 12, à 14 arêtes, dont les sommets sont de degré 2 ou 3. Combien G a-t-il de sommets de degré 2 ?
3. Vous invitez 5 personnes. À chacune vous demandez combien d’invités elle connaît. Vous obtenez 5 réponses différentes. Est-ce possible ?
4. Montrer que parmi 6 personnes, il y en a au moins 3 qui se connaissent mutuellement ou au moins 3 qui ne se connaissent pas mutuellement. (Par mutuellement, on entend deux à deux.)
5. Montrer que tout graphe non orienté simple d’ordre n, n ≥ 2, a au moins deux sommets de même degré.
6. Un graphe non orienté simple d’ordre 4 peut-il avoir trois sommets de degré 3 et un sommet de degré 1 ?
7. On dit qu’une suite d’entiers naturels k₁, ..., kₙ est graphique s’il existe un graphe non orienté simple d’ordre n tel que ses sommets x₁, ..., xₙ ont respectivement les degrés k₁, ..., kₙ.
Les suites ci-dessous sont-elles graphiques ?
• 5, 5, 4, 4, 3, 3, 3, 1, 0, 0
• 7, 6, 2, 2, 2, 1, 0, 0
• 5, 3, 3, 3, 2, 2, 1, 1
• 3, 3, 2, 2, 2, 2, 1
Montrer que pour tout x ∈ {0, 1, 2, 3, 4, 5}, la suite x, 1, 2, 3, 5, 5 n’est pas graphique.
Théorème 1 (Havel-Hakimi) : une suite décroissante d’entiers naturels k₁ ≥ ... ≥ kₙ avec n ≥ 2 et k₁ ≥ 1 est graphique si et seulement si la suite k₂ − 1, k₃ − 1, ..., k_{k₁ + 1} − 1, k_{k₁ + 2}, ..., kₙ est graphique. (On a supprimé k₁, puis on a retranché 1 aux k₁ premiers termes.)
Ce théorème fournit un algorithme pour déterminer si une suite est graphique ou non.
8. Dessiner un graphe non orienté simple dont l’ensemble des degrés des sommets est {0, 4, 5}.
9. Le complément d’un graphe non orienté simple G = (X, E, φ) est le graphe Gᶜ = (X, Eᶜ, φᶜ) tel que deux sommets sont adjacents dans Gᶜ si et seulement s’ils ne sont pas adjacents dans G.
9.1. Comment formuler le problème de l’exercice 4 en termes de graphe utilisant la notion de graphes complémentaires ?
9.2. Un graphe G non orienté simple est dit autocomplémentaire si G est isomorphe à Gᶜ. Montrer que si G, d’ordre n, est autocomplémentaire, alors n ≡ 0 ou 1 modulo 4.
10. Soit A = {0, 1, 2, 3, 4}. Le graphe de Petersen est le graphe non orienté défini comme suit : les sommets sont les paires d’éléments de A et xy est une arête si et seulement si x ∩ y = ∅. Par exemple, {0,1} et {2,3} sont adjacents, et {0,1} et {1,3} ne sont pas adjacents.
Déterminer l’ordre de ce graphe, le degré de chaque sommet, le nombre d’arêtes et le diamètre de ce graphe.
Dessiner ce graphe. Est-il planaire ? Quel est son nombre chromatique ?
11. Un chimiste veut transporter des produits chimiques A, B, C, D, E, F, X dans des caisses. Mais certains produits ne peuvent se côtoyer sous peine de réaction dangereuse : A, B, C réagissent entre eux ; A et E réagissent ; A et F réagissent ; A et D réagissent ; et D et X réagissent avec C, E, F.
Trouver le nombre minimal de caisses nécessaires au transport.
12. Un commissariat doit effectuer 8 surveillances selon des horaires fixés par le tableau suivant :
| surveillance | no 1 | no 2 | no 3 | no 4 | no 5 | no 6 | no 7 | no 8 |
|---|---|---|---|---|---|---|---|---|
| début | 5 | 15 | 8 | 7 | 3 | 13 | 11 | 19 |
| fin | 10 | 18 | 18 | 12 | 14 | 21 | 20 | 23 |
Quel sera le nombre minimal de policiers nécessaires ? (Remarque : dans les horaires de début et de fin sont comptabilisés les déplacements depuis ou vers le commissariat.)
13. Soit G un graphe non orienté simple d’ordre n. Montrer que si G est biparti, alors m ≤ n²/4.
14. Trouver une représentation planaire du graphe K₅ − e, où e est une arête quelconque de K₅.
15. Soit χ(G) le nombre chromatique d’un graphe simple. L’algorithme glouton de coloration des sommets consiste à suivre une liste des sommets et à les colorier dans l’ordre avec le plus petit entier disponible.
Appliquer cet algorithme sur les graphes suivants : G, H, Γ.
Cet algorithme donne-t-il toujours le nombre chromatique ?
FAQ
1. Qu’est-ce qu’un graphe biparti ?
Un graphe biparti est un graphe dont l’ensemble des sommets peut être divisé en deux sous-ensembles disjoints tels qu’aucune arête ne relie deux sommets du même sous-ensemble.
2. Comment déterminer si une suite est graphique ?
On utilise le théorème de Havel-Hakimi : une suite est graphique si la suite obtenue après suppression du premier terme et soustraction de 1 des k₁ premiers termes est également graphique.
3. À quoi sert le nombre chromatique d’un graphe ?
Le nombre chromatique χ(G) d’un graphe simple représente le plus petit nombre de couleurs nécessaires pour colorier les sommets de G de sorte que deux sommets adjacents n’aient pas la même couleur.