[PDF] Optimisation Combinatoire et Graphes Exercices et Solutions PDF konyv.pdf

30 avr 2018 · GRAPHES NON ORIENTÉS Exercice 21 Dans un graphe G, soient s et t deux sommets distincts Montrer qu'il existe une (s, t)-chaîne dans G

GRAPHES - EXERCICES CORRIGES Le graphe probabiliste sera constitué de deux sommets A et B origines et extrémités de deux arètes orientées et

[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 de »

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

1 Graphes non orientés établi dans l'exercice 7, un tel graphe doit posséder un nombre pair de sommets, le réseau Corrigé en partant du sommet 3 :

[PDF] Exercices

Contenu : graphe orienté ; matrice associée à un graphe orienté Exemple 17 : coloration de graphes - Montrer que le nombre chromatique du graphe (1) ci-

[PDF] graphes

1 4 corrigés exercices 3 graphe orienté, matrice d'adjacence, graphe étiqueté 32 3 1 activités définition 2 : (matrice d'adjacence d'un graphe non orienté )

[PDF] TD no 1

Exercice 8 Un sommet x d'un graphe non orienté connexe G est dit point d' articulation de G si G−x est non connexe Corrigé du TD no 1 Généralités sur les

[PDF] Graphes Orientés - Meilleur En Maths

Un graphe orienté est un graphe dont les arêtes sont orientées (c'est à dire Matrice associée à une graphe orienté Exercice 2 ( sujet bac Liban mai 2006)

[PDF] Exercice sur les Graphes - Moodle INSA Rouen

3) En considérant le graphe comme orienté idem question (1) et (2) avec les chemins et arcs 3 2 Circuit Soit le graphe : 1) Donner un circuit non élémentaire

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

Pour ce graphe non orienté à 14 sommets, les voisins de chaque sommet sont supposés écrits dans l'ordre croissant de leurs numéros Ainsi 0 a pour voisins 1,

[PDF] Optimisation Combinatoire et Graphes Exercices et Solutions

30 avr 2018 · GRAPHES NON ORIENTÉS Exercice 21 Dans un graphe G, soient s et t deux sommets distincts Montrer qu'il existe une (s, t)-chaîne dans G

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). (g)Non, car il y a trois nombres impairs dans cette suite or, par l"Exercice 5, dans un graphe le nombre de sommets de degré impair est pair. (h)Oui, voirFig.1.10 (h).

10CHAPITRE 1. GRAPHES NON ORIENTÉS

3v4v5v4v3v2v

1 v 6v 1 v 2v3v 4 v 5v6v 7 v 8v9 Figure1.10 - Les graphes simples dont les degrés correspondent auxsuites indiquées.? Exercice 3Montrer qu"un graphe simple ayant au moins deux sommets contient deux sommets de même degré. SolutionSoitGun graphe simple avecn≥2sommets. Par la Remarque 1, il y anvaleurs possibles pour le degré d"un sommet deG:0,1,...,n-1. Si tous les sommets sont de degrés En effet, considérons les sommetsv0etvn-1.Puisque0?=n-1,ces sommets sont distincts. De

plus : d"une partv0vn-1ne peut pas être une arête carv0n"est relié à aucun sommet, et d"autre

partv0vn-1doit être une arête carvn-1est relié à tous les sommets.?

Remarque 4L"énoncé de l"exercice précédent peut être exprimé de la manière suivante : dans

