[PDF] Corrigé de linterrogation de théorie des graphes G : D A E G H F G PDF corr-interroGraph.pdf

Exercice 5 S'il existe un sommet de degré n − 1 dans un graphe simple `a n sommets, ce sommet est voisin de tous les autres,

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

[PDF] É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

[PDF] GRAPHES - EXERCICES CORRIGES Compilation réalisée à partir

Exercice n°1 Un groupe d'amis organise une randonnée dans les Alpes On a représenté par le graphe ci-dessous les sommets B

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

Exercice 5 S'il existe un sommet de degré n − 1 dans un graphe simple `a n sommets, ce sommet est voisin de tous les autres,

[PDF] Exercice sur les Graphes - Moodle INSA Rouen

Livret d'exercices Théorie des Graphes et (Exercices et problèmes résolus de recherche opérationnelle, Dunod) dont les exemplaires sont disponibles à la

[PDF] Exercices

La théorie des graphes est rarement abordée en France dans le cursus universitaire Contenu : introduction des graphes (arêtes, sommets, ordre, sommets

[PDF] Corrigé : Théorie des graphes I - SportPro

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 c) 100 sommets et

[PDF] Corrigé des exercices

Corrigé des exercices • Combinatoire des graphes £ ¢ ¡ Exercice 1 a) Soit G = (V,E) un graphe non orienté simple Notons V1 l'ensemble des sommets de

[PDF] Différents problèmes en théorie des graphes

24 fév 2012 · La naissance officielle de la théorie des graphes remonte à 1741 à la calculabilité : cours et exercices corrigés, 2e cycle (Sciences SUP),”

[PDF] Théorie des Graphes

Montrer qu'il existe deux sommets ayant le même degré dans G Exercice 8 Soit G=(X,U) un graphe d'ordre n, le nombre d'arcs est

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] [PDF] Corrigé de linterrogation de théorie des graphes G : D A E G H F G

[PDF] Introduction à la théorie des graphes Solutions des exercices