Règles de Doppelblock

Règles

Les règles du doppelblock sont les suivantes : noircir exactement deux cases dans chaque ligne et chaque colonne. Dans les cases restantes, il faut placer un entier entre 1 et X-2, où X est le nombre de cases dans chaque ligne, de telle sorte que chaque nombre apparaisse une et une seule fois dans chaque ligne et chaque colonne. Les nombres à l’extérieur de la grille indiquent la somme des entiers entre les deux cases noircies dans la ligne ou colonne correspondante. Le contenu de certaines cases peut déjà être donné.

Exemple

Voici un exemple de grille de doppelblock et sa solution.

Résoudre l’exemple en ligne.

Histoire du doppelblock

D’après le WPC unofficial wiki, le doppelblock apparaît dans les qualifications pour la compétition de puzzle Japonaise de 2006 par un auteur inconnu. Il a ensuite été inventé indépendamment en 2008 par Naoki Inaba (Japon)

Sudoku #4

Ultimate Sudoku

Résoudre en ligne ici !

Les règles du Sudoku habituelles s’appliquent. De plus :

  • Les règles du even/odd Sudoku s’appliquent : les cases avec des carrés contiennent un nombre pair, et les cases avec des ronds un nombre impair.
  • Les règles du arrow Sudoku s’appliquent : La somme des chiffres sur le chemin de la flèche est égale au chiffre au début de la flèche (dans ce cas, soit un rond soit un carré)
  • Les règles du sudoku consécutif s’appliquent : deux cases orthogonalement adjacentes séparées par une barre possède des chiffres consécutifs. Toutes les barres sont indiquées, autrement dit, s’il n’y a pas de barres entre deux cases, leur contenu n’est pas consécutif.

Le fait que certaines barres soient blanches ou noires n’a aucun impact, cela est purement décoratif.

Mot croisé cryptique #3

Horizontal

1 : Début de formidables tentes resserrées pour un retranchement $(10)$

2 : Large univers naissant parcouru $(2)$ — Fer au masculin décomposé $(5)$

3 : La clé du cœur d’autrui $(2)$ — L’oiseau au sommet de l’amour de l’écho du public $(3)$ — Déesse achevant Onyx $(3)$

4 : Cuivre qu’ils promettent arrangé sans aversion $(9)$

5 : Léger en hauteur $(6)$ — Élaguer un bonsaï naturel pour la postérité $(3)$

6 : Nom déshydraté d’une courte distance $(2)$ — Réseau après l’agrafe du carnet $(3)$

7 : Suça un brassage d’état $(4)$ — Ventre d’un favori européen moqueur $(5)$

8 : Connecta et élira en confusion $(5)$

9 : Milieu de juillet déterminant $(2)$ — Pourrir le noyau d’une Bretagne renversée $(5)$

10 : Journaux très brefs que je devine $(8)$

Vertical

A : Sifflant un court liquide, un roi affamé décapité $(7)$ — Adresse de fin d’épitaphe anglaise $(2)$

B : La queue à numéroter en tumulte bleue $(8)$

C : Conjonction de métal $(2)$ — Démantèlement en profondeur du poste $(4)$

D : Nous ralentîmes la désorganisation des étudiants $(10)$

E : Saga d’une musique au centre des œufs $(6)$

F : Note, dans un siècle, en colère, la réorientation $(10)$

G : Le revers espagnol $(2)$ — Période chez les francs $(2)$

H : Cloisons des sentinelles des gouvernements des émotions $(10)$

I : Pièce du crépuscule du doyen $(3)$

J : Plusieurs au fond des yeux $(3)$ — L’orateur des rives tumultueuses aux mains rosés $(6)$

Solution (à venir)

Les graphes cordaux

On s’intéresse à une famille de graphes dont les graphes d’intervalles font partis. Il s’agit des graphes cordaux. Tout comme les graphes d’intervalles, on présente un algorithme de coloration pour cette famille.

Exercice

Un graphe est dit cordal si pour tout cycle de taille supérieur ou égale à 4, il existe une corde. C’est à dire qu’il existe une arête entre deux sommets non consécutifs du cycle.

Soit un graphe $G = (S,A)$ connexe. Soit $u$ et $v$ deux sommets de $G$. On appelle séparateur minimale de $u,v$ tout sous-ensemble $V$ de $S$ tel que $u$ et $v$ ne soient pas accessibles dans le graphe induit par les sommets $S \smallsetminus V$ et tel qu’il n’existe pas de sous-ensemble strictement inclus dans $V$ qui vérifie la même propriété.

$1.$ Montrer que les sous-graphes induits d’un graphe cordal sont également des graphes cordaux.

$2.$ Montrer que si tous les séparateurs minimaux de $G$ sont des cliques alors $G$ est cordal.

$3.$ Prouver la réciproque.

Un sommet est dit simpliciale si l’ensemble de ses voisins forment une clique.

$4.$ Montrer par récurrence que tout graphe cordal à plus de deux sommets contient au moins deux sommets simpliciaux. De plus, si le graphe n’est pas complet, il possède deux sommets simpliciaux non adjacents.

On appelle ordre d’élimination parfait de $G$, un ordre sur les sommets $s_1 \lt s_2 \lt \ldots \lt s_n$ de $G$ tels que $s_i$ soit simplicial dans le sous-graphe induit de $G$ par les sommets $s_1, \ldots, s_i$.