un groupe d"au moins deux individus, il y en a toujours deux qui ont le même nombre d"amis (en

supposant que l"amitié est une relation symétrique). En effet, la relation d"amitié dans le groupe

peut être modélisée par un graphe : les sommets sont les individus et deux sommets sont reliés

par une arête si les deux individus correspondants sont amis. Exercice 4Montrer que la somme des degrés des sommets d"un grapheG= (V,E)est égale à deux fois le nombre d"arêtes, c"est-à-dire v?Vd(v) = 2|E|. SolutionCalculer la somme des degrés des sommets d"un grapheGrevient à compter les arêtes

incidentes à chaque sommet et puis à ajouter ces nombres. Chaque arêteuvest comptée exacte-

ment deux fois dans la somme : une fois dansd(u)et une autre fois dansd(v).? Exercice 5SoitGun graphe. Montrer que le nombre de sommets deGde degré impair est pair. SolutionSoits1la somme des degrés des sommets de degré pair ets2la somme des degrés des sommets de degré impair. Une somme de nombres pairs est paire, doncs1est un nombre pair. On as1+s2égal à la somme des degrés des sommets deG,laquelle d"après l"Exercice 4, est paire. On en déduit ques2est un nombre pair. Or une somme de nombres impairs n"est paire que si le nombre de termes de cette somme est pair. Exercice 6(a) Montrer que le nombre d"arêtes d"un graphe completKnàn≥2sommets est égal à n(n-1) 2. (b) Montrer que le nombre deK3d"un graphe completKnàn≥3sommets est égal à n(n-1)(n-2) 6.

1.1. EXERCICES D"ÉCHAUFFEMENT11

Solution (a)Première démonstration :Le nombre d"arêtes deKnest égal au nombre de sous-

ensembles à2éléments d"un ensemble ànéléments, qui est par définition,C2n=n(n-1)

2. Deuxième démonstration :Puisque chacun desnsommets deKnest de degrén-1, la somme

des degrés des sommets est égale àn(n-1)et aussi, par l"Exercice 4, à deux fois le nombre

d"arêtes deKn. (b)Le nombre deK3deKnest égal au nombre de sous-ensembles à3éléments d"un ensemble ànéléments, qui est par définition,C3n=n(n-1)(n-2) 6.? Exercice 7Combien de graphes simples distincts peut-on définir surnsommets donnés? SolutionPour construire un grapheGsimple surnsommets donnés, il faut décider pour chaque paire de sommetsuetvsi l"on prend ou non l"arêteuv.On a donc deux choix possibles pour chaque paire, et ces choix sont indépendants. Comme le nombre de paires de sommets estC2n, on peut construire exactement2C2ngraphes simples différents surnsommets donnés.? Exercice 8Décrire l"ensembleGdes graphesGsimples sans sommet isolé tels que les arêtes deGsont mutuellement adjacentes.(1.1) SolutionNous allons montrer qu"un grapheGest dansGsi et seulement siGest soit unK3

soit une étoile. Remarquons que ces graphes appartiennent àG. Il reste à montrer que ce sont les

seuls. SoitG? G.Une arête étant une étoile, on peut supposer queGpossède deux arêteseetf.

Par (1.1), ces arêtes ont une extrémité commune, on notee=uv,f=uw.Par (1.1), pour toute

autre arêtegdeG,comme elle est adjacente mais pas parallèle àeet àf, soitgest incidente à

uet dans ce casvwne peut pas exister, soitg=vw. Par hypothèse,Gest sans sommet isolé et doncGest une étoile ouG=K3.? Exercice 9Montrer que pour un sous-ensembleXde sommets d"un grapheGon a d(X) =? v?Xd(v)-2|E(G[X])|. SolutionQuand on fait la somme des degrés des sommets dansX,chaque arête deGest comptée

autant de fois qu"elle a d"extrémités dansX.Puisque les arêtes deG[X]ont deux extrémités

dansXet que les arêtes deδ(X)ont une extrémité dansX,on obtient : v?Xd(v) = 2|E(G[X])|+|δ(X)|. Exercice 10SoientGun graphe simple contenant au moins une arête etk≥2un entier. Montrer que si pour tout sous-ensembleXde sommets deG, d(X)est un multiple dek, alors k= 2. SolutionSoituvune arête deG.D"après l"Exercice 9,

2 = 2|E(G[{u,v}])|=d(u) +d(v)-d({u,v}).

Par hypothèsed(u),d(v)etd({u,v})sont multiples dek, donc2aussi est multiple deket alors, k≥2implique quek= 2.?

12CHAPITRE 1. GRAPHES NON ORIENTÉS

XV-XYV-Y

A 1A4A 3A2

Figure1.11 - Les ensemblesA1,A2,A3,A4.

Exercice 11SoientXetYdeux sous-ensembles de sommets d"un grapheG.Montrer que d(X) +d(Y) =d(X∩Y) +d(X?Y) + 2d(X,Y).(1.2) SolutionSoientA1:=X∩Y, A2:=V(G)\(X?Y), A3:=X\Y, A4:=Y\X.Dénotons par d ij=djile nombre d"arêtes entreAietAj.VoirFig.1.11.

Alors on voit que

d(X) =d12+d14+d32+d34 d(Y) =d12+d13+d42+d43 d(X∩Y) =d12+d13+d14 d(X?Y) =d12+d32+d42

2d(X,Y) =d34+d43

d"où vient l"égalité (1.2). Remarque 5Dans un grapheGayantn≥2sommets, ou bien tous les sommets sont deux à deux adjacents et alorsGest un graphe completKn, ou bien il existe deux sommets non-adjacents et alors

Gcontient une arête c"est-à-dire unK2.

Exercice 12 (Théorème de Ramsey :K3,K3)

(a) Montrer que dans un groupe composé d"au moins6individus, ou bien il y a3individus qui se connaissent mutuellement, ou bien il y a3individus qui ne se connaissent pas du tout, ou les deux. (On suppose que si un individuAconnaît un individuB, alorsB connaîtA.) (b) La propriété de (a) reste-t-elle vraie pour un groupe de5individus? SolutionLa relation de connaissance dans le groupe peut être modélisée par un graphe : les sommets sont les individus et deux sommets sont reliés par une arête si les deux individus correspondants se connaissent. (a)L"énoncé de (a) s"exprime alors de la manière suivante : Montrer que pour un grapheG simple ayantn≥6sommets, au moins l"un des deux graphesGou

Gpossède unK3.Soitv

un sommet quelconque deG.Par la Remarque 3, le nombre d"arêtes deGincidentes àvplus le nombre d"arêtes de Gincidentes àvest égal àn-1≥5.Par conséquent, dans l"un des deux

1.1. EXERCICES D"ÉCHAUFFEMENT13

graphesGet G,il y a au moins trois arêtes incidentes àv.Supposons, sans perte de généralité, que c"est dansG,et soient doncvu1,vu2,vu3,trois arêtes deG. Deux cas sont possibles (Fig.

1.12) :

par les sommetsv,ui,ujest unK3.

G.Alors le sous-graphe deG

induit par les sommetsu1,u2,u3est unK3.quotesdbs_dbs21.pdfusesText_27

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

10CHAPITRE 1. GRAPHES NON ORIENTÉS

3v4v5v4v3v2v

1.1. EXERCICES D"ÉCHAUFFEMENT11

2 = 2|E(G[{u,v}])|=d(u) +d(v)-d({u,v}).

12CHAPITRE 1. GRAPHES NON ORIENTÉS

XV-XYV-Y

Figure1.11 - Les ensemblesA1,A2,A3,A4.

Alors on voit que

2d(X,Y) =d34+d43

Gcontient une arête c"est-à-dire unK2.

Exercice 12 (Théorème de Ramsey :K3,K3)

Gpossède unK3.Soitv

1.1. EXERCICES D"ÉCHAUFFEMENT13

1.12) :

G.Alors le sous-graphe deG