|
 
|
[TT11] Etude d'une nouvelle classe de graphes: les hypotriangulés.
Mémoire de Thèse : Soutenue le: 26 May 2011, pp. 150, pp.: Directeur:M.-C. Costa et C. PicouleauRapporteur 1: D. de Werra
Rapporteur 2: C. Bazgan
Membre du jury: N. Trottignon
Membre du jury: C. Bentz
Membre du jury:, : Etude d'une nouvelle classe de graphes: les hypotriangulés.,
motcle:
Résumé:
Dans cette thèse, nous définissons une nouvelle lasse de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre hemin de longueur deux entre ses extrémités. Cette lasse permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à es partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixé. Dans une deuxième partie, nous étudions la complexité, pour la lasse des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modifation de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou à supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes, pour plusieurs lasses de graphes.
Equipe:
oc
BibTeX
| @phdthesis { | |||
| TT11, | |||
| title | = | "{Etude d'une nouvelle classe de graphes: les hypotriangulés.}", | |
| author | = | "H. Topart", | |
| year | = | 2011, | |
| pages | = | "150", | |
| address | = | "{CEDRIC Laboratory, Paris, France}", | |
| note | = | "{ Directeur:M.-C. Costa et C. Picouleau Rapporteur 1: D. de Werra Rapporteur 2: C. Bazgan Membre du jury: N. Trottignon Membre du jury: C. Bentz Membre du jury:}", | |
| } |
