Coloriage de graphes

L'algorithme de Brélaz ou DSATUR permet de colorier un graphe et de donner une bonne borne supérieur du nombre chromatique. On considère que les couleurs sont numérotées : 1, 2, 3, 4, ... Voici les étapes de l'algorithme. Détaillons un exemple Considérons le graphe suivant \[ \xymatrix@R=2.5cm@C=1.5cm{ &a\ar@{-}[r]\ar@{-}[rrd]\ar@{-}[rrdd]\ar@{-}@/_2pc/[dd] &b\ar@{-}[rd]\ar@{-}[rdd]\ar@{-}[dd]\ar@{-}[ddl] &c\ar@{-}[ddll]\ar@{-}[dll]\ar@{-}@/^2pc/[dd]\\ i &h\ar@{-}[l]& &d\ar@{-}[d]\ar@{-}[dl]\\ &g\ar@{-}[u] &f\ar@{-}[lu]\ar@{-}[l] &e\ar@{-}@/^2pc/[ll] } \]
On commence par calculer les degrés de chaque sommet \[ \begin{array}{*{10}{|c}|} \hline \Som(\G)&a&b&c&d&e&f&g&h&i\\\hline d^1(x,\G)&4&5&3&4&5&4&6&4&1\\\hline \end{array} \] On va ensuite compléter le tableau suivant où l'on a ordonner les sommets par degré croissant. \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &&&&&&&&&\\\hline \texttt{DSAT}(x)_3 &&&&&&&&&\\\hline \texttt{DSAT}(x)_4 &&&&&&&&&\\\hline \texttt{DSAT}(x)_5 &&&&&&&&&\\\hline \texttt{DSAT}(x)_6 &&&&&&&&&\\\hline \texttt{DSAT}(x)_7 &&&&&&&&&\\\hline \texttt{DSAT}(x)_8 &&&&&&&&&\\\hline \texttt{DSAT}(x)_9 &&&&&&&&&\\\hline \texttt{COULEUR} &&&&&&&&&\\\hline \end{array} \] Il y a autant de ligne que le sommet. La ligne \( \texttt{DSAT}(x)_1\) correspond aux degrés puisqu'aucun sommet n'est colorié. On choisi donc toujours le sommet non colorié avec le plus grand \( \texttt{DSAT}\) et le plus à gauche (en cas d'égalité). Le premier sommet à être colorié est \( g\) . On lui attribue la plus petite couleur possible et on recalcule \( \texttt{DSAT}(x)\) (dans la ligne \( \texttt{DSAT}(x)_2\) ) pour chaque sommet \( x\) non colorié. \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &{\color{red} \blacksquare}&1&1&1&4&1&1&1&1\\\hline \texttt{DSAT}(x)_3 &{\color{red} \blacksquare}&&&&&&&&\\\hline \texttt{DSAT}(x)_4 &{\color{red} \blacksquare}&&&&&&&&\\\hline \texttt{DSAT}(x)_5 &{\color{red} \blacksquare}&&&&&&&&\\\hline \texttt{DSAT}(x)_6 &{\color{red} \blacksquare}&&&&&&&&\\\hline \texttt{DSAT}(x)_7 &{\color{red} \blacksquare}&&&&&&&&\\\hline \texttt{DSAT}(x)_8 &{\color{red} \blacksquare}&&&&&&&&\\\hline \texttt{DSAT}(x)_9 &{\color{red} \blacksquare}&&&&&&&&\\\hline \texttt{COULEUR} &\color{red}{\textbf{1}}&&&&&&&&\\\hline \end{array} \] Le DSAT maximal est celui du sommet \( d\) . On le colorie avec la couleur \( 1\) également puisque cela est possible. On complète le tableau \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &{\color{red} \blacksquare}&1&1&1&4&1&1&1&1\\\hline \texttt{DSAT}(x)_3 &{\color{red} \blacksquare}&2&2&2&{\color{red} \blacksquare}&2&1&1&1\\\hline \texttt{DSAT}(x)_4 &{\color{red} \blacksquare}&&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_5 &{\color{red} \blacksquare}&&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_6 &{\color{red} \blacksquare}&&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_7 &{\color{red} \blacksquare}&&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_8 &{\color{red} \blacksquare}&&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_9 &{\color{red} \blacksquare}&&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{COULEUR} &\color{red}{\textbf{1}}&&&&\color{red}{\textbf{1}}&&&&\\\hline \end{array} \] A l'étape suivante il y a conflit : deux sommets ont un DSAT maximal. On choisi alors celui qui est le plus à gauche dans le tableau. Il s'agit donc du sommet \( b\) . Ce sommet étant adjacent aux sommets \( g\) et \( d\) coloriés avec la couleur \( 1\) , on le colorie avec la couleur \( 2\) . \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &{\color{red} \blacksquare}&1&1&1&4&1&1&1&1\\\hline \texttt{DSAT}(x)_3 &{\color{red} \blacksquare}&2&2&2&{\color{red} \blacksquare}&2&1&1&1\\\hline \texttt{DSAT}(x)_4 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&3&3&{\color{red} \blacksquare}&3&1&1&1\\\hline \texttt{DSAT}(x)_5 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_6 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_7 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_8 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_9 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&&&{\color{red} \blacksquare}&&&&\\\hline \texttt{COULEUR} &\color{red}{\textbf{1}}&\color{blue}{\textbf{2}}&&&\color{red}{\textbf{1}}&&&&\\\hline \end{array} \] Viens ensuite le sommet \( e\) qui est adjacent à \( g\) et à \( b\) ; il faut donc le colorier avec la couleur \( 3\) \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &{\color{red} \blacksquare}&1&1&1&4&1&1&1&1\\\hline \texttt{DSAT}(x)_3 &{\color{red} \blacksquare}&2&2&2&{\color{red} \blacksquare}&2&1&1&1\\\hline \texttt{DSAT}(x)_4 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&3&3&{\color{red} \blacksquare}&3&1&1&1\\\hline \texttt{DSAT}(x)_5 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&4&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_6 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_7 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_8 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_9 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&&{\color{red} \blacksquare}&&&&\\\hline \texttt{COULEUR} &\color{red}{\textbf{1}}&\color{blue}{\textbf{2}}&\color{green}{\textbf{3}}&&\color{red}{\textbf{1}}&&&&\\\hline \end{array} \] Viens ensuite le sommet \( a\) qui a \( g\) , \( b\) et \( e\) comme sommet adjacents ; on le colorie avec la couleur \( 4\) . \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &{\color{red} \blacksquare}&1&1&1&4&1&1&1&1\\\hline \texttt{DSAT}(x)_3 &{\color{red} \blacksquare}&2&2&2&{\color{red} \blacksquare}&2&1&1&1\\\hline \texttt{DSAT}(x)_4 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&3&3&{\color{red} \blacksquare}&3&1&1&1\\\hline \texttt{DSAT}(x)_5 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&4&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_6 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_7 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_8 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&&&&\\\hline \texttt{DSAT}(x)_9 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&&&&\\\hline \texttt{COULEUR} &\color{red}{\textbf{1}}&\color{blue}{\textbf{2}}&\color{green}{\textbf{3}}&\textbf{4}&\color{red}{\textbf{1}}&&&&\\\hline \end{array} \] Le sommet \( f\) est adjacent à \( g\) et à \( b\) mais pas à \( e\) ; on le colorie donc avec la couleur \( 3\) . \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &{\color{red} \blacksquare}&1&1&1&4&1&1&1&1\\\hline \texttt{DSAT}(x)_3 &{\color{red} \blacksquare}&2&2&2&{\color{red} \blacksquare}&2&1&1&1\\\hline \texttt{DSAT}(x)_4 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&3&3&{\color{red} \blacksquare}&3&1&1&1\\\hline \texttt{DSAT}(x)_5 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&4&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_6 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_7 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&2&2&1\\\hline \texttt{DSAT}(x)_8 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&&&\\\hline \texttt{DSAT}(x)_9 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&&&\\\hline \texttt{COULEUR} &\color{red}{\textbf{1}}&\color{blue}{\textbf{2}}&\color{green}{\textbf{3}}&\textbf{4}&\color{red}{\textbf{1}}&\color{green}{\textbf{3}}&&&\\\hline \end{array} \] Le sommet \( h\) est adjacent à \( g\) mais pas à \( b\) ; on le colorie avec la couleur \( 2\) . \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &{\color{red} \blacksquare}&1&1&1&4&1&1&1&1\\\hline \texttt{DSAT}(x)_3 &{\color{red} \blacksquare}&2&2&2&{\color{red} \blacksquare}&2&1&1&1\\\hline \texttt{DSAT}(x)_4 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&3&3&{\color{red} \blacksquare}&3&1&1&1\\\hline \texttt{DSAT}(x)_5 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&4&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_6 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_7 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&2&2&1\\\hline \texttt{DSAT}(x)_8 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&{\color{blue} \blacksquare}&3&1\\\hline \texttt{DSAT}(x)_9 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&{\color{blue} \blacksquare}&&\\\hline \texttt{COULEUR} &\color{red}{\textbf{1}}&\color{blue}{\textbf{2}}&\color{green}{\textbf{3}}&\textbf{4}&\color{red}{\textbf{1}}&\color{green}{\textbf{3}}&\color{blue}{\textbf{2}}&&\\\hline \end{array} \] Puisque le sommet \( c\) est adjacent aux sommet \( g\) , \( h\) et \( e\) on le colorie avec la couleur \( 4\) . \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &{\color{red} \blacksquare}&1&1&1&4&1&1&1&1\\\hline \texttt{DSAT}(x)_3 &{\color{red} \blacksquare}&2&2&2&{\color{red} \blacksquare}&2&1&1&1\\\hline \texttt{DSAT}(x)_4 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&3&3&{\color{red} \blacksquare}&3&1&1&1\\\hline \texttt{DSAT}(x)_5 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&4&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_6 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_7 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&2&2&1\\\hline \texttt{DSAT}(x)_8 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&{\color{blue} \blacksquare}&3&1\\\hline \texttt{DSAT}(x)_9 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&{\color{blue} \blacksquare}&\blacksquare&1\\\hline \texttt{COULEUR} &\color{red}{\textbf{1}}&\color{blue}{\textbf{2}}&\color{green}{\textbf{3}}&\textbf{4}&\color{red}{\textbf{1}}&\color{green}{\textbf{3}}&\color{blue}{\textbf{2}}&\textbf{4}&\\\hline \end{array} \] Et pour finir la couleur \( 1\) convient au dernier sommet non colorié : \( i\) . \[ \begin{array}{*{10}{|c}|} \hline \Som(\G) &g&b&e&a&d&f&h&c&i\\\hline \texttt{DSAT}(x)_1 &6&5&5&4&4&4&4&3&1\\\hline \texttt{DSAT}(x)_2 &{\color{red} \blacksquare}&1&1&1&4&1&1&1&1\\\hline \texttt{DSAT}(x)_3 &{\color{red} \blacksquare}&2&2&2&{\color{red} \blacksquare}&2&1&1&1\\\hline \texttt{DSAT}(x)_4 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&3&3&{\color{red} \blacksquare}&3&1&1&1\\\hline \texttt{DSAT}(x)_5 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&4&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_6 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&3&1&2&1\\\hline \texttt{DSAT}(x)_7 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&2&2&1\\\hline \texttt{DSAT}(x)_8 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&{\color{blue} \blacksquare}&3&1\\\hline \texttt{DSAT}(x)_9 &{\color{red} \blacksquare}&{\color{blue} \blacksquare}&{\color{green} \blacksquare}&\blacksquare&{\color{red} \blacksquare}&{\color{green} \blacksquare}&{\color{blue} \blacksquare}&\blacksquare&1\\\hline \texttt{COULEUR} &\color{red}{\textbf{1}}&\color{blue}{\textbf{2}}&\color{green}{\textbf{3}}&\textbf{4}&\color{red}{\textbf{1}}&\color{green}{\textbf{3}}&\color{blue}{\textbf{2}}&\textbf{4}&\color{red}{\textbf{1}}\\\hline \end{array} \] \[ \xymatrix@R=3cm@C=4cm{ &{\color{black}{a}}\ar@{-}[r]\ar@{-}[rrd]\ar@{-}[rrdd]\ar@{-}@/_2pc/[dd] &{\color{blue}{b}}\ar@{-}[rd]\ar@{-}[rdd]\ar@{-}[dd]\ar@{-}[ddl] &{\color{black}{c}}\ar@{-}[ddll]\ar@{-}[dll]\ar@{-}@/^2pc/[dd]\\ {\color{red}{i}} &{\color{blue}{h}}\ar@{-}[l]& &{\color{red}{d}}\ar@{-}[d]\ar@{-}[dl]\\ &{\color{red}{g}}\ar@{-}[u] &{\color{green}{f}}\ar@{-}[lu]\ar@{-}[l] &{\color{green}{e}}\ar@{-}@/^2pc/[ll] } \] Nous pouvons donc affirmer que \( X(\G)\leqslant 4\) . En fait \( X(\G)=4\) . En effet \( \Kk_4\subset\G\) donc \( 4=X(\Kk_4)\leqslant X(\G)\leqslant 4\) et ces inégalités sont des égalités. \[ \xymatrix@R=1cm@C=1cm{ &&5\ar@{-}[rdd]\ar@{-}[ldd]\ar@{-}[rrd]\ar@{-}[lld]&&\\ 4\ar@{-}[rd]\ar@{-}[rrrr]\ar@{-}[rrrd]&&&&1\ar@{-}[ld]\\ &3\ar@{-}[rrru]&&2& } \] Ce graphe est planaire ; en effet en réarrangeant ses sommets et en traçant les arêtes astucieusement il est équivalant au graphe de droite. \[ \xymatrix@R=1.5cm@C=1cm{ 3\ar@{-}[rr]\ar@{-}[d]\ar@/_5pc/@{-}[ddr]&& 4\ar@{-}[lld]\ar@{-}[d]\ar@/^5pc/@{-}[ddl]\\ 1\ar@{-}[rr]\ar@{-}[rd]&& 2\ar@{-}[ld]\\ &5&} \] Par exemple les deux graphes suivants sont homéomorphes : \[\xymatrix{ \bullet\ar@{-}[rr]\ar@{-}[rrdd]\ar@{-}[dd]&&\bullet\ar@{-}[dd]\ar@{-}[ddll]\\ &&\\ \bullet\ar@{-}[rr]&&\bullet }\] \[\xymatrix{ \bullet\ar@{-}[rr]\ar@{-}[rrdd]\ar@{-}[dd]&\bullet&\bullet\ar@{-}[dd]\ar@{-}[ddll]\\ \bullet&\bullet&\\ \bullet\ar@{-}[rr]&&\bullet }\] Le théorème suivant permet de repérer si un graphe est planaire. Il existe une caractérisation plus faible des graphes planaires. Voici un algorithme permettant, assez souvent, de planarifier¹ un graphe. Par exemple : \( \xymatrix@R=1.5cm@C=0.79cm{ &&5\ar@{-}[rdd]\ar@{-}[ldd]\ar@{-}[rrd]\ar@{-}[lld]&&\\ 4\ar@{-}[rd]\ar@{-}[rrrr]\ar@{-}[rrrd]&&&&1\ar@{-}[ld]\\ &3\ar@{-}[rrru]&&2& } \) Nombre d'intersection entre arêtes : \( 5\) . \[ \begin{array}{c||c|c|c|c|c} Sommet&1&2&3&4&5\\\hline di &4&4&4&4&4 \end{array} \] On sélectionne le sommet \( 1\) qui admet \( 2\) , \( 3\) , \( 4\) et \( 5\) comme voisin. On place donc le sommet \( 1\) au milieu du quadrilatère \( 2345\) . \[ \xymatrix@R=1.5cm@C=0.79cm{ &&5\ar@{-}[rdd]\ar@{-}[ldd]\ar@{-}[ld]\ar@{-}[lld]&&\\ 4\ar@{-}[rd]\ar@{-}[r]\ar@{-}[rrrd]&1\ar@{-}[rrd]&&&\\ &3\ar@{-}[u]&&2& } \] Nombre d'intersection entre arêtes : \( 3\) . \[ \begin{array}{c||c|c|c|c|c} Sommet&1&2&3&4&5\\\hline di &2&3&3&2&2 \end{array} \] En arquant l'arête \( \{2;4\}\) les degrés d'intersections seraient respectivement \( 1\) , \( 1\) , \( 1\) , \( 0\) , \( 1\) . Dans ce cas il ne faut pas sélectionner le sommet \( 1\) qui a déjà été sélectionné à l'itération précédente. On sélectionne le sommet \( 2\) qui admet \( 1\) , \( 4\) et \( 5\) comme voisin. On place donc le sommet \( 2\) au milieu du triangle \( 145\) . \[ \xymatrix@R=0.53cm@C=0.79cm{ &&5\ar@{-}[ld]\ar@{-}[ldddd]\ar@{-}[ldd]\ar@/_0.79pc/@{-}[lldd]&&\\ &2&&&\\ 4\ar@{-}[rdd]\ar@{-}[r]\ar@{-}[ur]&1\ar@{-}[u]&&&\\ &&&&\\ &3\ar@{-}[uu]&&& } \] Nombre d'intersection entre arêtes : \( 0\) . \[ \begin{array}{c||c|c|c|c|c} Sommet&1&2&3&4&5\\\hline di &0&0&0&0&0 \end{array} \] Fin. Le théorème des 4 couleurs fut d'abord conjecturer en 1852 par Francis Guthrie intéressé par la coloration de la carte d'Angleterre : il est possible, en n'utilisant que quatre couleurs différentes, de colorier n'importe quelle carte découpée en régions, de sorte que deux régions adjacentes, c'est-à-dire ayant toute une frontière (et non simplement un point) en commun reçoivent toujours deux couleurs distinctes. Presque 30 ans plus tard une preuve est publié mais on se rendra compte 10 après qu'elle est fausse et qu'elle prouve plutôt un théorème des 5 couleurs. Il faudra attendre 1976 et l'avènement de l'ère informatique pour qu'une preuve sérieuse soit publié par deux Américains, Kenneth Appel et Wolfgang Haken. Leur preuve consiste à diviser le problème des 4 couleurs en 1478 problèmes que l'on peut résoudre par ordinateur (et 1200 heures de calcul). A l'époque leur démonstration partageait la communauté scientifique : quel crédit accorder à une preuve réalisée par ordinateur ? Aujourd'hui il n'existe toujours aucune preuve de ce théorème n'utilisant pas l'outil informatique.

---

¹Toi aussi ! Invente des mots !