$5.$ Montrer qu’un graphe est cordal si et seulement si il admet un ordre d’élimination parfait.

$6.$ En déduire un algorithme de coloration des graphes cordaux et prouver son optimalité.

$7.$ Conclure que les graphes cordaux sont des graphes parfaits.

Correction

$1.$ On note que tout cycle de longueur supérieur ou égale à $4$ dans un sous-graphe induit d’un graphe $G$ est également présent dans $G$. De ce fait, il admet une corde dans $G$ et donc par définition d’un sous-graphe induit, admet une corde dans le sous-graphe induit. Ainsi, tous sous-graphe induit d’un graphe cordal est un graphe cordal.

$2.$ Soit $G$ un graphe dont tous les séparateurs minimaux sont des cliques. S’ils ne possède pas de cycle de longueur supérieur ou égale à $4$, alors il est cordal. Sinon, soit $k\geq4$ et $s_1, s_2, \ldots, s_k$ un cycle de $G$. On s’intéresse à un séparateur minimal de $s_1$ et $s_3$ noté $W$. Comme $(s_1, s_2)$ et $(s_2,s_3)$ sont des arêtes de $G$ on a $s_2 \in W$. De plus, on a $i$ avec $4 \leq i \leq k$ tel que $s_i \in W$ par définition de cycle. Or par hypothèse, $W$ est une clique. Donc, $(s_2,s_i)$ est une arête de $G$.

Ainsi, tout cycle de $G$ de taille supérieur ou égale à $4$ admet une corde. Donc $G$ est cordal.

$3.$ Si $G$ est cordal. On suppose qu’il existe $W$ un séparateur minimal de $G$ qui ne soit pas une clique et qui sépare les sommets $x$ et $y$. Soit $S_1$ et $S_2$ deux composantes connexes du sous-graphes induits par $S \smallsetminus W$. On suppose que $x \in S_1$ et $y \in S_2$. Soit deux sommets $s_1$ et $s_2$ de $W$ qui ne sont pas adjacent.

On rappel que $W$ est un séparateur minimal. De ce fait, $s_1$ et $s_2$ ont tous deux une arête vers $S_1$ et une vers $S_2$. En effet, si tel n’étais pas le cas, par exemple, si $s_1$ n’avait pas d’arêtes vers $S_1,$ alors $W \smallsetminus {s_1}$ serait un séparateur plus petit de $x,y$ ce qui contredit l’hypothèse de minimalité.

On a donc un plus court chemin de $s_1$ vers $s_2$ dans $S_1$ et un plus court chemin de $s_1$ vers $s_2$ dans $S_2$. On a donc un cycle de longueur au moins $4$. Or, ce cycle ne possède pas de cordes. En effet, il n’y a pas d’arêtes entres $S_1$ et $S_2$, $s_1$ et $s_2$ sont non adjacents et s’il existait une corde à l’intérieur de $S_1$ ou $S_2$ on aurait un chemin plus court. Cela contredit donc l’hypothèse de cordalité de $G$.

De ce fait, on a montré que si $G$ est un graphe cordal, alors ses séparateurs minimaux sont des cliques.

$4.$ On note que tous les sommets d’un graphe complet sont simpliciaux.

Soit $\mathcal{P}(n)$ la proposition : « Un graphe cordal non complet à $k$ sommets, où $2\leq k \leq n$, possède deux sommets simpliciaux non adjacents »

Dans le cas d’un graphe à deux sommets, s’il n’est pas une clique, alors le graphe n’a pas d’arêtes. De ce fait, les deux sommets n’ont pas de voisins et sont bien simpliciaux.

Soit $n \geq 2$. On suppose $\mathcal{P}(n)$ vrai et on cherche à prouver $\mathcal{P}(n+1)$.

Soit $G$ un graphe chordal non complet à plus de $2$ sommets. Si $G$ à moins de $n$ sommets, par $\mathcal{P}(n)$ il possède deux sommets simpliciaux non adjacents. Supposons maintenant que $G$ a $n+1$ sommets. Il nous faut juste prouver que $G$ possède deux sommets simpliciaux non adjacents. Soit $W$ un séparateur minimal de $G$ et $S_1$ et $S_2$ deux composantes connexes du sous-graphe induit par $S \smallsetminus W$. On s’intéresse maintenant au sous-graphe induit par $S_1 \cup W$. Si il est complet, alors on considère $x \in S_1$ qui est donc simplicial dans $G$. Sinon, par $\mathcal{P}(n)$, on a deux sommets simpliciaux non adjacents. Or, on rappelle que $W$ est une clique. De ce fait, il existe $x \in S_1$ simplicial dans le sous-graphe induit par $S_1 \cup W$, et donc par définition de $S_1$, simplicial dans $G$. On trouve de même $y \in S_2$ simplicial dans $G$.

On a donc bien trouvé deux sommets simplicial non adjacent, ce qui prouve $\mathcal{P}(n+1)$ et achève la récurrence.

