Scribd
Importer
324 vues10 pages

Graphe Triangul

Transféré par

Yosra Mzoughi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
324 vues10 pages

Graphe Triangul

Transféré par

Yosra Mzoughi
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
Vous êtes sur la page 1/ 10

République Tunisienne

Ministère de l’Enseignement Supérieur


et de la Recherche Scientifique

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éfinition d’un graphe triangulé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Propriétés des graphes triangulés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Definition 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éfinition des graphes triangulés,
ils apparaissent en 1958 dans les travaux de Hajós. Les graphes triangulés sont apparus
sous diffé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éfinition 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
classification. 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éfinition d’une coloration et le nombre de Grundy. On
appelle une coloration du graphe, l’affectation à 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 effet, 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 Definition 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 NPdifficiles

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 effet, 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 effet, la coloration


consiste à attribuer une couleur minimum au sommet spécifié, après la vérification de
tous les sommets de son voisinage (). A chaque fois on vérifie 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/laste dition/setit2009/T elecom

Vous aimerez peut-être aussi