Applications de la théorie des graphes
Graphes planaires
Un graphe G est dit plan s'il peut être représenté sur un plan de telle manière que les sommets sont tous des points distincts, les arêtes sont de simples courbes et il n'y a pas deux arêtes qui se rencontrent sauf à leurs bornes. Par exemple, K 4, le graphique complet sur quatre sommets, est plan, comme le montre la figure 4A.
On dit que deux graphes sont homéomorphes si les deux peuvent être obtenus à partir du même graphe par subdivisions d'arêtes. Par exemple, les graphiques de la figure 4A et de la figure 4B sont homéomorphes.
Le graphique K m, n est un graphique pour lequel l'ensemble de sommets peut être divisé en deux sous-ensembles, l'un avec m sommets et l'autre avec n sommets. Deux sommets du même sous-ensemble ne sont pas adjacents, tandis que deux sommets de sous-ensembles différents sont adjacents. Le mathématicien polonais Kazimierz Kuratowski en 1930 a prouvé le célèbre théorème suivant:
Une condition nécessaire et suffisante pour qu'un graphe G soit plan est qu'il ne contienne pas de sous-graphe homéomorphe à K 5 ou K 3,3 montré sur la figure 5.
Une contraction élémentaire d'un graphe G est une transformation de G en un nouveau graphe G 1, de telle sorte que deux sommets adjacents u et υ de G sont remplacés par un nouveau sommet w dans G 1 et w est adjacent dans G 1 à tous les sommets à où u ou υ est adjacent dans G. Un graphe G * est dit être une contraction de G si G * peut être obtenu à partir de G par une séquence de contractions élémentaires. Ce qui suit est une autre caractérisation d'un graphe planaire due au mathématicien allemand K. Wagner en 1937.
Un graphe est plan si et seulement s'il n'est pas contractable à K 5 ou K 3,3.
Le problème de la carte en quatre couleurs
Pendant plus d'un siècle, la solution du problème de la carte en quatre couleurs a échappé à tous les analystes qui l'avaient tenté. Le problème a peut-être attiré l'attention de Möbius, mais la première référence écrite à ce problème semble être une lettre d'un Francis Guthrie à son frère, un élève d'Auguste De Morgan, en 1852.
Le problème concerne les cartes planaires, c'est-à-dire les subdivisions du plan en régions sans chevauchement délimitées par de simples courbes fermées. Dans les cartes géographiques, il a été observé empiriquement, dans autant de cas particuliers qui ont été essayés, que, au plus, quatre couleurs sont nécessaires pour colorer les régions de sorte que deux régions qui partagent une frontière commune soient toujours colorées différemment, et dans certains cas où au moins quatre couleurs sont nécessaires. (Les régions qui ne se rencontrent qu'en un point, comme les États du Colorado et de l'Arizona aux États-Unis, ne sont pas considérées comme ayant une frontière commune). Une formalisation de cette observation empirique constitue ce qu'on appelle «le théorème des quatre couleurs». Le problème est de prouver ou d'infirmer l'affirmation que c'est le cas pour chaque carte planaire. Que trois couleurs ne suffiront pas est facilement démontré, alors que la suffisance de cinq couleurs a été prouvée en 1890 par le mathématicien britannique PJ Heawood.
En 1879, AB Kempe, un Anglais, proposa une solution au problème des quatre couleurs. Bien que Heawood ait montré que l'argument de Kempe était erroné, deux de ses concepts se sont avérés fructueux lors d'une enquête ultérieure. L'une d'elles, appelée inévitabilité, énonce correctement l'impossibilité de construire une carte dans laquelle chacune des quatre configurations est absente (ces configurations consistent en une région avec deux voisins, une avec trois, une avec quatre et une avec cinq). Le deuxième concept, celui de réductibilité, tire son nom de la preuve valable de Kempe que s'il existe une carte qui nécessite au moins cinq couleurs et qui contient une région avec quatre (ou trois ou deux) voisins, alors il doit y avoir une carte nécessitant cinq couleurs pour un plus petit nombre de régions. La tentative de Kempe de prouver la réductibilité d'une carte contenant une région avec cinq voisins était erronée, mais elle a été rectifiée dans une preuve publiée en 1976 par Kenneth Appel et Wolfgang Haken des États-Unis. Leur preuve a suscité quelques critiques car elle a nécessité l'évaluation de 1 936 cas distincts, chacun impliquant jusqu'à 500 000 opérations logiques. Appel, Haken et leurs collaborateurs ont conçu des programmes qui ont permis à un grand ordinateur numérique de gérer ces détails. L'ordinateur a nécessité plus de 1 000 heures pour effectuer la tâche, et la preuve formelle qui en résulte fait plusieurs centaines de pages.
Cycles eulériens et problème du pont de Königsberg
Un multigraphe G est constitué d'un ensemble non vide V (G) de sommets et d'un sous-ensemble E (G) de l'ensemble de paires non ordonnées d'éléments distincts de V (G) avec une fréquence f ≥ 1 attachée à chaque paire. Si la paire (x 1, x 2) de fréquence f appartient à E (G), alors les sommets x 1 et x 2 sont joints par f arêtes.
Un cycle eulérien d'un multigraphe G est une chaîne fermée dans laquelle chaque arête apparaît exactement une fois. Euler a montré qu'un multigraphe possède un cycle eulérien si et seulement s'il est connecté (en dehors des points isolés) et que le nombre de sommets de degré impair est soit zéro soit deux.
Ce problème est d'abord apparu de la manière suivante. La rivière Pregel, formée par la confluence de ses deux branches, traverse la ville de Königsberg et coule de chaque côté de l'île de Kneiphof. Il y avait sept ponts, comme le montre la figure 6A. Les citadins se sont demandé s'il était possible de se promener et de traverser chaque pont une seule fois. Cela revient à trouver un cycle eulérien pour le multigraphe de la figure 6B. Euler a montré que c'était impossible car il y avait quatre sommets d'ordre impair.