$5.$ Montrons que si un graphe possède un ordre parfait d’élimination alors il est cordal. Soit $G$ un graphe qui possède un ordre parfait d’élimination. Si $G$ n’a pas de cycle de taille supérieur à $4$ alors il est cordal. Sinon, soit $k \geq 4$ et $s_1, \ldots, s_k, s_1$ un cycle de $G$. Sans pertes de généralités, on peut supposer que $s_1$ est le plus grand dans l’ordre d’élimination. Cela implique donc que $s_k$ et $s_2$ sont adjacents. De ce fait, $G$ possède un corde. Il en résulte que $G$ est cordal.

Prouvons maintenant la réciproque et supposons que $G$ est cordal. On sait que tout graphe cordal possède au moins un sommet simplical. De plus, le sous-graphe induit d’un graphe cordal est un graphe cordal. Il en résulte qu’on peut construire un ordre parfait d’élimination de façon décroissante en sélectionnant un sommet simplicial puis en le supprimant avant de recommencer.

Ainsi on a donc qu’un graphe est cordal si et seulement si il possède un ordre parfait d’élimination.

$6.$ On note qu’on a un algorithme qui nous permet de construire l’ordre parfait d’élimination d’un graphe cordal. On visite chaque sommet selon l’ordre d’élimination parfait et on lui assigne première couleur qui n’est pas utilisé pour colorier un de ses voisins déjà visité. Chaque sommet visité fait partie d’une clique de la taille de ses voisins déjà coloré plus un. De ce fait, la couleur attribuée est toujours plus petite ou égale à la taille de la plus grande clique du graphe.

Or la taille de la plus grande clique du graphe est une borne minimal au nombre chromatique. Ainsi, on ne peut utiliser moins de couleurs. Il en résulte que notre coloration est optimale.

$7.$ De la question précédente on en déduit que le nombre chromatique d’un graphe cordal est égale à la taille de sa plus grande clique. De plus, comme le sous-graphe induit d’un graphe cordal est également un graphe cordal, cela reste vrai pour tous ses sous-graphes induits. Il en résulte donc que les graphes cordales sont des graphes parfaits.

Exercices en liens

Les graphes d’intervalles

On sait que le problème de coloration des graphes est difficile. Cependant, il existe certaines familles de graphes pour lequel le problème de coloration est polynomial. C’est le cas pour les graphes d’intervalles que nous étudions ici.

Exercice

On considère un ensemble d’intervalle fermé $\left(I_k\right)_{k \leq n}$. On appelle graphe d’intervalles associé, noté $G=(A,S)$, le graphe de $n$ sommets où chaque sommets représente un intervalle, et deux sommets $u$ et $v$ sont connectés par une arête si et seulement si $I_u \cap I_v \neq \emptyset$.

$1.$ On considère une clique de $G$. Que peut-on dire de l’intersection des intervalles associés ?

$2.$ Donner un algorithme de coloration d’un graphe d’intervalle et prouver son optimalité.

On dit que $\mathcal{H}$ est un sous-graphe induit d’un graphe $\mathcal{G}$, si l’ensemble des sommets de $\mathcal{H}$ est un sous-ensemble de l’ensemble des sommets de $\mathcal{G}$ et que $x$ et $y$ sont liés par une arête dans $\mathcal{H}$ si et seulement si ils sont liés par une arête dans $\mathcal{G}$.

On dit qu’un graphe est un graphe parfait si le nombre chromatique de chacun de ses sous-graphes induit, est égale à la taille de la plus grande clique du sous-graphe.

$3.$ Prouver que les graphes d’intervalles sont des graphes parfaits.

Correction

$1.$ L’intersection des intervalles associés à une clique de $G$ est non vide. En effet, soit $J_1, \ldots, J_k$ une clique de $G$. Si $\displaystyle \bigcap\limits_{i\leq k} J_i = \emptyset$ alors on a $l \geq 2$ tel que $\mathcal{J} = \displaystyle \bigcap\limits_{i \lt l} J_i \neq \emptyset$ et $\displaystyle \mathcal{J} \cup J_l = \emptyset$. Autrement dit, soit l’intervalle $J_l$ termine avant que $\mathcal{J}$ commence, soit l’inverse. Par symétrie, supposons que $J_l$ se termine en premier et notons $f$ sa date de fin. Notons $d$ la date de début de $\mathcal{J}$. On a $i \lt l$ tel que $i$ commence après $d$. En effet, s’ils commençaient tous strictement avant, la date de début de $\mathcal{J}$ seraient antérieur à $d$ ce qui est absurde. De ce fait, $J_l \cup J_i = \emptyset$ ce qui contredit l’hypothèse qu’ils soient dans la même clique.

De ce fait, l’intersection des intervalles associés à une clique de $G$ est non vide. Réciproquement, si l’intersection d’un ensemble d’intervalles de $G$ est non vide, alors ils forment une clique.

$2.$ On propose l’algorithme suivant : on trie les intervalles par dates de début, puis pour tous les intervalles on lui assigne la plus petite couleur non-utilisée par un intervalle visité précédemment et qui le chevauche.

On s’assure donc que deux intervalles voisins n’ont pas la même couleur. Il s’agit donc bien d’un algorithme de coloration. Montrons maintenat qu’il est optimal.

Pour montrer que notre algorithme précédent utilise le moins de couleurs possible, il suffit de remarquer que si on assigne la couleur $c$ à un sommet alors ce sommet fait partie d’une clique de taille au moins $c$.

