[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

En colorant les arêtes de ce graphe (1 couleur = 1 heure de l'horaire), en prenant garde que cher dans le graphe des cycles reliant quatre sommets, sans diagonale En effet, un tel carré Corrigé en partant du sommet 3 : Initialisation

[PDF] Examen de Théorie des Graphes Durée 1h30 - Documents - grug

20 jui 2011 · Appliquer cet algorithme sur le graphe GMails Idée du corrigé Il faut appliquer l' algorithme tri topologique et détecter les pré-visites qui arrivent 

[PDF] Examen de Théorie des Graphes - LRDE - Epita

Examen de Théorie des Graphes EPITA ING1 2014 S2; A DURET-LUTZ Durée : 1 heure 30 Corrigé — Document autorisé : une seule page A4 manuscrite 

[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] ESIAG – UPEC – L3 - FI A – Corrigé de lexamen de théorie des

Corrigé de l'examen de théorie des graphes 2010-2011 durée 2h – sans document – 2 pages 1 (2 points) Dans un graphe orienté, on rappelle les définitions 

[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] Examen écrit de théorie des graphes

Examen écrit de théorie des graphes Janvier 2017 Consignes (1) (5 points) Soit G un graphe simple ayant n sommets et n − 1 arêtes qui n'est pas un arbre

[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] Exercice sur les Graphes - Moodle INSA Rouen

Théorie des Graphes et La liste des inscriptions aux examens est la suivante : A 2) Quel est le nombre maximal d'examen que l'on peut effectuer par jour ?

[PDF] examen corrigé thermodynamique 2

[PDF] examen corrigés sur théorème de convergence dominée

[PDF] examen csdm 2017

[PDF] examen culture d'entreprise pdf

[PDF] examen d'adéquation d'un appareil de levage

[PDF] examen d'algebre s1 smpc pdf

[PDF] examen d'aptitude professionnelle echelle 11

[PDF] examen d'informatique 1 année collège

[PDF] examen de biochimie alimentaire pdf

[PDF] examen de botanique 2eme année biologie lmd

[PDF] examen de chimie générale s1 pdf

[PDF] examen de comptabilité analytique avec corrigé pdf

[PDF] examen de fin d'études secondaires 2018

[PDF] examen de fin de module santé et sécurité

[PDF] examen de genetiquepdf

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_dbs4.pdfusesText_7