Date : 1993
Editeur / Publisher : [S.l.] : [s.n.] , 1993
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Résumé / Abstract : DEUX OBJETS MATHEMATIQUES SONT AU CENTRE DE CE TRAVAIL ; LES POLYOMINOS ET LES GRAPHES PARFAITS. APRES AVOIR FAIT L'ETAT DES CONNAISSANCES DANS CES DEUX DOMAINES, NOUS PRESENTONS NOS RESULTATS. NOUS PROPOSONS UNE DEMONSTRATION ORIGINALE DE LA CONJECTURE DES GARDIENS DE MUSEE. UNE FOIS CE PROBLEME RESOLU NOUS NOUS INTERESSONS A D'AUTRES GRAPHES DEFINIS A PARTIR DE RELATIONS DIVERSES DANS LES POLYOMINOS. NOUS AVONS ETUDIE LA PERFECTION (AU SENS DE CLAUDE BERGE) DES GRAPHES ASSOCIES AUX RELATIONS DE VISIBILITE QUE NOUS AVONS ENVISAGEES. ENSUITE NOUS DONNONS UNE CARACTERISATION DES GRAPHES D'INTERSECTION DES RECTANGLES MAXIMAUX D'UN POLYOMINO. CETTE ETUDE NOUS A INCITE A INTRODUIRE UNE NOUVELLE CLASSE DE GRAPHES QUE NOUS AVONS BAPTISE LEGEREMENT TRIANGULES, CAR ILS GENERALISENT LES GRAPHES TRIANGULES. NOUS RESOLVONS LES PROBLEMES CLASSIQUES D'OPTIMISATION POUR CES GRAPHES. FINALEMENT, NOUS EXPOSONS DES NOUVELLES PROPRIETES DES GRAPHES PARTITIONABLES, UNE GENERALISATION DE LA NOTION DE SPLIT, ET DES RESULTATS SUR LES NOTIONS D'ARETES CRITIQUES DANS LES GRAPHES