RANGI NNE KWA RAMANI YOYOTE, ZIKIPATIKANA KWA MUDA WA MSTARI

Ramani yoyote iliyochorwa kwenye karatasi bapa inaweza kupakwa rangi nne ili nchi jirani zisiwahi kushiriki rangi moja. Francis Guthrie alikisia hivyo mwaka 1852; Appel na Haken walilithibitisha mwaka 1976. Lakini nadharia hiyo inasema tu kwamba rangi nne zipo. Unazipataje kwa ramani fulani? “Hakuna jibu rahisi,” wanaandika Yuta Inoue, wa University of Tokyo, na wenzake watano kutoka Japani, Kanada, Slovenia na Denmark. Suala hili limekuwa tata kiasi kwamba limesababisha mifano-kinzani mingi iliyopendekezwa.

Vitone, mistari na pembetatu

Kila nchi inakuwa kitone, au kipeo (vertex), na kila mpaka unaoshirikiwa unakuwa mstari, au ukingo (edge): ramani inakuwa grafu bapa (planar graph), iliyochorwa bila mistari kukatana. Kuipaka rangi kunamaanisha kumpa kila kipeo moja ya rangi nne, tofauti katika ncha mbili za kila ukingo. Iite n idadi ya vipeo. Inatosha kushughulikia pembetatuo (triangulations), ambapo kila uso ni pembetatu: kingo zaidi hufanya tu upakaji rangi kuwa mgumu zaidi.

Ubadilishanaji wa Kempe

Hatua ya msingi inarudi kwenye makala ya 1879 ya A. B. Kempe. Ziweke rangi nne katika jozi, tuseme nyekundu na buluu, na kijani na njano. Mnyororo wa Kempe (Kempe chain) ni kundi lililounganika la vipeo vinavyovaa rangi mbili za jozi moja. Kubadilishana rangi hizo mbili kote kwenye mnyororo mzima huhifadhi upakaji rangi ukiwa halali.

Chukua kipeo v chenye majirani wanne, v0 hadi v3 kwa mpangilio kukizunguka, na upake rangi vilivyobaki kwanza. Ikiwa majirani wanatumia rangi tatu au chache, v inachukua ile iliyo huru. Ikiwa wanatumia zote nne, fuata mnyororo unaoanzia v0 katika rangi za v0 na v2. Ikiwa haufiki v2, ubadilishe: v0 inachukua rangi ya v2, na kuacha moja huru kwa ajili ya v. Ikiwa unafika v2, badala yake badilisha mnyororo wa v1 katika rangi za v1 na v3, ili v1 ichukue rangi ya v3.

Vipande vinavyoweza kurekebishwa daima

Uthibitisho wa nadharia hiyo unategemea mipangilio inayopunguzika (reducible configurations): mifumo midogo inayoweza kukatwa, kisha kurudishwa mara vilivyobaki vikishapakwa rangi. Ikiwa rangi za pete (ring) yao — vipeo vilivyo karibu kuizunguka — hazilingani, idadi yenye kikomo ya mabadiliko ya Kempe yanayoboresha yanayofanywa nje daima huzirekebisha: si zaidi ya 25 kwa mifumo inayotumiwa hapa, ambayo pete zake zina vipeo 18 au chache.

Grafu ndogo ya vitone saba vilivyoandikwa namba, na grafu hiyo hiyo ikiwa imezungukwa na wavu mkubwa zaidi wa pembetatu.

Mpangilio unaopunguzika (kushoto; kila namba ni idadi ya majirani ambayo kipeo hicho lazima kiwe nayo katika ramani kamili) na mfumo huo huo ukikamilishwa na pete yake R (kulia). — Kielelezo 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour na Thomas walionyesha mwaka 1997 jinsi ya kupaka rangi kwa njia hii, mfumo mmoja kwa wakati. Kila mzunguko hupunguza grafu kwa vipeo vichache na hugharimu kupitia grafu nzima, hivyo muda ni wa kipeo cha pili (quadratic): mara nne zaidi kwa ramani yenye ukubwa mara mbili.

Katika makala iliyotangulia (FOCS’26), waandishi hao hao sita walithibitisha kwamba kila pembetatuo ina idadi ya mipangilio inayopunguzika isiyogusana inayolingana na n, ikichukuliwa kutoka orodha ya 8,202 — au idadi kama hiyo ya mizunguko mifupi yenye vipeo pande zote mbili, ambayo pia husaidia. Wanaondoa mifumo yote kwa wakati mmoja, wanapaka rangi vilivyobaki, kisha wanarekebisha kila pete kwa pamoja. Badiliko la Kempe la nasibu husaidia pete fulani ikiwa linachagua mpangilio sahihi wa jozi za rangi (nafasi moja katika tatu) na matokeo sahihi ya kurusha sarafu kwenye kila mnyororo unaogusa pete (nafasi moja katika mbili kwa kila mmoja). Kwa minyororo hadi 18 kama hiyo, hiyo ni angalau nafasi moja katika 3 × 2¹⁸, yaani 786,432: ndogo, lakini isiyobadilika. Kwa hiyo idadi ya mizunguko hukua tu kama log n, takriban idadi ya mara n inavyoweza kugawanywa kwa mbili. Lakini badiliko moja linaweza kuhusisha sehemu isiyobadilika ya grafu: kila moja hugharimu kupitia grafu nzima, n log n kwa jumla.

