[PDF] THEORIE DES GRAPHES 3) En déduire (I +

View - Download THEORIE DES GRAPHES

Previous PDF

Next PDF

ED N° 1

1

THEORIE DES GRAPHES

Notions de base

I) Soit le graphe G :

1) Donner

BABAGGGG

2) Donner les demi-degrés intérieurs et

extérieurs des sommets A et B. Donner les entrée(s) et les sortie(s) de G.

3) Donner un exemple de chemin simple mais

non élémentaire.

4) Existe-il un circuit hamiltonien dans G ?

5) G est-il fortement connexe ? Justifier en

détail.

6) Donner plusieurs arborescences différentes,

de racine B, extraites du graphe.

II) AFFAIRE DE LOGIQUE

LA TABLE POLYGLOTTE

Indication : introduire un graphe biparti.

a) UN DÎNER réunit huit personnes de nationalités différentes. Voici les langues qu'elles parlent :

Ann : anglais, français, portugais.

Biba : anglais, portugais, russe.

Charles : anglais, russe.

Dimitri : anglais, allemand, portugais, russe.

Evita: allemand, espagnol, néerlandais.

Frédéric : français, espagnol, néerlandais.

Gunther : allemand, italien.

Helena : espagnol, italien.

Complétez les cartons indiquant l'initiale des convives autour de la table ronde de sorte que : - chaque convive puisse converser avec chacun de ses deux voisins autrement que par signes. - il y ait alternance entre les hommes et les femmes. b) Même problème avec 2 tables rondes de 4 personnes. F E C D A B

ED N° 1

2

III) LA FRAGILITE DES TEMOIGNAGES

Cinq figures géométriques : un cercle, un triangle, un carré, un trapèze et un hexagone, ont été coloriées (chacune

d'une couleur différente) et montrées à Ariane et à Bruno.

On interroge, le lendemain, Ariane et Bruno en leur demandant quelle était la couleur de chaque figure : voici les

réponses :

Ariane : "le cercle était rouge, le triangle bleu, le carré blanc, le trapèze vert et l'hexagone jaune".

Bruno : "le cercle était jaune, le triangle vert, le carré rouge, le trapèze bleu et l'hexagone blanc".

Ariane s'est trompée trois fois, Bruno deux fois, mais pour chaque figure la couleur correcte à été citée par l'un ou

l'autre.

Déterminer la couleur de chaque figure.

ED N°2

3

GRAPHES : FORTE CONNEXITE

I) Déterminer les composantes fortement connexes du graphe ci-dessous :

S1 S11 S10 S9 S8

S3 S5

S2 S6 S7

II) On observe un système aux instants t = 0, 1, 2, ... ; à t, l'observation permet de déterminer l'état

du système X t OE {E 1 , E 2 , ..., E r } = E. E est donc l'ensemble des états du système.

On a affaire à une chaîne de Markov si :

Pr [X t+1 = E j I X 0 0 i E , X 1 1 i E , ..., X t = E i ] = Pr[X t + 1 = E j I X t = E i ] (propriété "sans mémoire"). De plus on suppose cette dernière probabilité indépendante de t ("homogénéité") : Pr [X t+1 = E j I X t E j ] = pij.

C'est donc la probabilité de transition de E

i vers E j entre deux instants consécutifs.

Ainsi une chaîne de Markov finie est-elle donnée par la connaissance de l'ensemble des états, E, et par celle des

probabilités de transition : M = [pij]

EXEMPLE E = {E1 , E2 , ... , E12}

123456789101112

10,50,5

20,20,50,3

30,10,10,30,5

41

50,30,60,1

61
71
81

90,20,30,5

100,60,4

110,30,7

120,60,4

Les probabilités de transitions non indiquées sont nulles. S4

ED N°2

4

Graphe G associé à la chaîne :

11 12

G = (X, U) avec

0 p j , i U

X ij Les COMPOSANTES CONNEXES sont les SOUS-CHAINES de la chaîne de Markov

A l'intérieur de chaque sous-chaîne, les COMPOSANTES FORTEMENT CONNEXES constituent des "classes

d'états".

On distingue les classes "transitoires", pour lesquelles la probabilité de quitter cette classe est non nulle, les