En effet, le nombre chromatique d’un graphe est toujours supérieur à la taille de sa plus grande clique. Si on montre que la plus grande couleur utilisée est de la taille de la plus grande clique, on aura montré qu’on ne peut utiliser moins de couleurs.

Lorsqu’on assigne une couleur $c \geq 2$ à un intervalle $\mathcal{I} = [\,d\,;\,f\,]$, cela signifie que $c-1$ intervalles $J_1, \ldots, J_{c-1}$ ayant commencé avant $\mathcal{I}$ se terminent après $d$. Donc on a :

\[\{d\} \subset \left(\bigcup\limits_{i \leq c-1} J_i\right) \cup \mathcal{I} \]

Ainsi, $\mathcal{I}$ appartient à une clique de taille au moins $c$. Donc, notre algorithme de coloration est bien optimale.

$3.$ On a montré à la question précédente que le nombre chromatique d’un graphe d’intervalle est égale à la taille de sa plus grande clique. De plus, on note que le sous-graphe d’un graphe d’intervalle est toujours un graphe d’intervalle. Il en résulte que les graphes d’intervalles sont des graphes parfaits.

Exercices en lien

Le problème de la couverture par sommet

Exercice

Une couverture par sommet d’un graphe $G=(S,A)$ non orienté est un sous ensemble $W \subseteq S$ tel que pour chaque arrête $(u,v) \in A$ on a $u \in W$ ou $v \in W$. Le problème de décision de la couverture par sommet, appelé en anglais vertex cover et désigné par la suite par VC, est le suivant :

Entrée : Un graphe $G = (S,A)$ et un entier $k$.

Sortie : Existe-t-il une couverture par somme de $G$ de taille $k$ ?

Ce problème fait partie des 21 problèmes NP-complet de Karp qui ont été prouvé NP-complet par Richard Karp en 1972.

$1.$ Montrer que VC est dans NP.

On effectue une réduction à partir de Clique : le problème de l’existence d’une clique de taille $l$ dans un graphe $G$. Considérons une instance $\displaystyle \left(G=\left(S,A\right),\;l\right)$ de clique.

$2.$ Montrer que $G$ a une clique de taille $l$ si et seulement si $\bar{G}$, le complémentaire de $G$, a une couverture par sommet de taille $|S| – l$.

$3.$ Conclure.

À présent que nous avons montré que VC est NP-complet, on note que $k$ est un paramètre du problème. On peut donc se demander ce qui se passe si $k$ est fixé.

$4.$ Montrer que pour tout $k$ entier, le problème $k$-VC qui prend en entrée un graphe $G$ représentée sous forme de matrice d’adjacence et vérifie s’il existe une couverture par sommet de taille exactement $k$ se résout en temps cubique en le nombre de sommets.

Correction

$1.$ On donne comme certificat une liste de $k$ sommets et on vérifie en temps polynomiale en la taille du graphe qu’ils constituent bien d’une couverture par sommet. De ce fait, VC appartient à NP.

$2.$ Supposons que $G$ a une clique de taille $l$ et soit $C$ l’ensemble des sommets de cette clique. On note que pour toute arrête $(x,y)$ dans $\bar{G}$ on ne peut avoir $x \in C$ et $y \in C$, car cela contredirait le fait que $C$ soit une clique dans $G$. Ainsi $S \smallsetminus C$ est une couverture par sommet de $\bar{G}$ et il en résulte donc que $\bar{G}$ admet une couverture par sommet de taille $|S|-l$.

Réciproquement, si $\bar{G}$ possède une couverture par sommet de taille $|S|-l$, on note $V$ cette couverture. Par définition, il n’y a aucune arrête entre les éléments de $S \smallsetminus V$. De ce fait, $S \smallsetminus V$ constitue une clique dans le complémentaire de $\bar{G}$. On a donc bien exhibé une clique de taille $l$ dans $G$.

$3.$ On peut transformer tout problème de Clique en un problème de VC en temps polynomiale. Or Clique est un problème NP-complet. Il en résulte que VC est NP-difficile. Or VC est dans NP, donc VC est un problème NP-complet.

$4.$ Notons que pour toute arrête $(s,t)$ de $G$ et toute couverture par sommet $V$ de $G$, on a au moins $s$ ou $t$ dans $V$. Autrement dit, pour tout sommet $s$, soit $s \in V$ soit tous ses voisins font partie de $V$. Cela nous donne donc l’algorithme récursif suivant.

algrorithme recursif pour résoudre vertex cover

Dans le pire des cas, notre algorithme tourne en $O\left(2^{k}n^{3}\right)$ étapes. Il est important de noter que $k$ ne fait pas partie de l’instance du problème $k$-VC. Ainsi, le facteur $2^{k}$ ne varie pas suivant la taille de $G$ et n’est donc qu’une constante. Ainsi, kVertexCover fonctionne en temps $O\left(n^{3}\right)$.

Exercice en lien

Sudoku #3

Sudoku haché #2

English version here

Un nouveau sudoku haché ! Les règles sont sous la grille ! Amusez-vous bien.

Résoudre en ligne !

