Les Graphes - Notions de base PDF

Les Graphes - Notions de base Mohand Cherif BOUKALA, [email protected] October 2, 2024 Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 1 / 61 Plan 1 Introduction...

Les Graphes - Notions de base Mohand Cherif BOUKALA, [email protected] October 2, 2024 Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 1 / 61 Plan 1 Introduction 6 Exploration d’un graphe 2 Définitions de base 7 Propriétés des graphes 3 Représentation d’un graphe 8 Coloration dans les graphes 4 Sous-graphes et graphe partiel 9 Encadrement du nombre chromatique 5 Isomorphisme 10 Algorithme de Welsh et Powell Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 2 / 61  Introduction Introduction Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 3 / 61  Introduction Introduction La théorie des graphes est un très vaste domaine de Recherche Opérationnelle. Ce cours ne constituera donc qu’une introduction à cette théorie. La théorie des graphes est née au 18me siècle en essayant de trouver des solutions à des exercices considérés comme curiosités mathématiques. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 4 / 61  Introduction Introduction En 1736 Euler présenta le célèbre problème des ponts de Kônigsberg. Le probème était le suivant: Deux deltas C et D sur la rivière Pregel à Kônigsberg (Actuellement Kaliningrad) étaient reliées entre elles ainsi qu’aux rivages A et B à l’aide de sept ponts. Figure: Problème des ponts de Kônigsberg Question: peut-on partir d’un point quelconque A, B, C, ou D, traverser chacun des ponts une fois et une seule et à revenir au point de départ ? Euler représenta cette situation à l’aide d’un graphe et démontra que ce problème n’admet pas de solution. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 5 / 61  Introduction Introduction Deux autres problèmes d’importance pour la théorie des graphes furent également proposés. Le premier est la conjecture des quatre couleurs qui affirme que quatre couleurs suffisent pour colorier n’importe quelle carte plane telle que les pays ayant une frontière commune soient de couleurs différentes. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 6 / 61  Introduction Introduction Deux autres problèmes d’importance pour la théorie des graphes furent également proposés. Le premier est la conjecture des quatre couleurs qui affirme que quatre couleurs suffisent pour colorier n’importe quelle carte plane telle que les pays ayant une frontière commune soient de couleurs différentes. Ce problème est resté très longtemps sans solution. Il a fallu attendre jusqu’en 1976 pour que Appel et Haken prouvent ce théorème en réduisant le problème à un nombre fini de situations particulières et en trouvant une solution pour chacune d’entre elles à l’aide d’un ordinateur. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 6 / 61  Introduction Introduction En 1859, Sir Hamilton posa un autre problème qui consiste à visiter N villes en passant une fois et une seule fois par chacune des villes. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 7 / 61  Introduction Introduction En 1859, Sir Hamilton posa un autre problème qui consiste à visiter N villes en passant une fois et une seule fois par chacune des villes. La condition nécessaire et suffisante de l’existence d’un tel chemin (appelé chemin Hamiltonien) dans un graphe quelconque n’est pas connue. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 7 / 61  Introduction Introduction La théorie des graphes a connu un développement plus important lors de la deuxième guerre mondiale, et la contribution de l’armée américaine est considérable. Les graphes constituent donc à la fois une théorie et un outils qui permettent de modéliser une grande variété de problèmes en se ramenant à l’étude de graphes. Les derniers travaux en théorie des graphes sont aussi effectués par des informaticiens, du fait de l’importance que revêt l’aspect algorithmique. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 8 / 61  Introduction Introduction Les domaines d’applications des graphes sont diverses, justifiant une recherche importante en algorithmique. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 9 / 61  Introduction Introduction Les domaines d’applications des graphes sont diverses, justifiant une recherche importante en algorithmique. Les réseaux de communication : réseaux routiers, de chemin de fer, de téléphone, de relais de télévision, réseaux électriques, réseaux des informations dans une organisation, etc... ; Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 9 / 61  Introduction Introduction Les domaines d’applications des graphes sont diverses, justifiant une recherche importante en algorithmique. Les réseaux de communication : réseaux routiers, de chemin de fer, de téléphone, de relais de télévision, réseaux électriques, réseaux des informations dans une organisation, etc... ; La gestion de la production et les problèmes d’ordonnancement des tâches : Le graphes potentiels-étapes plus connu sous le nom de graphes PERT (Programme Evaluation and Research Task) est l’outil de résolution de ce type de problèmes; Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 9 / 61  Introduction Introduction Les domaines d’applications des graphes sont diverses, justifiant une recherche importante en algorithmique. Les réseaux de communication : réseaux routiers, de chemin de fer, de téléphone, de relais de télévision, réseaux électriques, réseaux des informations dans une organisation, etc... ; La gestion de la production et les problèmes d’ordonnancement des tâches : Le graphes potentiels-étapes plus connu sous le nom de graphes PERT (Programme Evaluation and Research Task) est l’outil de résolution de ce type de problèmes; Les flots dans les réseaux: l’étude des circuits électriques, Kirchhof, qui a étudié les réseaux électriques, peut être considéré comme un des précurseurs de cette théorie ; Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 9 / 61  Introduction Introduction Les domaines d’applications des graphes sont diverses, justifiant une recherche importante en algorithmique. Les réseaux de communication : réseaux routiers, de chemin de fer, de téléphone, de relais de télévision, réseaux électriques, réseaux des informations dans une organisation, etc... ; La gestion de la production et les problèmes d’ordonnancement des tâches : Le graphes potentiels-étapes plus connu sous le nom de graphes PERT (Programme Evaluation and Research Task) est l’outil de résolution de ce type de problèmes; Les flots dans les réseaux: l’étude des circuits électriques, Kirchhof, qui a étudié les réseaux électriques, peut être considéré comme un des précurseurs de cette théorie ; La chimie, la sociologie et l’économie : la notion de clique est un exemple de l’implication de la théorie des graphes dans ces disciplines. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 9 / 61  Définitions de base Définitions de base Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 10 / 61  Définitions de base Graphe non orienté Définition Un graphe non orienté G = (X , E ) est défini par les deux ensembles: X = {x1 , x2 ,... , xn } est l’ensemble fini de sommets, n > 1. E = {e1 , e2 ,... , em } est l’ensemble fini d’arêtes. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 11 / 61  Définitions de base Graphe non orienté Définition Un graphe non orienté G = (X , E ) est défini par les deux ensembles: X = {x1 , x2 ,... , xn } est l’ensemble fini de sommets, n > 1. E = {e1 , e2 ,... , em } est l’ensemble fini d’arêtes. Chaque élément ei ∈ E est une paire non ordonnée de sommets, ei = {x , y }. x et y sont appelés extrémités de ei. E peut être vide. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 11 / 61  Définitions de base Graphe non orienté Définition Un graphe non orienté G = (X , E ) est défini par les deux ensembles: X = {x1 , x2 ,... , xn } est l’ensemble fini de sommets, n > 1. E = {e1 , e2 ,... , em } est l’ensemble fini d’arêtes. Chaque élément ei ∈ E est une paire non ordonnée de sommets, ei = {x , y }. x et y sont appelés extrémités de ei. E peut être vide. Les sommets représentent les objets et les arcs ou les arêtes représentent la relation ou le lien entre les différents objets. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 11 / 61  Définitions de base Graphe non orienté Exemple Les sommets peuvent representer des villes, des ordinateurs, des personnes,... Les arêtes representeront par exemple : - Il y a une liaison aérienne entre deux villes - Deux ordinateurs partageant une ressource (imprimante, fichiers,...) - Deux personnes amis sur facebook. Exemple de graphes 2 5 1 5 1 2 2 2 6 1 4 6 2 3 1 4 1 3 3 7 6 3 4 4 5 3 4 5 G1 G2 G3 G4 G5 Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 12 / 61  Définitions de base Graphe orienté Définition Un graphe orienté G = (X , U) est défini par les deux ensembles: X = {x1 , x2 ,... , xn } est l’ensemble fini de sommets, n > 1. U = {u1 , u2 ,... , um } est l’ensemble fini d’arcs. Chaque élément ui ∈ U est une paire ordonnée de sommets, ui = (x , y ). x est appelé extrémité initiale de ui et y est extrémité terminale. U peut être vide. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 13 / 61  Définitions de base Graphe orienté Exemple 2 5 4 2 5 2 5 1 4 1 4 1 6 3 3 6 3 G1 G2 G3 Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 14 / 61  Définitions de base L’ordre n d’un graphe G est le nombre de sommets dans le graphe G. n = IXI Si les deux extrémités d’un arc (resp. d’une arête) sont confondues alors cet arc (resp. cette arête) est appelé(e) boucle. Si deux ou plusieurs arcs (resp. d’une arête) possèdent les mêmes extrémités initiales et mêmes extrémités terminales, on dit alors qu’ils (resp. elles) sont parallèles. Un graphe qui comporte des arcs (arêtes) parallèles est appelé multigraphe. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 15 / 61  Définitions de base Soit un arc u=(x, y) (resp. un arête e = {x , y }) : x et y sont dits sommets adjacents. Pour le cas de l’arc u : x est dit prédécesseur de y. y est dit successeur de x. Soit x ∈ X , un sommet du graphe orienté G = (X , U). On définit : Γ+ (x ) = {y ∈ X /(x , y ) ∈ U} appelé ensemble des successeurs de x. Γ− (x ) = {y ∈ X /(y , x ) ∈ U} appelé ensemble des prédécesseurs de x. Soit x ∈ X , un sommet du graphe G, on appelle voisin de x tout sommet y ∈ X différent de x et qui est adjacent à x. L’ensemble des voisins de x, noté V (x ), est défini comme suit: V (x ) = {y ∈ X / x 6= y et (x , y ) ∈ U ou (y , x ) ∈ U} Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 16 / 61  Définitions de base Notion de degré Définition (Degré d’un sommet) Soit G = (X , E ) un graphe non orienté (resp. G = (X, U) un graphe orienté). Le degré d’un sommet x ∈ X , noté dG (x ), est égal au nombre d’arcs ou d’arêtes incidentes au sommet x , les boucles étant comptées deux fois. Dans le graphe x1 x2 x3 dG (x1 ) = 4 dG (x2 ) = 3 x5 dG (x3 ) = 2 x4 Figure: Un graphe non orienté Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 17 / 61  Définitions de base Notion de degré Définition Soit G = (X , U) un graphe orienté: Le demi-degré extérieur d’un sommet x ∈ X , noté dG+ (x ), est égal au nombre d’arcs dont x est l’extrémité initiale. Le demi-degré intérieur d’un sommet x ∈ X , noté dG− (x ), est égal au nombre d’arcs dont x est l’extrémité terminale. Le degré d’un sommet x : dG (x ) = dG+ (x ) + dG− (x ) Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 18 / 61  Définitions de base Notion de degré Dans le graphe x2 x3 x1 x4 x6 x5 Figure: Un graphe orienté dG+ (x1 ) = 1, dG− (x1 ) = 0, dG+ (x2 ) = 1, dG− (x2 ) = 2, dG+ (x4 ) = 2, dG− (x4 ) = 2. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 19 / 61  Définitions de base Notion de degré Le degré minimal d’un graphe G, noté par δ(G), est le plus petit degré dans le graphe G. δ(G) = min{dG (x )} Le degré maximal d’un graphe G, noté par ∆(G), est le plus grand degré dans le graphe G. ∆(G) = max{dG (x )} Si dG (x ) = 0 Alors x est dit sommet isolé. Si dG (x ) = 1 Alors x est dit sommet pendant. Un arc (resp. Une arête) incident(e) à un sommet pendant est aussi dit(e) arc (arête) pendant(e). Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 20 / 61  Définitions de base Formule des degrés Formule des degrés Cas non orienté: Pour tout graphe non orienté G = (X , E ), on a: X dG (x ) = 2|E | x ∈X preuve: Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 21 / 61  Définitions de base Formule des degrés Formule des degrés Cas non orienté: Pour tout graphe non orienté G = (X , E ), on a: X dG (x ) = 2|E | x ∈X preuve: On peut prouver cette égalité par récurrence. En effet, pour un graphe G0 ayant n sommets et aucune (zéro) arêtes l’égalité est vérifiée. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 21 / 61  Définitions de base Formule des degrés Formule des degrés Cas non orienté: Pour tout graphe non orienté G = (X , E ), on a: X dG (x ) = 2|E | x ∈X preuve: On peut prouver cette égalité par récurrence. En effet, pour un graphe G0 ayant n sommets et aucune (zéro) arêtes l’égalité est vérifiée. On P suppose maintenant que l’égalité est vraie pour m arêtes, c-à-d x ∈X dG (x ) = 2m, il est facile de voir que l’ajout d’une arête: Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 21 / 61  Définitions de base Formule des degrés Formule des degrés Cas non orienté: Pour tout graphe non orienté G = (X , E ), on a: X dG (x ) = 2|E | x ∈X preuve: On peut prouver cette égalité par récurrence. En effet, pour un graphe G0 ayant n sommets et aucune (zéro) arêtes l’égalité est vérifiée. On P suppose maintenant que l’égalité est vraie pour m arêtes, c-à-d x ∈X dG (x ) = 2m, il est facile de voir que l’ajout d’une arête: - d’une part augmentera de un le degré de deux sommets (ou de deux le degré d’un même sommet si l’arête est une boucle), - d’autre part le nombre d’arêtes augmente de 1, le second membre augmente donc de 2. L’égalité est donc préservée, ce qu’il fallait montrer. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 21 / 61  Définitions de base Notion de degré Cas orienté: Pour tout graphe orienté G = (X , U), on a: X X X dG (x ) = 2|U| et dG+ (x ) = dG− (x ) = |U| x ∈X x ∈X x ∈X Preuve: On peut adapter la démonstration précedente. Conséquence: De là, on peut déduire que le nombre de sommets de degrés impairs dans un graphe est toujours pair. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 22 / 61  Représentation d’un graphe Représentation d’un graphe Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 23 / 61  Représentation d’un graphe Représentation graphique On représente généralement un sommet par un point ou par un cercle. Un arc est représenté par une flèche et une arête par un trait qui peuvent être courbés. Exemple 1. x2 x1 x3 x4 x5 Figure: Un graphe non orienté Ce graphe est défini par l’ensemble des sommets X = {x1 , x2 , x3 , x4 , x5 } et l’ensemble des arêtes E = {{x1 , x2 }, {x1 , x3 }, {x1 , x4 }, {x1 , x5 }, {x2 , x2 }, {x3 , x5 }, {x4 , x5 }} Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 24 / 61  Représentation d’un graphe Représentation graphique Exemple 2. x2 x3 x1 x4 x6 x5 Figure: Un graphe orienté De même pour ce graphe, l’ensemble des sommets X = {x1 , x2 , x3 , x4 , x5 , x6 } et l’ensemble d’arcs U = {(x1 , x6 ), (x2 , x5 ), (x3 , x2 ), (x3 , x4 ), (x3 , x6 ), (x4 , x2 ), (x4 , x4 ), (x6 , x5 )} Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 25 / 61  Représentation d’un graphe Matrice d’adjacence A tout graphe d’ordre n on associe une matrice M de n lignes et n colonnes dont les éléments sont notés Mij. Pour un graphe non orienté G = (X , E ),  1 si {xi , xj } ∈ E Mij = (1) 0 sinon x1 x2   0 1 1 1 1 1 1 0 0 0 x3   1 M= 0 0 0 1 1 0 0 0 1 x5 1 0 1 1 0 x4 Figure: Un graphe non orienté Figure: Matrice d’adjacence du graphe Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 26 / 61  Représentation d’un graphe Matrice d’adjacence Remarques La matrice d’adjacence M d’un graphe non orienté est toujours symétrique. P P i=1,n Mik = j=1,n Mkj = dG (k). La boucle est comptée deux fois. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 27 / 61  Représentation d’un graphe Matrice d’adjacence Pour un graphe orienté G = (X , U):  1 si (xi , xj ) ∈ U Mij = (2) 0 sinon x2 x3   0 0 0 0 0 1 0 0 0 0 1 0   0 1 0 1 0 1 x1 M= 0  x4  1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 x6 x5 Figure: Un graphe orienté Figure: Matrice d’adjacence Remarque La somme d’une ligne i = d + (i). LesLaGraphes Mohand Cherif BOUKALA, [email protected] somme- Notions d’une de base colonne j = d − (j). October 2, 2024 28 / 61  Représentation d’un graphe Matrice d’incidence Graphes non orientés A tout graphe non orienté G = (X , E ), on peut associer une matrice M de n lignes et m colonnes. Où n est le nombre de sommets dans G et m est le nombre d’arêtes dans G. Mij représente le nombre de fois où le sommet i est incident à l’arête j. Les éléments de M sont dans {0, 1, 2} Si deux colonnes j1 et j2 sont identiques alors les arêtes j1 et j2 sont parallèles. Pour un graphe non orienté G = (X , E ),   2 si l’arête j est une boucle reliée au sommet i Mij = 1 si le sommet i est une extrémité de l’arête j (3) 0 sinon  Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 29 / 61  Représentation d’un graphe Graphes orientés A tout graphe orienté G = (X , U), on peut associer une matrice M de n lignes et m colonnes. Où n est le nombre de sommets dans G et m est le nombre d’arcs dans G.   1 si le sommet i est une extrémité initiale de l’arc j Mij = −1 si le sommet i est une extrémité terminale de l’arc j (4) 0 sinon  Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 30 / 61  Représentation d’un graphe Représentation par les listes A tout graphe orienté G=(X, U) avec |X | = n et |U| = m, on peut associer deux tableaux (vecteurs) PS et LS: PS : tableau de pointeurs à n+1 éléments, où: PS[i] : pointe sur l’éléments (la case) de LS contenant le premier successeur du sommet i. On pose PS = 1, et PS[n + 1] = m + 1. Pour tout n > i > 2 : PS[i] = k, où k = PS[i − 1]+ nombre de successeurs de i-1 Si un sommet i n’a pas de successeurs, on aura PS[i] = PS[i + 1] LS : tableau de m éléments, où : Les successeurs d’un sommet i se trouvent dans LS entre la case indiquée dans PS[i] et la case PS[i + 1] − 1. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 31 / 61  Représentation d’un graphe Représentation d’un graphe 1 2 3 4 5 6 7 x2 x3 PS 1 2 3 6 8 8 9 1 2 3 4 5 6 7 9 LS 6 5 6 2 4 4 2 5 x1 x4 Figure: Représentation par les listes de successeurs x6 x5 Figure: Un graphe orienté Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 32 / 61  Représentation d’un graphe Représentation d’un graphe Il existe encore d’autres représentations, les performances des algorithmes manipulant les graphes peuvent en dépendre. une représentation peut donc être plus ou moins adaptée. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 33 / 61  Sous-graphes et graphe partiel Sous-graphes et graphe partiel Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 34 / 61  Sous-graphes et graphe partiel Sous-graphes et graphe partiel Soit G = (X , U) un graphe orienté (resp. G = (X , E ) un graphe non orienté). Soit A ∈ X un sous ensemble de sommets et V ∈ U (resp. V ∈ E ). Graphe partiel Un graphe partiel G 0 de G engendré par l’ensemble d’arcs (resp. d’arêtes ) V 0 ⊂ V (resp. E 0 ⊂ E ) est le graphe G 0 = (X , V ) ()resp. G 0 = (X , E 0 ). Sous graphe Un sous graphe de G engendré par l’ensemble de sommets A est le graphe : GA = (A, UA ) où UA = {u ∈ U/I(u) ∈ A et T (u) ∈ A} dans le cas orienté. GA = (A, EA ) où EA = {e = {x , y } ∈ E /x ∈ A et y ∈ A} dans le cas non orienté. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 35 / 61  Isomorphisme Isomorphisme Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 36 / 61  Isomorphisme Définition Soient deux graphes orientés G1 = (X1 , U1 ) et G2 = (X2 , U2 ). On dit que G1 et G2 sont isomorphes (on note G1 ≡ G2 ) ssi ∃f : X1 → X2 et ∃g : U1 → U2 deux bijections telles que ∀u ∈ U1 , u = (x , y ) ⇔ g(u) = (f (x ), f (y )). Définition Soient deux graphes non orientés G1 = (X1 , E1 )etG2 = (X2 , E2 ). On dit que G1 et G2 sont isomorphes (on note G1 ≡ G2 ) ssi ∃ϕ : X1 → X2 une bijection telle que ∀x , y ∈ X1 , e = x , y ∈ E1 ⇒ ϕ(x ), ϕ(y ) ∈ E2. Figure: Deux graphes isomorphes Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 37 / 61  Isomorphisme Proposition Soient deux graphes isomorphes G1 = (X1 , U1 ) ≡ G2 = (X2 , U2 ) (resp. G1 = (X1 , E1 ) ≡ G2 = (X2 , E2 )) alors |X1 | = |X2 | et |U1 | = |U2| (resp. |E1 | = |E2 |) et ∀x ∈ X1 de degré dG1 (x ), ∃y ∈ X2 de degré dG2 (y ) = dG1 (x ). Remarque La réciproque n’est pas toujours vraie. On peut trouver deux graphes non isomorphes ayant le même nombre de sommets et le même nombre d’arc (ou arêtes). Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 38 / 61  Exploration d’un graphe Exploration d’un graphe Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 39 / 61  Exploration d’un graphe Exploration d’un graphe Beaucoup de problèmes sur les graphes nécessitent que l’on parcourt l’ensemble des sommets et des arcs/arêtes du graphe (exploration du graphe). Pendant l’exploration du graphe un sommet peut être dans l’un des états: - Non visité, ce sommet n’a pas encore été rencontré. - Visité, sommet rencontré mais ces succésseurs n’ont pas été traités. - Exploré, sommet visité et ses successeurs ont été traités. On peut numéroter les sommets, pour chaque sommet x , ρ(x ) correspond à l’ordre dans lequel on a rencontré x. Pour chaque sommet x on peut aussi garder le sommet père, pere(x ) par lequel on est passé pour arriver à x. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 40 / 61  Exploration d’un graphe Algorithme Exploration Entrées: Graphe G; Sommet de départ s Initialisation: Visited = {x0 } ; Explored = ∅ ; i = 1; while Visited 6= ∅ do Choisir un sommet x ∈ Visited ; Visited = Visited \ {x } ; Explored = Explored ∪ {x } ; for each sommet y adjacent à x do if y 6∈ Explored then Visited = Visited ∪ {y } ; pere(y ) = x ; ρ(x ) = i ; i = i + 1 end if end for end while Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 41 / 61  Exploration d’un graphe x1 x2 x3 x5 x4 Figure: Un graphe non orienté s = x4 , Visited = {x4 }, Explored = ∅ Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 42 / 61  Exploration d’un graphe x1 x2 1ère itération: On prend le sommet s4 de Visited, on l’ajoute à Explored, et on ajoute les sommets x1 , x5 adjacents à x4 à Visited. x3 Visited = {x1 , x5 } ; Explored = {x4 } ; x5 x4 Figure: Un graphe non orienté s = x4 , Visited = {x4 }, Explored = ∅ Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 42 / 61  Exploration d’un graphe x1 x2 1ère itération: On prend le sommet s4 de Visited, on l’ajoute à Explored, et on ajoute les sommets x1 , x5 adjacents à x4 à Visited. x3 Visited = {x1 , x5 } ; Explored = {x4 } ; x5 x4 2ème itération: On prend un des sommets de Visited, par exemple Figure: Un graphe non orienté x5. On l’ajoute à Explored, et on ajoute aussi les sommets x1 , x3 adjacents à x5 à Visited Visited = {x1 , x3 } ; Explored = {x4 , x5 } ; s = x4 , Visited = {x4 }, Explored = ∅ Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 42 / 61  Exploration d’un graphe x1 x2 1ère itération: On prend le sommet s4 de Visited, on l’ajoute à Explored, et on ajoute les sommets x1 , x5 adjacents à x4 à Visited. x3 Visited = {x1 , x5 } ; Explored = {x4 } ; x5 x4 2ème itération: On prend un des sommets de Visited, par exemple Figure: Un graphe non orienté x5. On l’ajoute à Explored, et on ajoute aussi les sommets x1 , x3 adjacents à x5 à Visited Visited = {x1 , x3 } ; Explored = {x4 , x5 } ; s = x4 , Visited = {x4 }, Explored = ∅ 3ème itération: On prend un des sommets de Visited, par exemple x1. On l’ajoute à Explored, et on ajoute aussi les sommets x2 , x3 adjacents à x1 à Visited Visited = {x2 , x3 } ; Explored = {x1 , x4 , x5 } ; Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 42 / 61  Exploration d’un graphe x1 x2 1ère itération: On prend le sommet s4 de Visited, on l’ajoute à Explored, et on ajoute les sommets x1 , x5 adjacents à x4 à Visited. x3 Visited = {x1 , x5 } ; Explored = {x4 } ; x5 x4 2ème itération: On prend un des sommets de Visited, par exemple Figure: Un graphe non orienté x5. On l’ajoute à Explored, et on ajoute aussi les sommets x1 , x3 adjacents à x5 à Visited Visited = {x1 , x3 } ; Explored = {x4 , x5 } ; s = x4 , Visited = {x4 }, Explored = ∅ 3ème itération: On prend un des sommets de Visited, par exemple x1. On l’ajoute à Explored, et on ajoute aussi les sommets x2 , x3 adjacents à x1 à Visited Visited = {x2 , x3 } ; Explored = {x1 , x4 , x5 } ; 4ème itération: On prend un des sommets de Visited, par exemple x2. On l’ajoute à Explored Visited = {x3 } ; Explored = {x1 , x2 , x4 , x5 } ; Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 42 / 61  Exploration d’un graphe x1 x2 1ère itération: On prend le sommet s4 de Visited, on l’ajoute à Explored, et on ajoute les sommets x1 , x5 adjacents à x4 à Visited. x3 Visited = {x1 , x5 } ; Explored = {x4 } ; x5 x4 2ème itération: On prend un des sommets de Visited, par exemple Figure: Un graphe non orienté x5. On l’ajoute à Explored, et on ajoute aussi les sommets x1 , x3 adjacents à x5 à Visited Visited = {x1 , x3 } ; Explored = {x4 , x5 } ; s = x4 , Visited = {x4 }, Explored = ∅ 3ème itération: On prend un des sommets de Visited, par exemple x1. On l’ajoute à Explored, et on ajoute aussi les sommets x2 , x3 adjacents à x1 à Visited Visited = {x2 , x3 } ; Explored = {x1 , x4 , x5 } ; 4ème itération: On prend un des sommets de Visited, par exemple x2. On l’ajoute à Explored Visited = {x3 } ; Explored = {x1 , x2 , x4 , x5 } ; 5ème itération: On prend le sommets x3 de Visited et on l’ajoute à Explored Visited = ∅ ; Explored = {x1 , x2 , x3 , x4 , x5 } ; Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 42 / 61  Exploration d’un graphe Il existe deux grandes stratégies "opposées" pour sélectionner à chaque étape le sommet à marquer: 1 La recherche en profondeur DFS (Depth First Search) Dans l’exploration, l’algorithme cherche à aller très vite "profondément" dans le graphe, en s’éloignant du sommet s de départ. La recherche sélectionne à chaque étape un sommet voisin du sommet marqué à l’étape précédente. Dans cette exploration, l’ensemble Visited est une pile et la procédure choisir consiste donc à dépiler un sommet (LIFO). 2 La recherche en largeur BFS (Breadth First Search). Dans l’exploration l’algorithme cherche au contraire à épuiser la liste des sommets proches de s avant de poursuivre l’exploration du graphe (FIFO). Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 43 / 61  Propriétés des graphes Propriétés des graphes Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 44 / 61  Propriétés des graphes Définition (Multiplicité d’un graphe) On appelle multiplicité d’un arc u = (x , y ) (resp. arête e = {x , y }), la valeur mxy correspondant au nombre d’arcs qui relient x à y. La multiplicité d’un graphe G est le nombre m(G) correspondant au maximum des mxy. Si m(G) > 1 G est appelé multigraphe. Si G = (X , E ) (resp. G = (X , U)) est un multigraphe alors E (resp. U) est un multi-ensemble. Un graphe orienté est dit p-graphe si m(G) = p. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 45 / 61  Propriétés des graphes Graphe Simple Un graphe non orienté est dit simple s’il ne contient pas de boucles, de plus entre tout couple de sommets il y a au plus une arête. Graphe Complet Dans le cas orienté : G est complet ssi ∀x , y ∈ X , (x , y ) ∈ / U ⇒ (y , x ) ∈ U Dans le cas non orienté : G est complet ssi ∀x 6= y ∈ X , {x , y } ∈ E. Un graphe simple complet d’ordre n est noté Kn. x2 x3 x1 x4 x6 x5 Figure: Un graphe complet K6 Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 46 / 61  Propriétés des graphes Graphe Régulier Un graphe G est dit k-régulier si ∀x sommet de G, on a dG (x ) = k. En d’autres termes, δ(G) = ∆(G) = k. x2 x3 x1 x4 x6 x5 Figure: Un graphe 4-régulier Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 47 / 61  Propriétés des graphes Graphe Biparti G est dit biparti ssi l’ensemble de ses sommets X admet une partition en 2 sous ensembles X1 et X2 avec X1 ∩ X2 = ∅ et X1 ∪ X2 = X. Dans le cas orienté : ∀(x , y ) ∈ U ⇒ x ∈ X1 et y ∈ X2 Dans le cas non orienté : ∀x , y ∈ E (x ∈ X1 et y ∈ X2 )ou(x ∈ X2 ety ∈ X1 ). G est dit biparti complet ssi G est dit biparti et ∀x ∈ X1 et ∀y ∈ X2 ⇒ (x , y ) ∈ U. x1 y1 x2 y2 x3 y3 x4 Figure: Un graphe biparti Un graphe biparti complet G = (X1 ∪ X2 , U) (resp. G = (X1 ∪ X2 , E )) avec |X1 | = p et |X2 | = q est noté Kp,q. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 48 / 61  Propriétés des graphes D’autres propriétés peuvent caractériser les graphe orientés: G est symétrique ssi ∀x , y ∈ X , (x , y ) ∈ U ⇒ (y , x ) ∈ U G est antisymétrique ssi ∀x , y ∈ X , (x , y ) ∈ U ⇒ (y , x ) ∈ /U G est transitif ssi ∀x , y , z ∈ X , (x , y ) ∈ U et (y , z) ∈ U ⇒ (x , z) ∈ U Remarque Il existe encore d’autres types de graphes tels que: - Les arbres et arborescences, qu’on verra en détail plus loin. - Les graphes planaires, Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 49 / 61  Propriétés des graphes Complément d’un graphe Le graphe complémentaire d’un graphe simple G est noté Ḡ = (X , Ē ) où : Ē = {{x , y } ∈ X 2 / x 6= y et {x , y } ∈ / E} Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 50 / 61  Coloration dans les graphes Coloration dans les graphes Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 51 / 61  Coloration dans les graphes Coloration dans les graphes La question de coloration, datant du 19ème siècle, revêt une importance particulière en théorie des graphes, tant sur le plan théorique que sur le plan pratique. En effet, la question célèbre du nombre minimum de couleurs nécessaires pour colorier un graphe planaire (carte géographique) suscite toujours autant d’intérêt. Sur le plan pratique, la coloration dans les graphes permet de résoudre des problèmes de planification et d’emplois du temps pour ne citer que cela. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 52 / 61  Coloration dans les graphes Cliques et Stables On appelle stable dans un graphe G un sous-ensemble de sommets S ⊆ X et le sous graphe engendré par S est formé de sommets isolés (ne contient aucun arc ou arête). Dans le graphe de la figure : x1 x2 x3 x5 x4 l’ensemble de sommets S = {x2 , x3 , x4 } forme un stable. Chaque partition d’un graphe biparti est un stable. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 53 / 61  Coloration dans les graphes Cliques et Stables On appelle clique dans un graphe G un sous-ensemble de sommets C ⊆ X où le sous graphe engendré par C est un graphe complet. Les ensemble de sommets {x1 , x3 , x5 } et {x1 , x4 , x5 } forment des cliques. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 54 / 61  Coloration dans les graphes Coloration dans les graphes Définition (Coloration d’un graphe) La coloration des sommets d’un graphe consiste à affecter à chaque sommet de ce graphe une couleur de telle sorte que deux sommets adjacents ne portent pas la même couleur. Une coloration avec k couleurs est donc une partition de l’ensemble des sommets en k parties stables. Définition (Nombre chromatique d’un graphe) Le nombre chromatique, noté γ(G); du graphe G est le plus petit entier k pour lequel il existe une partition de X en k sous-ensembles stables. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 55 / 61  Coloration dans les graphes Exemple x2 x1 x3 x4 x5 Figure: Les sommets de ce graphe peuvent être colorié avec 2 couleurs. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 56 / 61  Encadrement du nombre chromatique Encadrement du nombre chromatique Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 57 / 61  Encadrement du nombre chromatique Majoration Théorème γ(G) ≤ ∆(G) + 1 Preuve: Construisons une partition de X en sous-ensembles stables de la manière suivante: - on considère un sommet x1 arbitraire de X ; et S1 est une plus grande partie stable de X contenant x1. - s’il existe un sommet x2 de X qui n’est pas dans S1 , on construit S2 ; une plus grande partie stable de X contenant x2 disjointe de S1 - sil existe un sommet x3 de X qui n’est pas dans S1 ∪ S2 ; on construit S3 ; plus grande partie stable de X contenant x3 telle que S1 ; S2 et S3 soient deux à deux disjointes. - X étant un ensemble fini, ce procédé se terminera et nous obtenons une partition {S1 ; S2 ;... ; Sk } de X: En choisissant une couleur par élément de la partition, nous aurons nécessairement : γ(G) ≤ k. Considérons maintenant un sommet x de la partie Sk , x est adjacent à au moins un sommet de chaque partie Si ; i ∈ {1; 2;... ; k − 1}, On en déduit alors que d(x ) ≥ k − 1 ≥ γ(G) − 1, ce qui établit donc l’inégalité: γ(G) ≤ ∆(G) + 1 Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 58 / 61  Encadrement du nombre chromatique Minoration Théorème Le nombre chromatique d’un graphe est supérieur ou égal au cardinal de la clique d’ordre maximal. Preuve: Puisque par définition les sommets d’une clique sont tous adjacents, il faudra donc autant de couleurs que de sommets de cette clique. Le nombre chromatique du graphe sera donc supérieur ou égal à l’ordre de cette clique. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 59 / 61  Algorithme de Welsh et Powell Algorithme de Welsh et Powell Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 60 / 61  Algorithme de Welsh et Powell Cet algorithme permet d’obtenir une coloration n’utilisant pas un trop grand nombre de couleurs. Cependant il n’assure pas que le nombre de couleurs utilisé soit minimum (et donc égal au nombre chromatique du graphe). L’algorithme se déroule comme suit: Etape 1 Attribuer une couleur non encore utilisée au sommet non encore coloré de degré maximum, et attribuer cette même couleur à chaque sommet non encore coloré et non adjacent à un sommet de cette couleur. Etape 2 S’il reste des sommets non colorés dans le graphe, revenir à l’étape 1. Sinon, la coloration est terminée. Mohand Cherif BOUKALA, [email protected] Les Graphes - Notions de base October 2, 2024 61 / 61