Remerciez-le!

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

Théorie des graphes et optimisation 1 ESSECT – 2 BC CHAPITRE 1. INTRODUCTION AU

Théorie des graphes et optimisation 1 ESSECT – 2 BC CHAPITRE 1. INTRODUCTION AUX GRAPHES : DÉFINITIONS ET REPRÉSENTATIONS Théorie des graphes - ESSECT N. Ben Azzouna Définitions Un graphe est un ensemble fini de sommets et d'arcs ou d’arêtes défini comme des couples G = (S, A) ou S est l’ensemble des sommets et A l’ensemble des arcs (ou arêtes) qui est un ensemble de couples de sommets (si; sj) Є S2. Si « e » Є A et « e » = (a, b) | a, b Є S ⇒{a, b} sont les extrémités de l’arc « e ». Les sommets a et b sont dits adjacents. Exemple : G = (S,A) S = {a, b, c, d} A = {(a,b),(a,d),(b,d),(c,d)} N. Ben Azzouna Théorie des graphes - ESSECT 2 Définitions Un sommet qui n’apparaît dans aucune arête est dit isolé. Le nombre de sommets est dit l’ordre du graphe. Un graphe discret d’ordre « n » est dénoté par Dnet correspond à : G = (S, A) S = (1, 2, 3, ..., n ) A = ∅ Une boucle est un arc ou une arête reliant un sommet à lui- même. N. Ben Azzouna Théorie des graphes - ESSECT 4 Définitions Un graphe partiel d’un graphe est le graphe obtenu en supprimant certains arcs ou arêtes. Un sous-graphe d’un graphe est le graphe obtenu en supprimant certains sommets et tous les arcs ou arêtes incidents aux sommets supprimés. N. Ben Azzouna Théorie des graphes - ESSECT 5 Graphe orienté : Définitions Dans un graphe orienté, les couples (si, sj) Є A sont orientés, c’est à dire que (si, sj) est un couple ordonné, où si est le sommet initial, et sj le sommet terminal. Un couple (si, sj) est appelé un arc, et est représenté graphiquement par si sj . N. Ben Azzouna Théorie des graphes - ESSECT 6 Graphe orienté : Définitions Un graphe orienté est un p-graphe s’il comporte au plus p arcs entre deux sommets. Le plus souvent, on étudiera des 1-graphes. Un graphe orienté est dit élémentaire s’il ne contient pas de boucle. Un graphe orienté est dit complet s’il comporte un arc (si, sj) et un arc (sj, si) pour tout couple de sommets différents (si, sj) Є S2. On appelle clique un sous-graphe complet de G. Dans un graphe orienté, on distingue les sommets successeurs des sommets prédécesseurs : succ(si) = {sj / (si, sj) Є A} pred(si) = {sj / (sj, si) Є A} N. Ben Azzouna Théorie des graphes - ESSECT 7 Graphe orienté : Définitions Dans un graphe orienté, le demi-degré extérieur d’un sommet si, noté do+(si), est le nombre d’arcs partant de si (dans le cas d’un 1-graphe, on aura do+ (si) =|succ(si)|). Le demi-degré intérieur d’un sommet si, noté do-(si), est le nombre d’arcs arrivant à si (dans le cas d’un 1- graphe, on aura do-(si) = |pred(si)|). N. Ben Azzouna Théorie des graphes - ESSECT 8 Exercice On considère le graphe orienté G = (S;A) tel que S = {1; 2; 3; 4; 5} A = {(1; 2); (1; 4); (2; 2); (2; 3); (2; 4); (3; 5); (4; 3); (5; 3)} 1. Représenter graphiquement ce graphe, 2. Donner le demi-degré extérieur de 2 et le demi-degré intérieur de 4, 3. Donner les sommets prédécesseurs de 4 et les sommets successeurs de 2, 4. Donner un graphe partiel et un sous-graphe de ce graphe. Correction : N. Ben Azzouna Théorie des graphes - ESSECT 9 Chemins : définitions Un chemin dans un graphe orienté est une séquence (suite) de sommets et d’arcs telle que 1. la séquence débute par un sommet et se termine par un sommet ; 2. les sommets et les arcs alternent ; 3. chaque arc est précédé par son sommet origine et est suivi par son sommet cible ; Par exemple, dans la figure ci-contre, Sont des chemins N. Ben Azzouna Théorie des graphes - ESSECT 10 La longueur d’un chemin est le nombre d’arcs de ce chemin : La description des chemins peut être simplifiée en donnant seulement la suite de sommets. Un chemin pourrait aussi être décrit en donnant seulement la séquence d’arcs. Un chemin simple est un chemin ne passant pas deux fois par un même arc, c'est-à-dire dont tous les arcs sont distincts. (b,c,e) et (b,d) sont des chemins simples mais pas (c,e,c,e,d) Graphe orienté : Chemins N. Ben Azzouna Théorie des graphes - ESSECT 11 Graphe orienté : Chemins Un chemin est un circuit s’il contient au moins un arc et que le premier et le dernier sommet du chemin sont identiques. Un chemin est élémentaire si les sommets qu’il contient sont tous distincts. N. Ben Azzouna Théorie des graphes - ESSECT 12 Graphe orienté fortement connexe Graphe orienté fortement connexe : S’il y a un chemin entre n’importe quelle paire de sommets distincts du graphe. Graphe orienté faiblement connexe : S ’il existe une chaîne entre n’importe quelle paire de sommets dans le graphe, sans tenir compte de l’orientation des arcs c’est-à-dire ssi le graphe non-orienté correspondant est connexe. N. Ben Azzouna Théorie des graphes - ESSECT 13 Graphe non orienté : Définitions Dans un graphe non orienté, les couples (si; sj) Є A ne sont pas orientés, c’est à dire que (si; sj) est équivalent à (sj ; si). Une paire (si; sj) est appelée une arête, et est représentée graphiquement par si—sj . N. Ben Azzouna Théorie des graphes - ESSECT 14 Graphe non orienté : Définitions Un graphe non-orienté est dit simple si : il ne comporte pas de boucle, et il ne comporte jamais plus d’une arête entre deux sommets. Un graphe non orienté qui n’est pas simple est un multigraphe. On se restreindra généralement dans la suite aux graphes simples. Un graphe non-orienté est dit complet s’il comporte une arête (si; sj) pour toute paire de sommets différents si; sj Є S2. Celui d’ordre n est noté Kn N. Ben Azzouna Théorie des graphes - ESSECT 15 Graphe non orienté : Définitions N. Ben Azzouna Théorie des graphes - ESSECT 16 Dans un graphe non orienté, le degré d’un sommet est le nombre d’arêtes incidentes à ce sommet (dans le cas d’un graphe simple, on aura do(si) = |adj(si)|). Théorème (Lemme des poignées de mains) La somme des degrés des sommets d’un graphe est égale à deux fois le nombre d’arêtes. Le degré d’un graphe est le degré maximum de tous ses sommets. Un graphe dont tous les sommets ont le même degré est dit régulier. Si le degré commun est k, alors on dit que le graphe est k- régulier. Exercice Montrez qu’un graphe simple a un nombre pair de sommets de degré impair. Indication : Utiliser le lemme des poignées de mains Correction : Notons P l’ensemble des sommets de degré pair et I l’ensemble des sommets de degré impair d’un graphe simple G = (V,E). P et I forment une partition de V . D’après le lemme des poignées de mains, on a : Or 2 *|E| et ∑vЄP d(v) sont des entiers pairs. ∑ vЄI d(v) est également pair, puisque c’est la différence de deux entiers pairs. Or, chaque terme de la somme ∑ vЄI d(v) est impair. Elle ne peut donc être paire que si le nombre de termes est pair. On a ainsi montré que le cardinal de I est un entier pair. N. Ben Azzouna Théorie des graphes - ESSECT 17 Graphe non orienté : Définitions Un graphe est connexe s’il est possible, à partir de n’importe quel sommet, de rejoindre tous les autres en suivant les arêtes. Point de coupure : Le retrait de ce sommet et de toutes les arêtes incidentes à ce sommet conduit à former un sous-graphe qui n’est plus connexe. Séparateur: Le retrait de cette arête rend le graphe non connexe. Un graphe non connexe se décompose en composantes connexes. Sur le graphe ci-dessous, les composantes connexes sont {1,2,3,4} et {5,6}. N. Ben Azzouna Théorie des graphes - ESSECT 18 Exemple Trouver les points de coupure et les séparateurs dans le graphe suivant : N. Ben Azzouna Théorie des graphes - ESSECT 19 Exercice Dessiner un graphe non orienté complet à 4 sommets. Quel est le degré des sommets de ce graphe ? Combien d’arêtes possède-t-il ? Généralisez ces résultats à un graphe simple complet ayant n sommets. Correction : N. Ben Azzouna Théorie des graphes - ESSECT 20 Une chaîne dans G, est une suite ayant pour éléments alternativement des sommets et des arêtes, commençant et se terminant par un sommet, et telle que chaque arête est encadrée par ses extrémités. (v1, e1, v2, e2, v3, e5, v5) et (v4, e4, v3, e2, v2, e1, v1) sont des chaînes. La chaîne a pour longueur le nombre d’arêtes de la chaîne. On appelle distance entre deux sommets la longueur de la plus petite chaîne les reliant. On appelle diamètre d’un graphe la plus longue des distances entre deux sommets. Graphe non orienté : Définitions N. Ben Azzouna uploads/Philosophie/ chap1-intro.pdf