Remerciez-le!

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

Les graphes  4ème : I Sciences de l'Informatiques Mr: HIDOURI Mosbah 1 I.

Les graphes  4ème : I Sciences de l'Informatiques Mr: HIDOURI Mosbah 1 I. Graphe Non Orienté Simple Soit le graphe G ci-dessous  Un graphe non orienté simple est la donnée d’un ensemble fini, non vide, de points appelés sommets et d’un ensemble de liens entre deux sommets, appelés arêtes, deux sommets étant reliés par au plus une arrête (une arête reliant A et B est une paire {A, B} ou simplement AB)  Deux sommets reliés par une arête sont dits adjacents. Exemple : A et B sont adjacents mais A et C ne le sont pas  L’ordre d’un graphe est le nombre de sommets de ce graphe Exemple : l'ordre de G est égal à 5  Le degré d’un sommet est le nombre d’arêtes dont ce sommet est une extrémité Exemple : le degré de A est égal à 3 et celui de C est égal à 2  Un graphe complet est un graphe tel qu’il existe toujours une arête entre deux sommets quelconques Exemple : G n'est pas complet car A n'est pas relié à C par une arrête  Un sous graphe d’un graphe G est un graphe G’ composé de certains sommets de G ainsi que de toutes arêtes qui le relient  Un sous graphe stable est un sous graphe sans arête (les sommets sont dits isolés) Exemple : Le sous graphe ci-dessous est un sous graphe de complet G 1) Lemme des poignées de mains La somme des degrés des sommets d’un graphe non orienté est égale à deux fois le nombre d’arêtes du graphe Application : Pour le graphe G : On a : Deg (A) + Deg (B) + Deg(C) + Deg (D) + Deg (E) = 3 + 3 + 4 + 4 + 2 = 28 = 16 Remarque : Deg veut dire degré ; une notation non adaptée dans le chapitre  Une chaîne est une liste ordonnée de sommets telle que chaque sommet de la liste est adjacent au suivant. Exemple ABCD est une chaîne  La longueur d’une chaîne est le nombre d’arêtes qui la composent Exemple ABCD est de longueur égale à 3  Une chaîne est fermée lorsque l’origine et l’extrémité sont confondues Exemple ABCDA est une chaîne fermée  Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes Exemple ABCDBA est une chaîne mais n'est pas un cycle Les graphes  4ème : I Sciences de l'Informatiques Mr: HIDOURI Mosbah 2  La distance entre deux sommets est la plus courte longueur des chaînes qui le relient. Exemple la distance entre A et C est la longueur de la chaîne ABC qui est 2  Le diamètre d’un graphe est la plus grande distance entre deux sommets du graphe Exemple le diamètre de G est la distance entre A et B ou entre E et D qui est 4  Un graphe est connexe s’il existe toujours une chaîne entre deux sommets distincts. Exemple le graphe G est connexe  Une chaîne eulérienne est une chaîne qui contient une fois et une seule chaque arête du graphe Exemple : EBCDBADEA est une chaîne eulérienne de G  Un cycle eulérien est une chaîne eulérien fermée 2) Théorème (1) de l’Euler (admis) Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de sommets de degrés impairs vaut 0 ou 2. 3) Théorème (2) de l’Euler (admis) Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degrés pairs Remarque : Si un graphe connexe admet deux sommets de degrés impairs, alors ils sont nécessairement les extrémités de la chaîne eulérienne. Exemple : 1. Le graphe G ne contient pas de cycle Eulérien 2. Le graphe suivant admet un cycle Eulérien : ACEBDA (En effet il est connexe et tous les sommets sont de degrés paire) Exercice n°1 Peut – on dessiner les graphes ci-contre, sans lever le crayon et en ne passant qu’une seule fois sur chaque arête ? Exercice n°2 Dire, en justifiant, si chacun des graphes suivants admet une chaîne eulérienne ou un cycle eulérien et donner, dans l’affirmative, un exemple de telle chaîne ou de tel cycle 4) Matrice associe à un graphe non orienté a) Définition La matrice associée à un graphe non orienté à n sommets S1, S2, …….Sn est une matrice carrée  1 , ij i j n M a    où le terme ij a est égale à 1 si i S est adjacent à j S et 0 si non¨ Les graphes  4ème : I Sciences de l'Informatiques Mr: HIDOURI Mosbah 3 Exemple : la matrice associée à G est de la forme : On la note par : 0 1 0 1 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 0 M                  b) Commentaire : 12 1 a  car A est adjacent à B (Il y a une arrête entre A et B) c) Remarque : La matrice associée à un graphe non orienté est symétrique par rapport à la 1ère diagonale La somme de tous les termes de la matrice associée à un graphe non orienté est égale à la somme des degrés du graphe correspondant. (On a :1 16 16   et 16 correspond à la somme des degrés du graphe G) d) Propriété Soit M la matrice associée à un graphe non orienté dont, les sommets sont numérotés de 1 à n. Pour tout p  le terme ij a de la matrice p M donne le nombre de chaînes de longueur p reliant i à j. Exemple: Si on calcule p M on aura: 1) Pour p = 2 2) Pour p = 3 e) Commentaires: Si p = 2 alors G admet 3 chaînes de longueur 2 reliant D à B Si p = 3 alors G admet 9 chaînes de longueur 3 reliant D à B Exercice 1) Donner la matrice associée à chacun des graphes suivants : 2) Représenter un graphe dont la matrice associée est : a) 0 1 1 1 0 0 1 0 0           b) 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0               5) Coloriage D’un Graphe a) Définition Colorier un graphe consiste à attribuer une couleur à chaque sommet de façon à ce que deux sommets adjacents ne soit pas coloriés de la même couleur. Un même graphe G peut être colorié de plusieurs façons différentes. On appelle nombre chromatique d’un graphe G, le plus petit nombre de couleurs nécessaires à la coloration de G. On note (G) Les graphes  4ème : I Sciences de l'Informatiques Mr: HIDOURI Mosbah 4 b) Propriété Le nombre chromatique d’un graphe G est inférieur ou égal à  +1 où  (On note aussi r au lieu de ) est le plus grand degré des sommets Le nombre chromatique d’un graphe G est supérieur ou égal à celui de chacun de ses sous graphes Le nombre chromatique d’un graphe complet d’ordre n est n. Exercice 1 : organisation d'un examen On veut organiser un examen comportant, outre les matières communes, 6 matières d’options : Français (F), Anglais (A), Mécanique (M), Dessin industriel (D), Internet (I), Sport (S) ; les profils des candidats à options multiples sont : F, A, M D, S I, S I, M 1) Quel est le nombre maximum d’épreuves qu’on peut mettre en parallèle ? 2) Une épreuve occupe une demi-journée ; quel est le temps minimal nécessaire pour ces options ? Solution Le graphe associé à cette situation est le suivant : 1) Tout sous-graphe de plus de trois sommets comporte des arêtes ; deux sous-graphes d’ordre trois (de sommets respectivement A, D, I et F, D, I) n’ont pas d’arêtes : le nombre maximum d’épreuves en parallèle est 3. 2) Il y a un sous-graphe complet d’ordre 3 ; le nombre chromatique est au moins égal à 3 ; on voit que 3 couleurs suffisent. (Ci : couleur numéro i) Exercice 2 : ouvertures de magasins Une chaîne de cinq magasins décide d'ouvrir ses magasins en nocturne avec les contraintes suivantes : les deux premiers magasins ne peuvent pas être ouverts ensemble ; il en est de même pour les deux derniers ; au plus un seul magasin peut être ouvert parmi les magasins 1, 3, 4. Trouver un état qui maximise le nombre de magasins ouverts en nocturne, tout en respectant les contraintes. Solution Il n’y a qu’un seul sous-graphe a trois éléments sans arêtes ; tous les sous-graphes d’ordre 4 ou 5 ont des arêtes. Les graphes  4ème : I Sciences de l'Informatiques Mr: uploads/Science et Technologie/ cours-math-theorie-des-graphes-bac-economie-amp-gestion-2010-2011-mr-hidouri-mosbah.pdf