Application du théorème des quatre couleurs

8

Je lisais le théorème des quatre couleurs et je me demande s'il y a une application pratique. (Je ne pense pas que séparer la carte en quatre couleurs différentes puisse être considéré comme une application.)

J'ai essayé Google pour les applications mais je n'en ai pas trouvé.

graph-theory colorings Ballot d'ordinateur
la source
Puisqu'on savait que cinq couleurs suffisent (avec une simple preuve), la vraie question est: quelle application bénéficie du fait que quatre couleurs plutôt que cinq suffisent.
Yuval Filmus
La coloration des cartes n'est sans doute pas une application, car le théorème ne permet pas de territoires déconnectés. Par exemple, l'Alaska, Hawaï et le continent américain doivent tous être de la même couleur. La possibilité de territoires déconnectés signifie que le graphique correspondant à une carte n'est pas nécessairement planaire: en effet, tout graphique avec arêtes peut être réalisé en ayant îles telles que les pays et partagent une île si est une arête dans le graphique. Je ne me souviens pas si la carte du monde réelle est à 4 couleurs; c'est probablement le cas. mmjejjej
David Richerby

Réponses:

7

L'une des applications les plus remarquables du théorème des 4 couleurs concerne les mâts de téléphonie mobile. Ces mâts couvrent tous certaines zones avec un certain chevauchement, ce qui signifie qu'ils ne peuvent pas tous transmettre sur la même fréquence. Une méthode simple pour s'assurer que deux mâts qui se chevauchent n'ont pas la même fréquence consiste à leur donner à tous une fréquence différente. Mais, comme le gouvernement possède toutes les fréquences et facture pour chacune, on veut utiliser le nombre minimum de fréquences possible. Les zones couvertes peuvent être dessinées sous forme de carte et les différentes fréquences peuvent être représentées sous forme de couleurs.

Raaman Nair
la source
En d'autres termes, en supposant qu'une coloration quatre puisse être trouvée efficacement, il vous suffit de réserver quatre fréquences à l'avance même si l'emplacement exact des mâts est inconnu (ou pourrait même changer).
Yuval Filmus
1
Est-ce vraiment vrai? Le graphique n'est pas garanti d'être plan (cinq mâts assez proches les uns des autres induiront un sous-graphique ), il n'est donc pas garanti qu'il soit à quatre couleurs. K5
David Richerby
@YuvalFilmus Les graphes planaires peuvent être quadrichromes en temps quadratique: Robertson, Sanders, Seymour et Thomas, "Efficiently four-colouring graph graphes", Proc. STOC 1996 ( PDF ).
David Richerby
En fait, permettez-moi de revenir et de faire une déclaration plus forte. Ce n'est pas vrai, précisément parce que cinq mâts étroitement placés donnent un . En fait, ceci est une application du fait qu'il existe un algorithme polynomial de temps pour calculer le nombre chromatique de graphes de disques unitaires , qui ne sont pas nécessairement planaires et ne sont pas nécessairement à 4 couleurs. K5
David Richerby
3

Les problèmes de coloration des graphiques sont largement applicables au problème de planification.

Considérez une université, où vous essayez de planifier des horaires pour tous les examens finaux. Certains étudiants suivent plusieurs cours, vous devez donc vous assurer qu'ils n'ont pas deux examens programmés en même temps. Cependant, vous souhaitez que votre période de rédaction des examens soit aussi courte que possible, afin d'exécuter autant d'examens simultanément que possible.

Vous pouvez représenter cela comme un problème de coloration graphique: vous faites où chaque classe est un sommet et une arête entre les sommets chaque fois que deux classes contiennent le même élève. Vos couleurs représenteront différentes plages horaires d'examen. Le nombre minimum avec lequel vous pouvez colorier ce graphique est le plus petit nombre de plages horaires dont vous avez besoin pour passer tous vos examens.g=(V,E)

Le problème en général est NP difficile, mais si vous aviez une certaine connaissance de votre emploi du temps, disons qu'il était planaire, alors vous pourriez appliquer le théorème des 4 couleurs pour écrire tous les examens ensemble.

Je ne suis pas sûr à 100% que vous obtiendriez un graphique planaire dans un problème de planification réel, mais il y a une leçon plus large ici: les graphiques sont largement applicables à des choses qui ne sont pas immédiatement évidentes. Le théorème à 4 couleurs ne concerne pas seulement les graphiques et les cartes, il peut être utilisé pour modéliser des problèmes réels dans lesquels vous exprimez un ensemble d'objets et des relations binaires entre ces objets.

jmite
la source
1
Il semble relativement peu probable que vous obteniez un graphique planaire dans un problème de planification, car, comme vous le dites, cela vous permettrait de tout résoudre en utilisant seulement quatre emplacements. (Par exemple, dans l'exemple spécifique que vous donnez, le graphique n'est pas planaire s'il y a un seul étudiant prenant cinq classes.)
David Richerby
-3

oui graphe planaire -coloration faible / fixes a des applications minimales, principalement coloration de la carte plane. cependant -coloring pour arbitraire est NP complet , c'était l'un des 1 er problèmes prouvés NP complet, se liant ainsi à l'édifice massif de la théorie. mais en fait, même la coloration peut être réduite à une coloration 3 via une transformation de base. [1] donc coloration pour est NP terminée (mais non limitée aux graphes planaires) . il y a probablement d'autres réductionsnnnnnnn≥3aux cartes à 4 couleurs et planaires étudiées dans la littérature. c'est-à-dire pour avoir une meilleure idée de son importance, il faudrait étudier les réductions possibles, qui est un sujet complexe / avancé / plus large.

mais un autre angle est que la question de la 4-coloration d'une carte / graphique planaire a été un problème ouvert difficile en mathématiques / informatique pendant de nombreuses décennies (en fait plus de 1½ siècle , et l'un des premiers problèmes de graphique très avancés). les mathématiques progressent en résolvant des problèmes non résolus. il s'inscrit dans un schéma de base commun de "problèmes faciles à énoncer mais les solutions / preuves étaient inaccessibles pendant longtemps et sont très complexes". il s'agit d'une asymétrie fondamentale répandue en mathématiques qui montre les limites de l' effet de levier mathématique / théorique .

les techniques qui s'avèrent efficaces peuvent être appliquées à d'autres problèmes non résolus et parfois ouvrir de nouvelles perspectives / abstractions théoriques / conceptuelles. des preuves parfois remarquables sont précieuses en elles-mêmes et le théorème des 4 couleurs correspond à cette catégorie. c'est l'une des premières preuves théoriques automatisées les plus sophistiquées. des travaux supplémentaires ont été effectués pour améliorer les simplifications lisibles par l'homme depuis sa découverte et ont provoqué un choc relatif dans la communauté théorique lors de son annonce, et ont suscité une analyse et des commentaires beaucoup plus approfondis. il sert de référence clé / jalon / cas de test pour des améliorations dans la démonstration automatisée des théorèmes .

[1] 3 coloration est NP terminée

vzn
la source
1
C'est probablement une bonne idée d'utiliser un symbole différent de n pour désigner le nombre de couleurs, puisque ndénote souvent la cardinalité de l'ensemble de sommets. De plus, nous ne savons pas comment tracer des graphes planaires à 3 couleurs en temps polynomial.
Juho