classes "récurrentes" ou "terminales" (une fois que le système se trouve dans un état de cette classe, il ne peut

plus quitter la classe). Donner les classes transitoires et récurrentes de chaque sous-chaîne. Quelles remarques pouvez-vous faire sur la classe {4} ?

Sur la classe {6, 7, 8} ?

E 1 1 1 1

ED N°3

5

ORDONNANCEMENTS DE PROJETS : PERT

I

On doit exécuter 4 tâches A, B, C et D soumises aux contraintes de précédence ci-dessous :

TâcheDuréeContraintes

A6 jours-

B5 jours-

C4 joursA achevée

D5 joursA, B achevées

1. Tracer un graphe PERT et calculer le chemin critique.

Déterminer la marge totale de chaque tâche.

II

Très préoccupé de la réussite de vos prochaines vacances, vous avez décidé de procéder scientifiquement. Pour cela

vous avez déterminé l'ensemble des tâches indispensables à votre départ, puis estimé la durée probable de chacune

et établi les liens de précédence entre tâches.

Vous avez alors obtenu le tableau suivant :

TACHESDUREE (jours)TACHES

PREALABLES

AChoisir la destination2/

BDéterminer la date de départ et la durée des vacances3/

CFaire renouveler mon passeport7/

DPoser les jours de vacances auprès de mon employeur4B

EAcheter mes devises10A

FAcheter mon billet6A, D

GObtenir le visa du Pays5A, C

HChoisir l'itinéraire et réserver certains hôtels2E, F, G

Vous souhaitez trouver un ordonnancement qui minimise la durée de ces préparatifs. Si vous avez commencé à

vous soucier de vos vacances un 22 mai, pouvez vous envisager de partir le 6 Juin ?

ED N°4

6 ORDONNANCEMENTS : Méthodes des potentiels (MPM)

REPRESENTATION D'UN GRAPHE

I Reprendre les problèmes I ET II de l'ED n°3 par la méthode des potentiels (MPM) II

Représenter ce graphe sous forme :

a) matricielle b) de listes d'adjacence III

Soit le graphe G = (X, U) de n = 6 sommets (numérotés de I = 1 à I = 6 et de m = 7 arcs (numérotés comme ci-

dessous de j= 1 = 7), valué par des coûts et défini par les 3 tableaux suivants : a) le tableau NARC (I) désigne le demi-degré extérieur du sommet I :

I123456

NARC (I)121120

Vous expliquerez pourquoi on a

n ji

INARCm )(

b) le tableau EXTR(J) liste, dans l'ordre lexicographique, les successeurs du sommet 1, puis du sommet 2,

etc...(s'ils existent) ; EXTR(J) désigne le numéro du sommet qui est l'extrémité terminale de l'arc d'indice j(1 £ J £

7) : on a donc numéroté les arcs en commençant par ceux issus du sommet 1, puis du sommet 2 et ainsi de suite.

J1234567

EXTR(J)6136124

c) Le tableau COUT (J) désigne la capacité de l'arc d'indice J :

J1234567

COUT (J)9834576

Tracer le graphe G, à grande échelle. Montrer qu'il comporte une entrée e et une sortie D. F E D C B A

ED N°5

7

FERMERTURE TRANSITIVE ; COMPLEXITE

I

Soit M la matrice d'adjacence d'un graphe G :

ABCDE M = A B C D E 01010
01100
00001 00101
quotesdbs_dbs10.pdfusesText_16

[PDF] ISN S3 : Les algorithmes

[PDF] ISN TP 3 Une introduction aux pages web

[PDF] ISN – Terminale S Séance 16 du 16 /01/15 • Au sujet de l`Architecture - Travail

[PDF] isnar-img

[PDF] Isnt She Lovely Grille.mus - Anciens Et Réunions

[PDF] Isnyaktuell - Schwäbische Zeitung

[PDF] Isn`t She Lovely

[PDF] Isn`t she lovely Eb - Anciens Et Réunions

[PDF] ISO - IFAero

[PDF] ISO - Thomas - Anciens Et Réunions

[PDF] ISO 10993 – 1

[PDF] ISO 11783-3 - Austrian Standards plus

[PDF] ISO 1219-1 - Pétrole

[PDF] ISO 1219-1 - Austrian Standards plus

[PDF] ISO 13485:2016