DES POLYOMINOS AUX GRAPHES PARFAITS ; CONTRIBUTION A L'ETUDE DES PROPRIETES COMBINATOIRES DE CES STRUCTURES / FREDERIC MAIRE ; SOUS LA DIRECTION DE CLAUDE BERGE

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 1993

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Berge, Claude (1926-2002 ; mathématicien) (Directeur de thèse / thesis advisor)

Université Pierre et Marie Curie (Paris ; 1971-2017) (Organisme de soutenance / degree-grantor)

Relation : DES POLYOMINOS AUX GRAPHES PARFAITS ; CONTRIBUTION A L'ETUDE DES PROPRIETES COMBINATOIRES DE CES STRUCTURES / Frederic Maire ; sous la direction de Claude Berge / Grenoble : Atelier national de reproduction des thèses , 1993

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