Examen de Théorie des Graphes

Lecture 10: Dijkstra’s Shortest Path Algorithm CLRS 24 3 Outline of this Lecture Recalling the BFS solution of the shortest path problem for unweighted (di)graphs The shortest path problem for weighted digraphs Dijkstra’s algorithm Given for digraphs but easily modiﬁed to work on undirected graphs 1

Exercises 1 Minimum spanning trees and shortest paths

of Dijkstra’s algorithm, all shortest paths starting at vertex r have been found The union of these paths forms a tree, which we will call the Dijkstra tree at r a Give an example of a weighted graph, whose minimum spanning tree diﬁers from all its Dijkstra trees b Prove that a minimum spanning tree and a Dijkstra tree of G always have at

Troisième partie Graphes pondérés et algorithmedeDijkstra

Correctiondel’exercice 1:Antilles2016 Des touristes sont logés dans un hôtel H Un guide souhaite faire visiter la région à ces touristes en empruntant les routes signalées comme d’intérêt touristique parl’ofﬁce dutourisme Lestronçons deroutequ’il souhaite em-prunter sont représentés sur le graphe ci-contre

Sujet et corrigé du bac en mathématiques, série ES

En utilisant l’algorithme de Dijkstra, déterminons le trajet le moins cher pour aller de A à G: Après recours à l’algorithme de Dijkstra, nous trouvons comme trajet le moins cher pour aller de l’aéroport A à l’aéroport G: le trajet A - E - D - C - G Et ce dernier coûtera: 45 + 40 + 60 + 50 = 195 €

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 représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer Une arête entre deux sommets coïncide avec l’existence d’un chemin entre les deux sommets 1) a) Recopier et compléter le tableau suivant :

Tes Devoir surveillé n°6 : Exercice 1

Exercice 2 Une usine produit deux types E et F de moteurs Le bénéfice B, exprimé en milliers d’euros, pour une production journalière de x moteurs E et y moteurs F est : B x y x y x y22, 0,05 0,08 0,6 0,7 On admet que la production totale est vendue et que 0 10ddx; 08ddy 1 Calculer le bénéfice réalisé avec a

Correction Term ES spé Devoir Surveillé 3

Exercice 2 Un parc de loisirs décide d’ouvrir une nouvelle attraction pour les jeunes enfants : un parcours pédestre où chaque enfant doit recueillir, sur diﬀérents lieux, des indices pour résoudre une énigme Le parcours est représenté par le graphe ci-dessous

Corrigé du baccalauréat ES–L Antilles–Guyane juin 2016

