Théorie des graphes : Serie d exercices rop universite paris 8
Télécharger PDFUSTHB/FEI
Année 2015/2016 Dept :Info/ROP
SERIE D' EXERCICES ROP Exercice 1 :Un passeur doit faire passer d’une rive à l’autre d’un fleuve un chou, une chèvre et un loup. Cependant sa barque ne lui permet de transporter en sécurité qu’un seul passager à la fois. De plus, il lui est impossible, pour des raisons faciles à comprendre, de laisser seuls, la chèvre et le chou, ainsi que le loup et la chèvre. Comment peut‐il réaliser sa traversée ?
Exercice 2On a six wagons à trier. Dans la gare de triage, les wagons entrent dans l’ordre 2, 5, 3, 6, 1, 4 et doivent sortir dans l’ordre croissant. Deux wagons i et j peuvent être mis sur la même voie si et seulement s’ils entrent dans l’ordre dans lequel ils doivent sortir. Dessinez un graphe illustrant la situation, en indiquant ce que représentent les sommets et les arêtes de votre graphe. Quel sera le nombre minimal de voies nécessaires au tri ?
Exercice 3Montrer que tout graphe admet un nombre pair de sommets de degré impair. Exercice 4:Un graphe est dit régulier s’il est simple et si tous ses sommets ont le même degré. On s’intéresse dans cet exercice aux graphes réguliers dont les sommets sont de degré 3. 1. Que dire du nombre de sommets d’un tel graphe ? 2. Démontrer que, pour tout p ≥ 2, il existe un graphe régulier d’ordre 2p dont les sommets sont de degré 3. Exercice 5: La situation est‐elle identique pour les graphes dont tous les sommets sont de degre 4 Exercice 6 : Dessiner un graphe non orienté complet à 4 sommets. Quel est le degré des sommets de ce graphe ? Combien d’arêtes possède‐t‐il ? Généralisez ces résultats à un graphe simple complet ayant n sommets. Exercice 7: On considère le graphe orienté G = (S, A) tel que: S = {1, 2, 3, 4, 5}
A = {(1, 2),(1, 4),(2, 2),(2, 3),(2, 4),(3, 5),(4, 3),(5, 3)} 1. représenter graphiquement ce graphe, 2. donner le demi‐degré extérieur de 2 et le demi‐degré intérieur de 4, 3. donner les sommets prédécesseurs de 4 et les sommets successeurs de 2, 4. donner un graphe partiel et un sous‐graphe de ce graphe. Exercice 8: Montrez qu’un graphe simple a un nombre pair de sommets de degré impair. Exercice 9: Montrez que dans une assemblée de n personnes, il y a toujours au moins 2 personnes qui ont le même nombre d’amis présents. Exercice 10: Est‐il possible de relier 15 ordinateurs de sorte que chaque appareil soit relié avec exactement trois autres ? Une suite décroissante (au sens large) d’entiers est graphique s’il existe un graphe simple dont les degrés des sommets correspondent à cette suite. Par exemple, un triangle correspond à la suite (2, 2, 2). Les suites suivantes sont‐elles graphiques ? 1) (3, 3, 2, 1, 1)
2) (3, 3, 1, 1)
3) (3, 3, 2, 2)
4) (4, 2, 1, 1, 1, 1)
5) (5, 3, 2, 1, 1, 1)
6) (5, 4, 3, 1, 1, 1, 1) Trouvez deux graphes correspondant à la suite (3, 2, 2, 2, 1). Exercice13 : Est-il possible de tracer les figures suivantes sans lever le crayon (et sans passer deux fois sur le même trait !...) ? Pourquoi ?
Exercice 14Est-il possible de tracer une courbe, sans lever le crayon, qui coupe chacun des 16 segments de la figure suivante ?
Exercice15 : . Est-il possible de traverser les sept ponts de la ville de Königsberg en empruntant deux fois chaque pont, dans un sens puis dans l’autre ?
Exercice 16. Soit G un graphe non Eulérien. Est-il toujours possible de rendre
G Eulérien en lui rajoutant un sommet et quelques arêtes ?