Les Graphes
En théorie des graphes l'algorithme de Dijkstra sert à résoudre le problème du plus court chemin. Il s'applique à un graphe connexe dont le poids lié aux
Introduction à la théorie des graphes
Solution : Construisons le graphe G dont les sommets sont les épreuves numérotées de 1 à 7 une arête relie deux de ses sommets lorsque les deux cours
Theorie des graphes
La dimension de la base de cycle est v(G) = m – n +p. 79. Page 80. Arbre. Théorie des Graphes - 2015/2016. □ Un arbre est un graphe connexe sans cycles. □ Une
Guide pédagogique Teaching guide and syllabus
4 juil. 2023 • Appliquer la théorie des graphes aux chaînes de Markov et files d'attente ... Cours théorique classe entière (2h cours) + atelier TD en groupe ...
introduction à la théorie des graphes
1 Un graphe est connexe si pour toute paire de sommets du graphe il existe une chaîne les reliant. MM - Théorie élémentaire des graphes page 2/19. A. B. C fig
Cours - Recherche Opérationnelle.pdf
Introduction à la théorie des graphes. 3. Complexité des problèmes méthodes de résolution. 4. Programmation linéaire. 2. Page 3. Introduction générale. Page 4
Théorie des graphes
Ainsi un des premiers ouvrages
BTS SIO Août 2014 Cours de graphes Yann Barsamian yann
C'est un mode de représentation utile pour la théorie - par exemple les flots et la program- mation linéaire - mais assez peu utilisé en pratique car gourmand
Introduction à la théorie des graphes
Ce cours se veut accessible aux élèves de lycée car il ne demande pratiquement pas de connaissances préalables. Il est découpé en deux parties principales :
Théorie des graphes
7 avr. 2011 Le formalisme des graphes permet de décrire de nombreux probl`emes ... Dans le cadre de ce cours on traitera des probl`emes classiques o`u ...
Introduction à la théorie des graphes
Comme la théorie des graphes utilise un jargon bien particulier le début du cours comporte beaucoup de définitions. C'est un peu rébarbatif
Présentation PowerPoint
En théorie des graphes l'algorithme de Dijkstra sert à résoudre le problème du plus court chemin. Il s'applique à un graphe connexe dont le poids lié aux
Introduction à la théorie des graphes
Solution : Construisons le graphe G dont les sommets sont les épreuves numérotées de 1 à 7 une arête relie deux de ses sommets lorsque les deux cours
Chapitre 13 Théorie des graphes
Un graphe non orienté est dit connexe s'il y a un chemin entre n'importe quelle paire de sommets. Un graphe orienté est dit connexe si en transformant ses arcs.
Théorie des graphes et optimisation dans les graphes Table des
Exercice : Au cours d'une soirée les convives se serrent les mains les uns les autres (jamais plusieurs fois avec la même personne). Chacun se souvient du
Théorie des graphes
mier traitant de théorie des graphes“Theorie der endlichen und unendlichen ce cours
INTRODUCTION A LA THEORIE DES GRAPHES
1 Un graphe est connexe si pour toute paire de sommets du graphe il existe une chaîne les reliant. MM - Théorie élémentaire des graphes page 2/19. A. B. C fig
Représentation des graphes et Programmation
Un graphe est dit orienté si les relations sont graphes orientées) et arête (pour les graphes ... en cours jusqu'à arriver sur une impasse ou un.
cours-python.pdf
22 mars 2018 Cours de Python / Université Paris Cité / UFR Sciences du Vivant ... Même si en théorie ces fonctions peuvent prendre en argument une liste ...
[PDF] Les Graphes - Présentation PowerPoint - RTC
En théorie des graphes l'algorithme de Dijkstra sert à résoudre le problème du plus court chemin Il s'applique à un graphe connexe dont le poids lié aux
[PDF] Introduction à la théorie des graphes
L'histoire de la théorie des graphes débute peut-être avec les travaux d'Euler au XVIII e siècle et trouve son origine dans l'étude de certains problèmes
Théorie de graphe - Slideshare
Théorie des graphes L'objectif est de décrire des objets (d'où un vocabulaire spécifique) dont nous aurons besoin pour résoudre différents problèmes
[PDF] Théorie des graphes
Introduction 1 Chapitre I Premier contact avec les graphes 5 1 Graphes orientés 5 2 Graphes non orientés 8 3 Quelques exemples
[PDF] Introduction à la théorie des graphes - Apprendre en ligne
Ce cours se veut accessible aux élèves de lycée car il ne demande pratiquement pas de connaissances préalables Il est découpé en deux parties principales :
[PPT] Théorie des graphes - Mathématiques
Le WEB (graphe des liens calcul de pertinence dans les moteurs de recherche etc ) Graphes « petits mondes » (Kevin Bacon); Les réseaux optiques (producteurs-
Introduction à la Théorie des graphes - ppt télécharger - SlidePlayer
Une université doit organiser les horaires des examens de rattrapage On suppose qu'il y a 7 épreuves à planifier numérotées de 1 à 7 : Les paires de cours
Introduction à la Théorie des Graphes - ppt video online télécharger
C'est déjà Noël GRATUIT Le cours « Introduction à la Théorie des Graphes » (au format PowerPoint et Acrobat Reader) est disponible sur l'intranet du
[PDF] introduction à la théorie des graphes
1 Un graphe est connexe si pour toute paire de sommets du graphe il existe une chaîne les reliant MM - Théorie élémentaire des graphes page 2/19 A B C fig
[PDF] Théorie des graphes
7 avr 2011 · 4 Graphes sans circuit 5 Probl`eme du plus court chemin L Sais (Algorithmique Programmation 5) Théorie des graphes 7 avril 2011
![Théorie des graphes Théorie des graphes](https://pdfprof.com/Listes/17/50852-17graphesComplet.pdf.pdf.jpg)
Th´eorie des graphes
L. Sais
Algorithmique & Programmation 5
7 avril 2011
L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 1 / 1251Graphe et algorithme : pr´esentation
Introduction
D´efinitions et terminologie
Repr´esentation
Matrice d"adjacence
Listes d"adjacence
2Parcours, num´erotation et descendance
3Connexit´e et forte connexit´e
4Graphes sans circuit
5Probl`eme du plus court chemin
L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 2 / 125 Graphes et algorithme : pr´esentationIntroduction De nombreux probl`emes courants, en informatique, en ing´enierie, en sciences sociales, en intelligence artificielle, peuvent se repr´esenter en termes de relations (binaires) entre objets.On peut citer par exemple :
L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 3 / 125 r´eseaux de communications: routiers, ferroviaires, machines en r´eseaux, circuits int´egr´es, ... L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 4 / 125 On distingue les sommets(villes, carrefours, soudures) et les arcsou arˆetes (communication entre sommets) qui mettent en relation les sommets. On associe parfois aux arcs des caract´eristiques, qui permettent d"exprimer des distances, des coˆuts, des flux, ... Le type des probl`emes que l"on peut se poser alors concerne par exemple la recherche d"itin´eraires optimaux (probl`eme classique du voyageur de commerce : visiter toutes les villes avec un cheminement optimal). L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 5 / 125 relations sociales: familiales, hirarchiques, d"incompatibilit´e, ... Ici, les sommets correspondent aux individus, les arcs aux relations entre individus. ordonnancement de tˆaches: atelier, systmes d"informations, ... Une premi`ere possibilit´e consiste repr´esenter les instants de d´ebut et de fin d"activit´e par les sommets, et les activit´es par les arcs; on peut ´egalement repr´esenter les tˆaches par les sommets et les relations de pr´ec´edance par les arcs. L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 6 / 125 18 263 54 7 9
1 : cale¸con 4 : veste 7 : chemise
2 : pantalon 5 : cravate 8 : chaussures
3 : ceinture 6 : chaussettes 9 : montre
L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 7 / 125 repr´esentation d"algorithmes(organigrammes) : Les sommets correspondent aux instructions ou tests, les arcs correspondent aux enchanements possibles entre instructions ou tests.On retrouvera ´egalement :
* les emplois du temps * les automates `a ´etats finis * les probl`emes de coloration de cartes (2 pays voisins doivent avoir 2 couleurs diff´erentes) * etc. L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 8 / 125Remarque
Le formalisme des graphes permet de d´ecrire de nombreux probl`emes souvent de mani`ere simple, mais qui peuvent s"av´erer difficile `a r´esoudre. Dans le cadre de ce cours, on traitera des probl`emes classiques o`u de bons algorithmes sont connus (il existe des probl`emes o`u l"on ne connait pas de bons algorithmes) : ´etant donn´e un graphe, v´erifier s"il poss`ede certaines propri´et´es ´etant donn´e un graphe, d´eterminer une partie poss´edantcertaines propri´et´es. construire un, plusieurs, ou tous les graphes poss´edant certaines propri´et´es. L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 9 / 125 Graphes et algorithme : pr´esentationD´efinitions et terminologieD´efinition
Un graphe orient´eest un couple G=(S,A) o`u :
- S est un ensemble fini d"´el´ements appel´es sommets - A est un ensemble fini de couples de sommets appel´es arcs on a A?S×SRemarque
S"il existe plusieurs arcs entre deux sommets, on parle d"unmultigraphe (arcs multiples) L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 10 / 125Exemple
63 4215
7 8S={1..8}
L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 11 / 125D´efinitions
Etant donn´e un graphe G=(S,A) etx?S
si (x,y)?A, alorsyest un successeurdex si (y,x)?A, alorsyest un pr´ed´ecesseurdex xetysont adjacentssiyest un pr´ed´ecesseur et/ou un successeur de x l"ensemble des successeursdexest not´e Γ+(x) +(x) ={y|(x,y)?A} l"ensemble des pr´ed´ecesseursdexest not´e Γ+(x) -(x) ={y|(y,x)?A} l"ensemble des voisinsdexest not´e Γ(x)Γ(x) = Γ+(x)?Γ-(x)
L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 12 / 125 le degr´e int´erieurdexest not´e d-(x) d -(x) =|Γ-(x)| le degr´e ext´erieurdexest not´e d+(x) d +(x) =|Γ+(x)| le degr´edexest not´e d(x) d(x) =|Γ(x)|D´efinition
Un graphe non orient´eest un couple G=(S,A) o`u : - S est un ensemble fini d"´el´ements appel´es sommets - A est un ensemble fini de paires de sommets appel´es arˆetesUne arˆete est not´ee{x,y}
Dans le cas de ces graphes non-orient´es, on parle simplement de sommets voisins et de degr´e. L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 13 / 125Exemple
63 4215
87S={1..8}
A={{3,5},{4,5},{3,4},{6,7},{8,7}}
L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 14 / 125D´efinition (graphe complet)
Un graphe orient´e G=(S,A) est dit completsi A=S2 Un graphe non orient´e G=(S,A) est dit completsi toute paire de sommets figure dans AD´efinition
Etant donn´e un graphe orient´e G=(S,A) :
le graphe r´eciproque de Gest le graphe G-1=(S,A-1) o`u A -1={(x,y)?S×S|(y,x)?A} le graphe sym´etris´eassoci´e `a G est le graphe GS=(S,A?A-1)D´efinition
Un graphe valu´eest un graphe orient´e ou non orent´e G=(S,A) auquel on associe une fonction de coˆut c : A->R , un tel graphe est not´e (S,A,c) L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 15 / 125Exemple
Voir l"exemple sur le r´eseau routier (villes)
Notations
Si G=(S,A) On a|S|=card(S)=n et|A|=card(A)=m
Rapports etre n et m
: (cas des graphes orient´es)Si G=(S,A) n"est pas un multigraphe, on a A?S2
graphes tels que m=n2: graphes complets avec boucles graphes complets sans boucle : m=n(n-1) L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 16 / 125Relations entre d+, d-, d et m:
pour le cas des graphes orient´es sans boucles : x?Sd +(x) =? x?Sd -(x) =1 2? x?Sd(x) =m pour le cas des graphes non orient´es : x?Sd(x) = 2m L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 17 / 125D´efinition
Etant donn´e un graphe orient´e G=(S,A) et un sous-ensemblede sommets X, le sous-graphe de G induit (engendr´e) par X est G(X)=(X,E) o`u E={(x,y)?A|x,y?X} La d´efinition est identique dans le cas non orient´eD´efinition
Etant donn´e un graphe G=(S,A) et un sous ensemble d"arcs ou d"arˆetes E, le graphe partiel de G induit par E est le graphe G=(S,E) L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 18 / 125Exemple
Un graphe, le sous-graphe induit par X ={2,4,5,6,7} et le graphe partiel induit par l"ensemble d"arcsE={(2,2),(5,3),(4,5),(3,4),(8,7)}
graphe63 4215
7 8 sous-graphe 64257 graphe partiel
63 4215
7 8 L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 19 / 125D´efinition
Etant donn´e un graphe G=(S,A), une partition p={S1,...,Sp}de S, le graphe quotient induit par P est la graphe (V,E) o`u : V={s1,...,sp}(`a chaque partie S, on associe un sommet Si)E={(si,sj) /?(x,y)?A , x?Siet y?Sj}
Rappel
p={S1,...,Sp}est une partitionde S ssi? i= S et?i?=j,Si?Sj=∅ L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 20 / 125Exemple
Un graphe et le graphe quotient induit par la partition p={s1,...,s4} L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 21 / 125 Graphes et algorithme : pr´esentationRepr´esentationMatrice d"adjacence
Le graphe est repr´esent´e par un tableau `a deux dimensionsindex´e sur l"ensemble des sommetsGraphe et matrice d"adjacence
3 425 76 81X12345678
1FFFFFFFF
2FVFFFFFF
3FFFVVFFF
4FFFFVFFF
5FFVFVFFF
6FFFFFFVF
7FFFFFFFF
8FFFFFFVF
L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 22 / 125 Les ´el´ements du tableau peuvent ˆetre diff´erents types selon le graphe consid´er´e bool´eens: un ´el´ement [i,j] est vrai si l"arc (i,j) figure dans le graphe. Dans le cas non orient´e si l"´el´ement [i,j] est vrai, alorsl"´el´ement [j,i] est vrai r´eels: Dans le cas de graphes valu´es, on repr´esente la fonction de coˆut, ainsi pour valeur c(i,j) et si l"arc (i,j) ne figure pasdans le graphe [i,j] prend une valeur conventionnelle. entiers: Dans le cas du multigraphe, [i,j] aura pˆour valeur le nombre d"arcs (i,j) figurant dans le graphe. L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 23 / 125 en C: #define N_MAX typedef struct{ int g[N_MAX][N_MAX]; int n; }grapheM; en pseudo-langage constante N_MAX = ... (* nombre maxi de sommets *) type sommet = 1..N_MAX graphe = structure a:= tableau[sommet,sommet] de booleens n: 0..N_MAX fin L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 24 / 125Avantages
Acc`es direct aux arcs : tester l"existence d"un arc, ajouter, ou supprimer un arc sont des op´erations r´ealisables en tempsconstant (θ(1)) L"´ecriture des algos est g´en´eralement simplifi´ee : l"acc`es aux successeurs d"un sommet est ais´eInconv´enients
encombrement maximal de la m´emoire : ?le nombre d"arcs figurant dans le graphe, la place m´emoire n´ecessaire est enθ(N coˆut de l"initialisation :θ(n2) coˆut de la recherche des successeurs d"un sommet :θ(n), mˆeme s"il y"a pas de successeurs. l"acc`es aux successeurs d"un sommet est ais´e L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 25 / 125Listes d"adjacence
C"est g´en´eralement la repr´esentation la plus utilis´ee, celle o`u l"on dispose des algos les plus performants.Exemple
3 425 76 81L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 26 / 125 en C: typedef struct cel{ int st; struct cel* suiv; }cellule; typedef cellule* Liste; typedef struct{
Liste a[N_MAX];
int n; }grapheL; L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 27 / 125 en pseudo-langage: type Liste = ^cellule cellule = structure st : sommet suiv : Liste fin grapheL = structure a := tableau [sommet,sommet] de Liste n :0..N_MAX fin L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 28 / 125Avantages
encombrement minimal de la m´emoire :θ(NMAX+m) l"acc`es au successeur d"un sommet x est enθ(d+(x))Inconv´enients
cout d"acc`es `a un arc l"origine x :θ(d+(x)) l"acc`es aux pr´ed´ecesseurs d"un sommet x impose le parcours de toutes les listes d"adjacence :θ(n+m) L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 29 / 1251Graphe et algorithme : pr´esentation
2Parcours, num´erotation et descendance
3Connexit´e et forte connexit´e
4Graphes sans circuit
5Probl`eme du plus court chemin
L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 30 / 125D´efinition (Graphe orient´e)
un chemin x i1,xi2,...,xiksera not´e [xi1,xi2,...,xik] un chemin [xi1,xi2,...,xik] est dit ´el´ementairesi (ne contient pas deux fois le mˆeme sommet) la longueur d"un cheminest ´egale au nombre de sommets moins un. le chemin constitu´e du seul sommet x i1not´e [xi1] est de longueur nulle.Propri´et´e
si c=[xi1,...,xik] est un chemin de G, alors il existe une sous-suite de c qui est un chemin ´el´ementaire de x i1`a xik. xi1 xij xij+1 xil xik L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 31 / 125Preuve :Par r´ecurrence sur r
, le nombre de r´ep´etitions de sommets dans c. si r=0, c"est un chemin ´el´ementaire Supposons que la propri´et´e est vraie au rang r-1 Soit un chemin c=[xi1,...,xik] poss´edantr r´ep´etitions. Soit c" la sous-s´equence de c obtenue en supprimant de c la sous-suite x iu+1... xiv.Donc c"=[x
i1,...,xiu,xiv+1,...,xik] est un chemin ayant au plus c-1 r´ep´etitions, d"o`u par hypoth`ese de r´ecurrence c" qui est une sous-s´equence de c pos`ede une sous-s´equence qui est un chemin´el´ementaire de x
i1`a xik: c=[x i1,...,(xiu,...,xiv),xiv+1,...,xik] L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 32 / 125D´efinitions (Graphe non orient´e)
une chaˆınede G=(S,A) est une s´equence de sommets x (x ij,xij+1)?A ou (xij+1,xij)?A une chaˆıne(xi1,...,xik) est dite ´el´ementairesi (ne contient pas deux fois le meme sommet) la longueur d"une chaineest ´egale au nombre de sommets moins un.La chaine constitu´ee du seul sommet x
i1sera not´ee (xi1) est de longueur nulle.D´efinition
un circuit de G=(S,A) est un chemin [xi1,...,xik] de G tel que?k≥2 et xi1=xik. un cycle de G=(S,A) est une chaine (xi1,...,xik) de G tel que?k≥2 et xi1=xik. L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 33 / 125D´efinition
Etant donn´e un graphe G=(S,A) et x?S, on d´efinit les ensembles de descendants et ascendants d"un sommet x: descG(x)={y?S| ?[x,y] dans G} ascG(x)={y?S| ?[y,x] dans G} =>?x,y?S, y?descG(x)<=>x?ascG(y)Propri´et´e
Soit G=(S,A) un graphe
?x?S, ascG(x)=descG-1(x)D´efinition
Une racinede G=(S,A) est un sommet r de S tel que S=descG(r) L. Sais (Algorithmique & Programmation 5)Th´eorie des graphes7 avril 2011 34 / 125Parcoursenprofondeur :
Exemple
Parcours en profondeur d"un graphe : les num´eros correspondants auxquotesdbs_dbs32.pdfusesText_38[PDF] méthodes dextraction des huiles essentielles ppt
[PDF] huiles essentielles pdf gratuit
[PDF] tp extraction dune huile essentielle hydrodistillation
[PDF] extraction huile essentielle eucalyptus pdf
[PDF] principe dune loupe
[PDF] cours sur les lentilles 1ere s
[PDF] les lentilles optique pdf
[PDF] cours sur les lentilles convergentes et divergentes
[PDF] lentilles minces cours physique
[PDF] elaboration des métaux
[PDF] elaboration de lacier pdf
[PDF] cours procédés délaboration des matériaux
[PDF] elaboration des metaux ferreux
[PDF] elaboration de la fonte pdf