Les règles habituelles du sudoku s’appliquent. Le long des flèches, la somme des entiers est divisible par le nombre le plus proche de la flèche. De plus, le long d’une flèche, tous les nombres sont différents. Enfin, la somme des cellules le long des doubles flèches est divisible par le carré du nombre le plus proche de la double flèche.

Bonne chance !

Et si vous aimez ce type de sudoku, un autre sudoku haché est présent ici !

Distance d’édition

Étant donné deux textes, il est parfois utile de savoir à quel point ils sont semblables ou différents. Un des outils utilisé pour répondre à ce problème est la distance de Levenshtein ou distance d’édition. Elle est notamment utilisé dans les correcteurs orthographiques.

Exercice

À partir d’un mot donné, on définit les opérations élémentaires comme l’ensemble d’actions suivants :

  • Suppression d’une lettre
  • Insertion d’une lettre
  • Substitution d’une lettre par une autre.

On définit alors la distance d’édition $d$ entre deux mots comme le nombre d’opérations élémentaires nécessaires pour passer d’un mot à l’autre.

Pour $x$ un mot, on note $x_k$ la $k$-ème lettre de $x$. De plus on note $x^i$ le préfixes de $x$ composés de ses $i$ premières lettres. Ainsi on a $x^{0} = \epsilon$.

$1.$ Montrer que $d$ définit bien une distance.

$2.$ Quelle est la valeur de $d(x^i,y^0)$ ?

$3.$ Exprimer $d(x^i,y^j)$ en fonction de mots plus petits.

$4.$ Donner un algorithme pour calculer $d(x,y)$.

$5.$ Quel est sa complexité ?

Correction

$1.$ On rappel qu’une distance est un fonction $f$ positive à deux paramètres qui vérifie les propriétés de séparation (annulation de $f(x,y)$ si et seulement si $x = y$), de symétrie et l’inégalité triangulaire. La fonction $d(x,y)$ est une fonction positive qui ne s’annule que s’il n’y a pas d’opérations élémentaires à effectuer pour passer de $x$ à $y$, donc si $x=y$. Elle est également symétrique. En effet si on peut aller de $u$ à $v$ en une opération élémentaire, alors on peut aller de $v$ à $u$ également en une opération. Il nous reste à montrer que $d$ satisfait bien l’inégalité triangulaire. Si on avait $z$ tel que $d(x,z)+d(z,y)$ soit supérieur strictement à $d(x,z)$ cela signifierait qu’en considérant le chemin minimal pour aller de $x$ à $z$ puis de $z$ à $y$, on aurait un chemin de $x$ à $y$ de taille plus courte que $d(x,y)$ ce qui contredirait notre définition.

Ainsi $d$ définit bien une distance.

$2.$ On désigne la taille d’un mot $x$ par $|x|$. Commençons par noter que $d(x,y) \geq ||x|-|y||$. En effet, une opération élémentaire ne modifie la taille d’un mot que d’au plus une lettre. Ainsi, comme $y^0 = \epsilon$ on a $|y^0|=0$. On note donc que $d(x^i,y^0) \geq |x^i|$. Or le chemin qui consiste à ajouter une à une les lettres de $x_i$ prend $|x_i|$ étapes. On a donc :

\[d(x^i,y^0) = i\]

$3.$ Commençons par remarquer qu’il existe un chemin de taille minimal de $x$ à $y$ où chaque lettre n’est modifié qu’au plus une fois et que les modifications peuvent être effectuées dans l’ordre que l’on souhaite. En effet, si une solution nous incite à effectuer une opération sur une lettre à laquelle on a déjà touché, on aurait pu effectuer l’opération la première fois. De ce fait, les lettres sont indépendantes et peuvent être modifiées dans n’importe quel ordre.

Soit $i,j \geq 1$. On s’intéresse aux deux dernières lettres de $x^i$ et $y^j$. On note qu’une solution optimale ne permet pas de supprimer $x_i$ et d’ajouter $y_i$. En effet, si une telle solution existait, on remarque qu’en substituant $x_i$ en $y_i$ on gagne une étape. Il ne reste donc que trois possibilités. Soit on a modifié $x_i$ en $y_i$, ce qui a un coût de $0$ dans le cas où $x_i=y_i$, soit on a supprimé $x_i$ et dans ce cas là, il nous reste à transformer $x^{i-1}$ en $y^{j}$ ce qui a un coût de $d(i-1,j)$. Enfin, soit on a supprimé $y_j$ et il nous faut modifier $x^{i}$ en $y^{j-1}$. Notre but est de prendre la solution la moins coûteuse, ce qui nous permet donc d’obtenir la formule suivant.

\begin{align*} \forall\;0 \leq i \leq |x|,\quad d(x^i,y^0) = &\; i \\ \forall\;0 \leq j \leq |y|,\quad d(x^0,y^j) = &\; j \end{align*}

\[\forall\;1 \leq i \leq |x|,\quad 1 \leq j \leq |y|,\]

\[d(x^i,y^j) = \min(d(x^{i-1},y^{j-1}) + \delta_{i,j},\; d(x^{i-1},y^{j}) + 1,\; d(x^{i},y^{j-1}) + 1)\]

où $\delta_{i,j}$ vaut $1$ si $x_i \neq y_j$ et $0$ sinon.

