Journées Franciliennes de Recherche Opérationnelle
ROADEF




Retour

Programme (JFRO)

La théorie des graphes et ses applications

Carré des Sciences

Amphithéatre à préciser
Ministère de l'Education Nationale, de la Recherche et de la Technologie
1, rue Descartes - 75005 Paris

9h30-9h45

Accueil des participants

9h45-10h15

 

Hommage à Claude Berge

par M. Balinski - Laboratoire d'Econométrie - Ecole Polytechnique

10h15-12h

Tutorial : ON EN VERRA DE TOUTES LES COULEURS... ET AVEC DES ARGUMENTS DE POIDS !

Dominique DE WERRA - Ecole Polytechnique Fédérale de Lausanne

Transparents au format PDF

 

Quelques variations très chromatiques seront illustrées avec des motivations esthétiques et même pratiques ; cherchant à atteindre des sommets et suivant d'innombrables arêtes, il sera procédé à quelques extensions d'ordre musculaire où il s'agira de manier des poids, ce qui soulèvera des montagnes de problèmes nouveaux. Mais on n'oubliera pas pour autant le cas usuel où l'on a tous les poids des haltères égaux.

 12h - 13h30

DEJEUNER

13h45-14h30

POLYNÔMES CHROMATIQUES DES GRAPHES

Olivier HUDRY - ENST Paris

Transparents au format PDF

 

Les polynômes chromatiques des graphes ont été introduits en 1912 par G.D. Birkhoff pour étudier le problème des quatre couleurs. Etant donné un graphe G, le polynôme chromatique P(G, x) associé à G est tel que, pour tout entier x, P(G, x) indique le nombre de colorations différentes de G à l'aide de x couleurs. Plus précisément, les polynômes chromatiques sont définis récursivement à partir de la supression ou de la contraction d'une arête par : P(G, x) = P(G - a, x) - P(G/a, x), où a est une arête quelconque de G, où G - a désigne le graphe obtenu en supprimant a de G, et où G/a désigne le graphe obtenu en contractant a dans G. On s'intéresse ici à la valeur des racines des polynômes chromatiques des graphes quelconques ou au contraire de graphes particuliers comme les graphes planaires, les graphes hamiltoniens ou les graphes de degré majoré...

14h30-15h15


COLORIAGE ET DOMINOS : APPLICATIONS A LA CONSTRUCTION DE PLANNING

Christophe PICOULEAU - CEDRIC - CNAM Paris

 

L'objet de la tomographie discrete est la reconstruction d'un objet discret a partir de ses projections. Nous allons presenter
quelques problemes de base de cette discipline comme la reconstruction d'un tableau colore ou la reconstruction du pavage d'un rectangle par des dominos. Nous formulerons aussi ces problemes en termes de graphes, d'ordonnancements et presenterons quelques applications concernant la construction de planning de personnel.

 15h15 - 15h45

PAUSE

15h45-16h30

PROBLÈME D'AFFECTATION DE FREQUENCES

Thierry DEFAIX - CELAR - DGA

 

On assiste des dernières années à une densification du besoin : augmentation de la demande (de plus en plus d'utilisateurs et de nouveaux services) dans une ressource spectrale qui reste physiquement inextensible. Ce constat conduit à chercher à optimiser toujours plus la gestion des fréquences. Depuis le projet CALMA (Combinatorial Algorithms for military applications), la modélisation des contraintes a évolué et continue d'évoluer pour approcher au mieux la réalité physique. L'objectif de cette présentation consiste à illustrer certaines de ces évolutions sur le cas assez générique de l'allocation des fréquences pour les faisceaux hertziens.

 16h30-17h15

 LES GRAPHES PARFAITS

Jean FONLUPT - Equipe Combinatoire - CNRS UMR 7090 - Université Paris 6

En 1961 Claude Berge a introduit la notion de graphes parfaits et a énoncé une célèbre conjecture connue sous le nom de "Conjecture Forte des Graphes Parfaits". Cette conjecture vient juste d'être démontrée par Paul Seymour, Robin Thomas et deux autres chercheurs. L'importance des graphes parfaits réside dans le fait que leur étude s'inscrit dans de nombreux domaines tels que les
structures combinatoires générales, l'optimisation discrète, les polyèdres entiers, la programmation linéaire, la complexité des algorithmes, l'algorithmique combinatoire. Nous présentons dans cet exposé ces diverses approches en mettant l'accent sur les opérations de décomposition des graphes parfaits qui ont permis d'établir la preuve récente de la validité de la Conjecture Forte des Graphes Parfaits.