Le Concept de Graphes PDF

CHAPITRE 1 LE CONCEPT DE GRAPHES Dr. A. F. Tandjaoui 1.1 Introduction Comme pour les probabilités, beaucoup de travaux de la théorie des graphes ont ét...

CHAPITRE 1 LE CONCEPT DE GRAPHES Dr. A. F. Tandjaoui 1.1 Introduction Comme pour les probabilités, beaucoup de travaux de la théorie des graphes ont été motivés par le jeu. Les graphes sont constitués de points et de liens entre ces points. Les points peuvent repré- senter différentes notions selon le problème étudié, et les liens représentent des relations entre ces notions. Un graphe sera dit non orienté si la relation représentée est réciproque. Dans le cas contraire, il sera dit orienté. Les graphes sont pratiques pour représenter des problèmes de manière visualisable (gra- phique) : coloration de carte, représentation de molécules, problème des sept ponts de König- sberg (problème original), etc. Ils permettent de construire un modèle théorique d’un problème et de le résoudre en exploi- tant des propriétés et des algorithmes déjà disponibles. La plupart des problèmes traités par la théorie des graphes peuvent être décrits comme suit : — Problèmes d’existence : généralement formulé comme suit : — Existe-il... ? — Est-il possible de... ? — Problèmes de construction : généralement formulé comme suit : — Si... existe, comment pouvons-nous le construire ? — Problèmes d’énumération : généralement formulé comme suit : — Combien y a-t-il de... , et comment pouvons-nous les lister tous ? — Problèmes d’optimisation : généralement formulé comme suit : — S’il y a plusieurs..., quel(le) est le/la meilleur(e) ? Le concept de graphes 2 Ainsi, le problème des sept ponts de Königsberg formulé par Euler, était un problème d’existence. La question était : existe-il une promenade dans les rues de Königsburg permettant, à partir d’un point de départ, de passer une et une seule fois par chaque pont, et de revenir à son point de départ (voir la figure 1.1). Figure 1.1 – Problème des sept ponts de Königsberg. Ce problème peut être modélisé par un graphe non orienté où les points seraient les surfaces terrestres (zones hors de l’eau) et les liens seraient les ponts. La représentation graphique de ce graphe G1 est donné à la figure 1.2. B 1 5 2 6 A D 3 7 4 C Figure 1.2 – Graphe G1 modélisant le problème des sept ponts de Königsberg. On remarque bien la simplification apportée par une telle représentation. Il n’est tout de même pas encore évident de répondre à la question de l’existence ou non de la promenade pour l’instant. Nous y reviendrons vers la fin de ce chapitre. Le concept de graphes 3 Ce problème est à l’origine de la théorie des graphes. 1.2 Graphes non orientés Un graphe non orienté G = (X, U ) est déterminé par deux ensembles X et U , avec : — X : ensemble des points appelés sommets, — U : ensemble des liens non orientés entre les paires non ordonnées de sommets appelés arêtes. Exemple Le problème des sept ponts de Königsberg a été modélisé précédemment par un graphe non orienté G1 = (X1 , U1 ) où : — l’ensemble des sommets X1 = {A, B, C, D} représente l’ensemble des surfaces terrestres, — l’ensemble des arêtes U1 = {1, 2, 3, 4, 5, 6, 7} représente l’ensemble des sept ponts. Si N = |X|, on dit que N est l’ordre du graphe. Exemple Le graphe G1 est d’ordre 4. Une arête u qui relie les deux sommets x et y est une paire non ordonnée de sommets et elle peut s’écrire donc u = (x, y). On dit que : — x et y sont les deux extrémités de u, — u est incidente à x et à y, — x et y sont adjacents. Deux arêtes sont dites parallèles si elles possèdent les mêmes extrémités. Exemple L’arête 6 du graphe G1 précédent peut également être écrite sous la forme (A, B). A et B sont donc les extrémités de cette arête qui est elle même incidente à ces deux sommets. A et B sont adjacents. Dans ce même graphe, les arêtes 1 et 2 sont parallèles car elles possèdent les mêmes extré- mités A et B. Remarque L’ensemble des sommets adjacents à un sommet x est noté par Γ(x). Exemple Dans le graphe précédant G1 , nous avons : Γ(A) = {B, C, D}, Γ(B) = {A, D}, Γ(C) = {A, D}, Γ(D) = {A, B, C}. Le concept de graphes 4 Une arête dont les deux extrémités sont identiques est appelée boucle. Exemple La figure 1.3 représente un graphe G2 comprenant un seul sommet et une boucle sur ce sommet. x Figure 1.3 – Graphe G2 comprenant un sommet et une boucle. Le degré d’un sommet x est le nombre d’arêtes incidentes à x, avec les boucles comptées deux fois. On le note d(x). Exemple Dans le graphe G1 , d(A) = 5. Dans le graphe G2 , d(x) = 2. Un graphe non orienté simple est un graphe sans boucle et sans arêtes parallèles. Exemples — Le graphe précédant G1 est un graphe qui est non simple, car il existe deux arêtes parallèles entre les sommets A et B, et aussi deux arêtes parallèles entre les sommets A et C. — Le graphe précédant G2 est également un graphe qui est non simple, car il comporte une boucle. — Le graphe représentant le réseau social Facebook où les sommets sont les comptes des utilisateurs et les arêtes sont les liens d’amitié entre les comptes est un graphe simple car un compte ne peut pas être ami avec lui-même, et deux comptes ne peuvent pas être amis plus d’une seule fois. Un graphe non orienté complet est un graphe simple où il existe une arête entre chaque paire de sommets. Un graphe non orienté complet d’ordre N est noté par KN. Exemple La figure 1.4 représente le graphe non orienté complet G3 d’ordre 4, c.à.d. K4. Une chaîne est une séquence finie et alternée de sommets et d’arêtes, débutant et finissant par deux sommets appelés respectivement extrémité initiale et extrémité terminale, telle que chaque arête est incidente avec les sommets qui l’encadrent dans la séquence. La longueur d’une chaîne est égale au nombre d’arêtes qui la composent, en comptant les Le concept de graphes 5 Figure 1.4 – Graphe G3 = K4. répétitions. Une chaîne élémentaire est une chaîne qui ne parcourt pas plus d’une fois le même sommet. Une chaîne simple est une chaîne qui ne parcourt pas plus d’une fois la même arête. Remarques — L’écriture complète d’une chaîne se fait en listant de manière ordonnée les sommets et les arêtes qui la composent. — Une chaîne peut également être décrite uniquement par les arêtes qui la composent. — De plus, dans le cas de graphes sans arêtes parallèles, une chaîne peut aussi être décrite uniquement par les sommets qui la composent. Exemple Dans le graphe précédant G1 , nous avons par exemple la chaîne (A, 1, B, 5, D, 7, C), qui est de longueur 3. Cette chaîne est simple et élémentaire. Son extrémité initiale est le sommet A et son extrémité terminale est le sommet C. Cette même chaîne peut aussi être décrite par ses arêtes uniquement comme suit : (1, 5, 7). Par contre, puisque G1 n’est pas simple, cette chaîne ne peut pas être décrite unique- ment par ses sommets, car en écrivant (A, B, D), on ne saurait pas s’il s’agit de la chaîne (A, 1, B, 5, D, 7, C) ou bien (A, 2, B, 5, D, 7, C). Un cycle est une chaîne simple dont les extrémités sont identiques. La longueur d’un cycle est égale au nombre d’arêtes qui le composent. Exemple Dans le graphe G1 , nous avons par exemple le cycle (A, 1, B, 5, D, 7, C, 4, A) qui est de longueur 4. Le concept de graphes 6 1.3 Graphes orientés Les mêmes notions que pour les graphes non orientés sont reprises et adaptées au cas orienté dans cette section. Un graphe orienté G = (X, U ) est déterminé par les deux ensembles X et U , avec : — X : ensemble de points appelés sommets, — U : ensemble de liens orientés entre des couples ordonnés de sommets appelés arcs. N = |X| est l’ordre du graphe. Un arc u qui relie le sommet x au sommet y est un couple ordonné qui peut donc s’écrire u = (x, y). On dit que : — x est l’extrémité initiale de u, — y est l’extrémité terminale de u, — y est successeur de x et x est prédécesseur de y, — u est incident à x et à y. Deux arcs ayant la même extrémité initiale et la même extrémité terminale sont dits pa- rallèles. Un arc dont les deux extrémités sont identiques est appelé boucle. Remarque Un arc est une arête à laquelle on précise un sens/une orientation. Exemple Soit le graphe orienté G4 = (X4 , U4 ) où l’ensemble des sommets est X4 = (1, 2, 3), l’ensemble des arcs est U4 = (a, b, c, d, e), et la représentation graphique est donnée à la fi- gure 1.5. b 2 a c d 1 3 e Figure 1.5 – Graphe orienté G4. G4 est d’ordre 3 étant donné qu’il comporte 3 sommets. L’arc a = (1, 2) possède le sommet 1 comme extrémité initiale et le sommet 2 comme extré- mité terminale. Le sommet 2 est donc successeur du sommet 1 et le sommet 1 est prédécesseur du sommet 2. Le concept de graphes 7 Les deux arcs d et e sont des arcs parallèles puisqu’ils ont la même extrémité initiale 3 et la même extrémité terminale 1. Les arcs c et d ne le sont pas. L’arc b est une boucle. Remarque L’ensemble des successeurs d’un sommet x est noté par Γ(x) ou bien Γ+ (x) alors que l’ensemble des ses prédécesseurs est noté par Γ− (x). Exemple Dans le graphe G4 , nous avons : — Γ+ (1) = {2, 3} et Γ− (1) = {3} — Γ+ (2) = {2} et Γ− (2) = {1, 2} — Γ+ (3) = {1} et Γ− (3) = {1} Dans un graphe orienté : — Le demi-degré extérieur d’un sommet x est le nombre d’arcs ayant x comme extrémité initiale. Il est noté d+ (x), — Le demi-degré intérieur d’un sommet x est le nombre d’arcs ayant x comme ex- trémité terminale. Il est noté d− (x), — Le degré d’un sommet x est le nombre d’arcs incidents à x, avec les boucles comptées deux fois. Il est noté d(x). Nous avons d(x) = d+ (x) + d− (x). Exemple Dans le graphe précédant G4 , d+ (2) = 1, d− (2) = 2, d(2) = 3. Un graphe orienté simple est un graphe sans boucle et sans arcs parallèles. Un graphe orienté complet est un graphe orienté simple où il existe un arc entre chaque couple ordonné de sommets. Exemple — Le graphe précédant G4 est un graphe orienté non simple car il comporte une boucle, de plus, il y a deux arcs parallèles d et e. Si les arcs b et e étaient retirés, alors le graphe obtenu serait simple. — Le graphe G5 représenté à la figure 1.6 est un graphe orienté complet d’ordre 4. Figure 1.6 – Graphe orienté complet G5. Le concept de graphes 8 Un chemin est une chaîne où tous les arcs sont parcourus dans le bon sens. La longueur d’un chemin est égale au nombre d’arcs qui le composent, en comptant les répétitions. Un chemin élémentaire est un chemin qui ne parcourt pas plus d’une fois le même sommet. Un chemin simple est un chemin qui ne parcourt pas plus d’une fois le même arc. Exemples Dans le graphe G4 : — Nous avons le chemin simple (1, c, 3, d, 1, a, 2, b, 2). Sa longueur est égale à 4. Ce chemin est non élémentaire car le sommet 2 est parcouru deux fois. — (2, a, 1, c, 3) est une chaîne mais pas un chemin car l’arc a est parcouru dans le mauvais sens. — (1, c, 3, d, 1, c, 3) est un chemin non simple car l’arc c est parcouru 2 fois. Un circuit est un chemin dont les deux extrémités sont identiques. La longueur d’un circuit est égale au nombre d’arcs qui le composent, en comptant les répétitions. Exemples Dans le graphe G4 : — (1, c, 3, d, 1) est un circuit de longueur 2. — (2, b, 2, b, 2) est également un circuit de longueur 2. 1.4 Lemme des poignées de main d(x) = 2 × |U |. P Lemme : Dans un graphe G = (X, U ) nous avons toujours x∈X Démonstration. Chaque arête/arc u ∈ U est compté(e) deux fois dans la somme P x∈X d(x) : une fois par extrémité. Exemple Cette propriété est valide pour tout graphe. À titre d’exemple, dans le graphe G1 , P la somme des degrés de tous les sommets est x∈X d(x) = d(A) + d(B) + d(C) + d(D) = 5 + 3 + 3 + 3 = 14 et le nombre d’arêtes du graphe est |U | = 7. La propriété est donc bien vérifiée. Théorème : Dans un graphe, il y a toujours un nombre pair de sommet à degré impair. Démonstration. À réaliser lors du TD. Le concept de graphes 9 B B 1 4 1 3 A D A D 2 5 2 5 C C (a) Graphe G6. (b) Graphe G7. B B 1 A A 6 D 2 C C (c) Graphe G8. (d) Graphe G9. Figure 1.7 – Exemples de sous-graphe, graphe partiel et graphe complémentaire. Exemple Dans le graphe G1 il y a exactement 4 sommets de degré impair. Il y a donc bien un nombre pair de sommets à degré impair. 1.5 Sous-graphe, graphe partiel et graphe complémen- taire Un sous-graphe du graphe G = (X, U ) est un graphe G′ = (X ′ , U ′ ) tel que X ′ ⊆ X et U′ ⊆ U. Un graphe partiel du graphe G = (X, U ) est un graphe G′ = (X, U ′ ) tel que U ′ ⊆ U. Le graphe complémentaire du graphe simple G = (X, U ) est un graphe simple G = (X, U ) tel que (x, y) ∈ U si et seulement si (x, y) ∈ / U. Exemples Soient les graphes G6 , G7 , G8 et G9 de la figure 1.7. Nous avons : — Le graphe G7 est un graphe partiel du graphe G6. Il est également sous-graphe du graphe G6. — Le graphe G8 est sous-graphe du graphe G6 ainsi que sous-graphe du graphe G7. — Le graphe G9 est le graphe complémentaire du graphe G6. Le concept de graphes 10 1.6 Connexité et forte connexité Un graphe non orienté G = (X, U ) est dit connexe s’il existe au moins une chaîne entre chaque paire de sommets distincts x, y ∈ X. Une composante connexe est un sous-graphe connexe maximal a. Le nombre de connexité d’un graphe est le nombre de ses composantes connexes. Il est noté p. a. Un sous-graphe est maximal par rapport à la connexité s’il n’est pas inclus dans un autre sous-graphe connexe. Exemples — Parmi les graphes de la figure 1.7, G6 , G7 et G8 sont des graphes connexes. Ils comportent donc une seule composante connexe et leur nombre de connexité p = 1. — Le graphe G9 est quant à lui non connexe, et il comporte 3 composantes connexes com- posées respectivement des sommets {A}, {B, C} et {D}. Son nombre de connexité p = 3. Un graphe orienté est dit fortement connexe si pour toute paire de sommets x, y ∈ X, il existe au moins un chemin de x vers y et au moins un chemin de y vers x. Une composante fortement connexe est un sous-graphe fortement connexe maximal. Exemples Le graphe orienté G4 vu précédemment est non fortement connexe car il n’existe par exemple, aucun chemin du sommet 2 au sommet 3. G4 comporte deux composantes forte- ment connexe {1, 3} et {2}. La modification de ce graphe en rajoutant un arc du sommet 2 au sommet 3 produirait le graphe G10 donné à la figure 1.8 qui est un graphe fortement connexe. b 2 a f c d 1 3 e Figure 1.8 – Graphe fortement connexe G10. 1.7 Graphe eulérien Le concept de graphes 11 Une chaîne eulérienne est une chaîne qui parcourt toutes les arêtes d’un graphe une et une seule fois. Un cycle eulérien est une chaîne eulérienne qui forme un cycle. Exemple Le graphe G11 , ci-dessous, contient la chaîne eulérienne : (a, b, d, i, e, f, h, g, c). Cette chaîne forme un cycle, c’est donc également un cycle eulérien. c 1 2 g e a b f d 5 h 3 4 i Figure 1.9 – Graphe G11 avec cycle eulérien. Un graphe semi-eulérien est un graphe qui contient une chaîne eulérienne. Un graphe eulérien est un graphe qui contient un cycle eulérien. Exemple Le graphe précédent G11 contient un cycle eulérien. Ce graphe est donc un graphe eulérien. Il est également semi-eulérien. Théorème : Un graphe connexe est semi-eulérien si et seulement s’il contient exactement 0 ou 2 sommets de degré impair. Il est eulérien si et seulement s’il contient 0 sommet de degré impair. Exemple Si on vérifie le degré de tous les sommets du graphe eulérien précédent G11 , on peut remarquer que tous ses sommets sont bien de degré pair. Si on supprime l’arête c, on obtient un nouveau graphe avec exactement 2 sommets à degré impair. Ce nouveau graphe serait donc non eulérien mais il serait semi-eulérien. Si on revient au problème introductif de notre cours, qui est le problème des ponts de Königsberg (voir la section 1.1), et qui consiste à déterminer s’il est possible de trouver un promenade qui parcourt tous les ponts de la ville une et une seule fois et qui revient au point de départ, on peut constater qu’il s’agit finalement de déterminer si le graphe correspondant, le graphe G1 , est eulérien, ou non. On peut constater que G1 possède des sommets à degré impair (ses 4 sommets sont tous à degré impair). Ce graphe n’est donc pas eulérien. On peut donc en déduire que la promenade recherchée n’existe pas. Le concept de graphes 12 1.8 Matrice d’adjacence Pour un graphe G = (X, U ) d’ordre N et sans arêtes/arcs parallèles, une matrice d’ad- jacence A est une matrice booléenne carrée de taille N × N et qui est construite de la manière suivante : ( 1 si (xi , xj ) ∈ U ∀i, j ∈ 1... N, aij = 0 sinon Exemples Soit le graphe non orienté G12 représenté graphiquement à la figure 1.10. 2 3 1 4 Figure 1.10 – Graphe G12. La matrice d’adjacence de G12 est donnée comme suit : 1 2 3 4 1 0 1 1 1   21 0 0 1 A=   31 0 0 0   4 1 1 0 1 Soit maintenant le graphe orienté G13 obtenu en retirant l’arc d du graphe G4 afin d’éliminer les arcs parallèles et dont la représentation graphique est donnée à la figure 1.11 : b 2 a c 1 3 e Figure 1.11 – Graphe G13 sans arcs parallèles. Sa matrice d’adjacence est la suivante : 1 2 3   1 0 1 1 A = 20 1 0   3 1 0 0 Le concept de graphes 13 Remarques — Pour les graphes non orientés : — A est symétrique — ∀i ∈ 1... N : 2aii + j=1...N aij = 2aii + j=1...N aji = d(xi ) P P j̸=i j̸=i P — i=1...N aii = nombre de boucles dans le graphe — Pour les graphes orientés : — A n’est pas nécessairement symétrique ∀i ∈ 1... N, j=1...N aij = d+ (xi ) P — ∀i ∈ 1... N, j=1...N aji = d− (xi ) P — ∀i ∈ 1... N, j=1...N (aij + aji ) = d(xi ) P — P — i=1...N aii = nombre de boucles dans G Exemple En ce qui concerne le graphe orienté G13 , on remarque que pour sa matrice d’ad- jacence, la somme des éléments de la ligne du sommet 1 donne bien son demi-degré extérieur ( j=1...N a1j = d+ (1) = 2). De même que la somme des éléments de la colonne du sommet 1 P donne bien son demi-degré intérieur ( j=1...N aj1 = d− (1) = 1). Le degré de ce sommet est la P somme des deux valeurs précédentes. Le nombre de boucles de ce graphe est égal à 1 et il correspond bien à la somme des éléments de la diagonale de A. Le concept de graphes 14 3 3 1 2 1 2 5 4 4 (a) (b)  BIBLIOGRAPHIE John M. Harris, Jeffry L. Hirst, and Michael J. Mossinghoff. Combinatorics and Graph Theory, second edition. Springer, 2008.