On remarque que lors d’un calcul récursif de $d(x,y)$ on recalcule souvent les mêmes objets. En réalité si on écrit une fonction récursive, le temps de calcul est exponentiel. C’est pourquoi, il est plus efficace de stocker les valeurs dans un tableau pour proposer l’algorithme de programmation dynamique suivant.

Algorithme distance edition

$5.$ L’initialisation a un coût en $O(|x|+|y|)$. Le calcul des éléments du tableau est en $O(1)$ par case. Ainsi notre algorithme tourne en $\displaystyle \boxed{O\left(|x||y|\right)}$.

Produit efficace en binaire

Exercice

Nous cherchons ici à effectuer le produit de deux entiers $x$ et $y$ écrits en binaire sur $k$ bits, avec $k$ une puissance de $2$. On peut noter $x = x_1 x_2 \ldots x_k$ et $y = y_1 y_2 \ldots y_k$. Les bits $x_1$ et $y_1$ sont les bits de poids forts.

$1.$ Donner la complexité de l’addition de deux nombres écrits en binaire écrits sur $n$ bits.

$2.$ Donner la complexité pour multiplier un nombre écrit en binaire sur $n$ bits par une puissance de $2$ inférieure à $2^{k}$.

$3.$ Quel est la complexité du produit naïf de deux nombres en binaire sur $n$ bits dont le résultat est écrit sur $2n$ bits ?

On pose $x_G = x_1 \ldots x_{k/2}$ et $x_D = x_{k/2+1} \ldots x_k$. De même, on pose $y_G$ et $y_D$.

$4.$ Exprimer naïvement $xy$ en fonction de $x_G$, $x_D$, $y_G$, $y_D$ et des puissances de $2$.

$5.$ Quelle est la complexité de l’algorithme de diviser pour régner associé ?

$6.$ Exprimer $xy$ en fonction de $x_G$, $x_D$, $y_G$, $y_D$ et des puissances de $2$ en utilisant moins de multiplication.

$7.$ Quelle est la complexité de l’algorithme de diviser pour régner associé ?

$8.$ Comment adapter l’algorithme pour multiplier des entiers sur $k$ bits avec $k$ quelconque ?

Cet algorithme de calcul a été développé par Anatolii Karatsuba en 1960 et publié en 1962.

Correction

$1.$ Pour additionner deux entiers, il est nécessaire de regarder chaque bits. De ce fait, le problème de l’addition de deux entiers est en $\Omega(n)$. De plus l’algorithme de la retenue tourne en $O(n)$. Il en résulte que la complexité de l’addition de deux entiers de $n$ bits est $\displaystyle \boxed{\Theta\left(n\right)}$.

$2.$ Pour multiplier un entier écris sur $n$ bits par une puissance de $2$, il nous suffit de décaler les bits de notre entier. Ainsi, il nous faut encore $\boxed{\Theta\left(n\right)}$ opérations.

$3.$ L’algorithme naïf de multiplication consiste à multiplier $x$ par chaque bit de $y$ avant de sommer. Cela nécessite donc $\displaystyle \boxed{\Theta\left(n^{2}\right)}$ opérations.

$4.$ On a la formule suivante :

\[xy = x_Gy_G\cdot2^{k} + (x_Gy_D + x_Dy_G)\cdot2^{k/2} + x_Dy_D\]

$5.$ Si on calcule récursivement cette formule, on remarque qu’on effectue 4 appels sur des instances de tailles $k/2$. De plus la fusion des différents résultats nécessite deux multiplications par des puissances de $2$ et trois additions, soit un coût en $O(k)$. Ainsi, un algorithme calculant cette formule a une complexité $C(n)$ qui vérifie la récurrence :

\[C(n) = 4C\left(\frac{n}{2}\right) + O(n)\]

Le master theorem nous permet donc de conclure que notre algorithme tourne en $\boxed{\Theta\left(k^{2}\right)}$ opérations. On ne remarque donc pas d’améliorations par rapport à la méthode naïf.

$6.$ Posons $g = x_Gy_G$, $d = x_Dy_D$ et $u = (x_G+x_D)(y_G+y_D)$. On note qu’on obtient ces valeurs en trois multiplications.

De plus, on note que $u – d – g = x_Gy_D + x_Dy_G$. On a donc :

\[xy = g\cdot2^{k} + (u-g-d)\cdot2^{k/2} + d\]

$7.$ L’algorithme de diviser pour régner associé à cette formule a une complexité définie par la formule :

\[T(k) = 3T\left(\frac{k}{2}\right) + O(k)\]

Le master theorem nous donne donc $\displaystyle T(k)=O\left(n^{\log_2(3)}\right)=O\left(n^{1.6}\right)$.

$8.$ Pour des entiers de tailles $n$ quelconque, on considère $m$ tel que $2^{m} \geq n \gt 2^{m-1}$. On complète à gauche nos entiers par des zéros pour obtenir des entiers de taille $2^m$. Ensuite, on procède avec notre algorithme qui aura une complexité en $O\left(2^{ \log_2(3) \cdot m}\right)$. Or on a $2^{m} \leq 2n$, donc notre algorithme fonctionne en $O\left(2^{ \log_2(3) } \cdot n^{ \log_2(3) }\right)$, soit en $O\left(n^{ \log_2(3) }\right)$.

Le problème des 3 couleurs (3-COLOR)

