Example: quiz answers

Théorie des graphes et optimisation dans les graphes

Th orie des graphes et optimisation dans les graphesChristine SolnonTable des mati res1 Motivations32 D finitions43 Repr sentation des sentation par matrice d adjacence .. sentation par listes d adjacence ..84 Cheminements et connexit de chemin, chaine, cycle et circuit .. transitive d un graphe .. de connexit .. de graphe eul rien .. de graphe hamiltonien ..165 Arbres et arborescences176 graphes planaires207 Coloriage de graphes , cliques et stables238 Parcours de couvrante associ e un parcours .. en largeur (Breadth First Search = BFS) .. du parcours en largeur .. en profondeur (Depth First Search = DFS) .. du parcours en profondeur ..2919 Plus courts finitions.

le loup est représenté par la lettre L, le chou par C, la brebis par B et l’homme par H, et où un état est représenté par un cercle coupé en deux demi-cercles représentant les rives gauche et droite de la rivière. Etant donné un tel graphe, on pourra chercher un chemin allant de l’état initial à …

Tags:

  Lupo, Le loup

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Théorie des graphes et optimisation dans les graphes

1 Th orie des graphes et optimisation dans les graphesChristine SolnonTable des mati res1 Motivations32 D finitions43 Repr sentation des sentation par matrice d adjacence .. sentation par listes d adjacence ..84 Cheminements et connexit de chemin, chaine, cycle et circuit .. transitive d un graphe .. de connexit .. de graphe eul rien .. de graphe hamiltonien ..165 Arbres et arborescences176 graphes planaires207 Coloriage de graphes , cliques et stables238 Parcours de couvrante associ e un parcours .. en largeur (Breadth First Search = BFS) .. du parcours en largeur .. en profondeur (Depth First Search = DFS) .. du parcours en profondeur ..2919 Plus courts finitions.

2 De Dijkstra .. de Bellman-Ford .. se ..3910 Arbres couvrants minimaux (ACM)3911 R seaux de transport4212 Planification de projet par les r Co t et dur e d une t che .. Contraintes .. Mod lisation des contraintes de pr c dence par un graphe .. Dur e minimale d ex cution .. Date au plus tard .. Marge totale .. Chemins et t ches critiques ..5213 Pour en savoir plus5221 MotivationsPour r soudre de nombreux probl mes concrets, on est amen tracer sur le papier des petitsdessins qui repr sentent (partiellement) le probl me r soudre. Bien souvent, ces petits dessins secomposent de points et de lignes continues reliant deux deux certains de ces points. On appelleraces petits dessins desgraphes, les points dessommetset les lignes desarcsouar tes, selon quela relation binaire sous-jacente est orient e ou exemples de mod lisation par des graphesR seaux routiers :Le r seau routier d un pays peut tre repr sent par un graphe dont les som-mets sont les villes.

3 Si l on consid re que toutes les routes sont double sens, on utilisera un graphenon orient et on reliera par une ar te tout couple de sommets correspondant deux villes reli espar une route (si l on consid re en revanche que certaines routes sont sens unique, on utilisera ungraphe orient ). Ces ar tes pourront tre valu es par la longueur des routes correspondantes. Etantdonn un tel graphe, on pourra s int resser, par exemple, la r solution des probl mes suivants :- Quel est le plus court chemin, en nombre de kilom tres, passant par un certain nombre de villesdonn es ?- Quel est le chemin traversant le moins de villes pour aller d une ville une autre ?- Est-il possible de passer par toutes les villes sans passer deux fois par une m me route ?

4 Processus tapes :Certains probl mes peuvent tre sp cifi s par un tat initial, un tat final,un certain nombre d tats interm diaires et des r gles de transition pr cisant comment on peutpasser d un tat l autre. R soudre le probl me consiste alors trouver une suite de transitionspermettant de passer de l tat initial l tat final. Beaucoup de jeux et autres casse-t te peuvent tre mod lis s ainsi. Consid rons, par exemple, le probl me du chou, de la brebis et du loup :Un brave homme se trouve au bord d une rivi re qu il souhaite traverser, en compa-gnie d un loup, d une brebis et d un chou. Malheureusement, il ne dispose que d unepetite barque, ne pouvant porter en plus de lui-m me qu un seul de ses compagnons( le loup ou la brebis ou le chou).

5 Bien s r, la brebis refuse de rester seule avec le loup ,tandis que le chou refuse de rester seul avec la brebis. Comment peut-il s y prendrepour traverser la rivi re avec ses trois compagnons et continuer son chemin ?L tat initial est l tat o tout le monde est sur la rive gauche de la rivi re, tandis que l tat finalest l tat o tout le monde est sur la rive droite de la rivi re. La r gle de transition est la suivante :si l homme est sur une rive avec certains de ses compagnons, alors il peut passer sur l autre rive,soit seul, soit accompagn par un seul de ses compagnons se trouvant sur la m me rive que lui,sous r serve qu il ne laisse pas le loup seul avec la brebis, ou la brebis seule avec le chou.

