Optimisation Combinatoire et Graphes Exercices et Solutions PDF

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

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

GRAPHES - EXERCICES CORRIGES. Compilation réalisée à partir d'exercices de BAC TES. Exercice n°1. Un groupe d'amis organise une randonnée dans les Alpes. On a

Introduction à la théorie des graphes

– Les graphes par l'exemple [2] est comme [1] accessible à des lycéens mais il contient en plus des exercices corrigés. – Introduction to graph theory [6] est

graphes.pdf

2.4 corrigés exercices . quels graphes sont connexes? A et C A et B B et C ✄. ✂. ✁. B et D. A. B. C. D s1 s2 s4 s3.... s1 s2 s5 s4 s3 s1 s2 s3.

Exercices dexamen sur les graphes (niveau L3) avec corrigés

Exercices d'examen sur les graphes (niveau L3) avec corrigés. 1) Exploration d'un graphe. Pour ce graphe non orienté à 14 sommets les voisins de chaque.

É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 corrigés théorie des graphes pdf

Théorie des graphes Exercices corrigés Pr. Fattehallah Ghadi QCM (la bonne solution est repérée par une étoile) 1)Qu'est ce qu'un parcours Eulérien !

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

29 août 2016 ... 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 ...

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

Exercice 7. Pour chacun des graphes simples non orientés suivants donner un exemple d'existence ou prouver l'inexistence. a) Un graphe biparti

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

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

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

Exercice 11. Soit G un graphe simple ayant n sommets et n ? 1 arêtes qui n'est pas un arbre. (On suppose qu'un sommet isolé est un arbre "trivial".).

graphes

1.4 corrigés exercices . 2 graphe connexe trajet Eulérien et algorithme d'Euler ... 3 graphe orienté

