Kvarkolormapa teoremo
La kvarkolormapa teoremo (aŭ la teoremo pri kvar koloroj) estas (jam pozitive solvita) problemo el teorio de grafeoj, kiu temas pri tio, ĉu sufiĉas kvar koloroj por kolorigi ajnan politikan mapon tiel, ke neniuj du najbarantaj ŝtatoj estu kolorigitaj per la sama koloro. (Kiel najbaraj ŝtatoj estas konsiderataj tiaj, kiuj havas komunan limlinion, t.e. ili ne najbaras komune nur en unu punkto.) Pli ĝenerale eblas demandi al minimuma bezonata nombro de koloroj, sed relative facile eblas pruvi, ke kvin koloroj sufiĉas. Kontraŭe la aserto, ke kvar koloroj sufiĉas, rezistis longan tempon al ĉiuj provoj por pruvi tion, sed ankaŭ neniu kapablis trovi mapon, kiu estas kontraŭekzemplo.
La teoremon pruvis nur en la jaro 1976 la usona matematikisto Kenneth Appel kaj la germana matematikisto Wolfgang Haken per tio, ke helpe de komputila programo ili modelis 1936 eblajn konfigurojn, pruvis, ke tiuj ĉi konfiguroj kovras ĉiujn eblecojn, kaj montris ĉe ĉiu el ili, ke por kolorigi ĝin sufiĉas kvar koloroj (ĝi bezonis por tio 1200 horojn de procesora tempo). Kelkaj matematikistoj rifuzis 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 grafeoj
[redakti | redakti fonton]Tiu ĉi problemo en la teorio de grafeoj estas formale prezentata tiel, ke celo estas kolorigo de pintoj de ebena grafeo 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.
La problemon eblas ĝeneraligi ankaŭ al aliaj grafeoj 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 grafeo) egaleco
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. grafeo de Franklin).
Eksteraj ligiloj
[redakti | redakti fonton]- El historio de matematiko kaj fiziko (3)
- Problemo de kvar koloroj en enciklopedio MathWorld angle