Home

Graphes

Contents

1. Formulation en langage naturel Une entreprise con oit et commercialise deux produits le pre mier est vendu avec un b n fice de 10 francs l unit le second avec un b n fice de 20 francs l unit La production tant soumise la contrainte suivante La quantit journali re fabriqu e ne peut d passer 100 unit s tous produits confondus On demande de d finir un plan de production quotidien qui optimise le b n fice de l entreprise Dans cette formulation les constantes sont 10 20 100 les variables sont les quantit s de produits fabriqu es chaque jour les relations doivent exprimer le b n fice et le fait que les quantit s produites sont positives et ne peuvent d passer quotidiennement 100 unit s Formulation dans le langage des math matiques On retrouvera dans cette formulation les constantes 10 20 100 Mais on introduira des noms de variable x resp y pour repr senter les quantit s de produit 1 resp 2 D autre part on utilisera une fonction f repr sentant le b n fice telle que f x y 10 x x 20 x y On utilisera enfin une relation d ordre pour exprimer les contraintes de production x y lt 100 0 lt x 0 lt y Finalement on arrive la formulation math matique suivante Maximiser f x y 10 x x 20 x y telque x y lt 100 0 lt xzx 0 lt y 5 Le traitement automatique A ce stade il faut D velopper une approche informatique dans les solutions au x probl me s
2. LD 1 2 2 1 3 3 2 1 2 2 2 1 2 3 3 3 1 3 E 3 2 2 si re s A jobs gt temps 8 2 2 Les graphes Deux formulations sont possibles e potentiel t ches e potentiel tapes plusieurs repr sentations sont possibles dans ce cas Diagramme 8 2 REPR SENTATION DES PROBL MES D ORDONNANCEMENT 51 Formulation potentielot ches On consid rera deux t ches 1 et j parmi n t ches de dur e respective d et dj et les dates de d but t et tj On traduira graphiquement et par des in galit s de type potentiel gt t che un certain nombre de contraintes 1 Post riorit au plus t t j commence au plus t t un temps a j unit s de temps apr s le d but de i L in galit correspondante cette contrainte est tj ti gt aij repr sent e par larc i 1 J 2 Post riorit au plus t t avec retard j commence au plus t t un temps A unit s de temps apr s l ach vement de i L in galit corre spondante cette contrainte est A y ditAij tj t gt di Aij repr sent e par l arc i j 3 Post riorit au plus t t avec chevauchement j commence au plus t t apr s une fraction c de la dur e de L in galit correspondante cette contrainte est T p Cij di tj ti gt cijd repr sent e par larc i gt 4 Post riorit au plus tard j commence au plus tard un temps vj unit s de temps apr s le d but de L i
3. exemple On applique l algorithme de Floyd au graphe de la figure 7 3 figure t ps width 6cm height 4cm Figure 7 3 Un graphe pour l algorithme de Floyd L algorithme de Floyd se d roule suivant les tapes Initialisation Etape 1 0 3 oo 3 0 3 00 2 0 2 2 2 0 2 2 00 0 1 a N i 0 00 4 4 0 oo 4 4 Les matrices correspondantes sont les suivantes Initialisation Etape 1 i O POROS CR i L Lel 23 2 2 52 2 2 2 2 3 3 3 3 3 1 3 3 4 4 4 4 4 4 4 4 exemple Orno Etape 2 D DH Etape 2 gt eNe EE kH amp D ND Ae ND A ND RA O RM NN w w we Etape 3 A e whe Aee gt 00 ND Ae ON il existe un circuit de longueur strictement n gative Ae wwe Orno w w we Si Pon veut par exemple retrouver le chemin de longueur minimale entre 4 et 1 on a comme premier pr d cesseur de 1 dans ce chemin le sommet 3 A41 3 et comme premier pr d cesseur de 3 le sommet 4 A43 4 On a donc le chemin 4 3 1 Etape 4 Eh EE kR gt 00 ND AeA ND Ae amp Q Orno 7 6 ARBRE DE POIDS MINIMAL TEST DE CONNEXIT 39 7 6 Arbre de poids minimal Test de connexit 7 6 1 D finition Etant donn un graphe non orient G X U on dit que le graphe partiel H X T U DT est une for t de G si il ne contient pas de cycle H est une for t maximale si il est sans cycle et que aucune ar te de U ne peut tre a
4. Exercice 1 D finir abstraitement sp cifier une proc dure qui permettra de supprimer toute redondance d l ments dans un ensemble et construire cette proc dure en utilisant le langage algorithmique ensemble rep ensemble E MOD E ACT Supprime les redondances d l ments dans E Retourne E sans redondance d l ments 28 CHAPTER 6 LE TYPE ABSTRAIT DE DONN E GRAPHE rep ensemble E elt X ensemble A A creer tant que taille pe FO x choisir pE oter E x si appartient p A x FAUX inserer A x E A retourner E Exercice 2 D finir le type graphe partir du type ensemble On supposera d fini abstraitement le type paire d entiers type graphe ensemblefentier SO ensemble paire AR 6 2 D FINITION ABSTRAITE DU TYPE GRAPHE 6 2 D finition abstraite du type graphe graphe creerg aj som aj arc sup som sup arc ens adj videg les types sommet et arc OP graphe creerg p ACT Retourne un graphe vide aj sommet E graphe G sommet s MOD G ACT Insere un sommet dans l ensemble X aj arc graphe G sommet sl s2 REQ s1 et s2 sont dans X MOD G ACT Insere dans U un arc dont les extremites sont s1 et s2 sup som G grapheG sommet s MOD G des extremites est s sup arc Q graphe G sommet s1 s2 MOD G ensemble ens adj 6 graphe G sommet s REQ s est dans X ACT Retourne l ensemble des sommets de G adjacents a s booleen videg f graphe G ACT Re
5. Oo ime me pe oe E Fee e DO E ams H be e om 1 a E Pooma fs EE IT Point Z Emm nagement E i y ES EGJ 1 Donner le graphe potentiel gt t ches mod lisant ce probl me 2 Donner les dates au plus t t de d but de chaque t che la dur e minimale du projet les dates au plus tard de d but de chaque t che la marge de chaque t che les t ches critiques e Graphe potentielot ches e0 B C G E niveau 1 niveau 2 niveau 3 niveau 4 niveau5 niveau 6 e Dates de d but au plus t t e 1 K 2 e le 2 o_ e 2 0 te 0 t4 0 tg 7 tp Tte 10ic 15 du 15 tp 11 tg 12 ty 14 tg 17 t 18 dur e minimale du projet e Dates de d but au plus tard T 18 Tg 17 Dares 16 Ty O Tp 12 Tp 15 Tg 160 To 11 Tp t ce Ti 0 T 0 e Marges ma 0 mpg l mc 1 mp 0 mg 0 mp 1 mg l mpy 1 m 1 mx O e T ches critiques A D E K S 8 4 M THODES S RIELLES 57 exemple Dans ce second exemple nous utilisons une mod lisation l aide d un graphe potentiel gt tapes Le tableau de donn es qui suit correspond aux diff rentes t ches d un projet de r alisation d un nouveau produit dans une entreprise AR AE Dee DE Etude de mare ee C Etude de faisabilit D Reaton so E D nition dune politique publique 3 JaA F Estimation
6. L affectation d une valeur d un type donn une variable compatible avec ce type se fait comme suit nom variable valeur Les instructions d criture et de lecture se font l aide des fonctions pr d finies crire et lire Un message que l on veut crire appa tra entre deux quotes en tant qu argument de crire L absence des quotes sous entent que ce message a une valeur et c est alors cette valeur qui est crite
7. algorithme par num ration D terminer pour un graphe quelconque un coloriage de taille minimale est un probl me NP complet On peut utiliser pour trouver l ensemble des coloriages en M couleurs au plus d un graphe un algorithme par num ration implicite qui examine l ensemble des solutions coloriages possibles ou au moins pour certaines d entre elles montre que il n est pas possible d obtenir un coloriage valide si certains sommets sont d j color s d une certaine mani re d o le terme implicite exemple Supposons que M 2 2 couleurs autoris es au maximum A une tape quelconque de l algorithme on a le coloriage d fini sur la figure 7 7 a Les sommets en blanc n ont pas alors de couleur d finie On peut voir que pour le sommet c il n est pas possible de choisir une couleur raies verticales ou horizontale sans violer la contrainte de k coloration soit par rapport l ar te a c soit par rapport l ar te bu c figure excolor ps width 3 5cm height 2 5cm Figure 7 7 Exemple de d but de coloriage par num ration M 2 Il n est donc pas n cessaire d aller attribuer des couleurs aux autres sommets non color s Il faut modifier la couleur de a ou la couleur de b L algorithme g n re l ensemble des solutions possibles en M couleurs au plus de la mani re suivante l arbre des solutions est construit en attribuant successivement les M couleurs chaque sommet Par exemple pour
8. cifi iy tous les autres sommets du graphe e Ceux dans lesquels on recherche un plus court chemin entre tout couple i j de sommets du graphe On distingue parmi ces algorithmes ceux qui prennet en compte des longueurs quelconques pour les arcs et ceux pour lesquels les longueurs doivent tre positives ou nulles Plus les types de longueurs sont restreints plus les algorithmes sont efficaces Un algorithme permettant de r pondre au probleme de chemin de capacit maximale est galement pr sent 7 2 Algorithme de Ford Bellman L algorithme de Ford Bellman permet de trouver un ensemble de plus court chemins d origine fix e io dans un graphe pond r de longueurs quelconques 7 2 1 Principe de l algorithme L algorithme de Ford Bellman consiste essentiellement en une proc dure de marquage dans laquelle on associe chaque sommet un nombre une marque m i Ces marques sont modifi es chaque tape de l algorithme de telle sorte que la fin de la proc dure r repr sente la longueur d un plus court chemin entre to et i Les valeurs finales n i 1 N des longueurs d un plus court chemin entre io r io 0 et les N 1 autres sommets d un graphe G X U sont caract ris s par les in galit s 1 Vi JEU Ti lt n j lij 33 34 CHAPTER 7 QUELQUES ALGORITHMES DANS LES GRAPHES o lij est la longueur de Parc i j L algorithme permet de parcourir la liste des arcs du gra
9. des fl ches en trait discontinu par exemple sa Fo X est une t che fictive introduite pour repr senter le fait que pr c de D Exercice Repr senter en PERT les diff rentes contraintes potentielles des pages pr c dentes Le multi PERT ou r seau PERT Quand un graphe PERT devient trop complexe on peut le diviser soit en sections soit en niveaux e Division en sections Exemple e a Le Pa Reseau principal O 0 me 4 sous reseau sous reseau e Division en niveaux 8 3 M THODE DU CHEMIN CRITIQUE 99 Exemple VS Va Niveau 1 En O e a v L tal 7 8 3 M thode du chemin critique Les chemins de valeur maximale joignant l entr e et la sortie d un graphe potentiel jouent un r le important dans un probl me d ordonnancement Toute t che appartenant ces chemins ne peuvent tre retard e sans que le retard soit r percut sur la dur e de l ordonnancement De telles t ches sont dites critiques et les chemins auquels elles appartiennent son appel s chemins critiques La m thode du chemin critique permet de d tecter les t ches critiques 8 3 1 Description de la m thode Un graphe potentiel nous permet de mesurer les quantit s suivantes pour certaines l aide des algo rithmes de Ford ou de Dijsktra 1 La date au plus t t de d but d une t che que l on notera t Cette date est gale la longueur du plus long chemin de l entr e 0 au sommet
10. mentaire est une chaine telle que en la parcourant on ne rencontre pas deux fois le m me sommet De mani re quivalente on peut d finir une chaine l mentaire comme une chaine dont tous les sommets sont de degr 2 au plus Dans le cas d un graphe simple une chaine de longueur q est parfaitement d finie par la succession des sommets qu elle rencontre figure i ps width 7cm height 4cm Figure 3 1 Une chaine arcs en gras dans un graphe exemple Dans le graphe de la figure 3 1 L u2 us ug u4 est une chaine reliant les sommets 2 et 3 Cette chaine est l mentaire L pourrait tre d crite partir de la succession de sommets suivante 2 1 4 5 3 e cycle cycle l mentaire Un cycle est une chaine dont les extr mit s coincident Un cycle l mentaire est un cycle tel que en le parcourant on ne rencontre pas deux fois le m me sommet sauf le sommet choisi comme origine du parcours exemple Dans le graphe de la figure 3 1 C u1 u3 ug us est un cycle l mentaire 3 2 Chemins et circuits e chemin chemin l mentaire Un chemin de longueur q de cardinalit q dans un graphe G est une s quence de q arcs P u1 uz uq telle que ui io i1 ua i1 i2 Uq g 1 iq 15 16 CHAPTER 3 CHEMINEMENT ET CONNEXIT io i1 12 g 1 44 tant des sommets du graphe G Autrement dit un chemin est une chaine dont tous les arcs sont orient s dans le m me sen
11. 5 2 repr sentent l ordre de visite des sommets lors du parcours en largeur du graphe de la figure 5 1 a L arbre de recouvrement arcs marqu s d une associ est galement repr sent figure p ps width 5cm height 4cm Figure 5 2 un graphe et son arbre de recouvrement recherche en largeur associ Pour implanter l algorithme on utilise une pile dans laquelle on place les sommets dont la liste d adjacence reste explorer Largeur Graphe G Sommet V Liste Sommet li_adj File Sommet pile Sommet S Cr erFile pile Mettre V pile Visiter V G tantque Vide pile FAUX Retirer S pile li adj ListSadj S G Pour chaque S dans li_adj Si Ouvert S G VRAI Visiter S G Mettre S pile 5 5 D termination des composantes connexes Pour d terminer les composantes connexes d un graphe on proc de comme suit On choisit un sommet Sy de G et on applique l algorithme de recherche en profondeur d crit pr c demment partir de So On associe Sy et chacun des sommets visit s lors de l exploration un m me num ro de composante connexe not NC So Apr s cette recherche deux cas peuvent se pr senter 1 Tous les sommets du graphe ont t atteints Dans ce cas le graphe G est connexe une seule composante connexe 2 Certains des sommets n ont pas t visit s Dans ce cas on relance l algorithme partir de l un d entre eux en incr mentant le num ro de
12. Compl rit ee a a date er BE Es nt ai 32 7 2 3 Enonc formel de l algorithme 32 7 3 Algorithme de Dijkstra 33 fi Principerde algorithme oi REA es a A A 33 7 3 2 Enonc formel de l algorithme 33 7 4 Chemin de capacit maximale 34 TA DERIO A A A RSR A ii 34 PAZ Remarques locura gs al re 6 a A ef gs ge A 34 7 4 3 Enonc formel de l algorithme 39 7 5 Plus court chemin entre toutes les paires de sommets Floyd 39 7 5 1 Principe de l algorithme retiri itg Re nt Be aaa 39 7 5 2 Enonc formel de l algorithme 36 7 6 Arbre de poids minimal Test de connexit 37 Tod DEMO AAA An afro fe Sp out DO ARE nn 37 7 6 2 Principe de l algorithme de Prim 37 7 6 3 Enonc formel de l algorithme de Prim 37 F1 Probl me de Hot Lens a LU die A A El de pe es Ann sl 38 Till D finition o sa te ae a Shaver As Th Me EN 38 7 7 2 Probl me du flot maximum 38 7 7 3 Graphe d cart et algorithme de Ford Fulkerson 39 TTA Algorithme de Ford Fulkerson 39 7 7 5 Enonc formel de l algorithme 40 1 8 K coloration de STaphe 4
13. DE FLOT 41 e s est appel arc de retour de flot de G Il sera not 0 par la suite e est appel sommet source s est appel sommet puits F I fi fa fm est un flot de e s dans G ssi l galit I est v rifi e fo est appel e valeur du flot On remarque que si f f1 f2 fm est un flot de e s dans G fF fo fi f2 fm est un flot dans G e Probleme de flot maximum Le probl me de flot maximum de e s dans G muni des capacit s Cu u U est le suivant D terminer un flot f fo f f2 fm dans G v rifiant les capacit s de contraintes O lt fu lt Cu u 1 M tel que la composante fo sur larc de retour i e la valeur du flot soit maximale 7 7 3 Graphe d cart et algorithme de Ford Fulkerson Soit G X U un graphe muni de capacit s cu Soit f un flot dans G Au couple G f on associe un graphe d cart GA f X U f U f est d fini comme suit A tout arc u i j de G de capacit cu de flux fu on associe dans GA f un arc ut i j de capacit c i j Cu fu si l arc u n est pas satur c est dire si fu lt Cu c i j repr sente la capacit r siduelle de Parc u dans G A unarcu j i de capacit c j i fu si le flux sur l arc u n est pas nul exemple La figure 7 5 a repr sente un couple G f Pour chaque arc le couple capacit flux est indiqu La figure 7 5 b repr sente le graphe d cart G
14. N X voir ci dessus a et m sont de taille N 7 6 3 Enonc formel de l algorithme de Prim Prim 1 Initialisation ViEeX mio 0 T i o si i lo MEX ai o00 A 2 It ration courante S lectionner i X A tel que r i Min a j lt o7 3 minimum pour j dans X Si 1 ou X fin Sinon a i a i Pour toute ar te u i j ayant i comme extr mit mise jour des marques Si wu lt 7 et a j lt 0 T J Wu a j u 40 CHAPTER 7 QUELQUES ALGORITHMES DANS LES GRAPHES Graphe It T A a gure u0 ps width 4cm height 3cn init 0 AT AD gt iso HR SS X o0 o0 o0 o0 o0 00 gure ul ps width 4cm height 3cx 1 ES 6 1 5 LS Les 2 3 4 5 6 00 1 2 3 00 00 00 5 5 6 gure u2 ps width 4cm height 3cxH 1 3 Aa D e do loa 00 2 4 5 6 exemple gure u3 ps width 4cm height 3cn 3 1 3 6 2 4 5 8 8 loa Aa ND e Low la gure u4 ps width 4cm height 3cH 1 3 4 6 2 5 1 3 4 5 6 2 X 0 La NR N 4 D 8 8 3 818 8 e aja o D ejr o wow o wji w o oo ue oo gure u5 ps width 4cm height 3cH gure u6 ps width 4cm height 3cx 7 7 Probl me de flot 7 7 1 D finition Soit G X U un graphe orient On associe chaque arc u U un nombre r el not fu tel que en tout sommet i X soit v rifi e l galit I he Doi uEwt i uEw i Pour to
15. Q A uz uz U4 U6 U7 e Graphe anti symtrique Un graphe G est dit symtrique ssi quels que soient les sommets et j le nombre d arcs i j est gal au nombre d arcs j i G est antisymtrique ssi i j U j i U exemple Le graphe de la figure 2 1 n est pas symtrique car par exemple 2 3 U et 3 2 U Il n est pas non plus antisymtrique car 1 2 U et 2 1 U e Graphe complet clique Un graphe G X U est complet ssi deux sommets quelconques sont joints par au moins un arc Un sous ensemble C de X est une clique ssi deux sommets quelconques sont joints par une ar te 2 5 IMPLANTATION D UN GRAPHE 13 figure c ps width 6cm height 3 5cm Figure 2 3 Un graphe orient contenant des cliques exemple Le graphe de la figure 2 3 n est pas complet car aucun arc ne joint le sommet 4 aux autres Dans le graphe non orient associ ce graphe le sous ensemble 1 2 3 est une clique Par contre le sous ensemble 1 2 4 n en est pas une e Sous graphe Soit G X U G X U deux graphes On dira que G est un sous graphe de G ssi X est inclus dans X et U est inclus dans U exemple Le graphe de la figure 2 4 est un sous graphe de celui de la figure 2 3 figure d ps width 4 5cm height 3 5cm Figure 2 4 Un sous graphe du graphe de la figure pr ce dente e Graphe bipartite Un graphe G X U est bipartite ssi il existe deux parties distinctes ensembles de sommets X et X2
16. REPR SENTATIONS D UNE RELATION 9 7 1 Le compl ment La relation R compl mentaire de R est par d finition la relation qui a pour graphe le compl mentaire du graphe de R dans X x X 7 2 L union U R U Ro x y ssi R1 x y ou Ro r y 7 3 L intersection N RiNRalzx y ssi Ri x y et Ro x y 7 4 L inverse 7 Rx y ssi R y x 7 5 Le produit x Ri xRalx y ssi Iz X tel que Ri x z et Ro z y 7 6 La fermeture transitive RF Ui gt K avec R Idxxx et R RT x R 7 7 La fermeture r flexive transitive R Idxxx U R Ui gt 0 R 8 D finition 4 Soit x X la classe d quivalence de x par rapport une relation d quivalence R not e T est par d finition l ensemble X R z x Propri t s Dans tout ce qui suit on supposera d finie une relation d quivalence R sur un ensemble X x d signera un l ment de X 1 TE 2 Vz a E X Ru 1 gt 1 3 Vx LEX TAT 0 7T 7 9 D finition 5 Soit R une relation d quivalence sur un ensemble X L ensemble quotient de X par R est par d finition l ensemble X R 7 x X Propri t s Uzex R Comme les classes d quivalence distinctes ont des intersections vides on dira que X R d finit une partition de X 1 5 Repr sentations d une relation Soit R une relation sur un ensemble X on pourra repr senter le fait que deux l ments a b de X sont en relation par
17. V entier NC Si Visiter G V NC Profondeur2 G S NC L algorithme de d termination des composantes connexes est alors le suivant Connexit Graphe G Liste Sommet Sommet S Liste Sommet L NC 0 L ListSom G Pour chaque S dans L Si Ouvert G S VRAI NC NC 1 Profondeur2 G S NC 32 CHAPTER 6 LE TYPE ABSTRAIT DE DONN E GRAPHE retourner L L contient la liste des sommets marqu s par leur num ro de composante connexe Chapter 7 Quelques algorithmes dans les graphes 7 1 Probl mes de cheminement Plus court chemin On consid re un graphe G X U On associe chaque arc u U un nombre r el l u appel longueur de l arc probl me de plus court chemin Il existe de nombreuses applications aux probl mes de plus court chemin et leurs variantes Le probl me de plus court chemin entre deux sommets et j consiste d terminer parmi tous les chemins joignant et j un chemin l mentaire y dont la longueur totale 57 l u soit minimale u y signifie que l arc u appartient au chemin y On admettra le r sultat suivant Une solution ce probl me existe ssi il n existe pas dans le graphe de circuit de longueur strictement n gative pouvant tre atteint partir de 1 Les algorithmes de cheminement qui sont pr sent s peuvent tre divis s en deux grandes cat gories uEp e Ceux pour lesquels on recherche un plus court chemin d un sommet sp
18. chemin de y j de capacit au moins gale celle de Pf e Soit un chemin l mentaire optimal Pf entre to et j Si est sur le chemin Pf alors le chemin de to i not P contenu dans P est aussi un chemin optimal e Si on note Rx l ensemble des pr d cesseurs d un sommet j du graphe alors on a la relation i j Vi fo cj Mazer Min4c cij et Cio 00 3 a c P d signe les valeurs optimales des capacit s des chemins de io j lorsque j parcourt l ensemble des sommets distincts de io On peut remarquer l analogie avec les quations du probl me de plus court chemin ii Vi io 7 Miner r i liz et TE io 0 e Les quations i peuvent tre consid r es comme constituant un syst me d quations lin aires Vifi E Q ci lt 1 icr en prenant comme op rations alg briques les op rations d finies par Va bER a b Max a b a amp b Min a b 7 5 PLUS COURT CHEMIN ENTRE TOUTES LES PAIRES DE SOMMETS FLOYD 37 et co 00 l ments neutres de et respectivement L analogie des syst mes i et ii permet de construire un algorithme adapt au probl me de capacit maximale partir de l algorithme de Dijkstra 7 4 3 Enonc formel de l algorithme Capacit 1 Initialisation E io Df Cisi Cioi est la capacit de Parc io 1 si il existe O sinon 2 It ration courante choisir i E tel que Dfi soit maximum E EU Pour chaque j tel q
19. d it rations 2 It ration courante Modif FAUX aucune modification de 7 n est possible vie X Vier T est l ensemble des successeurs de v mi lij Si v lt r j m j v pli i Modif VRAI 3 Test de fin Si Modif FAUX aucune am lioration des marques lors de l tape k fin Sinon k k 1 Sik N fin car circuit de longueur n gative Sinon aller en 2 it ration suivante exemple On d roule l algorithme de Ford Bellman partir du sommet xy du graphe de la figure 7 1 avec les initialisations r x0 0 r x 00 Vri X i o p ri zi On obtient r x1 2 r x2 4 r x3 3 n x4 8 pour les chemins xoxl 29111312 Totits ToliT3T2Ta 7 3 ALGORITHME DE DIJKSTRA 39 j plj figure r ps width 6cm height 4cm Figure 7 1 Application de Ford Bellman sur un graphe pond r 7 3 Algorithme de Dijkstra Cet algorithme permet de d terminer un ensemble de plus courts chemins partir d un sommet y dans un graphe muni d arcs de longueurs positives ou nulles 7 3 1 Principe de l algorithme Comme dans l algorithme de Ford Bellman on associe chaque sommet du graphe une marque 7 i qui doit en fin d algorithme repr senter la longueur d un plus court chemin de io 1 Cet algorithme tient jour un ensemble E de sommets dont les distances les plus courtes y sont d j connues Au d part E contient uniquement 9 A chaque tape on ajoute E l un des so
20. et en fixant leur date d ex cution De nombreux projets li s des activit s sociales ou conomiques demandent une organisation et une coordination parfaite pour leur r alisation Les probl mes qui apparaissent en cours de r alisation rejoignent dans la quasi totalit des cas des problemes d ordonnancement exemple Chantier de construction ex cution de t ches sur des machines dans un atelier ordonnance ment de t ches sur plusieurs processeurs En toute g n ralit les problemes d ordonnancement se posent en ces termes Etant donn un objectif qu on se propose d atteindre et dont la r alisation suppose Vexistence de ressources E x y l ex cution de t ches soumises de nombreuses contraintes d terminer l ordre et le calendrier d ex cution des diff rentes t ches afin d optimiser une fonction conomique e Un probl me d ordonnancement peut tre statique lorsque l ensemble des t ches accomplir au cours du temps est connu au d part ainsi que les dates de d but d ex cution des t ches e Un probl me sera dynamique si l ensemble des t ches accomplir au cours du temps volue de fa on non d terministe e Quand les param tres d une t che sont connus en probabilit on dit que le probl me consid r est stochastique Examinons de fa on plus d taill les diff rentes notions introduites pr c demment 8 1 1 Les contraintes On consid re trois types de contrain
21. le temps total d ex cution soit minimis Ce probl me peut tre r solu en d terminant une coloration des sommets du graphe de mod lisation Chaque couleur correspond une date d ex cution distincte La minimisation du nombre de couleurs permet de minimiser le nombre de dates i e le temps global de ordonnancement Une telle mod lisation est illustr e sur la figure 7 10 pour une liste de 4 t ches pr sentant les conflits e Ti Ta T3 e T gt Ti T3 e T To T3 Ta e T T3 figure colorsched ps width 3cm height 2 5cm Figure 7 10 Mod lisation d un probleme d ordonnancement avec contraites de ressources pour 4 t ches Une solution est T1 T4 Ta T3 46 CHAPTER 7 QUELQUES ALGORITHMES DANS LES GRAPHES exercice Retrouvez une solution l aide de l algorithme par num ration donn ci dessus M 3 P exercice Les tudiants a b c et d doivent subir un examen d informatique les tudiants a e f et g une preuve de biologie les tudiants b c g une preuve de lettres a d f une preuve de sciences sociales b et c doivent aller un examen d histoire Chaque preuve a lieu une seule fois et dure la journ e Mod liser le probl me en tant que probl me de k coloration de graphes Trouvez le nombre de jours minimal pour faire passer les examens Chapter 8 Ordonnancement 8 1 Introduction Ordonnancer c est programmer la r alisation d un projet en attribuant des ressources aux t ches
22. orient de la figure 2 7 b a la matrice d incidence somets ar tes de la figure 2 7 a 1 1 0 0 0 10011 EP ESA 01110 figure 8 ps width 4cm height 3cm 0 0 1 0 1 Figure 2 7 a Une matrice d incidence sommets ar tes b le graphe non orient correspondant 2 8 Matrice d adjacence Soit G X U un 1 graphe comportant au plus une boucle par sommet avec X n La matrice d adjacence associ e G est une matrice n x n Aij telle que Aij 1si i j EU Aij 0 sinon Dans le cas non orient la matrice d adjacence A j d un graphe simple est telle que Aij Aji 1 si i j est une ar te du graphe gt Aij 0 sinon exemple Le graphe non orient de la figure 2 8 b a la matrice d adjacence de la figure 2 8 a 1100 0 1 1 0 oe cs PES 00 11 figure h ps width 4cm height 3cm 0 0 0 1 Figure 2 8 a Une matrice d adjacence b le 1 graphe correspondant Chapter 3 Cheminement et connexit 3 1 Chaines et cycles e chaine chaine l mentaire Une chaine de longueur q de cardinalit q est une s quence de q arcs L u1 u2 uq telle que chaque arc ur de la s quence 2 lt r lt q 1 ait une extr mit commune avec l arc u _1 ur ur 1 et l autre extr mit avec u 1 Ur ur 1 L extr mit 1 de u1 non adjacente uz et l extr mit j de uq non adjacente u _1 sont appel es les extr mit s de la chaine L On dit aussi que L joint les sommets i et j Une chaine l
23. partir d une matrice d incidence 18 A1 Liste des aretes sis annee moe ne a D ses his EE vo 18 4 2 2 Liste des cocycles Q i ou in amuse s algue un nes 18 5 Recherche dans un graphe 19 5 1 Objectifs de cette recherche enep a ni E a ala dut 19 5 2 Principe du parcours en profondeur d un graphe 19 5 3 L algorithme de parcours en profondeur 20 5 4 Parcours en largeur d un graphe 21 5 5 D termination des composantes connexes 21 6 Le Type Abstrait de Donn e graphe 23 6 1 D finition abstraite de proc dures ou de types 23 6 1 1 D finition abstraite d une proc dure 23 6 1 2 D finition abstraite d un nouveau type 24 6 1 3 Exemple Le TAD ensemble 25 6 2 D finition abstraite du type graphe ooa 27 6 3 L algorithme de parcours en profondeur 27 6 4 L algorithme de parcours en largeur 28 6 5 Recherche des composantes connexes 29 2 CONTENTS 7 Quelques algorithmes dans les graphes 31 7 1 Probl mes de cheminement Plus court chemin 31 7 2 Algorithme de Ford Bellman 31 1 2 1 Principe de l algorithme 4 eiaa E ape E Ra Hurt o 31 1 22
24. que la quantit disponible t la t che de plus haute priorit Les m thodes s rielles permettent la construction d une solution approch e avec certains inconv nients En effet l ex cution d une t che pr te r pondant la contrainte de disponibilit de ressource s il en existe peut tre moins int ressante que le fait de laisser momentan ment des ressources inutilis es en vue d ex cuter une autre t che Dans l tablissement des priorit s en g n ral deux r gles sont tr s utilis es Ordonner suivant les dates au plus tard Ordonner suivant les dates de fin au plus tard 8 4 1 Algorithme de liste initialisation U t 0 U est l ensemble des t ches ordonnanc es Etape courante tant que U XI Si le sous ensemble U de compl mentaire de U dans 7 des t ches disponibles t est non vide Prendre la t che i de plus grande priorit t t U UU i Sinon D terminer le plus petit instant t o une t che dans compl metaire de U dans devient disponible 8 4 2 Exemple On consid re un probl me d ordonnancement dont les donn es sont r sum es dans le tableau suivant rames ppp rfp 21 Resoc fo jojo p fifiio fi fo ol Date au plsst t o 2 0 10 fe 2 is fx 7 Date au plus tard o 6 18 10 12 20 18 25 27 30 Dur e tofa 2 18 76 5 9 72 7 fa Tias 7 1 17 Ja o fe facferfen r 1 Tracer le graphe potentiel t ches
25. sous chemin entre k et j Ces sous chemins ne doivent contenir que des sommets dans 1 2 k 1 et tre de longueur minimale On aura donc ly le Le plus court chemin de j avec les sommets 1 2 k ne passe par k Dans ce cas on aura videmment k k 1 lj lij 38 CHAPTER 7 QUELQUES ALGORITHMES DANS LES GRAPHES La matrice LY donnant l ensemble des plus courts chemins dans le graphe est d termin e en N tapes par r currence partir de L gr ce la relation R Cet algorithme permet de d tecter la pr sence d un circuit strictement n gatif d s que l un des 1 est strictement n gatif Cet algorithme peut tre compl t par la construction de la matrice pr d cesseur A ij 1 lt i j lt N dont les termes a ont la signification suivante as est le num ro du sommet pr d cesseur de j sur le plus court chemin entre i et j trouv jusqu pr sent Cette matrice est mise jour par 5 Jk k 1 k 1 Qij Akj S l Le ej a zos dk _ 1k 1 aij reste inchang si l l chaque application de la relation de r currence R 7 5 2 Enonc formel de l algorithme Floyd 1 Initialisation Pour i 1 2 N etj 1 2 N li longueur i j si i j existe lij 00 sinon Li 0 Qij 1 2 It ration courante k k 1 N Pour i 1 2 N etj 1 2 N ve lik lkj Si v lt lij lij v Qij akj Si i j et lij lt 0 fin
26. 3 2 un graphe avec 3 composantes connexes exemple La figure 3 2 repr sente un graphe ayant trois composantes connexes Gi 1 2 4 u1 ua w G2 5 7 us Gs 13 8 9 us us u7 La v rification de la connexit d un graphe ou la d termination de ses composantes connexes est un des probl mes fondamentaux de la th orie des graphes 3 4 GRAPHES ET COMPOSANTES FORTEMENT CONNEXES 17 3 4 Graphes et composantes fortement connexes e graphe fortement connexe Un graphe G X U est dit fortement connexe si pour tout couple de sommets i et j dans cet ordre de X il existe un chemin de j La relation i iR J ou 14 j et il existe un chemin joignant i j est une relation d quivalence sur X Les sous graphes G1 G2 G engendr s par ses classes d quivalence Y1 Y2 Yp sont appel s composantes fortement connexes de G Le nombre p de composantes fortement connexes distinctes est le nombre de connexit s fortes du graphe Un graphe est dit fortement connexe ssi il n a que une seule composante fortement connexe grap q P exemple Le graphe de la figure 3 2 a une seule composante fortement connexe de taille sup rieure 1 y 1 2 Lux u2 18 CHAPTER 3 CHEMINEMENT ET CONNEXIT Chapter 4 Implantation sous forme de liste d un graphe Nous avons vu pr c demment qu il est possible de d crire un graphe partir de deux familles de matrices La matrice d
27. A f associ figure w0 ps width 6cm height 4cm figure w1 ps width 6cm height 4cm Figure 7 5 a Flot sur un graphe b Graphe d cart associ 7 7 4 Algorithme de Ford Fulkerson L int r t du graphe d cart apparait dans l utilisation du r sultat suivant Soit f un flot de e s dans un graphe G compatible avec les capacit s Cu ie 0 lt fu lt Cu Soit GA f le graphe d cart associ G Une condition n cessaire et suffisante pour que le flot f soit maximal sur G est qu il n existe pas de chemin de e s dans GR 9 Ce r sultat est la base de l algorithme de Ford Fulkerson 42 CHAPTER 7 QUELQUES ALGORITHMES DANS LES GRAPHES 7 7 5 Enonc formel de l algorithme Ford Fulkerson 1 Initialisation f 0 0 0 flot courant 2 It ration courante Trouver un chemin X de e s dans G4 f Si X non trouv f est maximum fin Sinon re Minuexc u r est le minimum des capacit s r siduelles des arcs du chemin Mise jour de f fo fo r SiuteX fu fu r Siu EX fus fur 7 8 K coloration de graphe 7 8 1 D finition On appelle X coloration d un graphe G V E la r partition des sommets de V en k ensembles disjoints X1 X2 Xp tels que e wEV veX gt C 1i 1 l 1 k correspond la couleur affect e au sommet v il y a une couleur par ensemble e Ve v w E C 4 Co Deux sommets adjacents doivent tre colori s par des couleurs diff rentes Le nombre
28. B donnant naissance une infinit de t ches B1 Ba Bx Une contrainte interne s exprime par le fait que la t che A pr c de la t che Bp Une contrainte externe s exprime par le fait que 3k Vh la t che Ap pr c de la t che Bp k Cette situation se rencontre dans le cas de productions industrielles en s rie 3 Les t ches dans un atelier contenant m machines sont regroup es en jobs travaux chacune d elles s ex cutant sur une machine diff rente on aura donc m t ches dans un job Un job peut contenir e des t ches ind pendantes on parle alors de probl me open shop e des t ches li es par un ordre total Cet ordre n tant pas forc ment le m me pour tous les jobs on parle alors de probl me job shop e Dans le cas o il y a le m me ordre total sur tous les travaux on parle de probl me flow shop 8 1 3 Les ressources Deux types de ressources seront consid r s 1 Les ressources renouvelables qui restent disponibles apr s avoir t allou es une ou plusieurs t ches par exemple les machines 2 Les ressources consommables qui peuvent devenir non disponibles apr s avoir t allou es une ou plusieurs t ches par exemple les mati res premi res l argent 8 1 4 Les fonctions conomiques Les fonctions conomiques ou crit res optimiser dans des probl mes d ordonnancement d pendent en g n ral des param tres suivants 1 Date de fin d ex cution d une
29. Graphes D Sarni L Lemarchand Contents 1 Relations ensembles ordonn s 5 A Definition ara E Mr mer Cr CEE EURE EL 5 12 Exemples ra 44e 6 ee e MAR A ue en A Sn nee a ct A S 5 1 3 Quelques propri t s des relations binaires 5 1 4 Relations d ordre Relations d quivalence 6 1 5 Repr sentations d une relation 7 2 El ments de base 9 2 1 Graphe orient D finitions n a a e a e a e a e a D E a E E G 9 2 2 Repr sentation graphique 9 2 3 Graphe non orient 9 2 4 Terminologie celia os ets es is Gars da dite A4 A Ste anse an MALI 10 2 5 Implantation d un graphe 11 2 6 Matrice d incidence sommets arcs 11 2 7 Matrice d incidence sommets ar tes 12 2 8 Matrice d adjacence 4 eda d d e RES nt de A RE BAS 12 3 Cheminement et connexit 13 3 1 Chaines ed Cycles dos a GR Pa nr dont de dd ALA RE GR A pe 13 3 2 Chemins et CITCUIES a srs ee has te br tt state dde dd a e 13 3 3 Connexit nombre de connexit 14 3 4 Graphes et composantes fortement connexes 15 4 Implantation sous forme de liste d un graphe 17 4 1 A partir de la matrice d adjacence 17 4 2 A
30. HE 45 o A D I Oo O D DH lt A Em e 200 O0 600 0 o A A 0 0 NA YA Y ND ND ND D ND ND D N N O 03M wW04NNoOSZWNNNOoOOOO 2 A gt TZ 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 2 hhh RO yywaNnNRr oy roya A oyNRRR D NO O1 Or OU ANO o Exercice Dessiner les solutions correspondant aux solutions trouv es et l arbre de recherche d fini par les tapes pr sent es dans le tableau D crivez les tapes suivantes de l ex cution de l algorithme 7 8 4 Une application Emploi du temps La coloration de graphes peut tre utilis e pour modeliser des problemes d emploi du temps avec con traintes sur les ressources Supposons un ensemble de t ches Ti Tn r aliser Chaque t che n cessite une unit de temps pour son ex cution Certaines t ches ne peuvent tre r alis es simultann ment car elles n cessitent la m me ressource Soit C 1 n 1 n la matrice de conflit entre t ches si C 1 j 1 les t ches n cessitent une ressource commune C i j 0 dans le cas contraire La matrice de conflit peut tre mod lis e comme un graphe G V E comme suit e V est l ensemble des t ches e e i j Esi C i j 1 Le probl me de trouver un ordonnancement des t ches correspond d terminer une date d ex cution pour chacune d entre elles tel que 2 t ches en conflit n est pas la m me date d ex cution et que
31. Lorsque le graphe est pond r c est dire que l on associe une valeur num rique chaque ar te on peut stocker les poids dans une liste de m me taille que B 19 20 CHAPTER 4 IMPLANTATION SOUS FORME DE LISTE D UN GRAPHE figure 1 ps width 9cm height 4cm Figure 4 2 a un graphe simple b liste d adjacence associ e 4 2 A partir d une matrice d incidence Deux repr sentations sont essentiellement utilis es pour repr senter un graphe G X U avec U M 4 2 1 Liste des ar tes Une premi re m thode consiste d finir deux tableau not s EI et EF Extr mit Initiale Finale de dimension M donnant pour chaque arc ou ar te le num ro des extr mit s Dans le cas non orient on ne tient pas compte des qualificatifs initial et terminal exemple La figure 4 3 b repr sente les listes d ar tes du graphe de la figure 4 3 a figure m ps width 10cm height 4cm Figure 4 3 a un graphe b liste d ar tes associ e remarques Cette repr sentation permet de d crire les p graphes ou des multigraphes comportant des boucles Lorsque le graphe est pond r on ajoute une liste P de dimension M en correspondance biunivoque avec EI et EF et contenant les poids 4 2 2 Liste des cocycles Q i ou Q7 1 On tablit pour chaque sommet i du graphe La liste Q i des arcs ayant i pour origine cas orient La liste Qi des arcs ayant pour origine cas non orient Deux tableaux LP e
32. M 2 et V 5 nombre de sommets l arbre de recherche complet avec les couleurs blanc et noir est d crit sur la figure 7 8 figure grrech ps width 10cm height 5cm Figure 7 8 Arbre de recherche complet pour un graphe 5 sommets en 2 couleurs V 2 M 2 La figure 7 9 montre un exemple de recherche pour M 2 et V 5 Le graphe colorer est repr sent en a et larbre de recherche effectif pour ce graphe est montr en b Une branche coup e d note l impossibilit de colorer le sommet suivant avec une couleur donn e Les nombre d ar tes effectivement explor es d pend de l ordre dans lequel les sommets sont ordonn s V1 va U3 Ua v5 dans l exemple pr c dent Il est possible que le nombre d ar tes de l arbre de recherche soit r duit en ordonnant l arbre de recherche diff rement 44 CHAPTER 7 QUELQUES ALGORITHMES DANS LES GRAPHES figure grrechcut ps width 10cm height 5cm Figure 7 9 Arbre de recherche b d un graphe 5 sommets a en 2 couleurs V 2 M 2 exercice D terminez l arbre de recherche que l on obtient en ordonnant les sommets pour l exemple du graphe de la figure 7 9 a en v1 va U5 va V3 Que pensez vous du r sultat 7 8 3 Ennonc formel de l algorithme Pour d finir l ensemble des coloriages possibles d un graphe G V E en au plus M couleurs l algorithme utilise un vecteur couleurs 1 V qui stocke l indice correspondant la couleur a
33. S La description formelle de l algorithme est la suivante Si S est ouvert on le visite puis on effectue un parcours en profondeur de tous ses sommets adjacents ouverts Pour effectuer le parcours on associe chaque sommet un drapeau que l on positionne lorsque l on visite le sommet pour le faire passer de ouvert ferm exemple Le tableau de la figure 5 1 b repr sente les diff rentes tapes de l algorithme pour le parcours en profondeur du graphe de la figure 5 1 a Les sommets ferm s sont en gras A chaque tape le sommet s lection parmi les sommets adjacents du sommet courant est soulign Lors des tapes 4 5 7 8 9 aucun sommet n est s lectionn car il n existe aucun sommet ouvert dans la liste d adjacence du sommet courant Cela signifie que l on ne peut esp rer de nouvelles possibilit s de cheminement partir de ce sommet Dans ce cas on effectue un retour en arri re backtracking vers l anc tre du sommet courant celui partir duquel le sommet courant a t s lectionn On relance alors l algorithme tapes 1 et 6 dans l exemple La recherche est termin e lorsque l on revient au sommet initial et que tous ses sommets adjacents sont ferm s c est le seul sommet ne poss dant pas d anc tre tape 9 dans l exemple remarque Le choix d un sommet courant parmi les sommets adjacents ouverts d un sommet est arbi traire Des choix diff rents peuvent mener des ordres de vi
34. X est de type nouveau type l acc s un champ se fait de la mani re suivante X nom champ On d finit les r gles suivantes sur les types abstraits La valeur d une variable d clar e sur un type abstrait est une r f rence une donn e de ce type On ne peut acc der aux donn es d un type abstrait que par les primitives apparaissant dans les sp cification du type ou par des fonctions et proc dures d finies partir de ces primitives Une variable ne faisant r f rence aucune donn e vaut NIL qui est la valeur FAUX pour une r f rence ll est possible de d clarer la fois le type des donn es de m me nature faisant partie d un groupe et le type du groupe On utlise alors le sch ma type groupeltype donnees A 3 3 Les tableaux Le TAD tableau ayant une importance particuli re par la suite nous l autorisons en tant que type pr d fini dans le langage avec le sch ma nom tableau type l ment dimension A 3 4 Les op rateurs Les op rateurs de comparaison sont lt gt lt gt Les op rateurs Bool ens sont ET OU NON Les constantes Bool ennes sont VRAI resp FAUX ou encore ce qui est quivallent valeur num rique d sont VRAi resp FAUX ou encore ce qui est quivallent valeur num rique diff rente de z ro resp valeur num rique gale z ro Les op rateurs arithm tiques sont X ainsi que modulo A 3 5 Les instructions primitives
35. a de e aii ab nee dd UN 4 at 4 A ae 4e al 44 40 Tes D finition Le A AMONT AA AU A PAR EE EE 40 7 8 2 Principe de l algorithme par num ration 41 7 8 3 Ennonc formel de l algorithme 42 7 8 4 Une application Emploi du temps a 43 8 Ordonnancement 45 S L ro duce tes a nai A de ie R Ne E A A au 45 8 11 Les COM TAIMEES nc a e a a e ese nt a 45 8 1 2 Lestache ea ita A AA E A E dos At 46 8 13 a Leg TESSOUIC S ia a A O A de nat tt de A 46 8 1 4 Les fonctions conomiques 46 8 1 5 Notations sa e rs NE vanne sg A E AA ARA deb dun de 47 8 2 Repr sentation des probl mes d ordonnancement 47 8 2 1 Le diasramme de Gantt creed i i aep a da e lt de a dd aa 47 8 227 Les graphes srta A A A A A ne de e w Ed 48 8 3 M thode du chemin critique 53 8 3 1 Description de la m thode 53 8 21 M thodes s rielles p acetas ra a a E A de ar e ad ps amp amp 55 841 Algorithimede liste cas aara au a ae 42 E dut A pe 56 8 42 Exemple iaa dt a e A A de CARE 5 56 A Le Langage algorithmique C Manuel d utilisation 57 A 1 Les structures de contr le 57 A 2 Les fonctions et proc dures 58 A3 Types etiop rateurs das en Dre LR RS AE Aa ME Let MEN PE Bt Lo Ed 58 A 3 1 Les types primit
36. a m thode PERT n sessite tout d abord de d finir le projet r aliser les diff rentes t ches leur dur e les liens qu il y a entre elles On repr sentera les tapes par des cercles sommets du graphe et les t ches par des fl ches arcs du graphe exemple Le graphe E C 5 C gt z repr sente le probl me d ordonnancemenmt r sum dans le tableau de donn es T ches Dur e en unit de temps T ches ant rieures Principes de la repr sentation On utilise la colonne t ches ant rieures on repr sente d abord les t ches sans ant c dent un premier niveau dans le graphe dans l exemple A est un premier niveau on supprime de la colonne les t ches repr sent es puis on repr sente les t ches qui n ont plus d ant c dent un second niveau dans l exemple B est un second niveau On peut ainsi obtenir plusieurs niveaux dans un graphe Les principes de base permettant la construction d un graphe PERT sont les suivants 1 un PERT a un seul sommet D but et un seul sommet Fin 2 2 t ches et j se succ dant sont repr sent es par Sa mn E 3 2 t ches et j se simultan es sont repr sent es par 4 2 t ches 2 et j pr c dant une t che k sont repr sent es par 54 CHAPTER 8 ORDONNANCEMENT pe e 5 pour les besoins de repr sentation des t ches fictives sont parfois n cessaires on les repr sente par
37. adjacence ou ses d riv es La matrice d incidence ou ses d riv es Dans tous les cas on se rend compte que les matrices consid r es contiennent beaucoup de z ros et donc que un stockage tel quel de ces tableaux en m moire n est pas judicieux C est pour cela que l on utilise souvent une repr sentation de ces matrices sous forme de listes 4 1 A partir de la matrice d adjacence On rappelle qu une matrice d adjacence sert d crire soit des 1 graphes orient s soit des graphes simples non orient s Une telle repr sentation peut tre mise en oeuvre par des listes d adjacence Pour un graphe G X U avec X N et U M on utilise deux tableaux A et B de dimensions respectives N 1 et M cas orient ou 2M cas non orient Pour chaque sommet i la liste des successeurs de est contenue dans le tableau B partir de la case A i On voit donc que l ensemble des informations relatives au sommet est stock entre les cases Ali et A i 1 1 du tableau B On a les galit s suivantes d i A i 1 Ali cas orient dti A i 1 A i cas non orient ALI D dt 1 figure k ps width 9cm height 4cm Figure 4 1 a un 1 graphe b liste d adjacence associ e exemple la figure 4 1 b repr sente les listes d adjacence d un 1 graphe 4 1 a avec N 3 et M 6 la figure 4 2 b repr sente les listes d adjacence d un graphe simple 4 2 a avec N 4 et M 5 remarque
38. associ 2 Donner les traces d ex cution de l algorithme 3 Tracer les diagrammes de Gantt correspondant Appendix A Le Langage algorithmique C Manuel d utilisation Le langage algorithmique que nous proposons devra permettre 1 Une meilleure criture du cours En effet en plus de la d finition d une syntaxe pour l criture des programmes notamment dans la clause ALGOSs d un sch ma abstrait de r solution il faudra donner un certain nombre de r gles facilitant la lisibilit et la coh rence du contenu des diff rents chapitres ainsi qu une meilleure compr hension des aspects th oriques li s l algorithmique L utilisation directe dans les programmes en C de proc dures ou de types d finis abstraitement tant possible 2 Une pr sentation naturelle et claire des diff rents programmes du cours en r duisant au minimum les contraintes de syntaxe de fa on ce que la structuration des programmes soit per ue comme une question devant se poser avant celle du choix d un langage de programmation 3 Un passage simplifi vers des programmes en langage de haut niveau notamment en C pour la programmation imp rative et en smalltalk pour la programmation objet Un tel passage devant tre sinon automatique du moins largement facilit pour r duire au maximum la phase finale de construction de programmes Le langage propos sera aussi proche que possible d un langage naturel et en l occurence pour nous d
39. ate y et habite l adresse 2 Exemple 2 Soit X x y z un ensemble de 3 individus participant un tournoi Sur X on peut d finir les relations suivantes Ri x y ssi x a rencontr y Ro x y ssi x a battu y Ra x y ssi x est plus ag que y Ra x y ssi x a le m me ge que y 1 3 Quelques propri t s des relations binaires Une relation R sur un ensemble X est e R flexive sur X ssi Vx X R x x e Sym trique sur X ssi Vx y X R x y gt R y 1 e Antisym trique sur X ssi Vx y X Rx y et R y 1 gt x y e Transitive sur X ssi Vx y z X R x y et R y z gt R x 2 8 CHAPTER 1 RELATIONS ENSEMBLES ORDONN S Retour l exemple 2 e R est sym trique e R n a aucune des propri t s d finies pr c demment e Rz est r flexive transitive et antisym trique e Ty est r flexive transitive et sym trique On supposera que x y ssi x a le m me ge que y 1 4 Relations d ordre Relations d quivalence 1 D finition 1 Une relation r flexive et transitive est une relation de pr ordre 2 D finition 2 Une relation de pr ordre antisym trique est une relation d ordre 3 D finition 3 Une relation r flexive transitive et sym trique est une relation d quivalence Exemples e La relation R3 de l exemple 2 est une relation d ordre e R est une relation d quivalence 4 Remarques 1 Une relation d ordre R sur un ensemble X est totale ss
40. composante connexe On continue ainsi tant que il reste des sommets non explor s La figure 5 3 illustre l algorithme A chaque tape d une recherche en profondeur la composante connexe d un sommet est d termin Les sommets initiaux des deux recherches effectu es sont 1 et 4 24 CHAPTER 5 RECHERCHE DANS UN GRAPHE figure q ps width 6cm height 4cm Figure 5 3 D termination des composantes connexes d un graphe Impl ntation de l algorithme On modifie la fonction Visiter de l algorithme Profondeur de fa on ce qu elle marque les sommets visit s avec un num ro de composante connexe La fonction de parcours s crira alors Profondeur2 Graphe G Sommet V entier NC Si Visiter V G NC Profondeur2 G S NC L algorithme de d termination des composantes connexes est alors le suivant Connexit Graphe G Liste Sommet Sommet S Liste Sommet L NC 0 L ListSom G Pour chaque S dans L Si Ouvert S G VRAI NC NC 1 Profondeur2 G S NC retourner L L contient la liste des sommets marqu s par leur num ro de composante connexe Chapter 6 Le Type Abstrait de Donn e graphe 6 1 D finition abstraite de proc dures ou de types Avant d crire des programmes il s av re souvent n cessaire de d finir de fa on abstraite une ou plusieurs proc dures un ou plusieurs nouveaux types que ces programmes vont impl menter Il s agira donc pour nous de donner des r
41. d entr e n cessaires L criture d un programme correspondant une fonction ou proc dure se fait suivant le sch ma type des donnees retourn es nom de la proc dure liste des types et noms des arguments d clarations des types et noms des variables locales s quence directe Une instruction particuli re pourra tre associ e une proc dure de la mani re suivante retourner donn e dans le cas o la proc dure retourne une donn e ou retourner si elle ne retourne rien A 3 Types et op rateurs Les types sont not s en italique La d claration d une variable ou d un param tre et de son type se fait suivant le sch ma type nom variable A 3 1 Les types primitifs Les types primitifs autoris s sont entier r el car bool en Les variables de boucle et leur type peuvent ne pas tre d clar es s il n y a pas d ambiguit possible A 3 2 Les types abstraits S il est d fini abstraitement un type abstrait peut tre soit directement utilis dans un programme soit repr sent par un type construit Cette seconde repr sentation est alors un niveau d abstraction inf rieur On appellera type construit tout type ne faisant pas partie des types primitifs On a les sch mas syntaxiques type nouveau type ancien type ou encore type nouveau type ancien typei nom champl ancien type2 nom champ2 A 3 TYPES ET OP RATEURS 61 ancien typen nom champn Dans ce cas si une donn e de nom
42. d une solution un probl me d ordonnancement Cette m thode est ancienne mais elle est encore utilis e dans de nombreux logiciels de gestion C est un outil de visualisation simple son utilisation est possible dans des probl mes ne comportant pas de nombreuses t ches risque d illisibilit du diagramme Nous d crivons cette m thode partir des exemples suivants exemple On consid re un probl me d ordonnancement cinq t ches I 1 2 3 4 5 avec p 6 p2 3 p3 4 p4 5 p5 5 1 3 2 3 unit s de ressource 1 et 1 52 4 1 du 8 7 10 10 4 unit s de ressource 2 lorsque les dates d ex cution respectives sont 0 3 6 8 10 50 CHAPTER 8 ORDONNANCEMENT taches 1 1 2 m l 3 1 1 1 j 1 i 4 e j 1 i l 1 l 1 i 1 i I I 5 1 i I A I i 1 l i 1 ji 1 es 1 3 6 8 10 13 15 temps t ches temps quantite de ressources 209 Mines I i i i 15 Pati rr J PR 1 1 14 I I I J i l l i I i i 109 Las 80 i ressource 2 4 1 Po 3 p ressource 1 i 3 6 8 10 13 15 temps ressources gt temps exemple Ordonnancement dans un atelier Diagramme Diagramme On a une repr sentation job par job Dans notre exemple on va consid rer quatre travaux constitu s de trois t ches On utilisera la notation 4 j k pour repr senter la j t che du travail sur la machine k jobs PRA
43. de couleurs minimal n cessaire au coloriage d un graphe correspond au nombre chromatique y G de ce graphe Un graphe qui admet une coloration en k couleurs est dit k coloriable Le nombre chromatique est de 2 pour les graphes bipartis Il est par exemple de 3 pour le graphe de Petersen figure 7 6 figure color ps width 8cm height 4 4cm Figure 7 6 Exemples de coloriage a graphe biparti b graphe de Petersen Un algorithme simple pour trouver un coloriage valide qui donne donc une borne sup rieure sur le nombre chromatique du graphe est le suivant La coloration est d finie par les couleurs entre 1 et couleurs attribu es aux diff rents sommets et stock e pour chaque sommet v dans 7 8 K COLORATION DE GRAPHE 43 Color G 1 Initialisation couleurs 0 nombre de couleurs utilis es Pour tout sommet v de G Cy 0 sommets non colori s 2 It ration courante tant que tous les sommets ne sont pas colori s Trouver un sommet v non colori dans G liladj ListSadj v g Si il existe une couleur 1 lt c lt couleurs t q Vs lizadj Cs c Cv C sinon couleurs couleurs 1 Cou couleurs retourner couleurs Cet algorithme a l inconv nient de ne pas d terminer un coloriage optimal correspondant au nombre chromatique du graphe Nous explicitons ci dessous un algorithme par num ration qui permet de d terminer tous les colo riages d un graphes en au plus M couleurs 7 8 2 Principe de l
44. des co ts o Femer a D 3 D termination du pris heu I Evaluation du chite dame 2 Ja Y Doo Senan Tancemont d 2 FOI E 9 H SR OS RE 9 13 Dans cette repr sentation sch matique les v nements fin et d but de t ches apparaissent en tant que cercles divis s en trois parties 1 la partie gauche porte le num ro de sommet 2 la partie sup rieure droite porte la valeur de d but au plus t t de la t che qui a pour origine ce sommet 3 la partie inf rieure droite porte la valeur de d but au plus tard de la t che qui a pour origine ce sommet Cette repr sentation nous permet de lire rapidement sur le graphe quelles sont les t ches critiques Dans notre cas C D E H I J sont critiques Les marges pour les t ches F et G tant respectivement de 4 et de 3 unit s de temps La dur e du projet est de 17 unit s de temps 8 4 M thodes s rielles Une des id es les plus simples pour construire une solution d un probl me d ordonnancement consisterait construire une liste de t ches ordonn es par ordre de priorit d ex cution cet ordre pouvant tre statique ou dynamique Les m thodes s rielles utilisent cette id e en tenant compte de la pr sence de ressources renouvellables 58 CHAPTER 8 ORDONNANCEMENT A l instatnt t on affecte parmi les t ches pr tes c est dire celles dont tous les pr decesseurs sont achev es et qui utilisent moins de ressource
45. du graphe Ona ti max tj dj jer Di tant l ensemble des pr d cesseurs de dans le graphe et dj tant la dur e d une t che j 2 La dur e minimale du projet tn 1 est la longueur du plus long chemin de 0 n 1 3 La date au plus tard T du d but de la t che i On a Ti tn 1 li n 1 O li n 1 est la longueur du plus long chemin de n 1 4 La marge m de la t che 1 est la diff rence T ti Les t ches critiques seront les t ches pour lesquelles la marge est nulle On rappelle que pour qu une t che puisse commencer il est n cessaire que toutes les t ches qui la relient la t che 0 soient r alis es On recherchera alors un ordonnancement qui minimise la dur e totale et d autre part on identifiera les t ches critiques Algorithme de recherche des dates au plus t t l poser to 0 2 prendre les sommets j par niveau croissant dans le graphe potentiel et faire tj max tx dy ker 56 CHAPTER 8 ORDONNANCEMENT Algorithme de recherche des dates au plus t t l poser Tn 1 tn 1 2 prendre les sommets par niveau d croissant dans le graphe potentiel et faire fn La d termination des marges et des t ches critiques se fait alors de fa on vidente exemple La construction d un ouvrage n cessite la r alisation d un certain nombre de t ches que l on r sume dans le tableau de donn es suivant CEE Doain ON SE ET CA iomem E Onapente et toitaro J3 A
46. e 3 2 les t ches 3 et 4 doivent se chevaucher sur au moins une unit de temps 3 la t che 4 ne peut commencer qu apr s la fin des t ches 1 et 2 4 la t che 5 ne peut commencer avant le d but de la t che 3 Les dur es des t ches tant d d3 ds 1 d2 3 da 2 les in galit s respectives correspondant aux contraintes seront ta to gt 3etto ta gt 3 encadrement du d but de 2 t3 lt t4 da 1 et ta lt t3 d3 1 ta to gt da et ta t gt di ts gt ta On aura le graphe potentiel gt t ches suivant Apr s suppression des arcs inutiles on obtient le graphe Si O 0 8 2 3 1 0 3 3 o 4 2 L arc 1 6 est inutile car l arc 1 4 indiquant que 4 est ex cut e apr s est suffisant Remarque Dans un graphe potentiel gt t ches une contrainte disjonctive entre deux t ches 1 j pourra tre repr sent e comme suit i j 8 2 REPR SENTATION DES PROBL MES D ORDONNANCEMENT 93 Formulation potentielo tapes La formulation potentiel gt tapes est la premi re repr sentation d un ordonnancement a tre utilis e historiquement 1958 Cette formulation appel e aussi P E R T Program Evaluation and Research Technic construit un graphe potentiel dont les sommets sont associ s des v nements du type fin de t che d but de t che et dont les arcs sont associ s aux t ches Comme pour tout ce qui pr c de l
47. est appel ensemble des sommets du graphe G e U est appel ensemble des arcs du graphe G e Tout arc u U est un couple ordonn de sommets i j i est l extr mit initiale de u j est l extr mit finale de u i est un pr decesseur de j et j est un sommet successeur de i Une boucle est un arc dont les extr mit s co ncident e Si X n on dira que G est d ordre n e Un p graphe est un graphe G tel que Vi X l ensemble des arcs i j a un cardinal fini inf rieur ou gal p 2 2 Repr sentation graphique Graphiquement chaque sommet d un graphe G est repr sent par un point ou un cercle et chaque arc u i j par une fl che joignant le point i au point j orient e vers j figure 2 1 figure a ps width 7cm height 4cm Figure 2 1 Un 2 graphe avec une boucle 2 3 Graphe non orient Etant donn un ensemble X de sommets une ar te de sommets et j est un couple non ordonn i j d l ments de X Un graphe non orient G consiste en la donn e d un ensemble X de sommets et d un ensemble U d ar tes Graphiquement une ar te est repr sent e par un segment figure b ps width 7cm height 4cm Figure 2 2 Un graphe non orient avec une boucle e Un multigraphe est un graphe tel qu il peut exister plus d une ar te entre deux sommets e un graphe sans boucle tel que deux sommets sont joints par au plus une ar te est un graphe simple 11 12 CHAPTER 2 EL MENTS DE BASE remar
48. gles permettant d avoir des d finitions pr cises Ces r gles devront en outre tenir compte de la mise en oeuvre des entit s qu elles d finissent 6 1 1 D finition abstraite d une proc dure Une proc dure est une application d finie sur un ensemble de donn es dites d entr e appel es arguments cet ensemble peut tre vide Cette application peut retourner un r sultat appel donn e de sortie la proc dure est alors appel e fonction ou bien r aliser une action Par exemple la proc dure OCC1 est une fonction la proc dure SUPP n est pas une fonction Pour exister en tant qu entit abstraite une proc dure peut tre sp cifi e Les normes de sp cification utilis es doivent permettre L identification de la proc dure de pr ciser son mode d utilisation de pr ciser ses effets de pr ciser les donn es qu elle modifient Pratiquement voici les r gles de sp cification de proc dures abstraites que nous retiendrons 1 Pr ciser dans un en t te le nom de la proc dure pr c d du type du r sultat retourn si la proc dure est une fonction et suivi de la liste des arguments et de leur type A travers les exemples qui suivent nous d crivons la pr sentation d un en t te booleen OCC tableaufentier A entier e SUPP tableaufentier A entier e liste cr er 2 Pr ciser le contenu de trois clauses e Une clause PRE contenant un descriptif des conditions d utilisat
49. i R est une relation totale sur X sinon on pourra dire que R est une relation d ordre partielle 2 Un ensemble X sera dit totalement resp partiellement ordonn par une relation R ssi R une relation d ordre totale resp partielle sur X 5 Elements particuliers sur un ensemble ordonn Soit X un ensemble partiellement ordonn par une relation R et soit P une partie de cet ensemble e mEX est un minorant de P ssi Vx P R m 1 e MEX est un majorant de P ssi Va P R x M e nE P est un l ment minimal de P ssi Vx P non R x n e NEP est un l mentmaximal de P ssi Va P non R N x e s P est un minimum plus petit l ment de P ssi Vx P R m x e SEP est un maximum plus grand l ment de P ssi Vx P R x S e La borne inf rieure de P not e Inf P est le plus grand des minorants de P e La borne sup rieure de P not e Sup P est le plus petit des majorants de P 6 Exemple Exercice On consid re l ensemble X 1 2 3 5 10 20 30 partiellement ordonn e par la relation Rs telle que Vx y X Rs x y ssi x divise y 1 Monter que Rs est une relation d ordre partielle sur X 2 Soit la partie P 2 5 10 de X Pr ciser dans ce cas quels sont les l ments particuliers d finis pr c demment 7 Quelques op rations entre relations Dans tout ce qui suit R R1 R2 d signeront des relations binaires sur un ensemble X x y d signeront des l ments quelconques dans X 1 5
50. ifs 58 Ae Lestypes apstrdlbs e mie dans ay Abus ds es mate ce af A 2e eee it 58 AE Des table Ct A dE A D S verrine nd 59 3 4 Les Op rateurs oo ta a e e a ad ta dd eE 59 CONTENTS A 3 5 Les instructions primitives CONTENTS Pr ambule Il est commun ment admis que la Recherche Op rationnelle R O en tant qu activit scientifique orga nis e est n e durant la seconde guerre mondiale Des groupes de chercheurs attach s des organismes de d fense avaient alors pour t che de donner le maximum d efficacit diff rentes op rations millitaires d o le nom de R O La recherche op rationnelle consiste en une analyse scientifique de syst mes op rationnels entreprises administrations dans lesquels des moyens humains et mat riels ont t engag s dans un environ nement naturel Les domaines d intervention de la R O sont tr s divers social conomique militaire En tant que sci ence la R O inter agit avec d autres activit s scientifiques comme les math matiques ou l informatique qu elle utilise et qu elle enrichit aussi Cependant un emploi sans discernement de la R O en tant qu aide la d cision d op rateurs peut conduire dans certaines situations des erreurs Ces erreurs sont souvent cons quentes un mauvais emploi de techniques issues de la R O ou l inadaptation de ces techniques par rapport la r alit d
51. ion de la proc dure e Une clause MOD contenant les arguments modifi s e Une clause ACT contenant un descriptif des r sultats cons quents l action de la proc dure On fera aussi figurer un descriptif des transformations des arguments modifi s apparaissant dans la clause MOD Les clauses pouvant ventuellement tre vides Nous donnons une pr sentation de ces clauses dans les exemples suivants booleen OCC tableaufentier A entier e PRE A est tri par ordre croissant et ne contient pas de doublons ACT Retourne VRAI si e est dans A FAUX sinon SUPP tableaufentier A entier e 25 26 CHAPTER 6 LE TYPE ABSTRAIT DE DONN E GRAPHE PRE A est tri par ordre croissant et ne contient pas de doublons MOD A ACT Supprime l entier e si e est dans A liste cr er ACT Cr e une liste vide La mise en oeuvre d une proc dure doit r pondre aux sp cifications de son abstraction Une fois v rifi le contenu de la clause PRE elle doit en particulier ne modifier que les arguments apparaissant dans la clause MOD et agir en conformit avec le contenu de la clause ACT Les proc dures abstraites une fois mise en oeuvre dans un langage permettront une extension des op rations pr d finies dans ce langage Remarques Dans certains situations il est n cessaire dans une proc dure de prendre en charge des exeptions Il est alors int ressant de faire appara tre ces exeptions dans les sp cifications Par exemple en re
52. jout e T sans cr er de cycle On d montre que Si G a N sommets et M ar tes alors toute for t maximale de G contient n cessairement N p ar tes o p est le nombre de composantes connexes de G Dans le cas o G est connexe p 1 un arbre de G est d fini comme tant une for t maximale De plus tout graphe connexe contient au moins un arbre 7 6 2 Principe de l algorithme de Prim La structure de l algorithme est la m me que pour l algorithme de Dijkstra chaque tape on ajoute un sommet l arbre de poids minimum en construction Le tableau des marques x est tel que i est le poids minimal d une ar te u i j connectant un sommet j de l arbre Le tableau a contient cette ar te u de connexion de l arbre a i au Deux cas peuvent se pr senter 1 n est pas encore inclus Dans ce cas a 1 2 i est d j inclus dans l arbre Dans ce cas a 1 A chaque tape le sommet i choisi est celui non inclus a i lt 0 le plus proche de l arbre x i minimum Lors de l inclusion de les informations concernant les sommets non inclus adjacents sont mises jour A la fin de l algorithme a contient les ar tes incluses dans l arbre de poids minimum et m les poids correspondant remarques Un sommet arbitraire est utilis comme point de d part de l arbre sans ar te associ e Comme un arbre de poids minimum sur le graphe G X U comporte au plus N 1 ar tes
53. la source chaque sommet on maintient en plus un tableau C de sommets tel que C j contienne le pr decesseur de dans un plus court chemin de iy j C est initialis par C 5 io Vj ip Pour la mise jour des chemins il faut ajouter l tape courante Si D j l5x lt DIk exemple Pour l exemple de la figure 7 2 on obtient d o un plus court chemin de x 5 est 1114315 7 4 Chemin de capacit maximale 7 4 1 D finition e Capacit On consid re un graphe orient G X U A chaque arc u U on associe un nombre r el cu appel capacit de larc u en g n ral cu gt 0 Etant donn un chemin l mentaire C 41u2 4p entre deux sommets et j de G on appelle capacit du chemin C la quantit c C minuec cu e Probl me du chemin de capacit maximale Le probl me du chemin de capacit maximale consiste rechercher parmi l ensemble des chemins possibles un chemin de capacit maximale Nous nous int ressons la recherche des chemins de capacit maximale entre un sommet y donn et les autres sommets du graphe G 7 4 2 Remarques e On peut toujours consid rer que les chemins optimaux cherch s sont l mentaires ne contiennent pas de circuits En effet si tel n est pas le cas supposons que un chemin optimal P entre y et j ne soit pas l mentaire alors il contient au moins un circuit En liminant certains arcs on peut liminer le circuit et construire un nouveau
54. mmets restant dont la distance 29 est la plus courte possible L algorithme proc de en N 1 it rations Lors d une it ration quelconque l ensemble X des sommets du graphe est partag entre E et son compl mentaire E contient l ensemble des sommets pour lesquells la marque r i repr sente effectivement la longueur d un plus court chemin entre ip et i Comme les arcs ont une longueur positive ou nulle il est possible de trouver un plus court chemin de y un sommet quelconque en passant par des sommets de E On utilise un tableau D pour inscrire les longueurs de tels chemins D s que tous les sommets sont inclus dans E D contient alors les distances des plus courts chemins entre la source et les autres sommets du graphe 7 3 2 Enonc formel de l algorithme Dijkstra 1 Initialisation E io Dfi lisi si Parc io i wexiste pas ligi 00 2 It ration courante choisir j E tel que D j soit minimum E EU 5 Pour chaque k tel que k E D k min D k Diz Lu exemple On d roule l algorithme de Dijkstra sur le graphe de la figure 7 2 Le sommet source est xo Etape E Sommet D choisi D 2 D 3 DA D 5 ti 21 22 11 2 4 figure s ps width 4cm height 4cm 21 T2 Ta 3 x1 T2 T4 T3 T5 Figure 7 2 Application de Dijkstra sur un graphe pond r 36 CHAPTER 7 QUELQUES ALGORITHMES DANS LES GRAPHES Si l on d sire retrouver un plus court chemin de
55. n galit correspondant cette contrainte est Vji tj lt ti vji out tj gt v repr sent e par l arc i gt j 5 Encadrement du d but de la t che j j commence au plus t t un temps vij unit s de temps apr s le d but de et au plus tard un temps vji unit s de temps apr s le d but de 5 Les in galit s correspondant cette contrainte sont dj ti gt Vi repr sent es par tj lt ti Uji ou ti tj gt Vji Se a a y ij 6 Compatibilit de cadence Lorsqu une fraction cj de la dur e de j s est coul e au moins une fraction c de la dur e de doit s tre coul e 0 lt cij Cji lt 1 L in galit correspondante cette contrainte est F x Cijdi Cjid tj cjidj gt ti cdi out ti gt cijdi cjidj repr sent e par Parc i Le graphe potentielot ches Un graphe potentiel gt t ches mod lise un probl me d odonnancement avec contraintes potentielles Les t ches consid r es seront les n t ches du projet ainsi que deux t ches fictives d but et fin de projet not es respectivement 0 et n 1 On associera e les t ches aux sommets le nombre de sommets est gal au nombre de t ches e les contraintes potentielles aux arcs tels que construits pr c demment 52 CHAPTER 8 ORDONNANCEMENT exemple Consid rons l ensemble de 5 t ches 1 2 3 4 5 soumises aux contraintes 1 La t che 2 commence la dat
56. nt peuvent exister pour un m me graphe correspondant aux diff rents parcours possibles 5 3 L algorithme de parcours en profondeur On d finit les deux fonctions suivantes Visiter Sommet S Graphe G qui ferme un sommet S et permet d effectuer une op ration sur ce sommet comme par exemple l affichage des informations associ es S Ouvert Sommet S Graphe G bool en qui retourne VRAI si S est ouvert et FAUX si S est ferm L algorithme de parcours d un graphe G partir d un de ses sommets V est alors le suivant Profondeur Graphe G Sommet V Sommet S Liste li_adj Si Ouvert V G VRAI Visiter V G li adj ListSadj V G Pour chaque S dans li_adj Si Ouvert S G VRAI Profondeur G S Exercice Ecrire une version it rative de Profondeur On pourra utiliser une pile pour stocker le sommet courant et sa liste d anc tres Cela revient simuler les diff rents appels r cursifs 5 4 PARCOURS EN LARGEUR D UN GRAPHE 23 5 4 Parcours en largeur d un graphe Le parcours en largeur d un graphe est similaire au parcours en largeur d un arbre On utilise les m mes notions de sommets ouverts ou ferm s que pour le parcours en profondeur La description formelle d un parcours en largeur d un graphe est la suivante On visite le premier sommet S puis tous ses sommets adjacents ouverts Pour chacun de ceux ci on examine leurs sommets adjacents ouverts Les chiffres de la figure
57. ons caract riser un type de fa on abstraite partir de sp cifications Les r gles que nous retiendrons pour sp cifier un nouveau TAD sont les suivantes Pr ciser dans un en t te le nom du TAD la liste des noms des proc dures autoris es Pr ciser le contenu d une clause DESC qui est un descriptif des entit s ayant pour type le TAD Pr ciser dans une clause OP les sp cifications de chacune des proc dures autoris es O O ct 6 1 D FINITION ABSTRAITE DE PROC DURES OU DE TYPES 27 6 1 3 Exemple Le TAD ensemble ensemble creer inserer oter appartient taille choisir DESC Tout entite de type ensemble est un ensemble non borne d elements de meme type elt sans doublon Le type elt etant deja defini OP ensemble creer p ACT Retourne un ensemble vide inserer ensemble E elt x MOD E ACT Insere x dans E oter ensemble E elt x MOD E ACT Supprime l element x de E appartient ensemble E eltx ACT Retourne VRAI si x est dans E FAUX sinon entier taille ensemble E ACT Retourne le nombre d element de E elt choisir ensemble E PRE E est non vide ACT Retourne un element quelconque de E Fig 5 Exemple 2 Le TAD ensemble Nous donnons en appendice ce chapitre un manuel d utilisation d un langage algorithmique permettant d int grer dans des programmes en langage algorithmique des proc dures ou des types d finis abstraite ment
58. phe et partir d un ensemble provisoire de valeurs Ti i X de remplacer par r i lij celles des valeurs m j pour lesquelles r j gt m i liz Une telle modification signifie que l on a am lior x j en empruntant un chemin de longueur 7 entre io et suivi de l arc i j de longueur l j Le parcours du graphe G partir de y se fait autant de fois que n cessaire jusqu obtention des longueurs 7 j j X v rifiant toutes les in galit s 1 Les marques sont initialis es par m ip 0 et m i 00 Vi X i io 7 2 2 Complexit La complexit de cet algorithme est facile d terminer en effet chaque it ration consiste en un parcours complet de la liste des arcs ce qui n cessite M U op rations et comme dans le pire des cas il faut N X it rations on en conclue que l algorithme est de complexit O M N En admettant le r sultat suivant Si un graphe G X U N X wadmet pas de circuit de longueur strictement n gative alors les valeurs finales n i sont obtenues en au plus N 1 it rations on peut aussi utiliser l algorithme de Ford Bellman pour d tecter un circuit de longueur strictement n gative dans le graphe suivant que le nombre d it rations est inf rieur ou sup rieur N 1 7 2 3 Enonc formel de l algorithme Ford Bellman 1 Initialisation rio 0 rfi Vi X i io Vi X p i i le pr decesseur de 1 est 1 k 0 compteur
59. prenant la proc dure SUPP et en supposant en plus que cette proc dure retourne la chaine de caract re vide si le tableau A est vide on aura SUPP tableaufentier A entier e chaine PRE A est tri par ordre croissant et ne contient pas de doublons MOD A ACT Supprime l entier e si e est dans A sinon retourne la chaine de caract re vide 6 1 2 D finition abstraite d un nouveau type Un type abstrait de donn es TAD permet de caract riser la nature d un groupe d entit s ainsi que les p rations autoris es sur les entit s de ce groupe Par exemple le type ensemble d l ments avec comme p rations autoris es sur un ensemble la creation l insertion la suppression la taille l appartenance Un nouveau TAD doit r pondre des applications pr cises par exemple un ensemble peut servir au stockage de donn es sans doublon et permettre en plus des op rations autoris es d autres op rations elles que la recherche d un l ment ou le tri Un TAD est ad quat lorsqu il contient toute op ration n cessaire une utilisation dans une application donn e Un type de donn es demeure abstrait tant qu il n a pas t construit dans un langage L abstraction de type permet de diff rer les d cisions de choix de mise en oeuvre dans un langage par exemple si l on d finit le TAD mot on pourra choisir de l impl menter soit par une cha ne de caract res soit par un tableau de caract res Nous pouv
60. que un graphe orient G X U on peut toujours associer un graphe non orient G en consid rant U comme un ensemble d ar tes C est le cas des graphes des figures 2 1 et 2 2 Dans la suite on dira graphe pour graphe orient sauf indication contraire 2 4 Terminologie e Arcs ar tes adjacents es Deux arcs ar tes sont adjacents es si ils ont au moins une extr mit commune exemple Dans le graphe de la figure 2 1 u2 et u3 sont adjacents au sommet 2 e Degr demi degr Le demi degr ext rieur d un sommet i not d i est le nombre d arcs ayant comme extr mit initiale Le demi degr int rieur d un sommet i not d7 i est le nombre d arcs ayant i comme extr mit finale ou terminale le degr d un sommet i not d i est la somme des ses demi degr s int rieur et ext rieur exemple Dans le graphe de la figure 2 1 d 2 2 d 2 1 et d 2 2 1 3 e Arcs ar tes incidents es Cocycles Soit A X A un est sous ensemble de sommets de X On d finit les ensembles suivants QT A u Ulu i j i E A j A QT A u Ulu i j i A j A Q A 974 U 4 Q A est l ensemble des arcs partant de A et aboutissant en dehors de A Q7 4 est l ensemble des arcs partant de l ext rieur de A pour aboutir dans A Q A est un cocycle du graphe exemple Dans le graphe de la figure 2 1 avec A 2 3 on a Q 4 Luz U4 U6 ur 07 A u
61. recouvrant X telles que V i j EU 1EX1 gt 7 X2 et 1E EX2 gt jE EX1 exemple Le graphe de la figure 2 5 est un graphe bipartite avec Xy 1 2 et X2 3 4 5 figure e ps width 4cm height 3cm Figure 2 5 Un graphe bipartite 2 5 Implantation d un graphe L implantation d un graphe peut se faire par le biais de diff rents types de matrices associ es au graphe 2 6 Matrice d incidence sommets arcs Une matrice d incidence sommets arcs d un graphe G X U avec X n et U m est une n x m matrice Aiu telle que Aju 1 et Aju 1 si i j est un ue arc dans G Aiu 0 Sinon exemple La matrice de la figure 2 6 a indique que l on a un graphe avec 4 sommets 4 lignes 5 arcs 5 colonnes le premier arc 1 colonne d extr mit initiale 1 et finale 2 411 1 421 1 le deuxi me arc 2 colonne d extr mit initiale 1 et finale 3 A12 1 A32 1 On obtient ainsi le graphe de la figure 2 6 b 14 CHAPTER 2 EL MENTS DE BASE 1 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 i figure f ps width 4cm height 3cm Figure 2 6 a Une matrice d incidence sommets arcs b le graphe correspondant 2 7 Matrice d incidence sommets ar tes Une matrice d incidence sommets ar tes d un graphe non orient G X U avec X net U m est une n x m matrice Aiu telle que Aiu 1 si i j est une u ar te dans G Aiu 0 sinon exemple Le graphe non
62. rire une version it rative de Profondeur On pourra utiliser une pile pour stocker le sommet courant et sa liste d anc tres Cela revient simuler les diff rents appels r cursifs Pour implanter l algorithme on utilise une pile dans laquelle on place les sommets dont la liste d adjacence reste explorer 6 4 L algorithme de parcours en largeur On d finit les deux proc dures suivantes Sommet oter tableau sommet FILE MOD FILE ACT supprime le dernier l ment de FILE et le retourne mettre tableau sommet FILE sommet s MOD FILE ACT Ins re s la premi re position dans FILE les autres positions dans FILE tant incr ment es d une unit 6 5 RECHERCHE DES COMPOSANTES CONNEXES Largeur Graphe G Sommet V sommet s ensemble E tableau sommet T FILE mettre FILE V visiter G V tant que videp FILE FAUX s oter FILE E ens adjp G s si taille E 0 copie E TAB Pour i 0 taille E 1 si ouvert T i G visiter G T i mettre FILE T i i i 1 o Exercice 31 Donner les traces d ex cution de ce programme avec en entr e le graphe de la figure 15 et le sommet a prog g g 6 5 Recherche des composantes connexes On modifie la fonction Visiter de Palgorithme Profondeur de fa on ce qu elle marque les sommets visit s avec un num ro de composante connexe La fonction de parcours s crira alors Profondeur2 Graphe G Sommet
63. s q est l extr mit initiale de P et iq est l extr mit finale de P Un chemin est l mentaire si en le parcourant on ne rencontre pas deux fois le m me sommet Dans le cas d un 1 graphe un chemin peut tre d crit de fa on quivalente par la succession ordonn e des sommets qu il rencontre exemple Dans le graphe de la figure 3 1 P u1 u3 u4 u7 est un chemin allant du sommet 1 au sommet 4 On peut le repr senter par la s quence 1 2 5 3 4 de sommets du graphe e circuit circuit l mentaire Un circuit l mentaire est un chemin l mentaire dont les extr mit s coincident 3 3 Connexit nombre de connexit o composante connexe Un graphe G X U est dit connexe si pour tout couple de sommets et j de X il existe une chaine joignant 2 et j La relation i R JD ou 14 j etil existe une chaine joignant i j est une relation d quivalence sur X Les classes d quivalence induites sur X par cette relation forment une partition de X Soit X1 X2 Xp cette partition Les sous graphes G1 G2 Gp engendr s par les sous ensembles X1 X2 Xp sont appel s composantes connexes de G e nombre de connexit graphe connexe Le nombre p de composantes connexes distinctes est le nombre de connexit du graphe un graphe est dit connexe si son nombre de connexit p 1 chaque composante connexe est un graphe connexe figure j ps width 9cm height 4cm Figure
64. site diff rents pour les sommets exemple Par exemple si l tape 2 de la figure 5 1 b le sommet e avait t choisi la place de c on aurait obtenu la s quence de visite a b e c d au lieu de a b c e d Le parcours d un graphe connexe comme celui de la figure 5 1 a partitionne implicitement l ensemble des arcs du graphe en deux ensembles ceux qui ne sont pas utilis s par la recherche et ceux qui sont utilis s assortis d une sur la figure L arbre correspondant ce second ensemble est appel arbre de 21 22 CHAPTER 5 RECHERCHE DANS UN GRAPHE Anc tres et sommets Commentaire MEME a est le sommet courant de d part on choisit b seul sommet adjacent de a on choisit c parmi les sommets ad jacents de b mais e ou c auraient pu tre choisis 3 ouvert il est choisi figure 0 ps width 4cm height 4cm 4 a gt b gt c gt e e ne poss de aucun adjacent ouvert on remonte son anc tre c idem pour c b et e sont ferm s on remonte l anc tre b de d a tant ferm a b c e d d est le seul sommet adjacent b encore ouvert 8 c e d on remonte de b vers a a n a pas d anc tre sommet ini tial et ses adjacents b sont tous ferm s fin Figure 5 1 a Un graphe b les tapes d un parcours en profondeur partir de a recouvrement Un tel arbre comprend tous les sommets de la composante connexe visit On notera que plusieurs arbres de recouvreme
65. t che 2 Retard d une t che ou indicateur de retard existence ou non existence d un retard Ils peuvent exprimer 1 Une dur e totale de l ordonnancement 2 Un respect des dattes au plus tard 3 Une minimisation d un co t 4 Un nombre d interruptions pr emption 8 2 REPR SENTATION DES PROBL MES D ORDONNANCEMENT 49 8 1 5 Notations Dans la suite du cours noous opterons pour les notations suivantes I ensemble de t ches i j I t ches appartenant T pi dur e de la t che i ri date de d but au plus t t d ex cution de la t che 2 d date de fin au plus tard d ex cution de 2 ti date de d but d ex cution de i c date de fin d ex cution de i w poids associ i Pik temps d ex cution de sur la machine k Une contrainte potentielle exprimant une ant riorit d une t che par rapport une t che j s exprimera par une in galit Par exemple l in galit tj t gt a exprimera le fait que la t che j d butera quand ay unit s de temps se seront coul es apr le d but d ex cution de la t che 2 Exercice Exprimer en fonction des donn es et des notations introduites pr c demment la dur e totale d un ordonnancement le retard d une t che 2 l indicateur de retard d une t che i 8 2 Repr sentation des probl mes d ordonnancement 8 2 1 Le diagramme de Gantt Le diagramme de Gant est une m thode de repr sentation
66. t LA Liste des Arcs ou Ar tes sont utilis s Les informations relatives un sommet sont contenues dans LA entre les cases LP i et LP i 1 1 Lorsque l on utilise ce type de repr sentation il est g n ralement n cessaire d indiquer dans un autre tableau LS 1 de m me taille que LA le num ro de l autre extr mit correspondant i LS n est pas n cessaire dans le cas o EI et EF sont en m moire De plus la dimension de LP est gale N 1 et celle de LA et LS M figure n ps width 10cm height 4cm Figure 4 4 a un graphe b liste de cocycles associ e exemple Pour le graphe de la figure 4 3 a repr sent nouveau en 4 4 b les listes de cocycles corre spondantes sont repr sent es sur la figure 4 4 b Chapter 5 Recherche dans un graphe 5 1 Objectifs de cette recherche Etant donn un graphe G X U nous allons d finir un algorithme r pondant aux probl mes suivants Un sommet j est il accessible par un chemin partir d un autre sommet Quel est l ensemble de tous les sommets accessibles partir d un sommet i donn 5 2 Principe du parcours en profondeur d un graphe Le parcours en profondeur d un graphe est similaire au parcours en pr ordre d un arbre Au cours de l exploration un sommet pourra se trouver dans deux tats ouvert si il n a pas encore t visit ferm sinon L exploration se fait partir d un sommet
67. tes 1 Les contraintes de type potentiel qui peuvent tre des contraintes e de succession Une t che B ne peut commencer avant qu une t che ne soit termin e ou parvenue un degr d ach vement e de localisation temporaire Une t che A ne doit pas commencer avant telle date ou encore doit tre achev e telle date 47 48 CHAPTER 8 ORDONNANCEMENT 2 Les contraintes de type disjonctif lorsqu on impose la r alisation non simultan e de certaines paires de t ches 3 Les contraintes de type cumulatif lorsqu au cours du temps il y a accumulation de moyens consacr s la r alisation de t ches Dans notre cours nous nous pr occuperons essentielllement de contraintes de type potentiel ou dis jonctif 8 1 2 Les t ches Dans un probl me d ordonnancement simple une t che est ex cut e une seule fois et enti rement Cepen dant dans la pratique plusieurs situations peuvent tre rencontr es 1 Une t che peut tre ex cut e par morceau on dit alors que la t che est morcelable ou que la pr emption est possible Une t che A est pr mpt e par une t che B l instant t si A tait en cours d ex cution avant t et employait une ressource allou e B l instant t ce qui provoque l interruption de 2 Plusieurs t ches A B peuvent tre soumises des contraintes de ressource et des contraintes internes de succession donnant naissance une infinit de t ches A1 Az Ap
68. tourne VRAI si G est vide FAUX sinon DESC Tout objet G de type it graphe est caracterise par un ensemble de sommets et un ensemble d arcs U dont les extremites sont dans X On suppose definis ACT Supprime le sommet s de X ainsi que tous les arcs dans U dont l une ACT Supprime les arcs dans U ayant pour extremites sl et s2 X Fig 5 Exemple 2 Le TAD grahe 29 Pour les proc dures que l on va construire voir la section pr c dente pour les principes des algorithmes 6 3 L algorithme de parcours en profondeur On d finit les trois propc dures suivantes Visiter Sommet S Graphe G MOD S G ACT Ferme le sommet S Effectue une op ration sur ce sommet comme par exemple l affichage des informations associ es S bool en ouvert sommet S Graphe G ACT Retourne VRAI si S est ouvert FAUX sinon sommet copie ensemblefelt E tableaufelt n TAB REQ taille E n ACT Recopie les lements de E dans TAB L algorithme de parcours d un graphe G partir d un de ses sommets V est alors le suivant Profondeur Graphe G Sommet V tableau sommet TAB 30 CHAPTER 6 LE TYPE ABSTRAIT DE DONN E GRAPHE ensemble E ens adj G V visiter G V copie E TAB Pour i 0 taille E 1 si ouvert V G Profondeur G TABTi i i 1 Exercices 1 Donner les traces d ex cution de ce programme avec en entr e le graphe de la figure 15 et le sommet a 2 Ec
69. travers par ex emple la construction d algorithmes de r solution dont la mise en oeuvre sous forme de programmes informatiques est r alisable et de mani re plus g n rale dans la gestion du projet D finir les sp cifications des l ments intervenant dans les solutions informatiques retenues Ces sp cifications devant permettre une d finition abstraite mais suffisamment pr cise de ces l ments 6 La validation du mod le On teste partir de jeux de donn es judicieusement choisies le mod le et les solutions retenues 7 L implantation et la maintenance informatique du modele et des solutions Chapter 1 Relations ensembles ordonn s 1 1 D finition Une relation n aire R Yn n N sur un ensemble E est un sous ensemble Ex du produit cart sien ExXEx xEB E ER est appel graphe de la relation R Notations Si e e2 n Er on dira que e1 e2 n sont en relation suivant R et on notera R e1 2 En Une relation n aire peut tre totale sur un ensemble E si elle met en relation tout n uple dans E elle est partielle sinon Pour la suite nous ne consid rerons que des relations binaires 1 2 Exemples Exemple 1 Consid rons les ensembles suivants X un ensemble de noms Y un ensemble de dates Z un ensemble d adresses On peur d finir sur X x Y x Z la relations R telle que V x y 2 X xY x Z R z y z ssi l individu dont le nom est x est n la d
70. ttribu e un som met comprise entre 1 et M Si un sommet i n a pas encore de couleur attribu e couleurs i 0 Une proc dure suivant couleurs i d termine et attribue la prochaine couleur valide pour le sommet Si aucune couleur valide ne peut tre attribu e au sommet suivant les couleurs d j attribu es aux sommets adjacents i couleurs i M 1 Enum_Color G V E M 1 Initialisation couleurs 1 V 0 aucune couleur attribu e k 0 fin FAUX 2 It ration courante Faire suivant couleurs k cas 1 couleurs k lt M et k lt V k k 1 avancer dans l arbre cas 2 couleurs k lt M et k V montrer couleurs une solution trouv e cas 3 couleurs k gt M et k gt M couleurs k 0 impossible de colorier k k 1 retour dans l arbre cas 4 couleurs k gt M et k 1 fin VRAI retour la racine jusqu fin VRAI retourner couleurs exemple L ex cution de l algorithme est illustr e pour le graphe de la figure 7 9 a dans le tableau ci dessous avec M 3 Les 18 premi res it rations de l algorithme sont repr sent es Les colonnes v repr sentent couleurs i la fin de chaque tape La colonne k montre la valeur de k la fin d une tape la colonne cas montre l action effectu e dans cette tape Si l on est dans le cas 3 suivant retourne M 1 4 et la couleur du sommet est remise 0 indiqu par 4 0 pour la couleur du sommet 7 8 K COLORATION DE GRAP
71. u Fran ais A l Les structures de contr le e La s quence directe instruction1 Commentaires instruction2 instructionn Chaque instruction peut tre suivie d un commentaire facilitant la compr hension du programme ces commentaires sont encadr s par et L accolade ouvrante indique le d but de la s quence et la fermante sa fin e Les structures conditionnelles si condition si condition s quence s quencel sinon s quence2 e Les structures it ratives 1 tant que condition faire 59 60 APPENDIX A LE LANGAGE ALGORITHMIQUE C MANUEL D UTILISATION s quence s quence tant que condition Il est important d insister sur le fait que dans toutes les structures pr c dentes les expressions conditionnant l ex cution de telle ou telle partie d un programme devront tre des expressions logiques dont l valuation pourra se faire simplement 2 pour i init term s quence Un inconv nient dans l utilisation de la structure pour est du au fait que l it ration n est pas modifiable et est fix e un l ment par it ration Pour forcer la sortie dune boucle on utilisera l instruction sortir boucle A 2 Les fonctions et proc dures Un appel une fonction ou proc dure d finie de fa on abstraite ou construite se fera par son nom soulign ou son nom soulign et index par p lorsqu il s agit d une primitive d un TAD Le nom est suivi de la liste des donn es
72. ue j E Dij max D j min Dfi cis SiE X fin 7 5 Plus court chemin entre toutes les paires de sommets Floyd 7 5 1 Principe de l algorithme On remarque tout d abord que si tous les arcs sont munis de longueurs positives ou nulles il suffit d appliquer N fois l algorithme de Dijkstra Si les certains arcs sont de longueur strictement n gative on peut utiliser N fois l algorithme de Ford Bellman Cependant on pr f re utiliser un algorithme associ une m thode matricielle Notons L la N x N matrice l 1 lt lt w dont le terme l j i j est gal la longueur de l arc i j si il existe 00 sinon Pour les l ments diagonaux i j li 0 Pour 1 lt k lt N notons L la matrice Di dont le terme 5 d signe la longueur minimale d un chemin d origine et d extr mit j dont tous les sommets interm diaires appartiennent au sous ensemble 1 2 k Lorsque i j 5 d signe la longueur minimale d un circuit passant par 4 et astreint n utiliser comme sommets interm diaires que des sommets parmi les sommets 1 2 k Pour k 0 on a L L On remarque que alors les coefficients des matrices L sont li s par la relation de r currence R vi vj Min lig l En effet deux situations peuvent se pr senter Le plus court chemin de j avec les sommets 1 2 k passe par k Dans ce cas le chemin consid r est form d un sous chemin entre et k suivi d un
73. un probl me L tude d un projet de R O pour tre bien men e doit en g n ral passer par les tapes suivantes 1 La d finition des objectifs A ce stade on d termine ce que le projet est suppos accomplir Pratiquement cela consiste entre autre tenir compte de toute hypot se et commentaire des personnes ou organisations impliqu es dans ce projet r examiner toute notion pr con ue li e au probl me que l on traite se mettre la place d un op rateur et d examiner le projet sous cet angle 2 L volution du plan de projet Il faut ce niveau planifier l volution dans le temps et l espace du projet d finir une chronologie et une r partition des diff rentes t ches accomplir 3 La formulation du ou des probl mes rencontr s C est une tape fondamentale dans la con duite du projet Elle n cessite une information la plus compl te possible afin de r unir suffisamment de donn es pour mieux cerner le ou les probl mes A un niveau plus formel des supports symbol iques de ces donn es sont utilisables variables constantes relations 4 Le mod le Un mod le exprime une ou plusieurs relations entre les diff rentes variables et con stantes D un mod le construit d pend lefficacit d ventuels d cisions prendre Un mod le peut tre d crit l aide d un langage formel ou dans un langage naturel Exemple Supposons que l on se trouve devant le probl me suivant
74. un arc de a vers b a b si a bet b a sont en relation on aura une ar te non orient e a b Une relation sera donc repr sent e par un ensemble d arcs ou d ar tes non orient es pouvant se succ der Exemple La relation D d finie sur X 1 2 3 6 12 telle que Va y EX D x y ssi x divise y peut tre repr sent e par 10 CHAPTER 1 RELATIONS ENSEMBLES ORDONN S X 7 O Ce type de repr sentation est appel e repr sentation sagitale On remarquera que 1 est origine d arcs ayant pour autre extr mit chacun des autres l ments et que d autre part 12 est une extr mit finale d arcs dont l autre extr mit est un autre l ment quelconque de X Les arcs peuvent tre tiquett Dans l exemple pr c dent une tiquette d un arc pourrait tre un entier dont le produit avec l entier l origine de l arc donnerait l entier l extr mit finale de Parc Dans le cas d une relation d ordre si l on supprime les boucles dues la r flexivit et les arcs dus la transitivit on obtient un diagramme de Hasse Le diagramme de Hasse de l exemple pr c dent est Poo o I 3 7 12 6 Ces deux repr sentations sont des graphes particuliers Exercice Repr sentation d un ordonnancement Etude d un cas Chapter 2 El ments de base 2 1 Graphe orient D finitions e Un graphe orient G consiste en la donn e d un couple d ensembles X U e X
75. ut sommet u dans U fu est appel e quantit de flot ou flux sur Parc u L galit I exprime que en un sommet du graphe la somme des flux sortant gt ew Ju est gale la somme des flux entrant gt uey i fu On remarquera l analogie entre l galit I et la loi de conservation aux noeuds de Kirchoff dans un r seau lectrique Pour cette raison l galit I est appel e loi de Kirchoff dans les graphes exemple Dans le graphe de la figure 7 4 le vecteur f 5 3 2 2 1 4 est un flot sur G L orientation choisie pour les arcs est arbitraire La n gativit d une composante f4 par exemple indique que le flot va du sommet 2 au sommet 3 sur l arc 4 figure v ps width 6cm height 4cm Figure 7 4 Un flot sur un graphe Les flux sont donn s entre parentheses c t des num ros des arcs 7 7 2 Probl me du flot maximum On consid re un graphe G X U o chaque arc u U est muni d un nombre cu gt 0 appel capacit de Parc u Lorsqu on d finit un flot sur G Cu indique la limite sup rieure d un flot admissible sur u On se donne deux sommets distincts e et s dans G e n a pas de pr d cesseur et constitue une entr e du graphe s n a pas de successeur et constitue une sortie du graphe exemple Dans l exemple de la figure 7 4 e 1 et s 4 On consid re le graphe G X U obtenu en ajoutant G un arc fictif de e vers s Dans l exemple il s agit de Parc 1 7 7 PROBL ME

Download Pdf Manuals

Related Search

Graphes graphesthesia graphes graphesthesia test graphesthesia definition graphenstone graphesthesia and stereognosis graphes nsi graphes python graphes de connaissances graphesthesia pronunciation

Related Contents

Manual de Usuario  Navigator 3000 User's Manual  LX-180EXA 型 取扱説明書 - レイシー  Foglio istruzioni hacrh433  DataTraveler Vault - Privacy  Operating Instructions And Parts Manual  3 gasmet dx-4030 ftir gas analyser  Manual de Instalación  HP ZBook 17 G2  

Copyright © All rights reserved. Failed to retrieve file