Corrigé de linterrogation de théorie des graphes G : D A E G H F G PDF

GRAPHES - EXERCICES CORRIGES. Compilation réalisée à partir d'exercices de BAC TES On a représenté par le graphe ci-dessous les sommets B C

Introduction à la théorie des graphes Solutions des exercices

Le nombre minimum de véhicules est le nombre minimum de chemins passant par tous les sommets du graphe. Exercice 70. Corrigé abrégé : 1. Oui. Preuve par

Exercices Corrigés

Théorie de graphes. 2ème année LMD. 50. Exercices Corrigés. Exercice 1 : Trois enseignants E1 E2

ÉLÉMENTS DE THÉORIE DES GRAPHES QUELQUES

Exercice 1. (o) Construire un graphe orienté dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs représentent la relation « être diviseur

Exercices de théorie des graphes Année académique 2020 ? 2021

Exercices de théorie des graphes Exercice 1. ... graphe ligne L(G) comme le graphe ayant m sommets v1...

Livret dexercices Théorie des Graphes et Recherche Opérationnelle

Cette série s'étoffera au cours du temps. Elle contient aussi les exercices donnés lors des contrôles des années précédentes. 1 Environnement des graphes.

Corrigé : Théorie des graphes I

Corrigé : Théorie des graphes I. Exercice 1. Peut-on construire un graphe simple ayant : a) 4 sommets et 6 arêtes b) 5 sommets et 11 arêtes.

Corrigé Examen - Théorie des graphes - Exercice n°=1 : (5 pts) 82

11 Mar 2021 Corrigé Examen - Théorie des graphes -. Exercice n°=1 : (5 pts). 1. Représentez cette situation par un graphe d'ordre 8 dont les sommets ...

Corrigé de linterrogation de théorie des graphes G : D A E G H F G

Conclusion : il y a au moins deux sommets de même degré. Exercice 6. Tous les sommets de Kn (graphe complet `a n sommets) sont de degré n?1 et Kn est connexe

Théorie des Graphes - TD n°1

Théorie des Graphes – TD 1 Un graphe d'intervalles est composé des sommets 1…n tel que il y a une arête entre un sommet i et j ... Corrigé Exercice 1.

Maths discretes, 2011-2012 Universite Paris-Sud

Corrige de l'interrogation de theorie des graphes

Exercice 1.On constate que les listes de degres dansGetG0sont les m^emes. En nous aidant des degres (qui doivent ^etre egaux dans les 2 cas), appelons : { dansG:s1=E,s2=B,s3=C,s4=D,s5=F, { dansG0:s1=A0,s2=E0,s3=D0,s4=F0,s5=C0. On a alors quesisjest une ar^ete dansGsi et seulement sisisjest une ar^ete dansG0. Conclusion :

GetG0sont isomorphes.

Exercice 2.Si on applique l'algorithme de distance en partant deA, on obtient le resultat ci-dessous.G :2 D(0) A C(5) (4)B (1) E (2)G(1)(2)H F (3)On en deduit que le distance deAversCest 5. Recherche des chemins minimaux :

C(5) D(4) F(3) H(2) G(1) A(0)

C(5) D(4) F(3) E(2) G(1) A(0)

C(5) D(4) F(3) E(2) B(1) A(0)

Il y a 3 chemins de plus courte longueur deAversC: AGHFDC, AGEFDC et ABEFDC,. Exercice 3.Si on applique l'algorithme de distance/connexite en partant deA, on obtient le resultat ci-dessous. On en deduit queG3 est connexe, et que la composante connexe deAest G

3tout entier.

3G :B (3)

C (4)

D (2)A (0)

I (5) H (1) G (2) F (5) E (1)Exercice 4.Voici deux graphes simples ayant chacun 5 sommets et 8 ar^etes. Ils ne sont pas isomorphes car ils n'ont pas la m^eme liste de degres (la liste des degres des sommets est 3, 3,

3, 3, 4 pour celui de gauche et 2, 3, 3, 4, 4 pour celui de droite). Ils sont connexes comme le

montre l'algorithme de distance/connexite (applique au sommet etiquete (0) dans chacun des graphes). (0) (1)(1) (1) (1)(0) (1) (1)(1)(1) Exercice 5.S'il existe un sommet de degren1 dans un graphe simple ansommets, ce sommet est voisin de tous les autres, donc les autres sommets ont un degre superieur ou egal a

1. Il ne peut donc pas y avoir a la fois un sommet de degren1 et un sommet de degre 0.

SoitGun graphe simple ansommets, et notonsd1;:::;dnles degres des sommets. S'il n'y a pas de sommet de degre 0, les entiersd1;:::;dnappartiennent a l'ensemblef1;2;:::;n1g. On a doncnentiers dans un ensemble den1 elements, par consequentd1;:::;dnne peuvent pas ^etre tous dierents. De m^eme, s'il n'y a pas de sommet de degren1, lesnentiersd1;:::;dn appartiennent a l'ensemblef0;1;:::;n2g, qui an1 elements, par consequentd1;:::;dnne peuvent pas ^etre tous dierents. Conclusion : il y a au moins deux sommets de m^eme degre. Exercice 6.Tous les sommets deKn(graphe complet ansommets) sont de degren1, etKn est connexe (tous les sommets sont voisins). Selon le theoreme d'Euler,Kna un cycle eulerien si et seulement sin1 est pair, autrement dit si et seulement sinest impair. Exercice 7.On modelise la situation par le graphe dont les sommets sont les pays et il y a une ar^ete entre deux pays s'ils ont une frontiere commune. On obtient le graphe ci-dessous. La question revient a savoir s'il existe un chemin eulerien (chemin passant une fois et une seule par chaque ar^ete) entre A et Z. Or ce graphe a 6 sommets de degre impair (A, B, D, E, G, Z) donc, par le theoreme d'Euler, il n'existe pas de chemin eulerien. Conclusion : il n'existe pas d'itineraire repondant a la volonte du voleur.AZ DFH B E CI GExercice 8.On modelise la situation par le graphe dont les sommets sont les regions et il y a une ar^ete entre deux regions si elles ont une frontiere commune. On obtient le graphe ci-dessous. La question revient a savoir s'il existe un chemin hamiltonien (chemin passant une fois et une seule par chaque sommet). Le graphe a 8 sommets, et les sommets sont de degre 4 ou 5 donc, par le theoreme de Dirac, il existe un cycle hamiltonien. Conclusion : il existe un circuit repondant au souhait du guide (on peut en donner un { bien que l'exercice ne le demande pas { par exemple ACBDEFGH est un chemin hamiltonien, et ACBDEFGHA est un cycle hamiltonien). B A CH E GD Fquotesdbs_dbs5.pdfusesText_9

[PDF] Corrigé de linterrogation de théorie des graphes G : D A E G H F G

GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir