Coloriage de graphes
Définition
Soit \( \G\) un graphe non orienté. Le nombre chromatique de \( \G\) , noté \( X(\G)\) , est le plus petit nombre de couleur différentes nécessaire pour colorier les sommets de \( \G\) de telle sorte qu'une même couleur ne soit pas attribuée à deux sommets adjacents.
Proposition
Soient \( \G\) et \( \G'\) des graphes non orientés et \( n\in \N_{{>}0}\)
- \( (i)\)
- Si \( \G'\subset \G\) alors \( X(\G')\leqslant X(\G)\) .
- \( (ii)\)
- \( X(\Kk_n)=n\) .
- \( (iii)\)
- \( X(\Cc_n)=2\) .
- \( (iv)\)
- \( X(\Zz_n)=\left\{\begin{array}{rl}
2&\text{si } n \text{ est pair,}\\
3&\text{sinon.}
\end{array}\right.\)
- \( (v)\)
- \( X(\Ss_n)=1\) .
Démonstration
Exercice.
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.
§ Algorithme de Brélaz
1. Initialisation
Pour chaque sommet x
DSAT[x] = degré de x
Fin pour
2. Itérations
Tant que il existe des sommets non coloriés
Pour chaque sommet x non colorié
Si aucun voisin de x n'est colorié
DSAT(x) = degré de x = nombre de voisin de x.
sinon
DSAT(x) = nombre de sommet adjacent de x qui sont coloriés.
Fin si
Fin pour
On choisit un sommet x non colorié tel que DSAT(x) soit le plus grand.
Si il y a conflit, on choisit le sommet qui a en plus le degré maximal.
On colorie le sommet avec la plus petite couleur possible.
Fin tant que
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.
Définition
On appelle graphe planaire tout graphe non orienté pouvant être dessiné
sur un plan de telle sorte que les sommets soient des points distincts, et que les arêtes ne se rencontrent pas en dehors de leurs extrémités (les arêtes pouvant être représentées par des courbes).
\[
\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&}
\]
Définition
On dira que deux graphes non orienté sont homéomorphes si l'on peut passer de l'un à l'autre en divisant des arêtes à l'aide de sommet supplémentaire.
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.
Théorème [(Kuratowski)]
Un graphe non orienté est non planaire si et seulement s'il possède un sous-graphe homéomorphe à
\[
\xymatrix@R=1cm@C=0.5cm{
&&\bullet\ar@{-}[rdd]\ar@{-}[ldd]\ar@{-}[rrd]\ar@{-}[lld]&&\\
\bullet\ar@{-}[rd]\ar@{-}[rrrr]\ar@{-}[rrrd]&&&&\bullet\ar@{-}[ld]\\
&\bullet\ar@{-}[rrru]\ar@{-}[rr]&&\bullet&
}
\]
\[\Kk_5\]
\[
\xymatrix@R=2cm@C=2cm{
\bullet\ar@{-}[d]\ar@{-}[dr]\ar@{-}[drr]&\bullet\ar@{-}[d]\ar@{-}[dl]\ar@{-}[dr]&\bullet\ar@{-}[d]\ar@{-}[dll]\ar@{-}[dl]\\
\bullet&\bullet&\bullet
}
\]
\[\Kk_{3,3}\]
Il existe une caractérisation plus faible des graphes planaires.
Proposition
Pour tout graphe planaire \( \G\) connexe possédant plus de \( 3\) sommets,
\[\Ar(\G)\leqslant 3\Som(\G)-6\]
Voici un algorithme permettant, assez souvent, de planarifier
1 un graphe.
§ Algorithme de planarification.
n = le nombre d'intersection entre les arêtes de G.
Tant que n{>}0
Pour chaque sommet x de G
di(x) = le nombre d'intersection que compte les arêtes issues de x.
Fin pour
x = le sommet tel que di(x) est maximal.
x' = l'isobarycentre des voisins de x.
G' = le graphe G ou l'on a déplacer le sommet x en x'.
n' = le nombre d'intersection entre les arêtes de G'.
Si x=x'
Fin de l'algorithme
Fin si
Si n' {<} n
Remplacer G par G' et n par n'
Fin si
Fin tant que
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.
Théorème [(Théorème des 4 couleurs)]
Pour tout graphe planaire \( \G\) ,
\[X(\G)\leqslant 4\]
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.
1Toi aussi ! Invente des mots !