Umsebenzi wokucwaninga mhlawumbe uyingxenye ethakazelisa kakhulu yokuqeqeshwa kwethu. Umqondo uwukuba uzizame ngendlela oyikhethile ngenkathi usenyuvesi. Isibonelo, abafundi abavela ezindaweni zeSoftware Engineering and Machine Learning bavame ukuya ukuyokwenza ucwaningo ezinkampanini (ikakhulukazi i-JetBrains noma i-Yandex, kodwa hhayi kuphela).
Kulokhu okuthunyelwe ngizokhuluma ngephrojekthi yami kuComputer Science. Njengengxenye yomsebenzi wami, ngafunda futhi ngasebenzisa izindlela zokuxazulula enye yezinkinga ezinzima ze-NP ezidume kakhulu: inkinga yokumboza i-vertex.
Namuhla, indlela ethokozisayo yezinkinga ze-NP-hard ikhula ngokushesha kakhulu - ama-algorithms anepharamitha. Ngizozama ukukusheshisa, ngikutshele ama-algorithms alula anepharamitha futhi ngichaze indlela eyodwa enamandla eyangisiza kakhulu. Ngethule imiphumela yami emqhudelwaneni we-PACE Challenge: ngokwemiphumela yokuhlolwa okuvuliwe, isisombululo sami sithatha indawo yesithathu, futhi imiphumela yokugcina izokwaziwa ngoJulayi 1.
Mayelana nami
Igama lami nginguVasily Alferov, manje ngiqeda unyaka wami wesithathu e-National Research University Higher School of Economics - eSt. Ngiye nginesithakazelo kuma-algorithms kusukela ezinsukwini zami zesikole, lapho ngifunda esikoleni saseMoscow No.
Inombolo elinganiselwe yochwepheshe kuma-algorithms anepharamitha ingena kubha...
Isibonelo esithathwe encwadini
Zicabange ungunogada wasebha edolobheni elincane. Njalo ngoLwesihlanu, ingxenye yedolobha iza endaweni yakho yokucima ukoma ukuze uphumule, okukunikeza izinkinga eziningi: udinga ukuphonsa amakhasimende anomsindo ngaphandle kwebha ukuze uvimbele ukulwa. Ekugcineni, uyakhathala futhi unqume ukuthatha izinyathelo zokuvimbela.
Njengoba idolobha lakho lilincane, wazi kahle ukuthi yimaphi amapheya abaxhasi okungenzeka alwe uma egcina esendaweni yokucima ukoma ndawonye. Ingabe unalo uhlu n abantu abazofika ebhawa namuhla ebusuku. Unquma ukugcina abantu abathile basedolobheni bengangeni endaweni yokucima ukoma ngaphandle kokuthi kube khona abalwayo. Ngesikhathi esifanayo, abaphathi bakho abafuni ukulahlekelwa inzuzo futhi ngeke bajabule uma ungavumeli okungaphezu k abantu.
Ngeshwa, inkinga ephambi kwakho yinkinga yakudala ye-NP-hard. Ungase umazi njengoba , noma njengenkinga yokumboza i-vertex. Ezinkingeni ezinjalo, esimweni esivamile, awekho ama-algorithms asebenza ngesikhathi esamukelekile. Ukunemba, i-hypothesis engaqinisekisiwe futhi enamandla impela i-ETH (Exponential Time Hypothesis) ithi le nkinga ayikwazi ukuxazululwa ngesikhathi. , okusho ukuthi, awukwazi ukucabanga nganoma yini engcono kakhulu kunokusesha okuphelele. Isibonelo, ake sithi othile uzoza endaweni yakho yokucima ukoma n = 1000 Umuntu. Khona-ke ukusesha okuphelele kuyoba ongakhetha ukuthi kukhona cishe - inani crazy. Ngenhlanhla, abaphathi bakho bakunikeze umkhawulo k =10, ngakho-ke inani lezinhlanganisela odinga ukuphindaphinda lincane kakhulu: inani lamasethi angaphansi wezakhi eziyishumi . Lokhu kungcono, kodwa namanje ngeke kubalwe ngosuku ngisho nakuqoqo elinamandla.
Ukuze kuqedwe ukuthi kungenzeka kube nokulwa kulokhu kucushwa kobudlelwano obunzima phakathi kwezivakashi zebha, udinga ukugcina uBob, uDaniel noFedor bengaphandle. Asikho isixazululo lapho kuzosala ababili kuphela.
Ingabe lokhu kusho ukuthi sekuyisikhathi sokuvuma futhi uvumele wonke umuntu angene? Ake sicabangele ezinye izinketho. Nokho, ngokwesibonelo, awukwazi ukuvumela kuphela labo okungenzeka balwe nenani elikhulu kakhulu labantu. Uma umuntu ekwazi ukulwa okungenani nge k+1 omunye umuntu, khona-ke awukwazi ukumvumela ukuba angene - ngaphandle kwalokho kuzodingeka ukhiphe wonke umuntu k+1 abantu basedolobheni, angalwa nabo, okuzocasula ubuholi.
Vumela ukuthi ukhiphe wonke umuntu ongakwazi ngokwalesi simiso. Khona-ke wonke umuntu angalwa ngokungaphezu kwalokho k abantu. Ebakhiphela ngaphandle k ndoda, ungakwazi ukuvimbela lutho ngaphezu izingxabano. Lokhu kusho ukuthi uma kukhona okungaphezu kwalokho Uma umuntu ehileleke okungenani ekungqubuzaneni okukodwa, khona-ke ngokuqinisekile awukwazi ukukuvimbela konke. Njengoba, vele, uzovumela abantu abangenazo izingxabano ngokuphelele, udinga ukudlula wonke ama-subsets osayizi weshumi kubantu abangamakhulu amabili. Kukhona cishe , futhi leli nani lemisebenzi selingakwazi ukuhlungwa kuqoqo.
Uma ukwazi ukuthatha ngokuphepha abantu abangenakho nhlobo ukungqubuzana, kuthiwani-ke ngalabo abahlanganyela engxabanweni eyodwa kuphela? Eqinisweni, bangavunyelwa futhi ngokuvala umnyango kulowo ophikisana nabo. Ngempela, uma u-Alice engqubuzana noBob kuphela, khona-ke uma sivumela u-Alice ukuba aphume kubo bobabili, ngeke silahlekelwe: UBob angase abe nezinye izingxabano, kodwa u-Alice ngokuqinisekile akanazo. Ngaphezu kwalokho, akunangqondo ngathi ukungasivumeli sobabili singene. Ngemva kokusebenza okunjalo akusekho okunye izivakashi ngesiphetho esingaxazululiwe: sinakho kuphela izingxabano, ngayinye inabahlanganyeli ababili futhi ngamunye ehilelekile okungenani kwababili. Ngakho-ke okusele wukuhlunga izinketho, ezingabhekwa kalula njengengxenye yosuku ku-laptop.
Eqinisweni, ngokucabanga okulula ungafinyelela izimo ezikhangayo nakakhulu. Qaphela ukuthi kufanele nakanjani sixazulule zonke izingxabano, okungukuthi, kumbhangqwana ngamunye ongqubuzanayo, khetha okungenani umuntu oyedwa esingeke simngenise. Ake sicabangele i-algorithm elandelayo: thatha noma yikuphi ukungqubuzana, lapho sisusa khona umhlanganyeli oyedwa futhi ngokuphindaphindiwe siqale kokusele, bese sikhipha omunye futhi siqale ngokuphindaphindiwe. Njengoba siphonsa umuntu kuzo zonke izinyathelo, isihlahla sokuphindaphinda se-algorithm enjalo isihlahla kanambambili sokujula k, ngakho-ke i-algorithm isiyonke isebenza kuyo kuphi n yinani lama-vertices, futhi m - inombolo yezimbambo. Esibonelweni sethu, lokhu kumayelana nezigidi eziyishumi, ezingabalwa ngomzuzwana wokuhlukaniswa hhayi kuphela kwi-laptop, kodwa ngisho nakumakhalekhukhwini.
Isibonelo esingenhla yisibonelo i-algorithm yepharamitha. Ama-algorithms anepharamitha ama-algorithms asebenza ngesikhathi f(k) i-poly(n)kuphi p - i-polynomial, f kuwumsebenzi osebenziseka kalula, futhi k - ipharamitha ethile, okungenzeka ukuthi, izoba yincane kakhulu kunobukhulu benkinga.
Konke ukucabanga ngaphambi kwale algorithm kunikeza isibonelo i-kernelization ingenye yezindlela ezijwayelekile zokudala ama-algorithms anepharamitha. I-Kernelization ukuncishiswa kosayizi wenkinga ube inani elikhawulelwe umsebenzi wepharamitha. Inkinga ewumphumela ngokuvamile ibizwa ngokuthi i-kernel. Ngakho-ke, ngokucabanga okulula mayelana namadigri ama-vertices, sithole i-quadratic kernel yenkinga Yekhava ye-Vertex, ebekwe ipharamitha ngosayizi wempendulo. Kukhona ezinye izilungiselelo ongazikhetha kulo msebenzi (njenge-Vertex Cover Above LP), kodwa lesi isilungiselelo esizoxoxa ngaso.
I-Pace Challenge
Umncintiswano (I-Parameterized Algorithms and Computational Experiments Challenge) yazalwa ngo-2015 ukuze kusungulwe ukuxhumana phakathi kwama-algorithms anepharamitha kanye nezindlela ezisetshenziswa ekusebenzeni ukuxazulula izinkinga zokubala. Imiqhudelwano emithathu yokuqala inikezelwe ekutholeni ububanzi besihlahla segrafu (), ifuna isihlahla se-Steiner () kanye nokusesha isethi yama-vertices esika imijikelezo (). Kulo nyaka, enye yezinkinga ongase uzame ngayo isandla sakho kube inkinga yokumboza i-vertex echazwe ngenhla.
Lo mncintiswano uthola ukuduma minyaka yonke. Uma ukholelwa imininingwane yokuqala, kulo nyaka amaqembu angu-24 abambe iqhaza emqhudelwaneni ukuze axazulule inkinga yokumboza i-vertex yedwa. Kuyaphawuleka ukuthi umncintiswano awuhlali amahora ambalwa noma ngisho nesonto, kodwa izinyanga ezimbalwa. Amaqembu anethuba lokutadisha izincwadi, aqhamuke nombono wawo wangempela futhi azame ukuwusebenzisa. Empeleni, lo mncintiswano uyiphrojekthi yocwaningo. Imibono yezixazululo ezisebenza kahle kakhulu kanye nokuklonyeliswa kwabaphumelele izobanjwa kanye nengqungquthela (I-International Symposium on Parameterized and Exact Computation) njengengxenye yomhlangano omkhulu waminyaka yonke we-algorithmic eYurophu . Ukwaziswa okwengeziwe mayelana nomncintiswano ngokwawo kungatholakala kokuthi , futhi imiphumela yeminyaka edlule ingelona iqiniso .
Umdwebo wesixazululo
Ukuxazulula inkinga yokumboza i-vertex, ngizamile ukusebenzisa ama-algorithms anepharamitha. Ngokuvamile aqukethe izingxenye ezimbili: imithetho yokwenza lula (okuholela ekukhiqizweni kwe-kernelization) kanye nemithetho yokuhlukanisa. Imithetho yokwenza lula iwukucubungula kusengaphambili okokufaka ngesikhathi se-polynomial. Inhloso yokusebenzisa imithetho enjalo ukunciphisa inkinga ibe inkinga encane efanayo. Imithetho yokwenza lula iyingxenye ebiza kakhulu ye-algorithm, futhi ukusebenzisa le ngxenye kuholela esikhathini esiphelele sokusebenza esikhundleni sesikhathi esilula se-polynomial. Esimweni sethu, imithetho yokuhlukanisa isekelwe eqinisweni lokuthi ku-vertex ngayinye udinga ukuthatha yona noma umakhelwane wayo njengempendulo.
Uhlelo olujwayelekile yilo: sisebenzisa imithetho yokwenza lula, bese sikhetha i-vertex ethile, futhi senze izingcingo ezimbili eziphindaphindiwe: okokuqala sithatha ngokuphendula, kanti kwenye sithatha bonke omakhelwane bayo. Yilokhu esikubiza ngokuhlukanisa (igatsha) eduze kwale vertex.
Impela kuzongezwa okukodwa kulolu hlelo endimeni elandelayo.
Imibono yokuhlukanisa (i-brunching) imithetho
Ake sixoxe ngokuthi ungayikhetha kanjani i-vertex lapho kuzohlukaniswa khona.
Umqondo oyinhloko unomhobholo kakhulu ngomqondo we-algorithmic: ake sithathe i-vertex yezinga eliphezulu kakhulu futhi sihlukanise phakathi kwalo. Kungani kubonakala kungcono? Ngoba egatsheni lesibili lekholi ephindaphindayo sizosusa ama-vertices amaningi ngale ndlela. Ungathembela kugrafu encane esele futhi singasebenza kuyo ngokushesha.
Le ndlela, ngamasu alula asekuxoxwe ngawo kakade, iziveza kahle futhi ixazulula ezinye izivivinyo zezinkulungwane ezimbalwa zosayizi. Kodwa, ngokwesibonelo, ayisebenzi kahle kumagrafu ayi-cubic (okungukuthi, amagrafu lawo izinga lawo le-vertex ngayinye lithathu).
Kukhona omunye umqondo osekelwe embonweni olula: uma igrafu inqanyuliwe, inkinga ezingxenyeni zayo ezixhunyiwe ingaxazululwa ngokuzimela, ngokuhlanganisa izimpendulo ekugcineni. Lokhu, ngendlela, ukuguqulwa okuncane okuthenjisiwe ohlelweni, okuzosheshisa kakhulu isisombululo: ngaphambilini, kulokhu, sasisebenzela umkhiqizo wezikhathi zokubala izimpendulo zezingxenye, kodwa manje sisebenzela isamba. Futhi ukusheshisa i-branching, udinga ukuguqula igrafu exhunyiwe ibe enqanyuliwe.
Kwenziwa kanjani? Uma kukhona iphuzu lokukhuluma kugrafu, udinga ukulwa nalo. Iphoyinti lokuhlanganisa i-vertex ngendlela yokuthi lapho isusiwe, igrafu ilahlekelwa ukuxhumana kwayo. Wonke amaphuzu okuhlangana kugrafu angatholwa kusetshenziswa i-algorithm yakudala ngesikhathi somugqa. Le ndlela isheshisa kakhulu i-branching.
Uma noma imaphi ama-vertices akhethiwe esuswa, igrafu izohlukana ibe izingxenye ezixhunyiwe.
Sizokwenza lokhu, kodwa sifuna okwengeziwe. Isibonelo, bheka ukusikeka okuncane kwe-vertex kugrafu futhi uhlukanise eduze kwama-vertices asuka kuyo. Indlela esebenza kahle kakhulu engiyaziyo yokuthola ubuncane bokusika kwe-vertex yomhlaba ukusebenzisa isihlahla seGomori-Hu, esakhiwe ngesikhathi se-cubic. Ku-PACE Challenge, usayizi wegrafu ojwayelekile izinkulungwane ezimbalwa. Kulesi simo, amabhiliyoni okusebenza adinga ukwenziwa endaweni ngayinye ye-recursion tree. Kuvela ukuthi akunakwenzeka ukuxazulula inkinga ngesikhathi esibekiwe.
Ake sizame ukukhulisa ikhambi. Ukusikwa kwe-vertex encane phakathi kwepheya lezimemo kungatholwa nganoma iyiphi i-algorithm eyakha ukugeleza okuphezulu. Ungayivumela ingene kunethiwekhi enjalo , ekusebenzeni kusebenza ngokushesha okukhulu. Nginokusola ukuthi ngokombono kungenzeka ukufakazela isilinganiso sesikhathi sokusebenza , eseyamukeleka kakade.
Ngizame izikhathi ezimbalwa ukubheka ukusikeka phakathi kwamapheya ama-vertices angahleliwe futhi ngithathe okulingana kakhulu. Ngeshwa, lokhu kukhiqize imiphumela engemihle ekuhlolweni kwe-PACE Challenge evulekile. Ngiyiqhathanise ne-algorithm ehlukanisa ama-vertices we-degree degree, ngiwasebenzisa ngomkhawulo ekujuleni kokwehla. I-algorithm ezama ukuthola ukusikwa ngale ndlela ishiye ngemuva amagrafu amakhulu. Lokhu kungenxa yokuthi ukusikeka kwabonakala kungenakulinganisela kakhulu: ngemva kokukhipha ama-vertices angu-5-10, kwakungenzeka ukuhlukanisa kuphela i-15-20.
Kuyaphawuleka ukuthi ama-athikili mayelana nama-algorithms ashesha ngokomqondo asebenzisa amasu athuthuke kakhulu ekukhetheni ama-vertices azokwehlukaniswa. Amasu anjalo anokuqaliswa okuyinkimbinkimbi kakhulu futhi ngokuvamile ukusebenza kabi ngokwesikhathi nenkumbulo. Angikwazanga ukuhlonza lezo ezamukelekile ngempela ukuzenza.
Isetshenziswa Kanjani Imithetho Yokwenza Lula
Sesivele sinemibono yokwenza i-kernelization. Ake ngikukhumbuze:
- Uma kukhona i-vertex engayodwa, yisuse.
- Uma kukhona i-vertex ye-degree 1, yisuse futhi uthathe umakhelwane wayo ekuphenduleni.
- Uma kukhona i-vertex of degree okungenani k+1, buyisela.
Ngezokuqala ezimbili konke kucacile, okwesithathu kukhona iqhinga elilodwa. Uma enkingeni yamahlaya mayelana nebha sinikezwe umkhawulo ophezulu k, bese ku-PACE Challenge udinga nje ukuthola ikhava ye-vertex yosayizi omncane. Lokhu ukuguqulwa okujwayelekile Kwezinkinga Zosesho zibe Izinkinga Zesinqumo; ngokuvamile awukho umehluko phakathi kwezinhlobo ezimbili zezinkinga. Empeleni, uma sibhala isixazululi senkinga yokumboza i-vertex, kungase kube khona umehluko. Ngokwesibonelo, njengasephuzwini lesithathu.
Ngokombono wokusebenzisa, kunezindlela ezimbili zokuqhubeka. Indlela yokuqala ibizwa ngokuthi i-Iterative Deepening. Kungokulandelayo: singaqala ngesithiyo esithile esizwakalayo kusuka ngezansi empendulweni, bese siqhuba i-algorithm yethu sisebenzisa lesi sivimbelo njengesithiyo sempendulo evela phezulu, ngaphandle kokwehla ngokuphindaphinda kunalesi sivimbelo. Uma sithole impendulo ethile, kuqinisekisiwe ukuthi izoba yinhle, ngaphandle kwalokho singakwazi ukwandisa lo mkhawulo ngokukodwa bese siqala futhi.
Enye indlela iwukugcina impendulo ethile yamanje efanele bese ubheka impendulo encane, ushintshe le parameter uma itholakele k ukuze kunqanyulwe amagatsha angadingekile ekusesheni.
Ngemva kokwenza izivivinyo ezimbalwa zasebusuku, ngaxazulula inhlanganisela yalezi zindlela ezimbili: okokuqala, ngisebenzisa i-algorithm yami ngohlobo oluthile lomkhawulo ekujuleni kokusesha (ukuyikhetha ukuze kuthathe isikhathi esincane uma kuqhathaniswa nesixazululo esikhulu) futhi ngisebenzise okungcono kakhulu. isisombululo esitholakala njengomkhawulo ophezulu wempendulo - okungukuthi, into efanayo k.
Iziqu ze-degree 2
Sibhekane nama-vertices edigri 0 kanye no-1. Kuvela ukuthi lokhu kungenziwa ngama-vertices e-degree 2, kodwa lokhu kuzodinga imisebenzi eyinkimbinkimbi evela kugrafu.
Ukuchaza lokhu, sidinga ukuqoka ama-vertices ngandlela thile. Masibize i-vertex ye-degree 2 nge-vertex v, kanye nomakhelwane bayo - vertices x и y. Okulandelayo sizoba namacala amabili.
- Nini x и y - omakhelwane. Khona-ke ungaphendula x и y, futhi v susa. Impela, kulo nxantathu okungenani kufanele kuthathwe amathonsi amabili njengembuyiselo, futhi ngeke silahlekelwe nakanjani uma sithatha x и y: mhlawumbe banabanye omakhelwane, futhi v Abekho lapha.
- Nini x и y - hhayi omakhelwane. Bese kuthiwa womathathu ama-vertices anganamathiselwa abe munye. Umqondo uwukuthi kuleli cala kukhona impendulo elilungile, lapho sithatha noma v, noma ama-vertices womabili x и y. Ngaphezu kwalokho, esimweni sokuqala kuzodingeka sithathe bonke omakhelwane ngokuphendula x и y, kodwa okwesibili akudingekile. Lokhu kufana ncamashi namacala lapho singathathi i-vertex enamathiselwe ekuphenduleni nalapho sikwenza. Kuhlala kuphela ukuqaphela ukuthi kuzo zombili izimo impendulo evela ekusebenzeni okunjalo iyancipha ngokukodwa.
Kubalulekile ukuqaphela ukuthi le ndlela inzima kakhulu ukuyisebenzisa ngokunembile ngesikhathi somugqa ofanelekile. I-Gluing vertices kuwumsebenzi oyinkimbinkimbi; udinga ukukopisha uhlu lomakhelwane. Uma lokhu kwenziwa ngokunganaki, ungagcina unesikhathi sokusebenza esingena-asymptotically (isibonelo, uma ukopisha imiphetho eminingi ngemva kokunamathisela ngakunye). Ngazimisela ekutholeni izindlela eziphelele zeziqu ze-degree 2 kanye nokuhlaziya inqwaba yamacala akhethekile, anjengemijikelezo esuka kulawo mavertices noma kuwo wonke ama-vertices anjalo ngaphandle kweyodwa.
Ngaphezu kwalokho, kuyadingeka ukuthi lokhu kusebenza kuhlehliswe, ukuze kuthi lapho sibuya ekuphindaphindeni sibuyisele igrafu esimweni sayo sangempela. Ukuqinisekisa lokhu, angizange ngisule uhlu lwama-vertices ahlanganisiwe, ngase ngazi ukuthi imaphi amaphethelo okudingeka aye lapho. Lokhu kusetshenziswa kwamagrafu nakho kudinga ukunemba, kodwa kunikeza isikhathi somugqa esifanelekile. Futhi kumagrafu amashumi ezinkulungwane zamaphethelo, ingena kunqolobane yokucubungula, enikeza izinzuzo ezinhle ngesivinini.
I-kernel yomugqa
Ekugcineni, ingxenye ethakazelisa kakhulu ye-kernel.
Okokuqala, khumbula ukuthi kumagrafu e-bipartite ubuncane bekhava ye-vertex ingatholakala kusetshenziswa . Ukuze wenze lokhu, udinga ukusebenzisa i-algorithm ukuze uthole ukufana okuphezulu lapho, bese usebenzisa i-theorem .
Umbono we-kernel ewumugqa yilo: okokuqala sihlukanisa igrafu, okungukuthi, esikhundleni se-vertex ngayinye. v ake sengeze iziqongo ezimbili и , futhi esikhundleni sonqenqema ngalunye u-v asifake izimbambo ezimbili и . Igrafu ewumphumela izoba yi-bipartite. Ake sithole ubuncane bekhava ye-vertex kuyo. Amanye ama-vertices egrafu yoqobo azofika lapho kabili, amanye kanye kuphela, kanti amanye awasoze. Inkolelo-mbono ka- Nemhauser-Trotter ithi kulokhu umuntu angakhipha amachopho angazange ashaye nakanye abuyisele lawo ashaye kabili. Ngaphezu kwalokho, uthi kuma-vertices asele (lawo ashaya kanye) udinga ukuthatha okungenani uhhafu njengempendulo.
Sisanda kufunda ukushiya hhayi ngaphezu 2k iziqongo Impela, uma impendulo esele okungenani iyingxenye yawo wonke ama-vertices, awasekho ama-vertices esewonke. 2k.
Lapha ngakwazi ukuthatha igxathu elincane eliya phambili. Kuyacaca ukuthi i-kernel eyakhiwe ngale ndlela incike ekutheni hlobo luni lwekhava ye-vertex encane esiyithathile kugrafu ye-bipartite. Ngingathanda ukuthatha eyodwa ukuze inani lama-vertices asele libe lincane. Ngaphambili, babekwazi ukwenza lokhu kuphela ngesikhathi . Ngiqhamuke nokusetshenziswa kwale algorithm ngesikhathi , ngakho-ke, lo mgogodla ungaseshwa kumagrafu amakhulu ezinkulungwane zama-vertices esigabeni ngasinye sokuhlanganisa.
Umphumela
Ukuzijwayeza kukhombisa ukuthi isixazululo sami sisebenza kahle ekuhlolweni kwama-vertices angamakhulu ambalwa kanye nemiphetho eyizinkulungwane ezimbalwa. Ezivivinyweni ezinjalo kungenzeka ukulindela ukuthi isisombululo sizotholakala ngesigamu sehora. Amathuba okuthola impendulo ngesikhathi esamukelekile, ngokomthetho, ayanda uma igrafu inenani elikhulu ngokwanele lama-vertices anezinga eliphezulu, isibonelo, i-degree 10 nangaphezulu.
Ukuze ubambe iqhaza emqhudelwaneni, izixazululo bekufanele zithunyelwe kuwo . Ukwahlulela ngolwazi olwethulwe lapho , isixazululo sami ekuhlolweni okuvulekile sithatha indawo yesithathu kwamashumi amabili, negebe elikhulu kusukela kwesibili. Ukwethembeka ngokuphelele, akucaci ngokuphelele ukuthi izixazululo zizohlolwa kanjani emncintiswaneni ngokwawo: isibonelo, isisombululo sami sidlula izivivinyo ezimbalwa kunesixazululo endaweni yesine, kodwa kulabo abaphumelele, sisebenza ngokushesha.
Imiphumela yokuhlolwa okuvaliwe izokwaziwa ngoJulayi XNUMXst.
Source: www.habr.com