Jedwali badala ya kupitia yote

Makala mpya inahifadhi mabadiliko log n lakini inafanya kila moja kuwa nafuu zaidi. Baada ya maandalizi yanayochukua muda unaolingana na n, kila badiliko hupatikana na kutekelezwa kwa takriban hatua n / log n kwa wastani. Mabadiliko log n kwa pamoja kisha huchukua muda unaolingana na n — muda wa mstari (linear time) — kikomo ambacho waandishi wanakiita bora kabisa.

Mbinu ni ile ya “Method of Four Russians” (Mbinu ya Warusi Wanne). Tatizo dogo linaloingia katika msimbo wa biti ½ log n — nusu ya tarakimu za mfumo wa jozi zinazohitajika kuandika n — lina matoleo yanayowezekana √n tu, si zaidi, hivyo majibu yao yote yanaweza kukokotolewa mapema na kuhifadhiwa katika jedwali. Kompyuta inayodhaniwa, yenye maneno ya kumbukumbu ya takriban biti log n, husoma jibu lolote lililohifadhiwa kwa hatua moja.

Grafu hukatwa, tena na tena, kuwa maeneo yaliyo ndani ya mengine yenye mipaka mifupi. Madogo kabisa yana takriban vipeo log n na yanaingia, rangi zikiwemo, katika msimbo mmoja. Kwa kila eneo, grafu ndogo ya muhtasari hurekodi ni vipeo vipi vya mpakani vinavyoshiriki mnyororo wa Kempe. Badiliko kisha hushuka kama mfuatano wa biti za “badilisha” au “acha”, na katika kila eneo dogo utafutaji mmoja kwenye jedwali husasisha kila rangi.

Grafu iliyopakwa rangi yenye vitone vyekundu, buluu, kijani na njano, ikiwa na eneo la kijivu lililozungushiwa mstari na baadhi ya kingo zilizochorwa kwa mistari minene myeusi.

Sehemu ya grafu iliyopakwa rangi nne. Eneo la kijivu ni eneo R; kingo nene nyeusi ni za minyororo ya Kempe ya jozi nyekundu-buluu na kijani-njano. — Kielelezo 2, Inoue et al. (2026), arXiv:2610.39753.

Mzunguko ule ule wa eneo, vitone vyake vya mpakani vikiunganishwa na madoa machache ya buluu hafifu kwa mistari myembamba ya buluu.

Muhtasari wa eneo hilo hilo: kila doa la buluu linawakilisha kipande cha mnyororo wa Kempe, na mistari yake inaonyesha ni vipeo vipi vya mpakani inavyoviunganisha. — Kielelezo 3, Inoue et al. (2026), arXiv:2610.39753.

Kuchagua bila kete

Kwa uchaguzi wa nasibu, hii tayari inapaka rangi ramani kwa muda wa mstari kwa wastani. Kuondoa kete bila kupoteza kasi ilikuwa “sehemu yenye changamoto kubwa zaidi kwa mbali”. Iite pete hai ilimradi kila uamuzi hadi sasa umeenda upande wake. Ikiwa minyororo u isiyoamuliwa inayoigusa ingeachiwa kurusha sarafu, ingesalimika kwa uwezekano wa 1/2^u; zikijumlishwa kwa pete zote hai, namba hizi hutoa idadi inayotarajiwa ya zinazosalimika. Kuamua mnyororo huongeza maradufu sehemu ya kila pete iliyotaka chaguo hilo na huzifanya nyingine kuwa sifuri. Algorithimu huchukua chaguo linalozuia jumla isishuke, ili mwishowe pete zilizosaidiwa ziwe angalau nyingi kama ambavyo bahati ingezisaidia kwa wastani.

Kikomo, si saa ya kupimia

Makala haiiripoti utekelezaji wowote wala muda wa kuendesha, na vigezo visivyobadilika vilivyofichwa katika “inayolingana na n” havijatolewa. Ni vikubwa: kwa kila moja ya mifumo 8,202, algorithimu huhifadhi ni mabadiliko mangapi yanayoboresha kila upakaji rangi wa pete yake unahitaji — “kiasi kikubwa mno, kisichobadilika, cha taarifa”. Katika kiambatisho, pia wanarekebisha “kosa dogo” katika ujenzi wa 2013 wa maeneo yaliyo ndani ya mengine wanaoujengea juu yake. Dhana iliyotolewa mwaka 1852 sasa inakuja na utaratibu wa kupaka rangi ambao gharama yake haikui haraka zaidi ya ramani inayoipaka rangi.