Notre but ici est de montrer que le problème de coloration avec trois couleurs est NP-complet que ce soit dans le cas des graphes planaire ou non planaire. Nous souhaitons le prouver pour le cas des graphes quelconque et pour le cas des graphes planaires. Ces résultats sont dus à Garey, Johnson et Stockmeyer.

Dans un autre exercice, on s’intéresse à une approximation du problème des 3 couleurs.

Exercice

On appelle coloration d’un graphe une fonction des sommets du graphe vers les entiers tels que deux sommets adjacents ne sont pas assignés le même entier. Le problème des 3 couleurs noté 3-COL prend en entré un graphe et répond vrai si et seulement si il existe une coloration du graphe utilisant moins de trois couleurs. Autrement dit, telle qu’il existe un fonction de coloration dont l’image est incluse dans ${1,2,3}$.

$1.$ Montrer que 3-COL est un problème dans NP.

Pour montrer que le problème est NP-difficile, on cherche à effectuer une réduction à partir de 3-SAT. Pour ce faire, une considère une formule $\varphi$ sous forme normale conjonctive dont toutes les clauses ont exactement trois littéraux. On note : $\varphi = \bigwedge\limits_{i=1}^{n}C_i$ et $C_i = (x_{1}^{i},x_{2}^{i},x_{3}^{i})$.

On veut maintenant construire un graphe qui est 3 coloriable si et seulement si $\varphi$ est satisfiable. Pour commencer on ajoute pour chaque variable et chaque négation de variable un sommet. Notre but est que pour chaque couple de variable et sa négation la couleur d’un des deux sommets corresponde à la valuation Vrai et la couleur d’un autre sommet corresponde à la valuation Faux.

$2.$ On souhaite que la fonction de coloration de notre graphe, si elle existe, soit une fonction de distribution de valeur de vérité. Donner une façon de s’en assurer.

Intéressons nous au gadget suivant :

Rendered by QuickLaTeX.com

$3.$ Que peut-on dire de la couleur du sommet $e$ en fonction des couleurs de $a$ et $b$ lorsqu’on se limite à $3$ couleurs ?

$4.$ En déduire un gadget tel qu’un sommet donné puisse être à la couleur de Vrai si et seulement si une clause et satisfaite. Donc si et seulement si une des variables de la clause soit coloré par la couleur associé à Vrai.

$5.$ Terminer la réduction.

$6.$ Montrer maintenant que pour tout $k$, $k$-COL est NP-complet.

Intéressons nous maintenant au cas planaire. On dit qu’un graphe est planaire si dans une de ses représentations graphique dans le plan, aucune arête ne se croise. Le théorème des quatre couleurs nous dit que tout graphe de ce type est 4-coloriable. Cependant, savoir si un tel graphe est 3-coloriable est NP-complet. Ce problème est appelé PLANAR-3-COL.

$7.$ Montrer que PLANAR-3-COL est dans NP.

On considère le gadget suivant :

Rendered by QuickLaTeX.com

$8.$ Montrer que pour tout 3-coloration $c$ correcte de ce gadget, on a nécessairement $c(a)=c(m)$ et $c(e)=c(i)$.

$9.$ Montrer que dans un graphe quelconque, on peut remplacer chacune de ses intersections par ce gadget et s’assurer que non seulement le nouveau graphe obtenue est planaire mais en plus il est 3-coloriable si et seulement si le graphe initial l’est.

$10.$ Conclure

$11.$ Expliquer en quelques mots pourquoi on ne peut pas adapter cette démonstration pour montrer que PLANAR-4-COL est NP-complet ?

Correction

$1.$ Si on dispose d’une $3$ coloration d’un graphe, un simple parcours du graphe nous permet de vérifier si elle est correcte. De ce fait on a un certificat de taille polynomiale en la taille de notre graphe qui permet de vérifier qu’un graphe est $3$-coloriable. On en déduit que 3-COL est dans NP.

$2.$ On crée trois sommets nommés $V$, $F$ et $A$ reliés entre eux. De plus, pour chaque variable $v_i$ de notre graphe on crée deux sommets nommés $v_i$ et $\bar{v_i}$. On ajoute alors les arêtes $(v_i,\bar{v_i}), (v_i,A), (A,\bar{v_i})$. Ainsi, chaque variable est soit de la même couleur que $V$ et sa négation de la couleur de $F$ soit l’inverse.

Rendered by QuickLaTeX.com

$3.$ Pour une coloration valide $c$, si $c(a) = c(b)$ alors $c(a) = c(e)$. De ce fait, si les couleurs de $a$ et $b$ sont soit celle de $V$ soit celle de $F$, alors $c(e)$ ne peut être égale à $c(V)$ que si $c(a) = c(V)$ ou $c(b) = c(V)$.

$4.$ On vient de construire un gadget permettant de calculer, $a \vee b$. Il nous suffit donc de le répéter. Ainsi si une clause $C$ s’écrit $(x_1 \vee x_2 \vee x_3)$ on peut considérer le gadget suivant :

Rendered by QuickLaTeX.com

