Remerciez-le!

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

THEORIE DES GRAPHES Mostafa MASLOUHI 2020 - 2021 Mostafa MASLOUHI 2020 - 2021 1

THEORIE DES GRAPHES Mostafa MASLOUHI 2020 - 2021 Mostafa MASLOUHI 2020 - 2021 1. Un peu d’historique. 2. Vocabulaire de la théorie des graphes. 3. Plus court chemin: Algorithme de Dijkstra. 4. Arbre et recouvrement minimum: Algorithme de Kruskal. 5. Coloriage d’un graphe. Sommaire Mostafa MASLOUHI 2020 - 2021 Problème des sept ponts de Königsberg Ville de Königsberg (aujourd'hui Kaliningrad (Russie)) Le problème consiste à déterminer s'il existe ou non une promenade permettant, à partir d'un point de départ au choix (A,B,C ou D), de passer une et une seule fois par chaque pont, et de revenir à son point de départ. Un peu d’historique A D B C Mostafa MASLOUHI 2020 - 2021 Euler a résolu, en 1736, le problème des sept ponts de Königsberg et a montré que ce problème n’admet pas de solution. Les techniques qu’il a utilisé, ont donné naissance à la théorie des graphes ! Problème des sept ponts de Königsberg A D B C A B D C Leonhard Euler (1707 - 1783) A B D C Mostafa MASLOUHI 2020 - 2021 Déﬁnitions a b c e d g f S = {a, b, c, d, e, f, g} A = {(a, b), (a, c), (a, d), (a, e), (b, c), (e, c), (c, f ), (e, f ), (e, d), (d, g), (f, g)} D une manière abstraite, un graphe est un couple où est un ensemble non vide d objets appelé sommets (Vertices en anglais) et est l’ensemble, éventuellement vide, des “arêtes” ( Edges en anglais) reliant des sommets. • On appelle graphe tout couple où: - est un ensemble ﬁni de points appelés les sommets de , - est une partie de , appelé ensemble des arêtes. Chaque arête relie deux sommets qui sont alors appelés ses extrémités. • Si les deux extrémités d’une arête sont égales, on dit que l’arête est une boucle. • Deux sommets sont voisins ou adjacents s’ils sont reliés par une seule arête. • Le graphe est dit orienté, si l’on tient du sens de parcours pour se déplacer entre les arêtes. 1.2.1 Vocabulaire des graphes 1. Graphes simples: Un graphe est dit simple s’il est sans boucle et dans lequel deux sommets sont reliés par au plus une arête. 2. Graphes orientés: On dira qu’un graphe est orienté, si l’on tient compte du sens de parcours dans les arêtes. Si l h t i té l t ti d t l êt t té Graphe non orienté Mostafa MASLOUHI 2020 - 2021 Déﬁnitions S = {a, b, c, d, e, f, g} A = {(a, b), (a, c), (d, a), (e, a), (b, c), (c, e), (e, f ), (e, d), (d, g), (f, c), (f, g)} D une manière abstraite, un graphe est un couple où est un ensemble non vide d objets appelé sommets (Vertices en anglais) et est l’ensemble, éventuellement vide, des “arêtes” ( Edges en anglais) reliant des sommets. • On appelle graphe tout couple où: - est un ensemble ﬁni de points appelés les sommets de , - est une partie de , appelé ensemble des arêtes. Chaque arête relie deux sommets qui sont alors appelés ses extrémités. • Si les deux extrémités d’une arête sont égales, on dit que l’arête est une boucle. • Deux sommets sont voisins ou adjacents s’ils sont reliés par une seule arête. • Le graphe est dit orienté, si l’on tient du sens de parcours pour se déplacer entre les arêtes. 1.2.1 Vocabulaire des graphes 1. Graphes simples: Un graphe est dit simple s’il est sans boucle et dans lequel deux sommets sont reliés par au plus une arête. 2. Graphes orientés: On dira qu’un graphe est orienté, si l’on tient compte du sens de parcours dans les arêtes. Si l h t i té l t ti d t l êt t té Graphe orienté > a b c e d g f > < > > < > > < < < Mostafa MASLOUHI 2020 - 2021 Un peu de vocabulaire … 1.2.1 Vocabulaire des graphes • Graphes simples: Un graphe est dit simple s’il est sans boucle et dans lequel deux sommets sont reliés par au plus une arête. • Graphe biparti: Un graphe est dit bi-partie si on peut écrire avec et et disjoints et tels que et et . • Chemins et cycles: Soit un graphe et , deux sommets de . Un chemin allant de vers est une suite d’arêtes , tel que et . Si de plus on a , le chemin est appelé un cycle. La longueur d’un chemin est le nombre d’arêtes qui le composent. Exemple 1.2.1. La ﬁgure Fig. 1.2 représente un graphe simple et planaire. Fig. 1.2 Un graphe simple a b c e d f g Chemin(s) de a vers g: { L1 = ((a, d), (d, g)) L2 = ((a, e), (e, f ), (f, g)) … Un cycle de a vers a: C = ((a, e), (e, d), (d, a)) Mostafa MASLOUHI 2020 - 2021 Degré d’un sommet 1.2.2 Degré d’un sommet Soit un graphe. • Si est orienté et , on note: Nombre d’arêtes entrant dans : degré entrant de . Nombre d’arêtes sortant de : degré sortant de . Degré total du sommet , en comptant les boucles deux fois. • Si n’est pas orienté, le degré du sommet , noté , est le nombre d’arêtes dont est sommet en comptant les boucles deux fois. Le résultat suivant donne une relation entre la somme des degrés et le nombre des arêtes: Soit un graphe orienté. Le nombre des arêtes de est donné par la formule: En conséquence, Dans G1: d+(e) = 3, d−(e) = 1 Dans G2: d(e) = 4 > a b c e d g f > < > > < > > < < < Graphe G1 a b c e d g f Graphe G2 Mostafa MASLOUHI 2020 - 2021 Degré d’un sommet: Propriétés d arêtes dont est sommet en comptant les boucles deux fois. Le résultat suivant donne une relation entre la somme des degrés et le nombre des arêtes: Soit un graphe orienté. Le nombre des arêtes de est donné par la formule: En conséquence, 1.2.3 Graphes complets Un graphe complet à sommets est tout graphe de la forme où est un ensemble à éléments et est l’ensemble de toutes les paires , telles que et . Autrement dit, est simple sans boucle. 1.3 Connexité et distance Remarque 1.3.1. 1. La longueur d’un chemin est égale au nombre d’arêtes qui le constituent. 2 U h i t f é i l d t é ité t é l Mostafa MASLOUHI 2020 - 2021 Plus court chemin: Algorithme de Dijkstra A B C E D G F 3 5 6 3 4 8 10 10 4 6 5 Problème: Trouver un chemin ayant le minimum coût pour aller de A à G ? Edsger Dijkstra (1930-2002) A B C D E F G 0A 3A 5A 10A 4A ∞ ∞ A 3A B 5A 10A 4A ∞ ∞ E 5A 9E 4A ∞ 10E C 5A 9E ∞ 9C D 9E 19D 9C F 17F 9C 17F G Réponse: Le coût minimum pour aller de A à G est 17 suivant le chemin (A-C-F-G). Mostafa MASLOUHI 2020 - 2021 1.6 Graphes particuliers 1.6.1 Cycles et chemins eulériens Soit un graphe connexe. • Un chemin dans est dit eulérien si dans ce chemin on passe par toutes les arêtes du graphe une et une seule fois. • Un chemin eulérien fermé de est appelé un cycle eulérien. • Le graphe est dit eulérien s’il admet (au moins) un cycle eulérien. 1.6.2 Conditions nécessaires et suﬃsantes pour l’existence de cycles eulériens Un théorème dû à Euler donne une condition nécessaire et suﬃsante pour qu’un graphe admette un chemin ou cycle Eulérien. Ceci était lorsqu’il résolut le fameux problème des ponts de Königsberg ( appelée maintenant Kaliningrad) sur le ﬂeuve Praegel qui coule de part et d’autre de l’île de Kneiphof. On supposera que tous les graphes de cette section ont un nombre ﬁni de sommets et d’arêtes. Soit un graphe connexe non orienté. Alors est eulérien si et seulement si tous ses sommets ont un degré pair. Remarque 1.6.1. La preuve constitue une méthode de construction d’un cycle eulérien. Algorithme de détermination d’un cycle Eulérien Graphes Eulériens Graphe non Eulerien Graphe Eulerien a b c d e f g Mostafa MASLOUHI 2020 - 2021 Graphes Eulériens: Caractérisation a b c d g f e Non Eulerien a b c d g f e h Eulerien a b c d e f g A B D C Eulerien Non Eulerien A B D C Un théorème dû à Euler donne une condition nécessaire et suﬃsante pour qu’un graphe admette un chemin ou cycle Eulérien. Ceci était lorsqu’il résolut le fameux problème des ponts de Königsberg ( appelée maintenant Kaliningrad) sur le ﬂeuve Praegel qui coule de part et d’autre de l’île de Kneiphof. On supposera que uploads/Ingenierie_Lourd/ graph-theory-v1.pdf