7 avr 2011 · un circuit de G=(S,A) est un chemin [xi1 , ,xik ] de G tel que ∀k≥2 Dans le cas des graphes possédant des circuits absorbants, on pourrait
Previous PDF | Next PDF |
[PDF] Quelques rappels sur la théorie des graphes - CNRS
circuit absorbant, un plus court chemin sera de longueur inférieure à n et au bout de n - 1 passages, on aura trouvé tous les plus courts chemins partant de s0 (Si
[PDF] CH1 GRAPHES ORIENTÉS - IGM
Comme il peut y avoir des circuits, il faut recommencer S'il n'y a pas ce circuit absorbant, un plus court chemin est nécessairement élémentaire On est donc sûr
[PDF] Algorithmes de recherche du plus court chemin - LRDE - Epita
Si un graphe possède un circuit absorbant, alors il n'existe pas de plus court de circuits absorbants, et x et y deux sommets de G Si il existe un chemin allant
[PDF] Algorithmique des graphes - Cours 7 – Calcul de distances - LaBRI
Algorithme de Ford : Détection de circuit absorbant 13: for tout arc e = (u,v) ∈ E( G) do 14: if d[v] > d[u] + w(u,v) then 15: return FAUX 16: end if 17: end for
[PDF] GRAPHE ET LANGAGE
Un circuit absorbant est un circuit de valuation négative Proposition V 3 Soit G un graphe orienté valué n'ayant pas de circuits absorbants, et s et s deux sommets
[PDF] 1 Lalgorithme de Bellman-Ford
un graphe orienté pondéré G = (V,E), de fonction de poids w, et une origine s, l' algorithme retourne une valeur booléenne indiquant s'il existe un circuit de poids
[PDF] Théorie des graphes
7 avr 2011 · un circuit de G=(S,A) est un chemin [xi1 , ,xik ] de G tel que ∀k≥2 Dans le cas des graphes possédant des circuits absorbants, on pourrait
[PDF] RESOLUTION DE PROBLEMES DE PLUS COURT - AUNEGE
C'est un circuit dit "absorbant" En empruntant ce circuit autant de fois que l'on veut, la longueur des chemins peut tendre vers moins l'infini
[PDF] 1 Recherche de chemins optimaux dans les graphes - Proxem
On ne peut donc considérer les graphes à circuits absorbants, car on ne peut y trouver de chemin minimal: en tournant en rond dans un circuit absorbant, on
[PDF] ethique d'entreprise exemples
[PDF] exemple probleme ethique en entreprise
[PDF] situation non éthique vécue en entreprise
[PDF] dilemme ethique exemple
[PDF] refus de traitement et autonomie de la personne
[PDF] refus de traitement en psychiatrie
[PDF] exemple dilemme éthique infirmière
[PDF] dilemme éthique définition
[PDF] étude de cas éthique infirmière
[PDF] dilemme ethique santé
[PDF] exemple de situation éthique en stage
[PDF] situation éthique exemple
[PDF] problème éthique infirmière
[PDF] cas clinique éthique
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