Graphes et Algorithmes
|
| Archives année 2003-2004 |
11 Mars 2004: J.-M. Boé et F. Philippe, Partitions planes et partitions colorées
MacMahon a
trouvé en 1900 et qques la série
génératrices des partitions planes, et Knuth en a
trouvé une preuve bijective vers 1960. Sa preuve est
basée sur la transformation de Robinson-Schensted, bien connue
des amateurs de permutations et de tableaux d'Young.
Nous avons obtenu une nouvelle preuve bijective, basée sur les
notions de silhouette d'un ordre et de diagramme de croissance. Nous ne
présenterons pas cette preuve en détails, mais
plutôt introduirons les éléments utiles et
décrirons notre transformation dans le cas simple des
permutations. On verra aussi les liens cachés mais finalement
étroits entre notre transformation et celle de Knuth. On
n'essayera pas d'aller trop vite, quitte à utiliser une autre
séance si affinités.
Jean-Marie a prévu une projection multimedia, mais
également des activités manuelles.
La courbe de Peano est une courbe infinie qui remplit l'espace. Elle est la limite à l'infini, d'une suite de courbes finies. Nous présentons une nouvelle famille de mots, les mots de Peano, qui décrivent la suite de courbes dont la courbe de Peano est la limite. Nous calculons le nombre d'occurrences de certains motifs dans ces mots et nous donnons un tag-système qui les engendre. Par contre, en montrant qu'ils sont sans cube (sauf ceux d'une lettre), nous prouvons qu'ils ne peuvent pas être engendrés par morphisme.
Avec M. Habib et M. Raffinot.
Une composante connexe commune à plusieurs graphes est un ensemble de sommets S, maximal pour l'inclusion, tel que pour chaque graphe, le sous-graphe induit par S soit connexe. Les composantes connexes communes forment une partition des sommets. En utilisant, un algorithme d'affinage de partition, nous obtenons une complexité en O(n+m.log n) dans le cas des graphes d'intervalles.
6 Novembre 2003: D. Corneil, Roots of graphD'après des articles de M. Thorup.
Nous considérons un graphe G sur une ensemble de n sommets fixés, dans le quel on ajoute et enlève des arêtes.A tout instant, on veut pouvoir répondre à la question : 2 sommets x et y appartiennent-ils à une même composante connexe de G ?
Nous présenterons une méthode de Thorup qui maintient une forêt couvrante maximale de G avec un coût amorti en O(log2n) par insertion/suppression d'arête et qui répond à la requête en O(log n).
with Lap Chi Lau (Computer Science, University of Toronto)
The Y-square root problem (given a graph G, does there exist a graph H in Y such that G is the square of H?) is known to be NP-complete if Y is unrestricted but can be solved in linear time if H must be a tree. Until recently, these were the only complexity results known for the square root problem. In this talk, we show that the square root problem is also in P for bipartite graphs and for unit interval graphs. Various new NP-complete results will also be presented, for example: chordal roots, split roots and roots of chordal graphs.
The square root problem can be generalized to k-roots for k >2. It is known that the k-root problem for trees is in P but surprisingly, the complexity of the cube root problem is not known (but certainly expected to be NP-complete). We show that the bipartite cube root problem is NP-complete whereas the unit interval graph k-root problem is in P for any fixed k.