Pour toute 3-coloration $c$ tel que $c(x_1)$, $c(x_2)$, $c(x_3)$ sont dans ${c(V),c(F)}$, on a $c(i) = c(V)$ seulement si il existe $1 \leq k \leq 3$ tel que $c(x_k) = c(V)$. En effet, si $c(i) = c(V)$ et $c(h) = c(F)$ alors $c(x_3) = c(V)$. Si $c(g) = c(F)$ alors $c(e) \neq c(F)$ et soit $c(x_1)$ soit $c(x_2)$ égale à $c(V)$.

De plus si on a $1 \leq k \leq 3$ tel que $c(x_k) = c(V)$ alors on a une coloration telle que $c(i) = c(V)$.

$5.$ Pour chaque clause $C_k$ on construit le gadget précédent. Pour les $x_i$ on utilise évidemment les sommets de variables déjà créés. Sinon, on associe à chacun les sommets $c_k$, $d_k$, $e_k$, $g_k$, $h_k$, $i_k$. Enfin, il nous suffit de rajouter pour tous $k$ les arêtes $(i_k,A)$ et $(i_k,F)$.

Ainsi, supposons que $\varphi$ soit satisfiable. On considère la coloration suivante : on associe à $F$ la couleur $0$, à $V$ la couleur $1$ et à $A$ la couleur $2$. On considère la distribution de valeur qui satisfait $\varphi$. Pour chaque variable $x_i$ on lui associe $1$ si elle est à vrai et $0$ sinon. Ensuite, comme cette distribution assure que pour chaque clause au moins une des variables soit de couleur $1$ on s’assure qu’on peut colorier chaque gadget de telle sorte à ce que tous les $i_k$ soient de couleur $1$. Ainsi deux sommets reliés sont de couleurs différentes et on a bien une 3-coloration de notre graphe.

Réciproquement, si notre graphe est 3-coloriable, cela signifie que tous les $i_k$ sont de la même couleur que $V$. De plus, comme les couleurs des $x_j$ sont dans ${c(V),\:c(F)}$, car voisins de $A$, on a prouvé qu’un des trois sommets initiaux de chaque gadget est de la même couleur que $c(V)$. De ce fait, si on met à vrai tous les littéraux de la même couleur que $V$ et les autres à faux, on s’assure qu’au moins un littéral par clause soit à vrai et que donc notre formule soit bien satisfaite.

Ainsi, on a construis un graphe de taille polynomiale en la taille de notre formule qui est $3$ coloriable si et seulement si $\varphi$ est satisfiable. On a donc bien montré que 3-COL est NP-complet.

$6.$ Pour montrer que pour tout $k \geq 4$, $k$-COL est NP-complet, on effectue une réduction à partir de $3$-COL. On considère un graphe $G$. On ajoute $k-3$ sommets tous reliés entre eux et reliés à tous les autres sommets de $G$ Le nouveau graphe obtenue est $k$ coloriable si et seulement si $G$ est 3 coloriable. Notons que notre réduction est bien polynomiale car $k$ n’est pas un paramètre du problème.

$7.$ Comme pour $3$-COL, il nous suffit de considérer comme certificat une coloration correcte du graphe.

$8.$ On considère une coloration correcte $c$ de notre gadget. On commence par appeler $1$ la couleur de $g$ et $2$ la couleur du sommet $c$. En effet, comme $g$ et $c$ sont liés par une arête, on sait qu’ils sont de couleurs différentes. Ainsi, on a nécessairement $c(f) = 3$, $c(h) = 3$ et $c(k) = 2$. Il nous reste alors deux choix pour colorier $b$. Soit $c(b) = 1$, soit $c(b) = 3$. Dans les deux cas, la coloration des derniers sommets est forcée et nous nous retrouvons dans une de ces deux configurations :

Rendered by QuickLaTeX.com

On a donc bien toujours $c(a)=c(m)$ et $c(e)=c(i)$.

$9.$ On considère les sommets $u,v,u’,v’$ et la situation suivante :

Rendered by QuickLaTeX.com

On remplace cette occurence par :

Rendered by QuickLaTeX.com

Il nous suffit alors de remplacer toutes les intersections en commençant par l’intersection la plus en haut à gauche. De ce fait, le graphe ainsi construit est planaire et est $3$ coloriable si et seulement si le graphe initial l’est.

$10.$ Il nous reste à montrer que notre transformation est bien de taille polynomiale. On note que cette transformation fonctionne pour toute représentation de notre graphe initial tel qu’aucune arête ne passe par un autre sommet. On considère uniquement des arêtes représenté par un segment du plan. Ainsi, tout couple d’arête ne se croise qu’au plus une fois. On ajoute donc $\displaystyle O\left(n^{2}\right)$ de sommets et d’arêtes.

Il en résulte donc qu’on a obtenu une réduction polynomiale de $3$-COL à PLANAR-$3$-COL qui est dans NP. Ainsi, PLANAR-$3$-COL est NP-complet.

$11.$ Le gadget qu’on a construit repose sur le fait qu’on colorie avec au plus $3$ couleurs. Ainsi, si on voulait pouvoir adapter cette démonstration il nous faudrait trouver un autre gadget jouant le même rôle pour un nombre plus élevés de couleurs. Cependant, on note que tout graphe planaire est $4$ coloriable donc on sait qu’un tel gadget n’existe pas car il existe des graphes non planaires qui ne sont pas $4$ coloriables.

Exercices en lien