Algorithmique et programmation Travaux dirigés, 23 et 24 janvier 2003 Graphes, flots et algèbre linéaire.

1 Multiplication de matrices et plus court chemin

On rappelle que l’algorithme de Strassen permet la multiplication de matrices carrées de dimension n en O(n^{log_{2} 7}) opérations élémentaires, si les éléments sont dans un anneau. On rappelle aussi que la recherche des chemins les plus courts d’un graphe peut se faire avec l’exponentiation de la matrice d’adjacence dans le semi-anneau (min, +).

1. Peut-on appliquer l’algorithme de Strassen ?

2. Si a et b sont entiers strictement positifs, montrez qu’on peut calculer min(a, b) à partir de log(x^{a} + x^{b})/ log x pour un petit x.

3. En déduire comment passer du semi-anneau (ℕ_{0} ∪{∞}, min, +) à l’anneau (ℝ, +, ×).

4. Proposer une multiplication de matrices dans le semi-anneau (min, +) qui utilise l’algorithme de Strassen.

5. Évaluer sa complexité en terme d’opérations arithmétiques, puis d’opérations sur les bits.

2 Couplages et mariages

1. Graphes bipartites

Un graphe non-orienté est dit bipartite si V se découpe en deux parties telles que toute arête relie un sommet dans chaque partie. On appelle couplage une partie M ⊂ E telle que chaque sommet du graphe appartient à au plus une arête de M. Un couplage est dit maximal si son cardinal l’est. Un couplage est parfait si tous les sommets en font partie. Pour toute partie X ⊂ V, on note V (X) l’ensemble des sommets adjacents à au moins un sommet de X.

(a) Proposer un algorithme pour décider si un graphe est bipartite.

(b) Proposer un algorithme pour trouver un couplage maximal.

(c) Montrer le théorème de Hall : un graphe admet un couplage parfait si, et seulement si ∀X ⊂ V, |X| ⩽ |V (X)|.

2. Mariages stables

(a) On se place dans le cas d’un graphe bipartite complet, où à chaque arête est associée un poids. Trouver un algorithme qui calcule un couplage parfait maximisant la somme des poids des arêtes du couplage.

(b) Une variante du problème des mariages stables s’exprime en assignant à chaque sommet de V_{1} un ordre de préférence parmi les sommets de V_{2} et réciproquement. Proposer un algorithme qui trouve un couplage stable (i.e. aucun échange n’augmente la satisfaction).

3 Petit exercice de programmation

Énumération des permutations Écrire un programme qui affiche les permutations de n éléments dans l’ordre lexicographique, en un temps O(n.n!) et utilisant un tableau de taille n plus quelques variables entières.