Kvarkolormapa teoremo

Politika mapo kolorigita per kvar koloroj

Teoremo kun kvar koloroj aŭ ankaŭ problemo de kvar koloroj estas (jam pozitive solvita) problemo el teorio de grafoj, kiu sonas: "Ĉu sufiĉas kvar koloroj por kolorigi libervolan politikan mapon tiel, por ke neniaj du najbarantaj ŝtatoj estu kolorigitaj per la sama koloro?" (Kiel najbaraj ŝtatoj estas konsiderataj tiaj, ke ili havas komunan limlinion, t.e. ili ne najbaras komune nur en unu punkto.) Pli ĝenerale eblas demandi al minimuma bezonata nombro de koloroj, sed proporcie facile eblas pruvi, ke kvin koloroj sufiĉas. Kontraŭ tio la aserto, ke kvar koloroj sufiĉas, rezistis longan tempon al ĉiuj provoj por pruvi tion, sed ankaŭ neniu kapablis trovi mapon, kiu repuŝus tion.

La teoremon pruvis nur en la jaro 1976 usonaj matematikistoj Kenneth Appel kaj Wolfgang Haken per tio, ke helpe de komputila programo ili modelis 1936 eblajn konfigurojn, ili pruvis, ke tiuj ĉi konfiguroj kovras ĉiujn eblecojn, kaj ili montris ĉe kiu el ili, ke por kolorigi ĝin sufiĉas kvar kolorojn (ĝi bezonis por tio 1200 horojn de procesora tempo). Sed granda parto de matematikistoj rifuzas akcepti tiun ĉi pruvon, ĉar neniu matematikisto kapablas rekte verkontroli ĝin. (Ekde tiu tempo la pruvo estis multfoje sendepende ripetita kaj simpligita fare de pluaj matematikistoj helpe de aliaj programoj, sed "bela" pruvo konvena por homo ne estis trovita.)

Formulado en teorio de grafoj

Tiu ĉi problemo en la teorio de grafoj estas formale prezentata tiel, ke celo estas kolorigo de pintoj de ebena grafo tiel, ke neniaj du pintoj kunigitaj per eĝo havu la saman koloron. Oni ŝanĝos la formuladon kun la mapo al tiu ĉi versio tiel, ke oni alvicigos al ĉiu ŝtato unu pinton (ekz. la ĉefurbo) kaj per eĝo oni kunigos tiujn ĉi pintojn, kies ŝtatoj havas la komunan limon.

Ŝanĝo de mapo al ebena grafo

La problemon eblas ĝeneraligi ankaŭ al aliaj grafoj sur alia surfaco ol en ebeno, ekz. mapo bildigita sur globo havas tiurilate la samajn ecojn kiel ebena mapo. Ĉe fermitaj surfacoj kun genro g indikas nombron de sufiĉaj koloroj (la t.n. kromata numero de grafo) egaleco

$\gamma (g)=\left\lfloor {\frac {7+{\sqrt {48g+1}}}{2}}\right\rfloor$

kie eksteraj citiloj markas rondigon al la plej proksima pli malgranda entjero. Tiu ĉi formulo estas markata kiel hipotezo de Heawood. La fakto, ke tiu ĉi nombro de koloroj estas la plej malalta ebla, pruvis por ĉiuj surfacoj escepte de botelo de Klein kaj globo (kaj ebeno) en la jaro 1968 Gerhard Ringel kaj J. T. W. Youngs. Post la pruvo de la problemo kun kvar koloroj restas unusola escepto la botelo de Klein, kiu havas genron 1, sed ĝi postulas 6 kolorojn (kion pruvas la t.n. grafo de Franklin).

Eksteraj ligiloj

• El historio de matematiko kaj fiziko (3)
• Problemo de kvar koloroj en enciklopedio MathWorld (angle)