Homepage
Previous JFRO
Organizing committee
Contact
5th Ile-de-France Operation Research Day
La théorie des graphes et ses applications
Date
This day took place
Wednesday, the 09 October 2002
Place
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

Program of the day


09h30-09h45
Accueil des participants

09h45-10h15
Hommage à Claude Berge
M Balinski (Laboratoire d'Econométrie - Ecole Polytechnique)

10h15-12h00
ON EN VERRA DE TOUTES LES COULEURS... ET AVEC DES ARGUMENTS DE POIDS !
Dominique De Werra (Ecole Polytechnique Fédérale de Lausanne)
Abstract : 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.

12h00-13h45
Déjeuner

13h45-14h30
POLYNÔMES CHROMATIQUES DES GRAPHES
Olivier Hudry (ENST Paris)
Abstract : 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)
Abstract : 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)
Abstract : 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)
Abstract : 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

Choose language : Français English