Remerciez-le!

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

République Tunisienne Ministère de l’Enseignement Supérieur et de la Recherche

République Tunisienne Ministère de l’Enseignement Supérieur et de la Recherche Scientiﬁque Université de La Manouba Institut Supérieur des Arts Multimédia de la Manouba rapport de synthése sur Graphe trinagulé Réaliser par : Mzoughhi Yosra Mastère de Recherche « IMD » Année Universitaire 2020 - 2021 Table des matières 1 Graphe triangulé 1 1.1 Déﬁnition d’un graphe triangulé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Propriétés des graphes triangulés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Deﬁnition d’une coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Algorithme de coloration des graphes triangulés 5 2.1 Principe d’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Etude de la complexité de l’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 Bibliographie 7 ii Chapitre 1 Graphe triangulé Chapitre 1. Graphe triangulé Ce n’est pas facile de savoir à quelle époque remonte la déﬁnition des graphes triangulés, ils apparaissent en 1958 dans les travaux de Hajós. Les graphes triangulés sont apparus sous diﬀérents noms au début des années 60. On trouve généralement l’appellation « chordal graphs » dans la littérature anglo-saxonne 1.1 Déﬁnition d’un graphe triangulé ‘ Un graphe est dit triangulé s’il ne contient aucun cycle induit de longueur supérieure ou égale à quatre (les graphes triangulés apparaissent sous le nom de chordal graphe dans la littérature anglophone). Un graphe G est dit faiblement triangulé si ni G, ni G’, ne contiennent de cycles induits de longueur au moins 5. M. Burlet [MBU81] montre que ces graphes sont parfaits et donne un algorithme polynomial pour les reconnaître. Les problèmes d’optimisation dans cette classe sont résolus par F. Maire [FMA93] ainsi que par M. Burlet and J.-P. Uhry [MBU84]. Les graphes triangulés correspondent exactement aux graphes d’intersection des sous arbres dans un arbre, ce qui leur confère certaines applications dans le domaine de la classiﬁcation. Ils sont reconnaissables en temps et espace linéaire et les problèmes de la clique maximum, de la coloration minimum, du stable maximum et de la partition minimum en cliques peuvent être résolus en temps et espace linéaire lorsque l’on se restreint à ceux-ci. Une sous-classe intéressante des graphes triangulés est la classe des graphes scindés. Un graphe scindé est un graphe dont les sommets admettent une partition en deux sous-ensembles S et C où S un est stable et C une clique ; par analogie aux graphes bipartis, nous noterons G = (S, C, E) le graphe en question. Clairement, le complément d’un graphe scindé est aussi un graphe scindé ; en fait, il s’avère qu’un graphe G est scindé si et seulement si G et G’ sont triangulés. 2 Chapitre 1. Graphe triangulé 1.2 Propriétés des graphes triangulés Ce type de graphe a plusieurs propriétés dont on peut citer a.La notion de sommet complété. Un sommet d’un graphe est dit complété (en anglais « simplicial ») si son voisinage N(x) est une clique. Tout graphe triangulé admet un sommet complété. De plus, si le graphe n’est pas complet, il admet deux sommets complétés non voisins. (Contient au moins deux sommets complétés non adjacents). b. La notion de schéma d’élimination parfait théorème : Un graphe est triangulé si et seulement s’il possède un schéma d’élimination parfait. Par la suite, on donne la déﬁnition d’une coloration et le nombre de Grundy. On appelle une coloration du graphe, l’aﬀectation à chaque sommet du graphe une couleur en faisant bien attention à ce que deux sommets adjacents, c’està-dire joints par un arc, ne possèdent pas la même couleur. En eﬀet, il ya plusieurs travaux de coloration de graphes, par exemple on trouve la coloration des sommets ; la coloration des arrêtes [BEH03][FGA72]. 1.3 Deﬁnition d’une coloration La coloration d’un graphe nécessite l’utilisation de plusieurs paramètres de coloration. Dans la littérature, on trouve plusieurs paramètres fondamentaux comme le nombre chromatique ; le Grundy partiel ; le Grundy total. Le nombre chromatique est un paramètre de coloration de graphe, qui utilise le minimum de couleurs. La détermination du nombre chromatique d’un graphe est dans le cas général un problème NPdiﬃciles a.. Propriétés de nombre de Grundy 3 Chapitre 1. Graphe triangulé Preuve. D’après la construction d’une coloration de Grundy, chaque sommet x G de couleur i doit être adjacent aux couleurs 1, 2, . . . , i-1. Les auteurs ont donné un algorithme linéaire pour déterminer le nombre de Grundy d’un arbre et ont montré une relation d’ordre entre le nombr de Grundy, le nombre chromatique et le nombre achromatique pour tout graphe G b.théorème Soit G = (V, E) un graphe et V’ V. s’il existe une k-coloration de Grundy pour le sous graphe induit donné par V’, alors : Dans le théorème suivant ils ont travaillé sur les graphes ayant un ensemble stable de sommets. 4 Chapitre 2 Algorithme de coloration des graphes triangulés Chapitre 2. Algorithme de coloration des graphes triangulés Notre algorithme permet de coloration des graphes triangulés, qui utilise un paramètre à savoir le « Grundy », permet d’assurer la stabilité du graphe a n’importe quel changement 2.1 Principe d’algorithme l’ algorithme se compose de trois grandes étapes : 1. La détermination de schéma d’élimination parfait 2. La coloration du graphe en fonction de schéma d’élimination parfait Colorer le premier sommet du schéma d’élimination parfait par le minimum de couleur Pour le deuxième sommet, donner une couleur minimale qui n’est pas encore utilisée par ses voisins. 3. Tant qu’il y a des sommets a colorés, répéter l’étape 2. 2.2 Etude de la complexité de l’algorithme La complexité d’algorithme est la somme de complexité de deux algorithmes : algorithme de schéma d’élimination parfait et algorithme de coloration du graphe (puisque l’algorithme de coloration est basé sur l’algorithme de schéma d’élimination parfait) La complexité de l’algorithme de schéma d’élimination est n. 2. En eﬀet, pour un sommet A d’un graphe (G), on cherche son voisinage () et le voisinage de son voisinage (). Donc, on répète le test pour les n sommet du graphe. Donc, la complexité est n. Pour l’algorithme de coloration simple la complexité est n. . En eﬀet, la coloration consiste à attribuer une couleur minimum au sommet spéciﬁé, après la vériﬁcation de tous les sommets de son voisinage (). A chaque fois on vériﬁe le voisinage de sommet à colorer (n). Donc, la complexité totale de l’algorithme est de n.2 . 6 Chapitre 3 Bibliographie Chapitre 3. Bibliographie http ://www.setit.rnu.tn/lastedition/setit2009/Telecom 8 uploads/Litterature/ graphe-triangul 1 .pdf