FUMBO LA GRAFU LA MIAKA YA 1960 HATIMAYE LATATULIWA

Chukua nukta kadhaa na uunganishe baadhi ya jozi zake kwa mistari: wanahisabati huita hii grafu, nukta zake vipeo (vertices) na mistari yake kingo (edges). Mzunguko (cycle) ni kitanzi kilichofungwa kinachotembelea vipeo tofauti na kurudi mwanzo wake. Swali la kawaida ni kama kingo za grafu zinaweza kugawanywa — kila ukingo ukitumika mara moja tu — kuwa mizunguko.

Jibu limejulikana kwa muda mrefu, kama makala inavyokumbusha: inawezekana pale tu kila kipeo kinapogusa idadi shufwa ya kingo. Grafu kama hizo huitwa grafu za Euler (Eulerian). Swali linalofuata ni mizunguko mingapi inahitajika. Na kwa grafu ambazo mizunguko pekee haitoshi, kingo za peke yake pia zinaruhusiwa kama vipande.

Dhana

Katika miaka ya 1960, Erdős na Gallai walikisia kuwa kingo za kila grafu yenye vipeo n zinaweza kugawanywa kuwa idadi ya mizunguko na kingo za peke yake isiyozidi kiasi kinacholingana na n — huandikwa O(n). Erdős aliliweka katika mikusanyiko yake kadhaa ya matatizo yasiyotatuliwa. Dhana inayohusiana ya Hajós inauliza mizunguko isiyozidi (n − 1)/2 katika kila grafu ya Euler.

Mstari (linear) ndio bora zaidi ambacho mtu angeweza kutumaini: Erdős alionyesha kuwa baadhi ya grafu zinahitaji takriban vipande 1.5 n. Swali lilikuwa kama kisiobadilika fulani mara n kinatosha kila mara.

Miaka hamsini ya vikomo vinavyosogea polepole

Erdős na Gallai wenyewe waliona njia rahisi: kuondoa mara kwa mara mzunguko mrefu zaidi. Inatoa takriban vipande n log n — na, kulingana na makala, hicho kilibaki kuwa kikomo bora cha jumla kwa karibu miaka hamsini. Hivi karibuni zaidi, Conlon, Fox na Sudakov walikishusha hadi n log log n, kisha Bucić na Montgomery hadi n log* n, ambapo log* n — idadi ya mara ambazo mtu lazima achukue logariti ili kushuka chini ya moja — hukua polepole kupita kiasi cha kufikirika. Mbinu hizi zilifanya kazi kwa awamu, na kila awamu iligharimu takriban mizunguko n, kwa hiyo idadi ya awamu kila mara ilijipenyeza katika hesabu ya mwisho. Dhana hiyo pia ilikuwa imethibitishwa kwa familia maalum, kama grafu nasibu.

Uzito unaolipia vitanzi

Jaehoon Kim, wa KAIST nchini Korea Kusini, sasa anaithibitisha dhana hiyo: kuna kisiobadilika maalum C ambacho kila grafu yenye vipeo n hugawanyika kuwa mizunguko na kingo zisizozidi Cn. Kama tokeo, dhana ya Hajós ni kweli hadi kipengele kisichobadilika.

Uthibitisho unaacha awamu. Utaratibu mmoja huondoa mizunguko na kingo moja baada ya nyingine, na jumla hudhibitiwa na viwango viwili ambavyo kila kimoja hubaki chini ya kisiobadilika mara n.

Uwezo unaotegemea digrii. Kila kipeo hupewa uzito unaopungua kadiri idadi ya kingo zake inavyoongezeka, takriban 1 / (digrii × log² digrii). Mzunguko ni mzito ikiwa uzito wa vipeo vyake unajumlisha angalau 1. Kuondoa mzunguko mzito hupunguza “uwezo” (potential) wa jumla kwa angalau 1, na uwezo huo huanza ukiwa si zaidi ya kisiobadilika mara n. Kwa hiyo mizunguko mizito inaweza kuondolewa mara O(n) tu.
Idadi ya vipeo. Pale ambapo hakuna mzunguko mzito uliobaki, grafu ni “nyepesi” — na nadharia kuu mpya inaonyesha kuwa grafu nyepesi yenye digrii kubwa lazima iwe na eneo zito, lililokaribia kufungika. Eneo hilo hugawanywa kuwa idadi ya mizunguko na kingo inayolingana na ukubwa wake, na baada ya hapo angalau sehemu moja ya hamsini ya vipeo vyake hubaki na kingo zisizozidi mbili na kutoka kabisa. Kwa kuwa kila kipeo kinaweza kutoka mara moja tu, sehemu hii pia hugharimu O(n).

Mchoro wa njia tatu zilizounganishwa kuwa mzunguko mmoja kupitia maeneo matatu ya expander yaliyotiwa kivuli, pamoja na njia za kuunganisha za vistari vya rangi.

Ndani ya sehemu zenye msongamano za grafu, vipande vya njia hufungwa kuwa mzunguko mmoja kwa njia za kuunganisha zinazopitishwa kupitia “expanders”; upakaji rangi nasibu huweka njia za kuunganisha za mzunguko mmoja mbali mbali. — Kielelezo 3, Kim (2026), arXiv:2610.07840.

Ili kugawanya maeneo hayo yenye msongamano, uthibitisho unapanua zana za Bucić na Montgomery za “expanders” imara — grafu ambazo kila seti ya vipeo ina majirani wengi — na kupaka vipeo rangi kwa nasibu ili njia zinazounganisha za mzunguko mmoja zisigongane kamwe.

Kisichotatuliwa bado

Kisiobadilika C ni kikubwa mno, na mwandishi hakujaribu kukiboresha. Kupata kisiobadilika bora zaidi — angalau 1.5 — bado ni swali wazi, kama ilivyo kwa dhana kamili ya Hajós na dhana inayohusiana ya Gallai kuhusu kugawanya grafu kuwa njia. Mbinu ya uzito inahitaji tu uzito ambao jumla yake inakaribia kikomo (converges), na mwandishi anapendekeza inaweza kutumika katika matatizo mengine ya ugawanyaji.

Hili ni chapisho la awali la mwandishi mmoja, ambalo bado halijakaguliwa na wataalamu wenzake.

Mgongano wa maslahi. Mwandishi anaeleza kuwa alitumia kwa kiasi kikubwa ChatGPT (OpenAI) na Claude (Anthropic) katika kuendeleza hoja na kuandaa maandishi na vielelezo, na kwamba alihakiki matokeo yote na anabeba jukumu kamili la makala. Maandishi unayosoma yaliandikwa na Claude pia.