Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

GÉNÉRALITÉS Dr ARMAND KODJO ATIAMPO, Équipe Math-Physique 2018 1.0 Avril 2018 L

GÉNÉRALITÉS Dr ARMAND KODJO ATIAMPO, Équipe Math-Physique 2018 1.0 Avril 2018 Légende Table des matières I - Objectifs 4 II - Introduction 5 III - Graphe orienté 6 1. Définition ..................................................................................................................................... 6 2. Vocabulaire .................................................................................................................................. 7 3. Propriétés des graphes ................................................................................................................. 8 4. Extensions .................................................................................................................................... 8 IV - Liste d'exercices sur les graphes orientés 10 V - Graphes non orientés 12 1. Définitions .................................................................................................................................. 12 2. Chaînes, cycles ........................................................................................................................... 13 3. Graphe biparti et graphe planaire .............................................................................................. 13 VI - Exercice : Graphes non orientés 15 VII - Conclusion 17 4 A la fin de ce cours, l’étudiant sera capable de : Savoir identifier un graphe Savoir manipuler les propriétés d'un graphe Objectifs 5 Les graphes sont utilisés en physique, en sciences sociales (pour représenter des relations entre groupes d'individus), en mathématique combinatoire, en informatique (structures de données et algorithmique). Concernant les applications, on peut citer : les réseaux électriques ; le transport d'énergie ; le routage du trafic dans les réseaux de télécommunications et les réseaux d'ordinateurs ; le routage de véhicules et l'organisation des tournées ou rotations ; les problèmes d'ordonnancement de tâches et d'affectation de ressources, ... L'article considéré comme fondateur de la théorie des graphes fut présenté par le mathématicien suisse Leonhard Euler à l'Académie des sciences de Saint Saint-Pétersbourg en 1735, puis publié en 1741, et traitait du problème des sept ponts de Konigsberg (source : https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes) Pour une meilleure compréhension, nous vous invitons à réviser votre cours d'algèbre de première année en son chapitre 2. Introduction Graphe orienté 6 Objectifs A la fin de cette section , l’étudiant sera capable de : un graphe orienté Savoir identifier Savoir manipuler les propriétés élémentaires d'un graphe orienté 1. Définition Dans la suite nous appellerons “graphe orienté” une relation dans un ensemble. Définition : Graphe orienté Un est déterminé par deux ensembles : un dont les éléments sont appelés graphe orienté ensemble X du graphe et dont les éléments sont des les sommets ou les nœuds un ensemble UV×V couples appelés . On le note G=(X,U). ordonnés de sommets arcs Exemple Soit U une relation sur un ensemble X X ={A, B, C, D, E} U={(A, D), (B,A), (C,A), (D,B), (D,C), (E,B)} Cette relation définit le graphe représenté ci-dessous. Dans cette représentation appelée représentation sagittale, les arcs(flèches) relient les éléments en relation Les sommets peuvent être représentés par des cercles(on peut les représenter par des points) et les arcs par des flèches. --> Exemple Un graphe est le modèle naturel des réseaux. On dira qu'un réseau est un graphe, pour lequel des valeurs numériques ont été associées aux nœuds et/ou arcs (Longueur de route, capacité de tuyau, flot de véhicule empruntant une route, ...). Réseaux routiers : sommets = villes, arêtes = routes Réseaux d'ordinateurs : sommets = ordinateurs/ routeurs, arêtes = liens physiques/WIFI Graphe orienté I Graphe orienté 7 Réseaux sociaux : sommets = personnes, arêtes = relation d'ami entre les personnes Réseaux de distribution d'eau, d'électricités ... 2. Vocabulaire Définition Soit un graphe orienté G=(X,U). alors : Si u=(x, y)U est un arc, le point x est appelé extrémité initiale ou origine de l'arc u et le point y est appelé extrémité terminale ou extrémité de l'arc u. n=|X| est appelé ordre de G m=|U| est appelé taille de G Une boucle est un arc (x,x) On dit que y est un de x, on dit aussi un s'il existe un arc uU de la forme successeur suivant, u=(x,y) comme le montre la ci-dessous. figure 1 De même x est un ou un de y, s'il existe un arc prédécesseur précédant uU de la forme u=(x,y) Γ (x) ou S(x) l'ensemble des successeurs ou des suivants de x. + Γ (y) ou P(y), l'ensemble des prédécesseurs de y. - L'ensemble des sommets voisins de x se note Γ(x)=Γ (x) U Γ (x) et se lit gamma de x. + - Deux sommets joints par un arc sont dits . voisins ou adjacent si G est orienté, le d (x) est le nombre d'arcs issus de x et son demi degré sortant + demi degré d (x) est le nombre d'arcs pointant sur x. entrant − le degré ́ d(x ) d'un sommet x est d(x) = d (x) + d (x) + − Un graphe orienté G=(X,U) est dit si tous les sommets de G ont même degré ; régulier c'est-à-dire d(x) = constante xX. figure 1 : Remarque Un sommet qui n'est adjacent à aucun autre sommet est dit isolé Exemple : Construire un graphe Construire le graphe G = (S, A) suivant : S = {1; 2; 3; 4} A = {(2, 1); (2, 2); (3, 1); (3, 2); (3, 3); (3, 4); (4, 1); (4, 2); (4, 3)} Solution Ce graphe est d'ordre 4 puisque l'ordre est le cardinal de S. La taille est 9 et est le cardinal de l'ensemble A. La représentation sagittale du graphe est la suivante : Graphe orienté 8 Ce graphe présente 2 boucles. les couples (2,2) et (3,3) : 3. Propriétés des graphes Fondamental : Graphes symétriques et graphes antisymétriques Soit G=(X,U) un graphe orienté. G est dit symétrique si (x ,x )U (x , x )U, x , x X avec ij. i j j i i j G est antisymétrique si (x , x )U (x ,x ) U, x , x X, avec ij. i j j i i j G est réflexif si xX, (x, x)U. G est transitif si (x , x )U et(x , x )U (x , x ) U, x , x , x X. i j j k i k i j k G est dit complet si (x , x ) U (x , x ) U, x , x X avec i j. i j j i i j Fondamental : Lemme des poignées de mains Soit G = (X, U) un graphe de taille m, alors les sommes des demi-degrés entrants et sortants des sommets de G sont égales au nombre d'arcs : --> en conséquence la somme des degrés est égale au double de nombre d'arcs 4. Extensions Définition : Sous-graphes Soit G=(X,U) un graphe orienté et Y une partie de X (Y X). On appelle sous-graphe de G engendré , le graphe G = (Y,W) où W est l'ensemble des arcs de U dont les deux extrémités sont dans par Y Y Y. Définition : Sous-graphe partiel Soit G=(X,U) un graphe orienté et Y une partie de X (Y X) et V une partie de U. On appelle sous Graphe orienté 9 , le graphe partiel de G engendré par V. graphe partiel de G engendré par Y et V Y Liste d'exercices sur les graphes orientés 10 Exercice 1 Exercice 2 Considérons le graphe suivant : --> réflexive symétrique transitive anti-symétrique relation d'ordre relation d'équivalence Liste d'exercices sur les graphes orientés II Liste d'exercices sur les graphes orientés 11 Exercice 3 Soit le graphe G suivant : --> Quelle est la taille de ce graphe ? 10 5 20 6 Exercice 4 En considérant le graphe de l'exercice précédent, calculez le degré du nœud 4 Exercice 5 En considérant le graphe de l’exercice 2, laquelle des assertions suivantes est vérifiée ? le graphe n'est pas transitif Le graphe est régulier Le graphe est réflexif Le graphe est complet Graphes non orientés 12 Objectifs Savoir identifier un graphe non orienté Savoir manipuler les propriétés élémentaires d'un graphe non orienté Dans l'étude de certaines propriétés des graphes, il arrive que l'orientation des arcs c'est-à-dire la distinction entre extrémité initiale et extrémité terminale ne joue aucun rôle. On s'intéresse simplement à l'existence ou à la non existence d'un arc entre deux sommets sans en préciser l'ordre. On parle alors de graphe non orienté. 1. Définitions Définition : Graphe non orienté Un graphe non orienté G est constitué d'un ensemble X={x ,...,x }, l'ensemble des points et U={u 1 n 1 ,...,u }P (X)P (X) où P (X) (respectivement P (X)) est l'ensemble des paires (respectivement des m 1 2 2 1 singletons) de X. Les éléments de X sont appelés sommets du graphe et ceux de U les arêtes. Si uU est un élément de P (X) avec u={x}, on dit que u est une boucle. 1 Si u U est un élément de P (X) avec u={x,y}, les sommets x et y sont appelés extrémités de l'arête 2 u. On note aussi u=xy=yx. Exemple : Construction d'un graphe non orienté G = (X, U) avec X = {1, 2, 3, 4, 5} et U = {{2},{3},{1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4},{3, 4}}. Le graphe non orienté résultant est donné par le schéma suivant : On représentera Les éléments de X par des points ou des nœuds. On représentera Les éléments de U par un trait reliant les extrémités Attention Dans un graphe non-orienté les notions de successeurs/prédécesseur ou de degrés entrant/sortant n'ont plus de signification. Cela crée un piège au niveau du lemme des poignées de mains. Fondamental : uploads/Ingenierie_Lourd/ graphe-lecon-1.pdf