Date : 1999
Editeur / Publisher : [S.l.] : [s.n.] , 1999
Format : 145 p.
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Résumé / Abstract : EN MATIERE DE GRAPHES, LA MISE EN UVRE DU PRECEPTE DIVISER POUR MIEUX REGNER PREND SOUVENT LA FORME D'UNE DECOMPOSITION FONDEE SUR UNE PARTITION DE L'ENSEMBLE DES SOMMETS. NOUS PRESENTONS UNE METHODE DE CE GENRE, LA DECOMPOSITION MODULAIRE DEJA INTENSIVEMENT ETUDIEE ET MONTRONS SON UTILITE DANS LE CADRE DE L'ETUDE DE CLASSES PARTICULIERES DE GRAPHES INCLUANT LES COGRAPHES. LA RECHERCHE D'ANALOGIES AVEC LES COGRAPHES OU LES SPLIT GRAPHES DANS LE CAS DES GRAPHES BIPARTIS NOUS CONDUIT A DEFINIR LES BICOGRAPHES AINSI QUE LES GRAPHES BISPLIT ETENDUS ET DEBOUCHE SUR UNE METHODE DE DECOMPOSITION GENERALE DES GRAPHES BIPARTIS : LA DECOMPOSITION CANONIQUE. LES GRAPHES BISPLIT ETENDUS QUE NOUS CARACTERISONS PAR DES CONFIGURATIONS EXCLUES SONT TOTALEMENT DECOMPOSABLES PAR DECOMPOSITION CANONIQUE. NOUS PROPOSONS UN ALGORITHME OPTIMAL DE RECONNAISSANCE DE CES GRAPHES. ENFIN PRESENTONS POUR DIFFERENTES FAMILLES DES SOLUTIONS EFFICACES POUR UN NOMBRE IMPORTANT DE PROBLEMES D'OPTIMISATION.