Quelques rappels sur la théorie des graphes
chaîne au lieu de chemin et de cycle au lieu de circuit. Dans le cas d'un cycle
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.
CH.1 GRAPHES ORIENTÉS
1.1 Rappels sur les graphes. • 1.2 Le parcours en profondeur. • 1.3 Les graphes sans circuit. • 1.4 Le plus court chemin – valuations positives.
Théorie des graphes et optimisation dans les graphes Table des
on parlera de chaine au lieu de chemin et de cycle au lieu de circuit. Un graphe sans cycle est dit acyclique. Exercice : Montrer que s'il existe un chemin
Graphes sans circuit et bilinéarité
se générale de graphes sans circuit utilisés en informatique ou en linguis- tique (DES.80) et le "calcul matriciel". Chaque graphe de la classe retenue.
GRAPHE
I.3 Différents modes de représentation d'un graphe . . . . . . . . . . . . . . . . 10 III.1.4 Notion de rang dans un graphe orienté sans circuit .
Présentation PowerPoint
Cheminement optimal – Les différents cas. Algorithme de Bellman. Algorithme de Ford. Algorithme de Dijkstra. Graphe sans circuit Graphe avec ou sans circuit.
RESOLUTION DE PROBLEMES DE PLUS COURT CHEMIN
Puis nous traiterons le cas d'un graphe quelconque. I Algorithme de détermination des plus courts chemins : cas des graphes sans circuit. Principe de l'
Graphes fortement connexes c-minimaux et Graphes sans circuit co
saris circuit) dont le nombre total de circuits (resp. cocircuits) elementaires est minimal. On caracterise ces graphes par I'existence d'un arbre (ou dun
SUR LES QUASI-NOYAUX DUN GRAPHE 1. Introduction
Tout graphe localement fini it droite et sans circuit a un noyau. L'existence d'un noyau n'est pas garantie pour les graphes sans circuit.
[PDF] Quelques rappels sur la théorie des graphes - CNRS
Le tri topologique d'un graphe orienté sans circuit G = (S A) consiste à ordonner linéairement tous ses sommets de telle sorte que si l'arc (u v) ? A alors
[PDF] Théorie des graphes et optimisation dans les graphes - CNRS
Une arborescence est un graphe orienté sans circuit admettant une racine s0 ? S telle que pour tout autre sommet si ? S il existe un chemin unique allant de
[PDF] Graphes sans circuit et bilinéarité - Numdam
Graphes sans circuit et bilinéarité Mathématiques et sciences humaines tome 81 (1983) p 5-45
[PDF] Theorie des graphes
Graphes sans circuits Théorie des Graphes - 2015/2016 ? Attention ce ne sont pas nécessairement des arbres ? On parle ici de circuit et non pas de
[PDF] GRAPHE
Circuit dans un graphe orienté : un chemin simple finissant à son point de départ Cycle dans un graphe non-orienté : une chaîne simple finissant à son point de
[PDF] GRAPHE ET LANGAGE
Un graphe orienté sans circuit n'est pas forcément un arbre orienté On appellera : — racine de l'arbre : le sommet qui n'a pas de prédécesseur — feuilles de l
[PDF] CH1 GRAPHES ORIENTÉS - IGM
1 1 Rappels sur les graphes • 1 2 Le parcours en profondeur • 1 3 Les graphes sans circuit • 1 4 Le plus court chemin – valuations positives
[PDF] Introduction à la théorie des graphes - Apprendre-en-lignenet
Un graphe sans cycle mais non connexe est appelé une forêt Une feuille ou sommet pendant est un sommet de degré 1 2 1 3 6 4
[PDF] CHAPITRE 2 : Théorie des graphes et applications
Lorsque le graphe est sans circuit on peut appliquer l'algorithme de Bellman-Ford consistant `a affecter une marque `a chaque sommet du graphe ordonné en
[PDF] Théorie des graphes
7 avr 2011 · Tout graphe sans circuit poss`ede au moins une source et un puits preuve : Considérons un chemin c de G qui soit maximal au sens suivant : c=[
C'est quoi un graphe sans circuit ?
Définition 7.5 Un graphe sans circuit est un graphe orienté dans lequel il n'y a pas de circuit. C'est une définition qui paraît triviale, mais il faut savoir que c'est la première fois que nous avons une définition du concept graphe sans circuit.Comment savoir si un graphe est sans circuit ?
Une extension linéaire d'un graphe G=(V,E) est un ordre strict total P=(V,F) tel que E?F. Théorème : Un graphe orienté est sans circuit quand il poss? une source (resp. un puits) et que tous ses sous-graphes sont sans circuit.Comment déterminer les niveaux d'un graphe ?
Le degré d'un sommet est égal au nombre d'arêtes qui le relient aux autres sommets. Dans l'exemple précédent, A est de degré 2, B de degré 2, D de degré 0. Propriété : La somme des degrés de tous les sommets d'un graphe est égal au double du nombre total d'arêtes.- Un graphe complet est un graphe dont chaque sommet est relié directement à tous les autres sommets. Un graphe est connexe quand tout sommet peut être relié à tout autre sommet par une arête ou une suite d'arêtes.
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 / 125quotesdbs_dbs16.pdfusesText_22
[PDF] algorithme des graphes exercices corrigés
[PDF] les graphes en c openclassroom
[PDF] algorithme de recherche des composantes connexes d'un graphe
[PDF] algorithme composante connexe graphe
[PDF] théorie des graphes livre gratuit
[PDF] suite graphique théorie des graphes
[PDF] histoire de la théorie des graphes
[PDF] théorie des graphes cours et exercices corrigés
[PDF] le gone du chaaba analyse
[PDF] le gone du chaaba azouz begag commentaire
[PDF] les différentes théories des organisations
[PDF] théorie des organisations résumé
[PDF] le gone du chaaba texte intégral
[PDF] telecharger le gone du chaaba livre