Upload
-
View
397
Download
3
Embed Size (px)
DESCRIPTION
Connexité des Graphes
Citation preview
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 1/42
Réalisé par :
Yassine JHILAL
Abdelmadjid CHADAD
Zakaria EZZENATI
Mohamed AIT AISSA
Abdessamad BOUTGAYOUT
Encadré par :
Mr.RAIHANI
ENSET Mohammedia – 2011/2012
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 2/42ENSET Mohammedia – 2011/2012
IntroductionLes graphesLes chemins
ConnexitéAlgorithmes de connexitésImplémentation en C
Connexité et RéseauConclusionBibliographie
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 3/42ENSET Mohammedia – 2011/2012
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 4/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes deconnexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Dans le cadre de notre formation à l’ENSET Mohammedia,nous étions amené a préparer un mini-projet en
algorithmique sous thème ‘‘connexité des graphes’’. Notre travail consiste a chercher les différentsalgorithmes de connexités et de les implémentéen langage C.
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 5/42ENSET Mohammedia – 2011/2012
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 6/42ENSET Mohammedia – 2011/2012
Introduction
Les graphes
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
Un graphe: est un ensemble de nœuds (ou sommets) quisont relier entre eux par des arcs (arrêts).Mathématiquement, un graphe est représenté par un
couple de deux ensemblesG = (X;U) où X est l'ensemble des nœuds (ou sommets) etU l'ensemble des arêtes (graphe non orienté) ou arcs(orienté).Le nombre de sommets présents dans un graphe est lel’ordre du graphe.
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 7/42ENSET Mohammedia – 2011/2012
Introduction
Les graphes
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
Dans cet exemple :G=(X,U)X={ a, b, c, d, e, f, g, h }U={ (a,d), (b,c), (b,d), (d,e), (e,c), (e,h), (h,d), (f,g), (d,g), (g,h) }
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 8/42ENSET Mohammedia – 2011/2012
Introduction
Les graphes
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
A B
A B
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 9/42ENSET Mohammedia – 2011/2012
Introduction
Les graphes
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
Le demi degré extérieur d’un nœuds est le nombre d’arcs
adjacent qui en partant d+(x) cad y est un successeur de x.Le demi degré intérieur d’un nœuds est le nombre d’arcs
adjacent qui en partant d-(x) cad y est un prédécesseur dex.
Exemple: Dans le graphe suivant , d+(x)=3( successeur) etd-(x)=2(prédécesseur) d(x)=5.
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 10/42ENSET Mohammedia – 2011/2012
Introduction
Les graphes
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
Arête:
une ligne qui joint deux sommets consécutifs, distincts ounon, d'un graphe non orienté.
Arc:
une ligne ou trait qui joint deux sommets consécutifs,distincts ou non, d'un graphe orienté.
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 11/42ENSET Mohammedia – 2011/2012
I d i
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 12/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes deconnexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Un chemin de x à y est une chaîne dans laquelle lesarcs sont orientés et tels que:
x est l’extrémité initiale du premier arc,
y est l’extrémité terminale du dernier arc,
l’extrémité terminale d’un arc est l’extrémitéinitiale de l’arc qui le suit dans la séquence.
I t d ti
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 13/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes deconnexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Exemple :
I t d ti
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 14/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes deconnexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
ch1 = ((A;C),(C;E)) est un chemin de A à E.ch2 = ((A;C),(C;F),(F;A),(A;C),(C;E)) est un chemin de A à E.ch3 = ((A;C),(C;F),(F;D),(D;C),(C;E)) est un chemin de A à E.ch4 = ((A;B),(B;D),(D;E)) est une chaîne de A à E.
ch5 = ((A;B),(B;D),(D;C),(C;A),(A;B),(B;D),(D;E)) est unechaîne de A à E.ch6 = ((A;B),(B;D),(D;C),(C;F),(F;D),(D;E)) est une chaîne deA à E.
I t d ti
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 15/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Représentation par matrices d’adjacence:
On souhaite définir une structure de données pourreprésenter un graphe.
Considérons S={s0,s1,….,sn-1} l’ensemble des sommets.Nous allons représenter le graphe par une matrice A detaille n*n.l’élément A[i][j] vaudra 1,s’il y a un arc (i,j) dusommet s(i) vers le sommet s(j) , sinon A[i][j] vaudra 0
Introd ction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 16/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 17/42ENSET Mohammedia – 2011/2012
0 1 2 3 4 5
0 0 0 0 0 1 0
1 0 1 0 1 0 0
2 1 1 0 0 0 0
3 0 0 0 0 0 1
4 0 0 1 0 0 05 1 0 0 1 0 0
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 18/42
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 19/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
La notion de connexité est liée à l'existence dechemins dans un graphe : depuis un sommet, existe-t-
il un chemin pour atteindre tout autre sommet?Les graphes connexes correspondent à lareprésentation naturelle que l'on se fait d'un graphe.Les graphes non connexes apparaissent comme lajuxtaposition d'un ensemble de graphes : sescomposantes connexes.
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 20/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Tous les sommets sont reliés, directement ou non,entre eux par une chaîne
NB :
un arbre est un graphe connexe .
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 21/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Il existe des sommets non reliés entre eux .
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 22/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Forte connexité :
x et y ont une relation de forte connexité il existeun chemin de x à y et un chemin de y à x ou bien x =
y.
Graphe connexe :
Un graphe est dit fortement connexe si tous sesnœuds ont deux à deux la relation de forte
connexité.
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 23/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 24/42
ENSET Mohammedia – 2011/2012
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 25/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Recherche d'une composante fortement connexe :
Cet algorithme recherche la composante fortementconnexe d'un graphe G contenant un sommet s. L'idée decet algorithme est de parcourir le graphe à partirdu point s dans le sens direct (i.e. en suivant lesflèches des arcs) et de créer un ensemble des nœuds
parcourus. La même chose est effectuée dans le sensindirect (i.e. en suivant les flèches des arcs en sensinverse) et de créer un deuxième ensemble des nœudsparcourus. Le premier ensemble regroupe les nœudsaccessibles à partir de s et le deuxième ensembleregroupe les nœuds qui peuvent atteindre s.L'intersection de ces deux ensembles donne les nœuds quià la fois peuvent atteindre s et sont accessibles àpartir de s. Cette intersection est donc lacomposante fortement connexe qui contient s.
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 26/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Recherche d'une composante fortement connexe :
La structure de données X représentant un ensemble desommets dispose des fonctions suivantes :
X=Créer Ensemble() crée l’ensemble vide XEnsemble Vide(X) retourne un booléen indiquant sil’ensemble X est vide ou pasInsérer(x, X) permet l'ajout d'un sommet x dans Xx=Extraire(X) permet le retrait du sommet x de X
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 27/42
Introduction
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Recherche de toutes les composantes fortement
connexes :
Pour trouver toutes les composantes fortement connexesd'un graphe, il suffit de choisir au hasard un nœud et de
déterminer, grâce à l'algorithme précédent, lacomposante fortement connexe qui le contient. Onobtient alors une première composante fortementconnexe X1. Ensuite, parmi les nœuds qui ne fontpas partie de X1, on en prend un au hasard pourdéterminer la composante fortement connexe qui le
contient. On obtient X2. On recommence ainsijusqu'à ce que tous les nœuds appartiennent à unecomposante fortement connexe.
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 28/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Début
Lire sommet-> S
Fin
Parcours de graphe
Parcours Directe -> X1
Parcours Indirecte -> X2
Intersection (X1,X2)->C
C==0
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 29/42
ENSET Mohammedia – 2011/2012
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 30/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
#include<stdio.h> #include<conio.h> #include<math.h> int * connex(int** adjacence,int ordre,int s){
int *c1,*c2; int *c;
int *marques; int x,y; int ajoute=1; //Allouer les tableaux dynamiques c1,c2,c et marque de taille
<<ordre>> c1=(int*)malloc(ordre*sizeof(int)) ; c2=(int*)malloc(ordre*sizeof(int)) ; c=(int*)malloc(ordre*sizeof(int)) ;
//Intialiser les valeurs de ces tableaux a 0 For(int i=0 ;i<n :i++){
c1[i]=0;} For(int i=0 ;i<n :i++){
c2 [i]=0;} For(int i=0 ;i<n :i++){
c[i]=0;}
Seule Composants Connexe :
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 31/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
//rendre le sommets connexe
c1[s]=1; c2[s]=1; //recherche des composantes connexes partant de s a ajouter dans c1: while(ajoute) {
ajoute=0; // a chaque tour, recherche d'une nouvelle composanteconnexe a ajouter //pour tous les sommets x non marqués et connectés en partant de s //marquer chaque sommet x et connecter les sommets non marqués yadjacents a x
for(x=0;x<ordre;x++){ if(!marques[x] && c1[x]){
marques[x]=1; for(y=0;y<ordre;y++){
if(adjacence[x][y] && !marques[y]){ c1[y]=1;
ajoute=1;//nouvelle composante connexe ajoutée } } } }
//recherche des composantes connexes arrivant a s a ajouter dans c2//composante fortement connexe c=intersection de c1 et c2 for(x=0;x<ordre;x++) c[x]=c1[x]&c2[x]; //retourner la composante fortement connexe c return c;
} }
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 32/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
#include<stdio.h> #include<conio.h> #include<math.h>
int * tousconnex(int** adjacence,int ordre){
int **tabc; int *marques; int x,y; int ajoute=1; //Allouer les tableaux dynamiques tabc,marques et marque de taille
<<ordre>> tabc=(int**)malloc(ordre*sizeof(int*)) ; marques=(int*)malloc(ordre*sizeof(int)) ; For(int i=0 ;i<n :i++){
tabc[i]= =(int*)malloc(ordre*sizeof(int)) ;}
Plusieurs Composants Connexe :
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 33/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
//Intialiser les valeurs de ces tableaux a 0 For(int i=0 ;i<n :i++){
tabc[i]=0;} For(int i=0 ;i<n :i++){
marques [i]=0;} //pour tous les sommets x non marqués
//rechercher la composante fortement connexe de x //marquer chaque sommet x et marquer les sommets y connectés a xet non marqués for(x=0;x<ordre;x++){
if(!marques[x]){ tabc[x]=connex(adjacence,ordre,x) marques[x]=1; for(y=0;y<ordre;y++){
if(tabc[x][y] && !marques[y]){ marques[y]=1; } }
return *tabc;} } }
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 34/42
ENSET Mohammedia – 2011/2012
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 35/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Un réseau est un graphe dont les machines sont lesnœuds du graphe.donc pour déterminer que deux machines sont
connecté; il faut chercher si les deux nœuds quireprésente ces machines sont connexe?
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 36/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
l'application des graphes aux domaine de réseaux amis en évidence un certain nombre de topologies desréseaux .
Réseau en étoile : connexe
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 37/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Réseau en bus : connexe
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 38/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Réseau en anneau : connexe
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 39/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Réseau maillé: fortement connexe
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 40/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Pour conclure, cette présentation nous apermet de découvrir la notion des graphes
ainsi, que la connexité et son importancesurtout dans le domaine des réseaux et dela programmation.
Introduction
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 41/42
Les graphes
Chemins
Connexité
Algorithmes de
connexités
Implémentation en C
Connexité et Réseau
Conclusion
Bibliographie
ENSET Mohammedia – 2011/2012
Livres
Eléments de Théorie des Graphes - Didier Maquin Algorithmique des graphes - Gaëtan BISSON Graphes - D. Sarni – L. Lemarchand parcours de graphes et connexité - Frédéric GuinandInitiation à l’algorithmique et à la programmation en C –
Rémy Malgouyres – Rita Zrour – Fabien Fashet
Sites web :
http://bruno.bachelet.net
www-g-scop-inpg-fr
5/12/2018 Connexit des Graphes - slidepdf.com
http://slidepdf.com/reader/full/connexite-des-graphes 42/42