Umsebenzi wophando yeyona nto inomdla kakhulu kuqeqesho lwethu. Umbono kukuzizama kwicala olikhethileyo ngelixa useyunivesithi. Umzekelo, abafundi abavela kwimimandla yeSoftware yobuNjineli kunye nokuFunda koMatshini bahlala beya kwenza uphando kwiinkampani (ikakhulukazi iJetBrains okanye iYandex, kodwa kungekhona kuphela).
Kule post ndiza kuthetha ngeprojekthi yam kwiSayensi yeKhompyutha. Njengenxalenye yomsebenzi wam, ndafunda ndaza ndasebenzisa iindlela zokusombulula eyona ngxaki idumileyo yeNP-nzima: ingxaki yokugquma i-vertex.
Kule mihla, indlela enomdla kwiingxaki zeNP-enzima ikhula ngokukhawuleza - i-algorithms yeparameterized. Ndiza kuzama ukukukhawulezisa, ndikuxelele ii-algorithms ezilula zeparameter kwaye ndichaze indlela enye enamandla eyandinceda kakhulu. Ndabonisa iziphumo zam kukhuphiswano lwePACE Challenge: ngokweziphumo zovavanyo oluvulekileyo, isisombululo sam sithatha indawo yesithathu, kwaye iziphumo zokugqibela ziya kwaziwa ngoJulayi 1.
Malunga nam
Igama lam nguVasily Alferov, ngoku ndigqiba unyaka wesithathu kwiYunivesithi yoPhando lweSizwe lweSikolo esiPhakamileyo sezoQoqosho - iSt. Ndinomdla kwii-algorithms ukususela kwiintsuku zam zesikolo, xa ndafunda esikolweni saseMoscow No.
Inani elilinganiselweyo leengcaphephe kwii-algorithms zeparameterized ukungena kwibar...
Umzekelo othathwe kwincwadi
Khawube nomfanekiso wakho ungunogada wasebharini kwidolophu encinane. Rhoqo ngolwesiHlanu, isiqingatha sesixeko siza kwibhari yakho ukuze uphumle, nto leyo ikunika ingxaki enkulu: kufuneka ulahle abathengi abangxolayo ngaphandle kwebhari ukunqanda imilo. Ekugqibeleni, uyahlutha kwaye uthathe isigqibo sokuthatha amanyathelo okuthintela.
Kuba isixeko sakho sincinci, uyazi kakuhle ukuba ngawaphi na abaxhasi abanokuthi balwe ukuba bagqibezela ebharini kunye. Ngaba unalo uluhlu lwe n abantu abaza kuza ebhari ngokuhlwanje. Uthatha isigqibo sokugcina abantu abathile bedolophu ngaphandle kwebar ngaphandle kokuba nabani na alwe. Kwangaxeshanye, abaphathi bakho abafuni ukuphulukana nengeniso kwaye abayi kuba nokonwaba ukuba awuvumeli ngaphezulu k abantu.
Ngelishwa, ingxaki phambi kwakho yingxaki enzima ye-NP. Usenokuba umazi , okanye njengengxaki yokugquma i-vertex. Kwiingxaki ezinjalo, kwimeko eqhelekileyo, akukho zi-algorithms ezisebenza ngexesha elamkelekileyo. Ukuchaneka, i-hypothesis engaqinisekiswanga kwaye inamandla kakhulu i-ETH (i-Exponential Time Hypothesis) ithi le ngxaki ayinakusonjululwa ngexesha. , oko kukuthi, awukwazi ukucinga nantoni na ngokubonakalayo engcono kunokukhangela okupheleleyo. Umzekelo, masithi kukho umntu oza kuza kwibhari yakho n = 1000 Umntu. Emva koko ukukhangela okupheleleyo kuya kuba iinketho ukuba kukho malunga - isixa crazy. Ngethamsanqa, ulawulo lwakho lukunike umda k = 10, ngoko ke inani leendibaniselwano olidingayo uliphinda-phinda lincinci kakhulu: inani leeseti ezisezantsi zeziqalelo ezilishumi . Oku kungcono, kodwa akusayi kubalwa ngosuku nakwiqela elinamandla.
Ukuphelisa ukubakho komlo kolu lungelelwaniso lobudlelwane obunzima phakathi kweendwendwe zebar, kufuneka ugcine uBob, uDaniel noFedor ngaphandle. Akukho sisombululo apho kuya kushiyeka babini kuphela.
Ngaba oku kuthetha ukuba lixesha lokunikezela kwaye uvumele wonke umntu angene? Makhe siqwalasele ezinye iindlela. Ewe, umzekelo, awukwazi ukuvumela kuphela abo banokuthi balwe nenani elikhulu kakhulu labantu. Ukuba umntu unokulwa ubuncinane nge k+1 omnye umntu, ngoko ngokuqinisekileyo awunakumvumela ukuba angene - kungenjalo kuya kufuneka ukhuphe wonke umntu ngaphandle k+1 abantu basezidolophini, anokuthi alwe nabo, nto leyo eya kuthi ngokuqinisekileyo iphazamise ubunkokeli.
Vumela ukuba ukhuphe wonke umntu onako ngokwalo mgaqo. Emva koko wonke umntu unokulwa ngokungekho ngaphezulu k abantu. Ukubakhupha k umntu, unako ukuthintela nto ngaphezu iingxabano. Oku kuthetha ukuba ukuba kukho ngaphezu Ukuba umntu ubandakanyeka ubuncinane kwingxabano enye, ngoko ngokuqinisekileyo awukwazi ukubathintela bonke. Kuba, ewe, ngokuqinisekileyo uya kubavumela ukuba bangene abantu abangangqubaniyo ngokupheleleyo, kuya kufuneka uhambe kuzo zonke iiseti zobungakanani beshumi kubantu abangamakhulu amabini. Kukho malunga , kwaye eli nani lemisebenzi sele ilungelelaniswe kwi-cluster.
Ukuba unokuthabatha ngokukhuselekileyo abantu abangangqubaniyo kwaphela, kuthekani ngabo bathabatha inxaxheba kungquzulwano olunye kuphela? Enyanisweni, banokuvunyelwa ukuba bangene ngokuvala umnyango kumchasi wabo. Ewe, ukuba uAlice ungquzulana noBob kuphela, ukuba siyamyeka uAlice aphume kubo bobabini, asiyi kulahlekelwa: UBob unokuba nezinye iingxabano, kodwa uAlice akanazo. Ngaphezu koko, akukho ngqiqweni ukuba singasivumeli singene sobabini. Emva kokusebenza okunjalo akusekho nto iindwendwe ezinekamva elingasonjululwanga: sinakho kuphela Iingxwabangxwaba, ngalinye linabathathi-nxaxheba ababini yaye ngalinye libandakanyeka ubuncinane kwababini. Ke okuseleyo kukuhlela iinketho, ezinokuthi ziqwalaselwe ngokulula isiqingatha sosuku kwilaptop.
Enyanisweni, ngokuqiqa okulula unokufezekisa iimeko ezinomtsalane ngakumbi. Qaphela ukuba ngokuqinisekileyo kufuneka sisombulule zonke iingxabano, oko kukuthi, kwisibini ngasinye esiphikisanayo, khetha ubuncinane umntu omnye esingayi kumvumela ukuba angene. Makhe siqwalasele le algorithm ilandelayo: thatha nayiphi na impixano, apho sisusa umthathi-nxaxheba omnye kwaye siqale ngokuphindaphindiweyo ukusuka kwintsalela, emva koko sisuse enye kwaye siqale ngokuphindaphindiweyo. Ekubeni siphosa umntu ngaphandle kwinqanaba ngalinye, umthi wokuphindaphinda we-algorithm ngumthi wokubini wobunzulu k, ngoko iyonke i-algorithm isebenza kuyo phi n linani lee nkqo, kwaye m - inani leembambo. Kumzekelo wethu, oku malunga nezigidi ezilishumi, ezinokuthi zibalwe kwisibini esiqhekezayo kungekhona nje kwi-laptop, kodwa nakwifowuni ephathekayo.
Lo mzekelo ungasentla ngumzekelo ialgorithm yeparameterized. Iparameterized algorithms zialgorithms ezihamba ngexesha f(k) poly(n)phi p - Polynomial, f ngumsebenzi ongenamkhethe, kunye k - enye ipharamitha, enokuthi, ngokuqinisekileyo, iya kuba ncinane kakhulu kunobungakanani bengxaki.
Konke ukuqiqa phambi kokuba le algorithm inika umzekelo ukwenziwa kwekernelization yenye yeendlela eziqhelekileyo zokudala ii-algorithms zeparameterized. I-Kernelization kukucuthwa kobungakanani bengxaki ukuya kwixabiso elilinganiselweyo ngumsebenzi weparameter. Ingxaki evelayo idla ngokubizwa ngokuba yi-kernel. Ke, ngokuqiqa ngokulula malunga needigri ze-vertices, sifumene i-quadratic kernel yengxaki ye-Vertex Cover, iparametered ngobungakanani bempendulo. Kukho ezinye iisetingi ongazikhetha kulo msebenzi (ezifana neVertex Cover Ngaphezulu kweLP), kodwa esi sisilungiselelo esiza kuthetha ngaso.
Isantya Challenge
Ukhuphiswano (I-Parameterized Algorithms kunye ne-Computational Experiments Challenge) yazalwa kwi-2015 ukuseka uxhulumaniso phakathi kwe-algorithms ye-parameterized kunye neendlela ezisetyenziswa ekusebenzeni ukusombulula iingxaki zokubala. Ukhuphiswano lokuqala oluthathu lunikezelwe ekufumaneni ububanzi bomthi wegrafu (), ikhangela umthi weSteiner () kunye nokukhangela iseti yee-vertices ezisika imijikelo (). Kulo nyaka, enye yeengxaki onokuthi uzame ngayo isandla sakho yingxaki yokugquma i-vertex echazwe ngasentla.
Olu khuphiswano lufumana ukuthandwa minyaka le. Ukuba uyakholelwa kwidatha yokuqala, kulo nyaka amaqela angama-24 athathe inxaxheba kukhuphiswano lokusombulula ingxaki yodwa egquma i-vertex. Kubalulekile ukuba uqaphele ukuba ukhuphiswano aluhlali iiyure ezininzi okanye ngeveki, kodwa iinyanga ezininzi. Amaqela anethuba lokufunda uncwadi, eze nombono wawo wokuqala aze azame ukuwuphumeza. Ngokwenyani, olu khuphiswano yiprojekthi yophando. Izimvo zezona zisombululo zisebenzayo kunye nokunikezelwa kwabaphumeleleyo kuya kubanjwa ngokubambisana nenkomfa. (I-Symposium yamazwe ngamazwe kwiParameterized and Exact Computation) njengenxalenye yentlanganiso enkulu yonyaka ye-algorithmic eYurophu . Ulwazi oluthe vetshe malunga nokhuphiswano ngokwalo lunokufumaneka apha , yaye iziphumo zeminyaka engaphambili zibubuxoki .
Umzobo wesisombululo
Ukusombulula ingxaki yokugquma i-vertex, ndizamile ukusebenzisa i-algorithms yeparameterized. Ngokuqhelekileyo zibandakanya iinxalenye ezimbini: imithetho yokwenza lula (ethi ikhokhelele kwi-kernelization) kunye nemithetho yokwahlula. Imithetho yokulula i-preprocessing yegalelo kwixesha le-polynomial. Injongo yokusebenzisa le mithetho kukunciphisa ingxaki ibe yingxaki encinane efanayo. Imithetho yokulula iyona nxalenye ebiza kakhulu ye-algorithm, kwaye ukusebenzisa le nxalenye kukhokelela kwixesha elipheleleyo lokusebenza endaweni yexesha elilula lepolynomial. Kwimeko yethu, imithetho yokwahlula isekelwe kwinto yokuba kwi-vertex nganye kufuneka uyithathe okanye ummelwane wayo njengempendulo.
Iskimu esiqhelekileyo yile: sisebenzisa imigaqo yokulula, ngoko sikhetha i-vertex ethile, kwaye senze iifowuni ezimbini eziphindaphindiweyo: okokuqala sithatha ngokuphendula, kwaye kwelinye sithatha bonke abamelwane balo. Yile nto siyibiza ngokucanda (branching) ecaleni kwale vertex.
Kuya kongezwa kanye kanye kwesi sikimu kumhlathi olandelayo.
Izimvo zokwahlula (brunching) imithetho
Makhe sixoxe ngendlela yokukhetha i-vertex apho kuya kwenzeka ukwahlula.
Uluvo oluphambili lubawa kakhulu kwi-algorithmic ingqiqo: masithathe i-vertex yeqondo eliphezulu kwaye sahlulwe ecaleni kwayo. Kutheni ibonakala ingcono? Ngenxa yokuba kwisebe lesibini le-recursive call siya kususa i-vertices eninzi ngale ndlela. Ungathembela kwigrafu encinci eseleyo kwaye sinokusebenza kuyo ngokukhawuleza.
Le ndlela, esele kuxoxiwe ngayo iindlela ezilula zekernelization, izibonisa kakuhle kwaye isombulule ezinye iimvavanyo zamawaka aliqela eendidi ngobukhulu. Kodwa, umzekelo, ayisebenzi kakuhle kwiigrafu ze-cubic (oko kukuthi, iigrafu ezinomlinganiselo we-vertex nganye zintathu).
Kukho enye ingcamango esekelwe kwingcamango elula: ukuba igrafu inqanyuliwe, ingxaki kumacandelo ayo adibeneyo ingasombululwa ngokuzimeleyo, ukudibanisa iimpendulo ekupheleni. Oku, ngendlela, yinto encinci ethenjisiweyo yokuguqulwa kwesikimu, eya kukhawuleza isisombululo: ngaphambili, kulo mzekelo, sasisebenzela imveliso yamaxesha ekubaleni iimpendulo zamacandelo, kodwa ngoku sisebenzela isimbuku. Kwaye ukukhawulezisa i-branching, kufuneka ujike igrafu edibeneyo ibe yinto edibeneyo.
Ukwenza njani? Ukuba kukho indawo yokucacisa kwigrafu, kufuneka ulwe kuyo. Indawo yokudibanisa i-vertex efana nokuba xa isusiwe, igrafu ilahlekelwa uqhagamshelwano lwayo. Zonke iindawo zokuhlangana kwigrafu zinokufunyanwa ngokusebenzisa i-algorithm yeklasi ngexesha lomgca. Le ndlela ikhawuleza kakhulu i-branching.
Xa naziphi na ii-vertices ezikhethiweyo zisusiwe, igrafu iya kwahlulwa ibe ngamacandelo adityanisiweyo.
Siza kukwenza oku, kodwa sifuna okungakumbi. Umzekelo, jonga ii-vertex ezincinci kwigrafu kwaye ucande kunye nee-vertices ezivela kuyo. Eyona ndlela isebenzayo endiyaziyo yokufumana ubuncinci bokusikwa kwevertex yehlabathi kukusebenzisa umthi weGomori-Hu, owakhiwe ngexesha le-cubic. Kumngeni we-PACE, ubungakanani begrafu eqhelekileyo ngamawaka aliqela ee-vertices. Kule meko, iibhiliyoni zemisebenzi kufuneka zenziwe kwi-vertex nganye yomthi wokuphindaphinda. Kuyavela ukuba akunakwenzeka ukusombulula ingxaki ngexesha elimiselweyo.
Masizame ukunyusa isisombululo. Ubuncinci be-vertex esikiweyo phakathi kweperi ye-vertices inokufunyanwa yiyo nayiphi na i-algorithm eyakha ukuhamba okuphezulu. Ungayivumela ingene kwinethiwekhi enjalo , ekusebenzeni isebenza ngokukhawuleza kakhulu. Ndinokrokro lokuba kunokwenzeka ngokwethiyori ukungqina uqikelelo lwexesha lokusebenza , esele yamkelekile.
Ndizame amatyeli aliqela ukukhangela ukusikeka phakathi kweeperi zamanani angaqhelekanga kwaye ndithathe eyona ilungeleleneyo. Ngelishwa, oku kuvelise iziphumo ezibi kuvavanyo oluvulekileyo lwePACE Challenge. Ndiyithelekise kunye ne-algorithm eyahlula ii-vertices zeqondo eliphezulu, ndibaqhuba ngomda kubunzulu bokwehla. I-algorithm ezama ukufumana i-cut ngale ndlela ishiye ngasemva iigrafu ezinkulu. Oku kubangelwa ukuba ukusika kwabonakala kungenakulungelelaniswa kakhulu: emva kokususa i-5-10 vertices, kwakunokwenzeka ukwahlula kuphela i-15-20.
Kuyaphawuleka ukuba amanqaku amalunga ne-algorithms ekhawulezayo ngokwethiyori asebenzisa ubuchule obuphambili kakhulu bokukhetha ii-vertices zokwahlula. Ubuchule obunjalo bunokuphunyezwa okunzima kakhulu kwaye kaninzi ukusebenza kakubi ngokwexesha kunye nememori. Andikwazanga ukuchonga ezo zamkelekileyo ukuba zisetyenziswe.
Indlela Yokusebenzisa Imithetho Yokwenza Lula
Sele sinemibono ye-kernelization. Makhe ndikukhumbuze:
- Ukuba kukho i-vertex eyodwa, yicime.
- Ukuba kukho i-vertex ye-degree 1, yisuse kwaye uthathe ummelwane wayo ngokuphendula.
- Ukuba kukho i-vertex yesidanga ubuncinane k+1, yibuyisele.
Ngezokuqala ezimbini yonke into icacile, kunye neyesithathu kukho iqhinga elinye. Ukuba kwingxaki ehlekisayo malunga nebha sanikwa umda ophezulu k, emva koko kwi-PACE Challenge ufuna nje ukufumana i-vertex cover yobungakanani obuncinci. Olu lutshintsho oluqhelekileyo lweeNgxaki zoPhando kwiiNgxaki zesiGqibo; rhoqo akukho mahluko phakathi kweentlobo ezimbini zeengxaki. Enyanisweni, ukuba sibhala isixazululi sengxaki yokugubungela i-vertex, kunokubakho umahluko. Umzekelo, njengakwinqaku lesithathu.
Ukusuka kwimbono yokuphunyezwa, kukho iindlela ezimbini zokuqhubeka. Indlela yokuqala ibizwa ngokuba yi-Iterative Deepening. Imi ngolu hlobo lulandelayo: sinokuqala ngesithintelo esinengqiqo ukusuka ngezantsi kwimpendulo, kwaye emva koko siqhube i-algorithm yethu sisebenzisa esi sithintelo njengesithintelo kwimpendulo evela phezulu, ngaphandle kokuhla ngokuphindaphindiweyo kunomqobo. Ukuba sifumene impendulo ethile, kuqinisekisiwe ukuba iyona nto ifanelekileyo, ngaphandle koko sinokuwunyusa lo mda ngenye kwaye siqale kwakhona.
Enye indlela kukugcina impendulo echanekileyo yangoku kwaye ujonge impendulo encinci, utshintshe le parameter xa ifunyenwe k ukunqunyulwa okukhulu kwamasebe angeyomfuneko kukhangelo.
Emva kokwenza iimvavanyo ezininzi zasebusuku, ndazinza kwindibaniselwano yezi ndlela zimbini: okokuqala, ndiqhuba i-algorithm yam ngohlobo oluthile lomda kubunzulu bokukhangela (ukuyikhetha ukuze kuthathe ixesha elingenakuthelekiswa nanto xa kuthelekiswa nesisombululo esiphambili) kwaye ndisebenzise eyona ilungileyo. isisombululo esifunyenwe njengomda ophezulu kwimpendulo - oko kukuthi, kwinto enye k.
Iincam zesidanga 2
Siye sajongana neentsika zesidanga 0 kunye no-1. Kuvela ukuba oku kunokwenziwa ngee-vertices ze-degree 2, kodwa oku kuya kufuna imisebenzi enzima ngakumbi kwigrafu.
Ukucacisa oku, kufuneka ngandlela thile sikhethe ii-vertices. Masibize i-vertex yesidanga sesi-2 njenge-vertex v, kunye nabamelwane bayo - vertices x и y. Okulandelayo siza kuba namatyala amabini.
- Xa x и y - abamelwane. Emva koko unokuphendula x и y, kwaye v cima. Ewe, kulo nxantathu ubuncinci iintlabathi ezimbini kufuneka zithathwe njengembuyekezo, kwaye ngokuqinisekileyo asiyi kulahlekelwa ukuba sithatha x и y: mhlawumbi banabanye abamelwane, kwaye v abekho.
- Xa x и y - hayi abamelwane. Emva koko kuchazwe ukuba zontathu ii-vertices zinokudityaniswa zibe nye. Ingcamango kukuba kule meko kukho impendulo efanelekileyo, apho sithatha khona nokuba v, okanye zombini iincam x и y. Ngaphezu koko, kwimeko yokuqala kuya kufuneka sithathe bonke abamelwane ekuphenduleni x и y, kodwa okwesibini akuyomfuneko. Oku kuhambelana ngqo namatyala xa singathathi i-vertex edibeneyo ekuphenduleni kwaye xa sisenza. Kuhlala kuphela ukuqaphela ukuba kuzo zombini iimeko impendulo evela kumsebenzi onjalo iyancipha enye.
Kubalulekile ukuqaphela ukuba le ndlela inzima kakhulu ukuyiphumeza ngokuchanekileyo ngexesha elifanelekileyo. I-Gluing vertices ngumsebenzi onzima; kufuneka ukope uluhlu lwabamelwane. Ukuba oku kwenziwa ngokungakhathali, ungaphela unexesha elingenalusini lokubaleka (umzekelo, ukuba ukhuphela imiphetho emininzi emva kokuncamatheliswa ngakunye). Ndiye ndazinza ekufumaneni iindlela ezipheleleyo ukusuka kwii-vertices zesidanga sesi-2 kunye nokuhlalutya iqela lamatyala akhethekileyo, anje ngemijikelo evela kwii-vertices ezinjalo okanye kuzo zonke ezo nkqo ngaphandle kwenye.
Ukongeza, kuyimfuneko ukuba lo msebenzi ubuyiselwe umva, ukwenzela ukuba xa sibuya kwi-recursion sibuyisela igrafu kwifom yayo yasekuqaleni. Ukuqinisekisa oku, khange ndilucime uluhlu lwee-vertices ezidityanisiweyo, kwaye ke ndazi nje ukuba yeyiphi imiphetho ekufuneka iye phi. Oku kuphunyezwa kweegrafu kufuna kwakhona ukuchaneka, kodwa kunika ixesha elifanelekileyo lomgca. Kwaye kwiigrafu zamashumi amashumi amawaka emiphetho, ingena kwi-cache yeprosesa, enika inzuzo enkulu kwisantya.
I-kernel yomgca
Ekugqibeleni, inxalenye enomdla kakhulu ye-kernel.
Ukuqala, khumbula ukuba kwiigrafu ze-bipartite ubuncinci bokhuselo lwevertex inokufunyanwa kusetyenziswa . Ukwenza oku kufuneka usebenzise i-algorithm ukuze ufumane eyona ithelekisekayo apho, uze usebenzise ithiyori .
Umbono we kernel yomgama ngulo: okokuqala sibeka kabini igrafu, oko kukuthi, endaweni yevertex nganye. v masenze iincopho ezimbini и , kwaye endaweni yomphetho ngamnye wena v masidibanise iimbambo ezimbini и . Igrafu enesiphumo iya kuba yi-bipartite. Makhe sifumane ubuncinci bokugquma kwevertex kuyo. Ezinye ii-vertices zegrafu yoqobo ziya kufika apho kabini, ezinye kube kanye kuphela, kwaye ezinye azisoze. Ithiyori ye- Nemhauser-Trotter ithi kule meko umntu unokukhupha iincam ezingabethanga nakanye abuyise ezo zibethe kabini. Ngaphezu koko, uthi kwii-vertices ezishiyekileyo (ezo zibethe kanye) kufuneka uthathe isiqingatha njengempendulo.
Sisanda kufunda ukushiya hayi ngaphezulu 2k iincopho Ewe, ukuba impendulo eshiyekileyo isiqingatha sazo zonke ii-vertices, akusekho zi-vertices zizonke. 2k.
Apha ndakwazi ukuthabatha inyathelo elincinane ukuya phambili. Kucacile ukuba i-kernel eyakhiwe ngolu hlobo ixhomekeke kuhlobo oluncinci lwesigqubuthelo se-vertex esisithathileyo kwigrafu ye-bipartite. Ndingathanda ukuthatha enye ukuze inani leentsika eziseleyo libe lincinci. Ngaphambili, babekwazi ukwenza oku kuphela ngexesha . Ndize nokuphunyezwa kwale algorithm ngexesha , ngoko ke, lo ngundoqo unokukhangelwa kwiigrafu zamakhulu amawaka ee-vertices kwinqanaba ngalinye lamasebe.
Isiphumo
Ukuziqhelanisa kubonisa ukuba isisombululo sam sisebenza kakuhle kuvavanyo lwamakhulu aliqela kunye nemiphetho engamawaka aliqela. Kwiimvavanyo ezinjalo kunokwenzeka ukuba ulindele ukuba isisombululo siya kufumaneka kwisiqingatha seyure. Amathuba okufumana impendulo ngexesha elamkelekileyo, ngokomgaqo, ukwanda ukuba igrafu inenani elikhulu ngokwaneleyo lee-vertices zeqondo eliphezulu, umzekelo, i-degree 10 nangaphezulu.
Ukuthatha inxaxheba kukhuphiswano, izisombululo kwafuneka zithunyelwe . Ngokujonga ulwazi oluchazwe apho , isisombululo sam kwiimvavanyo ezivulekileyo sithatha indawo yesithathu kwamashumi amabini, kunye ne-gap enkulu ukusuka kwisibini. Ukunyaniseka ngokupheleleyo, akucaci ngokupheleleyo ukuba izisombululo ziya kuvavanywa njani kukhuphiswano ngokwalo: umzekelo, isisombululo sam sidlula iimvavanyo ezimbalwa kunesisombululo kwindawo yesine, kodwa kwabo baphumeleleyo, basebenza ngokukhawuleza.
Iziphumo zeemvavanyo ezivaliweyo ziya kwaziwa nge-XNUMX kaJulayi.
umthombo: www.habr.com