Remerciez-le!

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

Graphe triangul 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 Yosr

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 - CTable des matières Graphe triangulé Dé ?nition d ? un graphe triangulé Propriétés des graphes triangulés De ?nition d ? une coloration Algorithme de coloration des graphes triangulés Principe d ? algorithme Etude de la complexité de l ? algorithme Bibliographie ii CChapitre Graphe triangulé CChapitre Graphe triangulé Ce n ? est pas facile de savoir à quelle époque remonte la dé ?nition des graphes triangulés ils apparaissent en dans les travaux de Hajós Les graphes triangulés sont apparus sous di ?érents noms au début des années On trouve généralement l ? appellation chordal graphs ? dans la littérature anglo-saxonne 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 M Burlet MBU 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 FMA ainsi que par M Burlet and J -P Uhry MBU 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 CChapitre Graphe triangulé 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