WANI WASAN ƘWAƘWALWA NA ZANE-ZANEN GRAPH NA SHEKARUN 1960 YA KAMMALA

Ɗauki wasu ɗigo kuma ka haɗa wasu nau’i-nau’i daga cikinsu da layuka: masana lissafi suna kiran wannan graph, ɗigogin kuma vertices (ƙulli), layukan kuma edges (gefuna). Da’ira (cycle) hanya ce a rufe da ke ziyartar ƙulli daban-daban kuma ta koma inda ta fara. Tambaya ta zahiri ita ce ko za a iya raba gefunan graph — kowane gefe a yi amfani da shi sau ɗaya daidai — zuwa da’irori.

An daɗe da sanin amsar, kamar yadda takardar ta tuna: hakan yana yiwuwa daidai idan kowane ƙulli yana taɓa adadin gefuna mai cikakken rabi (lamba mai rabuwa biyu). Ana kiran irin waɗannan graphs Eulerian. Tambaya ta gaba ita ce da’irori nawa ake buƙata. Kuma ga graphs da da’irori kaɗai ba za su isa ba, ana kuma yarda da gefuna guda-guda a matsayin guntaye.

Hasashen

A shekarun 1960, Erdős da Gallai sun yi hasashen cewa gefunan kowane graph mai ƙulli n za a iya raba su zuwa adadin da’irori da gefuna guda-guda da bai wuce wanda ya yi daidai da n ba — ana rubuta shi O(n). Erdős ya saka shi a cikin da yawa daga cikin tarin matsalolinsa da ba a warware ba. Wani hasashe mai alaƙa na Hajós yana neman da’irori da ba su wuce (n − 1)/2 ba a cikin kowane graph na Eulerian.

Layi madaidaici (linear) shi ne mafi kyawun abin da za a iya fata: Erdős ya nuna cewa wasu graphs suna buƙatar kusan guntaye 1.5 n. Tambayar ita ce ko wani ma’aunin dindindin sau n koyaushe ya isa.

Shekaru hamsin na iyakoki masu rarrafe

Erdős da Gallai da kansu sun lura da wata hanya mai sauƙi: a ci gaba da cire da’ira mafi tsawo. Tana ba da kusan guntaye n log n — kuma, a cewar takardar, wannan ya kasance iyaka mafi kyau ta gaba ɗaya kusan shekaru hamsin. Kwanan nan, Conlon, Fox da Sudakov sun saukar da ita zuwa n log log n, sannan Bucić da Montgomery zuwa n log* n, inda log* n — adadin lokutan da dole ne a ɗauki logarithm don a sauka ƙasa da ɗaya — ke girma a hankali fiye da yadda za a iya tunani. Waɗannan hanyoyi sun yi aiki a zagaye-zagaye, kuma kowane zagaye ya kashe kusan da’irori n, don haka adadin zagayen koyaushe yana shiga cikin jimillar ƙarshe. An kuma tabbatar da hasashen ga wasu iyalai na musamman, kamar graphs na kwatsam (random graphs).

Nauyoyi da ke biyan kuɗin da’irori

Jaehoon Kim, na KAIST a Koriya ta Kudu, yanzu ya tabbatar da hasashen: akwai wani ma’aunin dindindin C ta yadda kowane graph mai ƙulli n zai rabu zuwa da’irori da gefuna da ba su wuce Cn ba. A matsayin sakamako, hasashen Hajós ya tabbata har zuwa wani ma’aunin dindindin.

Hujjar ta watsar da zagaye-zagaye. Tsari ɗaya ne ke cire da’irori da gefuna ɗaya bayan ɗaya, kuma ana sarrafa jimillar da adadi biyu waɗanda kowannensu ke kasancewa ƙasa da ma’aunin dindindin sau n.

• Ƙarfin da aka gina bisa digiri (degree). Kowane ƙulli yana samun nauyi da ke raguwa yayin da yawan gefunansa ke ƙaruwa, kusan 1 / (degree × log² degree). Da’ira tana da nauyi idan nauyoyin ƙullinta suka haɗu suka kai aƙalla 1. Cire da’ira mai nauyi yana rage wani “ƙarfi” (potential) na gaba ɗaya da aƙalla 1, kuma wannan ƙarfin yana farawa ne da bai wuce ma’aunin dindindin sau n ba. Don haka za a iya cire da’irori masu nauyi sau O(n) kawai.
• Yawan ƙulli. Idan babu da’ira mai nauyi da ta rage, graph ɗin ya zama “mara nauyi” — kuma babban sabon theorem ya nuna cewa graph mara nauyi mai manyan digiri dole ne ya ƙunshi wani yanki mai cunkoso, kusan a rufe. Ana raba wannan yanki zuwa adadin da’irori da gefuna da ya yi daidai da girmansa, bayan haka aƙalla kashi ɗaya cikin hamsin na ƙullinsa suna rage da gefuna biyu ko ƙasa da haka kuma su fita gaba ɗaya. Tunda kowane ƙulli zai iya fita sau ɗaya kawai, wannan ɓangaren ma yana kashe O(n).

A cikin sassan graph masu cunkoso, ana rufe guntayen hanyoyi zuwa da’ira ɗaya ta hanyar haɗa hanyoyin da suka ratsa ta “expanders”; launuka na kwatsam suna nisanta hanyoyin haɗi na da’ira ɗaya da juna. — Figure 3, Kim (2026), arXiv:2610.07840.

Don raba waɗannan yankuna masu cunkoso, hujjar ta faɗaɗa kayan aikin Bucić da Montgomery na “expanders” masu ƙarfi — graphs da kowane tarin ƙullinsu ke da maƙwabta da yawa — kuma ta ba ƙulli launuka ba da tsari ba ta yadda hanyoyin haɗi na da’ira ɗaya ba za su taɓa yin karo ba.

Abin da har yanzu ba a warware ba

Ma’aunin dindindin C yana da girma ƙwarai, kuma marubucin bai yi ƙoƙarin inganta shi ba. Gano mafi kyawun ma’aunin dindindin — aƙalla 1.5 — har yanzu a buɗe yake, haka ma ainihin hasashen Hajós da wani hasashe mai alaƙa na Gallai kan raba graphs zuwa hanyoyi (paths). Dabarar nauyi tana buƙatar nauyoyi ne kawai da jimillarsu ke da iyaka (converges), kuma marubucin ya ba da shawarar cewa za ta iya amfani a wasu matsalolin rarrabawa.

Wannan takardar bincike ce ta marubuci ɗaya, wadda ba a riga an duba ta ta hanyar bitar takwarorin masana ba.

Rikicin moriya. Marubucin ya bayyana cewa ya yi amfani sosai da ChatGPT (OpenAI) da Claude (Anthropic) wajen haɓaka hujjoji da shirya rubutu da zane-zane, kuma ya tabbatar da dukkan sakamakon kuma ya ɗauki cikakken alhakin takardar. Rubutun da kuke karantawa ma Claude ne ya rubuta shi.