[Corrigé du baccalauréat ES–L Antilles–Guyane \ juin 2016 EXERCICE 1 5 points Commun à tous les candidats 1 L’équation f (x)=0 admet exactement 2 solutions, la première sur [−1 ; 1] et la deuxième sur

MATHS APPLIQUEES A LINFORMATIQUE - Introduction à la théorie

Enfin, à titre d'exercice, nous proposons quelques problèmes et applications Nous encourageons vivement le lecteur à essayer de les résoudre afin de prendre la matière bien en main Le lecteur qui veut aborder ce chapitre devrait avoir : - une maîtrise élémentaire d'un tableur de type Excel ou OpenOffice,

Examen de Théorie des Graphes - epiportalcom

Dans cet exercice on ne considère que des graphes simples, planaires, et non-orientés Pour un tel graphe G = (V, E), on note n = jVjle nombre de sommets, e = jEj/2 le nombre d’arêtes, et f le nombre de faces Le degré moyen d’un graphe est 1 n å v2V deg(v) 1 (2pts) Justiﬁez que 3f 2e Réponse :

Examen de Théorie des Graphes

EPITA ING1 2014 S2; A. DURET-LUTZ

Durée : 1 heure 30Corrigé

Document au torisé: une seule page A4 manuscrite (r ecto/verso). Cet examen se dér oulesans calculatrice, téléphone, ou autre appareil électroménager. Répondez dans l escadr esde façon clair eet concise. Le barème, in dicatif,corr espondà une note sur 26,5.

1 Graphe de Herschel (5,5 points)

On considère le graphe suivant :abc

defgh ijk. Précisez les caractéristiques de ce graphe :

1.(0,5pt)Rayon

Réponse :3

2.(1pt)Diamètre

Réponse :4

3.(0,5pt)État(s) du centre

Réponse :a,b,c,e,f,g,i,j,k(c.-à-d. tous saufdeth, dont l"excentricité est 4)4.(0,5pt)Maille

Réponse :4

5.(0,5pt)Nombre chromatique

Réponse :2

6.(0,5pt)Taille de la plus grande clique

Réponse :2

7.(2pt)Ce graphe est-il planaire? Justifiez votre réponse.

Réponse :Oui, par exemple :ab

c defgh i jk Les réponses annonçant fièrement que 18=e3n6=3116=27 rapportent (tout

aussi fièrement) 0, car j"ai insisté suffisamment souvent sur le fait que cette inégalité n"est

qu"unecondition nécessairepour qu"un graphe soit planaire.1

2 Graphes planaires (10 points)

Dans cet exercice on ne considère que des graphes simples, planaires, et non-orientés. Pour un tel

grapheG= (V,E), on noten=jVjle nombre de sommets,e=jEj/2 le nombre d"arêtes, etfle nombre de faces. Ledegré moyend"un graphe est1n v2Vdeg(v).

1.(2pts)Justifiez que 3f2e.

Réponse :SiFest l"ensemble des faces,åx2Fdeg(x) =2ecar chaque arête appartient à deux face.

D"autre part toute facexpossède au minimum 3 arêtes, donc deg(x)3 et 2e=

x2Fdeg(x)3f.2.(2pts)Un graphe planaire connexe peut-il contenir deux cliques de taille 4? Justifiez-vous.

Réponse :Sans aucun problème. Chaque 4-clique est un graphe planaire, et il n"est pas difficile de les

relier pour obtenir un graphe connexe. Par exempleOn peut ainsi construire un graphe planaire avec autant de 4-clique que l"on souhaite.

3.(2pts)OnconsidèrelegrapheG= (V,E)définiparV=f1,2,...,ngetE= (f1,2gf3,4,...,ng)[

(f3,4,...,ng f1,2g). Vers quelle valeur tend le degré moyen lorsquentend vers l"infini?

Réponse :Le sommetsf1,2gsont de degrén2, et les sommetsf3,4,...,ngsont de degré 2. Cela nous

donne un degré moyen de

2(n2)+(n2)2n

=48/nqui tend vers 4 lorsquen!¥.4.(2pts)Justifiez que le degré moyen d"un graphe planaire est strictement inférieur à 6.

Réponse :On sait que

åv2Vdeg(v) =2e. Et comme le graphe est planaire, il vérifiee3n6.

On en déduit que

1n v2Vdeg(v)6n12n <6.5.(2pts)Considérons un graphe planaire dans lequel tous les sommetsvont un degré deg(v)4. Montrez que lestrois quartsdes sommets ont forcément un degré strictement inférieur à 7.

Réponse :Preuve par l"absurde. Si trois quarts des sommets ont un degré7, alors que le dernier quart

n"a qu"un degré4 alors le degré moyen est(37+4)/4=25/4>6 ce qui contredit le fait que le graphe est planaire d"après la question précédente.3 Iso-morflons (2 points)

Le graphea

b cdefg hij est-il isomorphe au graphe 0921
7 8 536
4?

Page 2

Réponse :

Les deux graphes sont isomorphes. Voici une correspondance possible entre leurs états :

A B C D E F G H I J

0 9 2 1 7 8 5 3 6 44 Algorithme de Johnson (9 points)

(a)BC DA

367532

4 (b)x BC DA

367532

400
00 (c)x BC DA

3670h(C) =0h(A) =7h(B) =4h(D) =1(d)BC

DA 000 111
1 (e)v A B C D h(v)74 01d

A(v)0 0 1 0

B(v)1 0 1 1

C(v)0 0 0 1

D(v)1 1 1 0(f)A B C D

A0 3 8 6

B2 0 5 4

C74 01

D52 2 0L"algorithme de Johnson calcule les distancesD(u,v)pour toutes les paires de sommets(u,v)2V2

d"un graphe orientéG= (V,E,`)ne possédant pas de cycle négatif. Il fonctionne en plusieurs étapes,

illustrées par les figures ci-dessus. La figure(a)représente le graphe fourni en entrée, et le tableau(f)

est la sortie qui donne les distances pour toutes les paires.

JOHNSON(G):

J1. Ajouter un nouveau sommet xau graphe, et le connecter à tous les autres sommets, avec un poids nul. (Figure(b).) J2.quotesdbs_dbs7.pdfusesText_5

[PDF] Examen de Théorie des Graphes - epiportalcom

Examen de Théorie des Graphes

EPITA ING1 2014 S2; A. DURET-LUTZ

Durée : 1 heure 30Corrigé

1 Graphe de Herschel (5,5 points)

On considère le graphe suivant :abc

1.(0,5pt)Rayon

Réponse :3

2.(1pt)Diamètre

Réponse :4

3.(0,5pt)État(s) du centre

Réponse :4

5.(0,5pt)Nombre chromatique

Réponse :2

6.(0,5pt)Taille de la plus grande clique

Réponse :2

7.(2pt)Ce graphe est-il planaire? Justifiez votre réponse.

Réponse :Oui, par exemple :ab

2 Graphes planaires (10 points)

1.(2pts)Justifiez que 3f2e.

3.(2pts)OnconsidèrelegrapheG= (V,E)définiparV=f1,2,...,ngetE= (f1,2gf3,4,...,ng)[

2(n2)+(n2)2n

Réponse :On sait que

On en déduit que

Le graphea

Page 2

Réponse :

A B C D E F G H I J

0 9 2 1 7 8 5 3 6 44 Algorithme de Johnson (9 points)

367532

367532

3670h(C) =0h(A) =7h(B) =4h(D) =1(d)BC

A(v)0 0 1 0

B(v)1 0 1 1

C(v)0 0 0 1

D(v)1 1 1 0(f)A B C D

A0 3 8 6

B2 0 5 4

C74 01

JOHNSON(G):