6 Onpeut mod liser ce probl me par un graphe non orient , dont les sommets repr sentent les tatspossibles, et les ar tes le fait qu on peut passer d un tat l autre par une transition. On obtientalors le graphe non orient suivant :3 HCBLLBCHLCHBLCHBLHCBLHBCBLHCBHLCHBCLCBLH LBHCCHLBCHBLHBLCHLBCEtat initialEtat finalo le loup est repr sent par la lettreL, le chou parC, la brebis parBet l homme parH, et o un tat est repr sent par un cercle coup en deux demi-cercles repr sentant les rives gauche et droitede la rivi donn un tel graphe, on pourra chercher un chemin allant de l tat initial l tat finis :Un automate fini permet de reconna tre un langage r gulier et peut tre repr -sent par un graphe orient et tiquet.

7 Par exemple, l automate fini reconnaissant le langage desmots de la formeanbm(les mots compos s d une suite de a suivie d une suite de b ) peut trerepr sent par le graphe suivant132baabCe graphe poss de 3 sommets et 4 arcs, chaque arc tant tiquet par un symbole (aoub). Etantdonn un tel graphe, on peut s int resser, par exemple, la r solution des probl mes suivants :- Existe-t-il un chemin allant du sommet initial (1) au sommet final (3) ?- Quel est le plus court chemin entre deux sommets donn s ?- Existe-t-il des sommets inutiles, par lesquels aucun chemin allant du sommet initial un sommetfinal ne peut passer ?2 D finitionsDe fa on plus formelle, ungrapheest d fini par un coupleG= (S,A)tel que-Sest un ensemble fini de sommets,-Aest un ensemble de couples de sommets(si,sj) graphe peut tre orient ou non : Dans ungraphe orient , les couples(si,sj) Asont orient s, c est dire que(si,sj)est uncouple ordonn , o siest le sommet initial, etsjle sommet terminal.

8 Un couple(si,sj)estappel unarc, et est repr sent graphiquement parsi exemple,4123456repr sente le graphe orient G= (S,A)avecS={1,2,3,4,5,6}etA={(1,2),(2,4) ,(2,5),(4,1),(4,4),(4,5),(5,4),(6,3)}. Dans ungraphe non orient , les couples(si,sj) Ane sont pas orient s, c est dire que(si,sj)est quivalent (sj,si). Une paire(si,sj)est appel e unear te, et est repr sent egraphiquement parsi exemple,245361repr sente le graphe non orient G= (S,A)avecS={1,2,3,4,5,6}etA={(1,2),(1,5) ,(5,2),(3,6)}.Terminologie L ordred un graphe est le nombre de ses sommets. Uneboucleest un arc ou une ar te reliant un sommet lui-m me. Un graphe non-orient est ditsimples il ne comporte pas de boucle, et s il ne comporte jamaisplus d une ar te entre deux sommets.

9 Un graphe non orient qui n est pas simple est unmulti-graphe. Dans le cas d un multi-graphe,An est plus un ensemble mais un multi-ensembled ar tes. On se restreindra g n ralement dans la suite aux graphes simples. Un graphe orient est unp- graphes il comporte au plusparcs entre deux sommets. Le plussouvent, on tudiera des 1- graphes . Ungraphe partield un graphe orient ou non est le graphe obtenu en supprimant certains arcsou ar tes. Unsous-graphed un graphe orient ou non est le graphe obtenu en supprimant certains som-mets et tous les arcs ou ar tes incidents aux sommets supprim s. Un graphe orient est dit l mentaires il ne contient pas de boucle. Un graphe orient est ditcomplets il comporte un arc(si,sj)et un arc(sj,si)pour toutcouple de sommets diff rentssi,sj S2.

10 De m me, un graphe non-orient est dit complet s ilcomporte une ar te(si,sj)pour toute paire de sommets diff rentssi,sj d adjacence entre sommets : Dans un graphe non orient , un sommetsiest ditadjacent un autre sommetsjs il existe unear te entresietsj. L ensemble des sommets adjacents un sommetsiest d fini par :adj(si) ={sj/(si,sj) Aou (sj,si) A} Dans un graphe orient , on distingue les sommetssuccesseursdes sommetspr d cesseurs:succ(si) ={sj/(si,sj) A}pred(si) ={sj/(sj,si) A}5 Notion de degr d un sommet : Dans un graphe non orient , ledegr d un sommet est le nombre d ar tes incidentes ce som-met (dans le cas d un graphe simple, on aurad (si) =|adj(si)|). Dans un graphe orient , ledemi-degr ext rieurd un sommetsi, not d +(si), est le nombred arcs partant desi(dans le cas d un 1-graphe, on aurad +(si) =|succ(si)|).


Related search queries