É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 corrigés sur probl`emes NP-complets

12 sept. 2018 V fonctionne bien en temps polynomial. — Graphe Hamiltonien est dans NP. Comment comparer les probl`emes. Soient A et B deux probl` ...

Introduction à la théorie des graphes

1.12.4 Coloration des sommets d'un graphe planaire . Par manque de place dans ce fascicule les corrigés des exercices sont disponibles gratuite-.

Introduction à la théorie des graphes

Exercice. Soit G un graphe simple orienté d'ordre n de matrice d'adjacence M. Mon- trer que si Mn n'est pas nulle

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

GRAPHES - CORRECTION - AlloSchool

Exercice n°14 1) Les sommets du graphes étant les villes et les arêtes étant les liaisons un graphe représentant la situation est : Il existe au moins un vol de chaque ville Vi vers chaque ville Vj i j? comportant au plus deux escales car le diamètre du graphe est égal à 3 3) a) La matrice M associée à ce graphe est

Exercices corrigés -Théorie des graphes - exercices théoriques

Exercices de théorie des graphes Année académique 2020 2021 Parconventiontouslesgraphesdecesnotessontsupposés?nis Manipulations de base Exercice1 Ilexistequatregroupessanguins:-ABpourlespersonnesayantdesantigènesAetB-ApourlespersonnesayantdesantigènesAmaispasd’antigènesB-BpourlespersonnesayantdesantigènesBmaispasd’antigènesA

Compilation réalisée à partir d’exercices de BAC TES

GRAPHES - EXERCICES CORRIGES CORRECTION Exercice n°1 1) a) Recopier et compléter le tableau suivant : Sommets B C D F N T Degré des sommets du graphe 2 4 4 5 3 4 (Rappel : le degré d’un sommet est égal au nombre d’arêtes dont ce sommet est l’extrêmité) b) Justifier que le graphe est connexe

Images

Essayez d’exprimer (et non nécessairement de résoudre ) en termes de graphes les problèmes suivants : ? (o) Peut-on placer huit dames sur un échiquier sans qu’aucune d’elles ne puisse en prendre une autre ? ? (o) Un cavalier peut-il se déplacer sur un échiquier en passant surchacune des cases une fois et une seule ?

Optimisation Combinatoire et Graphes

Exercices et Solutions

Zoltán Szigeti

Myriam Preissmann

30 avril 2018

Table des matières1 Graphes non orientés5

1.1 Exercices d"échauffement . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 8

1.2 Chaînes, cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 17

1.3 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 24

1.4 Graphes hamiltoniens . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 28

1.5 Graphes eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 32

1.6 Coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 39

1.7 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60

1.8 Arbre couvrant de coût minimum . . . . . . . . . . . . . . . . . . . . . .. . . . . 68

2 Graphes orientés89

2.1 Degré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

2.2 Chemins, Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 94

2.3 Graphes orientés sans circuit . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 101

2.4 Arborescences et l"algorithme de Marquage Orienté . . . .. . . . . . . . . . . . . 104

2.5 Algorithmes spécifiques de Marquage Orienté . . . . . . . . . .. . . . . . . . . . 114

2.6 Arborescences : paquage et recouvrement . . . . . . . . . . . . .. . . . . . . . . 121

2.7 Arborescence couvrante de coût minimum . . . . . . . . . . . . . .. . . . . . . . 124

2.8 Graphes orientés eulériens . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 134

2.9 Forte connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 138

2.10 Tournois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 152

2.11 Plus courts chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 155

2.12 Applications des plus courts chemins . . . . . . . . . . . . . . .. . . . . . . . . . 183

2.13 Ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 187

4TABLE DES MATIÈRES

Chapitre 1Graphes non orientés

Ungraphe (non orienté)Gest constitué de deux ensembles : un ensemble fini et non

videVdont les éléments sont appeléssommets, et un ensemble finiEdont les éléments sont

appelésarêtes. A chaque arête est associée une paire (non ordonnée) de sommets deGnon nécessairement distincts. On noteG= (V,E). Généralement, étant donné un grapheG,on noteraV(G)l"ensemble de ses sommets,E(G)l"ensemble de ses arêtes,nle nombre de ses sommets etmle nombre de ses arêtes. Si les sommetsuetvsont associés à l"arêteealors on dit queerelie(ouconnecte)uetvet que lesextrémitésdeesontuetv,on dira aussi queuetvsontadjacentsouvoisins. Une arêteeestincidenteà un sommetvsivest une extrémité dee.Deux arêtes incidentes à un même sommet sontadjacentes. Un sommet est

isolés"il n"existe pas d"arête incidente à ce sommet. Une arête dont les extrémités sont égales

est appeléeboucle. Une arêtees"appellemultiples"il existe une autre arêtee??=ereliant les mêmes sommets quee; dans ce cas on dira aussi queeete?sontparallèles. Ungraphe simple est un graphe sans boucle et sans arête multiple. Dans le cas d"un graphe simple chaque arêtee

est caractérisée par ses deux extrémités distinctes; si lesextrémités deesontuetvon notera

e=uvou indifféremmente=vu. On peut représenter un graphe par un dessin : à chaque sommet est associé un point et à

chaque arête est associée une courbe qui relie ses extrémités et qui ne passe par aucun autre

sommet du graphe. Voir l"exemple de laFig.1.1. arête u ve sommet x y zw

V(G) ={x,y,z,u,v,w}

E(G) ={a,b,c,d,e,f,g,h,i}a

b cd f g h i

Figure1.1 - Un graphe non-orientéG.

Dans un grapheGsans boucle, le nombre d"arêtes incidentes à un sommetudeGest appelé degrédeudansG,on le notedG(u)oud(u)s"il n"y a pas d"ambiguïté. Étant donné un sous- ensembleXde sommets deG,ledegrédeXnotédG(X)(oud(X)) est le nombre d"arêtes entreXetV\X,autrement ditd(X) =|δ(X)|.Remarquons que siXcontient un seul sommetu

alors le degré deXet le degré deusont égaux, c"est à dired({u}) =d(u).Pour deux ensembles

6CHAPITRE 1. GRAPHES NON ORIENTÉS

XetYde sommets deG,d(X,Y)dénote le nombre d"arêtes entre les deux ensemblesX\Y etY\X.Le degré maximum deGest notéΔ(G)= max{d(v) :v?V}.Le grapheGest dit k-réguliersid(v) =kpour chaque sommetvdeG. Remarque 1SiGest un graphe simple ànsommets alors pour chaque sommetvdeGon a SoitG= (V,E)un graphe. SoitX?V.L"ensemble des sommets deV\Xqui ont au moins un voisin dansXest appelévoisinagedeXet est notéNG(X). Notons que siGest simple, alorsdG(X) =|NG(X)|.On appellesous-graphe deGinduit parX, le graphe notéG[X]

dont l"ensemble des sommets est égal àXet où deux sommets sont reliés s"ils sont reliés dans

G; en d"autres termesG[X] = (X,E?)avecE?={e=uv?E:u?X, v?X}(Fig.1.2 (a)). Étant donnéF?E,on appellegraphe partiel deGinduit parF, le graphe noté

G(F)dont l"ensemble des sommets est égal àVet dont l"ensemble des arêtes est égal àF; en

d"autres termesG(F) = (V,F)(Fig.1.2 (b)). Un graphe partiel d"un sous-graphe deGest un sous-graphe partieldeG(Fig.1.2 (c)).

Gsous-grapheG[X]

X(a) G F (b) graphe partielG(F)

Gsous-graphe partielG[X](F)

F X(c) Figure1.2 - (a) un sous-graphe, (b) un graphe partiel, (c) un sous-graphe partiel. Pour un ensembleS?V,lacoupe définie parSest l"ensemble des arêtes deGreliantS etV\S,on la noteδG(S)ouδ(S)s"il n"y a pas d"ambiguïté (Fig.1.3). On remarque que par

la symétrie de la définition,δG(S) =δG(V\S).On dira qu"un ensembleQd"arêtes deGest une

coupe deGs"il existe une partition des sommets en deux sous-ensemblesSetV\Stelle que

Qest l"ensemble des arêtes deGreliantSetV\S.

SoitXun sous-ensemble de sommets deG,le graphe obtenu à partir deGparsuppression deX, notéG-X,est le grapheG[V\X].SiX={v}, alors on pourra écrireG-và la place deG- {v}.Le graphe obtenu à partir deGparcontraction deX, notéG/X, est le graphe dont l"ensemble des sommets est égal à(V\X)? {x}oùxest un nouveau sommet, et dont 7 S

δ(S)

Figure1.3 - Les arêtes en gras représentent la coupe définie parS.

l"ensemble des arêtes s"obtient à partir deEen supprimant les arêtes dont les deux extrémités

appartiennent àXet en remplaçant chaque arête d"extrémitésu?Xetv?V\Xpar une arête d"extrémitésxetv.(Fig.1.4) x v1 v 2 v 3v4v 5v 6v1 v 2 v 3 Xe 1 e 2 e 3e 4e 5 e 6e 5e1
e 2e 3e 4 (a) (b) Figure1.4 - (a) Un grapheGet un ensemble de sommetsX,(b) le graphe contractéG/X.

Remarque 2Le graphe contracté peut avoir des arêtes multiples même si le graphe initial n"en

avait pas. SoitFun sous-ensemble d"arêtes deG,le graphe obtenu à partir deGparsuppression de F, notéG-Fest le grapheG(E\F).SiF={e}, alors on pourra écrireG-eà la place de G- {e}.Soientxetydeux sommets deG, on noteG+xyle graphe obtenu à partir deGen ajoutant une arête d"extrémitésxety. Uneétoileest un graphe simple dont l"ensemble des arêtes relie un sommet particulier à tous les autres sommets. Legraphe completànsommets notéKnest le graphe simple àn sommets dont toutes les paires de sommets sont reliées par une arête (Fig 1.5).

K1K2K3K4

Figure1.5 - Les graphes complets à1,2,3et4sommets. On dit que deux graphes simplesG= (V,E)etH= (V?,E?)sontisomorphess"il existe une bijection :?:V-→V?telle queuv?Esi et seulement si?(u)?(v)?E?.

Lecomplémentaire

Gd"un graphe simpleG= (V,E)est le grapheG:= (V,E?)oùuv?E? si et seulement siuv /?E,pour tout couple(u,v)de sommets deG.

8CHAPITRE 1. GRAPHES NON ORIENTÉS

Remarque 3Puisque le graphe induit par la réunion disjointe des arêtesdeGet de

Gest un

graphe complet ànsommets, pour chaque sommetvdeG, le nombre d"arêtes deGincidentes à vplus le nombre d"arêtes de Gincidentes àvest égal àn-1, c"est-à-diredG(v)+dG(v) =n-1. Pourn≥k≥0,Ckndénote le nombre de sous-ensembles àkéléments d"un ensemble àn

éléments. On rappelle queCkn=n!

k!(n-k)!.

1.1 Exercices d"échauffement

Exercice 1(a) Quels graphes sont-ils isomorphes parmi ceux de laFig.1.6?

G1G2G3

Figure1.6 - Les graphesG1,G2etG3.

(b) Même question pour les graphes de laFig.1.7.

G1G2G3

Figure1.7 - Les graphesG1,G2etG3.

Solution (a)G1etG3sont isomorphes comme le montre laFig.1.8. 1 1 G 3G123 456

46 25 3

Figure1.8 - La bijection qui montre l"isomorphisme deG1etG3. Par contre,G1etG2ne sont pas isomorphes :G1ne contient pas deK3alors queG2en contient. Par conséquent, puisqueG1etG3sont isomorphes,G2etG3ne le sont pas. (b)G1etG3sont isomorphes comme le montre laFig.1.9.

1.1. EXERCICES D"ÉCHAUFFEMENT9

G11 2 34
567
8

910G1G31

2 3 4 56789
10 Figure1.9 - La bijection qui montre l"isomorphisme deG1etG3. Par contre,G1etG2ne sont pas isomorphes :G1ne contient pas de deux sommets non adjacents qui ont deux voisins communs alors queG2en contient. Par conséquent, puisqueG1 etG3sont isomorphes,G2etG3ne le sont pas.?

Exercice 2Pour chacune des suites indiquées ci-dessous, décider si elle représente la liste des

degrés des sommets d"un graphe simple. (a)7,6,5,4,3,2,1, (b)6,6,5,4,3,3,1, (c)3,3,2,1,1, (d)3,3,2,2, (e)5,4,3,1,1,1,1, (f)4,2,1,1,1,1, (g)1,2,2,3,4,4,5,6,6, (h)1,1,1,2,2,2,3,3,3. Solution (a)Non. En effet, cette suite contient7valeurs, un tel graphe aurait donc7sommets

et, d"après la Remarque 1, le degré de chaque sommet serait inférieur ou égal à6,or cette suite

contient7. (b)Non. En effet, cette suite contient7valeurs, un tel graphe aurait alors7sommets dont deux de degré6.Chacun de ces deux sommets serait donc relié à tous les sommets (sauf lui-

même), ainsi tous les sommets seraient de degré supérieur ouégal à2;or cette suite contient la

valeur1, on aboutit à une contradiction. (c)Oui : voirFig.1.10 (c). (d)Oui : voirFig.1.10 (d). (e)Non. Supposons par l"absurde queGest un graphe simple tel que les degrés deGsoient

5,4,3,1,1,1,1.Par l"Exercice 4, le nombre d"arêtes deGest égal à la somme des degrés des

sommets divisée par2, donc8.En supprimant les quatre sommets de degré1on supprime au

plus quatre arêtes. Il reste donc trois sommets et au moins quatre arêtes, ce qui est impossible

dans un graphe simple. (f)Oui : voirFig.1.10 (f).quotesdbs_dbs10.pdfusesText_16

[PDF] Optimisation Combinatoire et Graphes Exercices et Solutions

Optimisation Combinatoire et Graphes

Exercices et Solutions

Zoltán Szigeti

Myriam Preissmann

30 avril 2018

Table des matières1 Graphes non orientés5

1.1 Exercices d"échauffement . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 8

1.2 Chaînes, cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 17

1.3 Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 24

1.4 Graphes hamiltoniens . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 28

1.5 Graphes eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 32

1.6 Coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 39

1.7 Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .60

1.8 Arbre couvrant de coût minimum . . . . . . . . . . . . . . . . . . . . . .. . . . . 68

2 Graphes orientés89

2.1 Degré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

2.2 Chemins, Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 94

2.3 Graphes orientés sans circuit . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 101

2.4 Arborescences et l"algorithme de Marquage Orienté . . . .. . . . . . . . . . . . . 104

2.5 Algorithmes spécifiques de Marquage Orienté . . . . . . . . . .. . . . . . . . . . 114

2.6 Arborescences : paquage et recouvrement . . . . . . . . . . . . .. . . . . . . . . 121

2.7 Arborescence couvrante de coût minimum . . . . . . . . . . . . . .. . . . . . . . 124

2.8 Graphes orientés eulériens . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 134

2.9 Forte connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 138

2.10 Tournois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 152

2.11 Plus courts chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 155

2.12 Applications des plus courts chemins . . . . . . . . . . . . . . .. . . . . . . . . . 183

2.13 Ordonnancement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 187

4TABLE DES MATIÈRES

Chapitre 1Graphes non orientés

V(G) ={x,y,z,u,v,w}

E(G) ={a,b,c,d,e,f,g,h,i}a

Figure1.1 - Un graphe non-orientéG.

6CHAPITRE 1. GRAPHES NON ORIENTÉS

Gsous-grapheG[X]

Gsous-graphe partielG[X](F)

Qest l"ensemble des arêtes deGreliantSetV\S.

δ(S)

K1K2K3K4

Lecomplémentaire

8CHAPITRE 1. GRAPHES NON ORIENTÉS

Gest un

éléments. On rappelle queCkn=n!

1.1 Exercices d"échauffement

G1G2G3

Figure1.6 - Les graphesG1,G2etG3.

G1G2G3

Figure1.7 - Les graphesG1,G2etG3.

46 25 3

1.1. EXERCICES D"ÉCHAUFFEMENT9

910G1G31

5,4,3,1,1,1,1.Par l"Exercice 4, le nombre d"arêtes deGest égal à la somme des degrés des