Ny asa fikarohana angamba no ampahany mahaliana indrindra amin'ny fiofananay. Ny hevitra dia ny manandrana ny tenanao amin'ny lalana nofidinao raha mbola any amin'ny oniversite. Ohatra, ireo mpianatra avy amin'ny sehatry ny Software Engineering sy Machine Learning dia matetika mandeha manao fikarohana amin'ny orinasa (indrindra fa ny JetBrains na Yandex, fa tsy izany ihany).
Amin'ity lahatsoratra ity dia hiresaka momba ny tetikasako amin'ny Siansa Informatika aho. Ao anatin'ny asako, dia nianatra sy nampihatra fomba famahana ny iray amin'ireo olana sarotra NP malaza indrindra aho: olana momba ny vertex.
Amin'izao fotoana izao, ny fomba mahaliana amin'ny olana NP-sarotra dia mivoatra haingana - algorithmized parameter. Hiezaka ny hanafaingana anao aho, hilaza aminao algorithm tsotra voafantina ary mamaritra fomba iray mahery izay nanampy ahy betsaka. Nanolotra ny valin-teniko tamin’ny fifaninanana PACE Challenge aho: araka ny valin’ny andrana misokatra, mahazo ny laharana fahatelo ny vahaolana azoko, ary ho fantatra amin’ny 1 Jolay ny vokatra farany.
Ny tenako
Vasily Alferov no anarako, mamita ny taona fahatelo ao amin'ny National Research University Higher School of Economics - St. Petersburg aho. Liana tamin'ny algorithm aho hatramin'ny andro nianarako, fony aho nianatra tao amin'ny sekoly Moskoa No. 179 ary nandray anjara tamim-pahombiazana tamin'ny Olympiad momba ny siansa informatika.
Maromaro ny manam-pahaizana manokana amin'ny algorithm voamarika miditra ao anaty bar...
Ohatra avy amin'ny boky
Alao sary an-tsaina hoe mpiambina trano fisotroana ianao ao amin'ny tanàna kely iray. Isaky ny zoma, ny antsasaky ny tanàna dia tonga ao amin'ny trano fisotroanao mba hiala sasatra, izay manome anao fahasahiranana be: mila manary ireo mpanjifa mitabataba hiala amin'ny bar ianao mba hisorohana ny ady. Amin'ny farany, leo ianao ary manapa-kevitra ny handray fepetra fisorohana.
Koa satria kely ny tanànanao, fantatrao tsara hoe iza amin'ireo mpivady no mety hiady raha miara-mifarimbona amin'ny trano fisotroana izy ireo. Manana lisitry ny n olona izay ho tonga ao amin'ny trano fisotroana anio alina. Manapa-kevitra ny hanakana ny mponina sasany tsy hiditra ao amin'ny bar ianao fa tsy hisy hiady. Mandritra izany fotoana izany, ny lehibenao dia tsy te-very tombombarotra ary tsy ho faly raha tsy mamela mihoatra ny k ny olona.
Indrisy anefa, ny olana eo anoloanao dia olana mahazatra NP-sarotra. Mety ho fantatrao izy , na toy ny vertex mandrakotra olana. Ho an'ny olana toy izany, amin'ny tranga ankapobeny, tsy misy algorithm izay miasa amin'ny fotoana azo ekena. Raha ny marina, ny petra-kevitra tsy voaporofo sy tena matanjaka ETH (Exponential Time Hypothesis) dia milaza fa ity olana ity dia tsy voavaha ara-potoana. , izany hoe tsy afaka mieritreritra zavatra tsara kokoa noho ny fikarohana feno ianao. Ohatra, andao atao hoe misy olona ho avy ao amin'ny trano fisotroanao n = 1000 olombelona. Dia ho ny fikarohana feno safidy izay misy eo ho eo - vola adala. Soa ihany fa nanome fetra ho anao ny fitantananao k = 10, noho izany dia kely kokoa ny isan'ny fitambarana tokony haverinao: ny isan'ny soisa amin'ny singa folo dia . Tsara kokoa izany, saingy mbola tsy isaina ao anatin'ny iray andro izany na dia amin'ny cluster matanjaka aza.
Mba hanafoanana ny mety hisian'ny ady amin'ity fanamafisana ny fifandraisana misy eo amin'ny mpitsidika ny trano fisotroana ity, dia mila mitazona an'i Bob, Daniel ary Fedor ianao. Tsy misy vahaolana ka roa sisa no tavela.
Midika ve izany fa fotoana tokony hilefitra sy hamela ny rehetra hiditra? Andeha isika handinika safidy hafa. Eny ary, ohatra, dia tsy azo avela afa-tsy ireo izay mety hiady amin'ny olona maro be. Raha misy afaka miady farafaharatsiny amin'ny k+1 olon-kafa, dia azo antoka fa tsy afaka mamela azy hiditra ianao - raha tsy izany dia tsy maintsy manakana ny olona rehetra ianao k+1 mponina ao an-tanàna, izay azony miady, izay azo antoka fa hampahory ny mpitondra.
Avelao ianao handroaka izay rehetra azonao atao araka ity fitsipika ity. Avy eo ny olon-drehetra dia afaka miady amin'ny tsy mihoatra k olona. Mandroaka azy ireo k ralehilahy, tsy misy afa-tsy ny misakana anao fifandirana. Midika izany fa raha misy mihoatra ny Raha misy olona voarohirohy amin'ny fifandirana iray farafahakeliny, dia azo antoka fa tsy azonao atao ny misakana azy rehetra. Satria, mazava ho azy, dia azo antoka fa hamela olona tsy misy fifandirana tanteraka ianao, mila mamakivaky ny ampahany rehetra misy habe folo amin'ny olona roan-jato ianao. Misy eo ho eo , ary efa azo alamina ao amin'ny cluster io isan'ny asa io.
Raha afaka mandray soa aman-tsara ireo olona tsy misy fifandirana mihitsy ianao, ahoana ny amin'ireo izay mandray anjara amin'ny ady iray monja? Raha ny marina dia azo avela hiditra amin'ny fanakatonana ny varavarana amin'ny mpifanandrina aminy ihany koa izy ireo. Raha ny marina, raha i Alice ihany no miady amin'i Bob, dia raha avelantsika hiala amin'izy roa i Alice, dia tsy ho very isika: Mety hanana fifandirana hafa i Bob, fa i Alice dia tsy manana azy ireo. Ankoatra izany, dia tsy misy dikany ho antsika ny tsy hamela antsika roa hiditra. Taorian'ny hetsika toy izany dia tsy misy intsony vahiny manana anjara tsy voavaha: isika ihany fifandirana, samy misy mpandray anjara roa ary samy tafiditra ao anatin'ny roa farafahakeliny. Ka ny hany sisa tavela dia ny mandamina safidy, izay azo heverina mora foana antsasaky ny andro amin`ny solosaina finday.
Raha ny marina, miaraka amin'ny fanjohian-kevitra tsotra dia afaka mahazo toe-javatra manintona kokoa ianao. Mariho fa tena mila mamaha ny disadisa rehetra isika, izany hoe, avy amin'ny mpivady mifanipaka tsirairay, mifidy olona iray farafahakeliny izay tsy havelantsika hiditra. Andeha hodinihintsika ity algorithm manaraka ity: raiso ny fifandirana rehetra, izay esorinay ny mpandray anjara iray ary atomboka amin'ny ambiny, avy eo esory ny iray ary manomboka miverimberina. Koa satria manipy olona iray isaky ny dingana isika, ny hazo recursion amin'ny algorithm toy izany dia hazo mimari-droa lalina k, ka amin'ny fitambarany dia miasa ao ny algorithm izay n dia ny isan'ny vertices, ary m - isan'ny taolan-tehezana. Amin'ny ohatra ataontsika dia eo amin'ny folo tapitrisa eo ho eo izany, izay azo kajy ao anatin'ny segondra vitsy tsy amin'ny solosaina finday, fa na amin'ny finday aza.
Ny ohatra etsy ambony dia ohatra Algorithm parameterized. Ny algorithm parameterized dia algorithm izay mandeha ara-potoana f(k) poly(n)izay p - polynomial, f dia asa kajy tsy misy dikany, ary k - paramètre sasany, izay mety ho kely kokoa noho ny haben'ny olana.
Ny fanjohian-kevitra rehetra alohan'ity algorithm ity dia manome ohatra kernelization dia iray amin'ireo teknika ankapobeny amin'ny famoronana algorithm parameterized. Ny Kernelization dia ny fampihenana ny haben'ny olana amin'ny sanda voafetra amin'ny fiasan'ny parameter iray. Ny olana aterak'izany dia matetika antsoina hoe kernel. Noho izany, tamin'ny fanjohian-kevitra tsotra momba ny ambaratongan'ny vertices, dia nahazo kernel quadratic izahay ho an'ny olana Vertex Cover, voafaritry ny haben'ny valiny. Misy toe-javatra hafa azonao isafidianana amin'ity asa ity (toy ny Vertex Cover Above LP), fa ity no toerana horesahinay.
Pace Challenge
fifaninanana (The Parameterized Algorithms and Computational Experiments Challenge) dia teraka tamin'ny 2015 mba hametrahana fifandraisana eo amin'ny algorithm voafantina sy ny fomba fiasa ampiasaina amin'ny fampiharana hamahana ny olan'ny kajy. Ny fifaninanana telo voalohany dia natokana hitady ny sakan'ny hazo amin'ny grafika (), mitady hazo Steiner () ary mitady andiana vertices manapaka tsingerina (). Tamin'ity taona ity, iray amin'ireo olana azonao andramana ny olana momba ny vertex izay voalaza etsy ambony.
Mahazo laza isan-taona ny fifaninanana. Raha mino ny angon-drakitra savaranonando ianao, tamin'ity taona ity dia ekipa 24 no nandray anjara tamin'ny fifaninanana hamahana irery ny olana mandrakotra ny vertex. Marihina fa tsy adiny maromaro na herinandro mihitsy no faharetan’ny fifaninanana fa volana maromaro. Manana fahafahana handalina ny literatiora ny ekipa, hamoaka ny heviny manokana ary hiezaka hampihatra izany. Raha ny tena izy dia tetikasa fikarohana ity fifaninanana ity. Ny hevitra momba ny vahaolana mahomby indrindra sy ny fanomezana ny mpandresy dia hatao miaraka amin'ny fihaonambe (International Symposium on Parameterized and Exact Computation) ho ampahany amin'ny fivoriana algorithmika isan-taona lehibe indrindra any Eropa . Ny fampahalalana bebe kokoa momba ny fifaninanana dia azo jerena ao amin'ny , ary lainga ny vokatry ny taona lasa .
Diagram vahaolana
Mba hamahana ny olana mandrakotra ny vertex dia nanandrana nampiasa algorithms parameterized aho. Amin'ny ankapobeny dia misy fizarana roa izy ireo: fitsipika fanatsorana (izay mitarika ho amin'ny kernelization) ary fitsipika fisarahana. Ny fitsipika fanatsorana dia ny fanodinana ny fampidirana amin'ny fotoana polynomial. Ny tanjon'ny fampiharana ireo fitsipika ireo dia ny hampihenana ny olana amin'ny olana kely mitovy aminy. Ny fitsipika fanatsorana no ampahany lafo indrindra amin'ny algorithm, ary ny fampiharana an'io ampahany io dia mitarika amin'ny fotoana fandehanana manontolo fa tsy fotoana polynomial tsotra. Amin'ny tranga misy antsika, ny fitsipiky ny fisarahana dia mifototra amin'ny hoe isaky ny vertex dia mila mandray azy na ny mpifanolobodirindrina aminy ho valiny.
Ny rafitra ankapobeny dia izao: mampihatra ny fitsipika fanatsorana isika, avy eo misafidy vertex sasany, ary manao antso roa miverimberina: amin'ny voalohany dia raisinay ho setrin'izany, ary amin'ny iray hafa dia maka ny mpifanolo-bodirindrina aminy rehetra. Izany no antsoina hoe fisarahana (sampana) manaraka ity vertex ity.
Fanampiana iray mihitsy no hatao amin'ity tetika ity ao amin'ny andalana manaraka.
Hevitra momba ny fisarahana (brunching) fitsipika
Andeha hodinihintsika ny fomba hifidianana vertex iray izay hitrangan'ny fisarahana.
Ny hevi-dehibe dia tena tia vola amin'ny hevitry ny algorithmika: andao haka vertex amin'ny ambaratonga ambony indrindra ary hizara azy io. Nahoana no toa tsara kokoa? Satria amin'ny sampana faharoa amin'ny antso recursive dia hanala vertices be dia be amin'izany fomba izany. Afaka miantehitra amin'ny kisary kely sisa ianao ary afaka miasa haingana izahay.
Ity fomba fiasa ity, miaraka amin'ireo teknika kernelization tsotra efa noresahina, dia mampiseho ny tenany ary mamaha ny fitsapana sasany amin'ny vertices an'arivony. Saingy, ohatra, dia tsy mandeha tsara amin'ny grafofaonina toratelo (izany hoe ny grafofaonina izay telo ny haavon'ny vertex tsirairay).
Misy hevitra iray hafa mifototra amin'ny hevitra tsotra iray: raha tapaka ny grafofaonina, ny olana amin'ny singa mifandray aminy dia azo voavaha tsy miankina, manambatra ny valiny amin'ny farany. Ity, raha ny marina, dia fanovana kely nampanantenaina amin'ny drafitra, izay hanafaingana ny vahaolana: teo aloha, tamin'ity tranga ity, dia niasa ho an'ny vokatra amin'ny vanim-potoana ho an'ny kajy ny valin'ny singa, fa ankehitriny miasa ho an'ny ny sum. Ary mba hanafainganana ny sampana dia mila mamadika grafika mifandray ho lasa iray tsy mifandray ianao.
Ahoana no hanaovana izany? Raha misy teboka articulation ao amin'ny grafika dia mila miady amin'izany ianao. Ny teboka articulation dia vertex toy ny hoe rehefa nesorina dia very ny fifandraisany. Ny teboka junction rehetra amin'ny grafika dia azo jerena amin'ny alàlan'ny algorithm klasika amin'ny fotoana andalana. Io fomba fiasa io dia manafaingana be ny sampana.
Rehefa esorina ny iray amin'ireo vertices voafantina dia hisaraka ho singa mifandray ny kisary.
Hanao izany izahay, saingy mila bebe kokoa. Ohatra, tadiavo ireo tapa-kazo kely ao amin'ny grafika ary zarao manaraka ny vertex avy aminy. Ny fomba mahomby indrindra fantatro mba hahitana ny tapany farany ambany indrindra eran-tany dia ny fampiasana hazo Gomori-Hu, izay miorina amin'ny fotoana toratelo. Ao amin'ny PACE Challenge, ny haben'ny grafika mahazatra dia vertices an'arivony. Amin'ity toe-javatra ity dia mila fandidiana an'arivony tapitrisa isaky ny vertex amin'ny hazo recursion. Hita fa tsy azo atao ny mamaha ny olana amin'ny fotoana voatondro.
Andao hiezaka hanatsara ny vahaolana. Ny fahatapahan'ny vertex faran'izay kely indrindra eo anelanelan'ny vertex roa dia azo jerena amin'ny algorithm rehetra izay manorina fikorianana ambony indrindra. Azonao atao ny mametraka izany amin'ny tambajotra toy izany , amin'ny fampiharana dia miasa haingana dia haingana. Manana ahiahy aho fa azo atao ny manaporofo ny tombantombana momba ny fotoana fiasana , izay efa tena azo ekena.
Nanandrana im-betsaka aho nitady fahatapahana eo anelanelan'ny vertices kisendrasendra tsiroaroa ary naka ny iray voalanjalanja indrindra. Indrisy anefa fa niteraka vokatra ratsy izany tamin'ny andrana misokatra PACE Challenge. Nampitahaiko tamin'ny algorithm izay manasaraka ny vertices amin'ny ambaratonga ambony indrindra, mametaka azy ireo amin'ny fetran'ny halalin'ny fidinana. Algorithm miezaka mitady fanapahana amin'izany fomba izany dia namela sary lehibe kokoa. Izany dia noho ny zava-misy fa ny fanapahana dia tena tsy voalanjalanja: rehefa nesorina 5-10 vertices, dia azo atao ny nisaraka afa-tsy 15-20.
Tsara ny manamarika fa ny lahatsoratra momba ny algorithm haingana indrindra ara-teorika dia mampiasa teknika mandroso kokoa amin'ny fisafidianana vertices amin'ny fisarahana. Ny teknika toy izany dia manana fampiharana tena sarotra ary matetika tsy mahomby amin'ny resaka fotoana sy fitadidiana. Tsy afaka namaritra ireo izay azo ekena amin'ny fampiharana aho.
Ahoana ny fampiharana ny fitsipika fanatsorana
Efa manana hevitra momba ny kernelization izahay. Mamelà ahy hampahatsiahy anao:
- Raha misy vertex mitoka-monina dia vonoy.
- Raha misy tampon'ny mari-pahaizana 1 dia esory ary alao ny mpifanolobodirindrina aminy ho setrin'izany.
- Raha misy vertex de degree farafaharatsiny k+1, ento miverina.
Amin'ny roa voalohany dia mazava ny zava-drehetra, miaraka amin'ny fahatelo dia misy fitaka iray. Raha amin'ny olana amin'ny tantara an-tsary momba ny bara dia nomena fetra ambony k, avy eo ao amin'ny PACE Challenge dia mila mitady fonon'ny vertex kely indrindra ianao. Fanovana mahazatra ny Olan'ny Fikarohana ho Olana Fanapahan-kevitra; matetika tsy misy fahasamihafana eo amin'ireo karazana olana roa ireo. Amin'ny fampiharana, raha manoratra solver ho an'ny vertex mandrakotra olana isika, dia mety hisy fahasamihafana. Ohatra, toy ny ao amin'ny teboka fahatelo.
Amin'ny fomba fijery fampiharana, misy fomba roa hirosoana. Ny fomba voalohany dia antsoina hoe Iterative Deepening. Toy izao manaraka izao: afaka manomboka amin'ny teritery mitombina avy eto ambany isika amin'ny valiny, ary avy eo dia mandehana ny algorithm amin'ny fampiasana an'io faneriterena io ho toy ny faneriterena amin'ny valiny avy any ambony, nefa tsy midina ambany kokoa noho io teritery io. Raha nahita valiny izahay dia azo antoka fa ho tsara indrindra, raha tsy izany dia afaka mampitombo an'io fetra io isika ary manomboka indray.
Ny fomba iray hafa dia ny fitahirizana valiny tsara indrindra amin'izao fotoana izao ary mitady valiny kely kokoa, manova an'io mari-pamantarana io rehefa hita k ho an'ny fanapahana bebe kokoa ny sampana tsy ilaina amin'ny fikarohana.
Rehefa avy nanao fanandramana isan-kariva aho, dia niorim-paka tamin'ny fitambaran'ireo fomba roa ireo aho: voalohany, mihazakazaka ny algorithm-ko aho miaraka amin'ny karazana fetra amin'ny halalin'ny fikarohana (mifidy izany mba haka fotoana kely raha oharina amin'ny vahaolana fototra) ary mampiasa ny tsara indrindra. vahaolana hita ho fetra ambony amin'ny valiny - izany hoe, amin'ny zavatra mitovy k.
Vertices amin'ny ambaratonga 2
Niresaka momba ny vertices amin'ny ambaratonga 0 sy 1 izahay. Hita fa azo atao amin'ny vertices ny mari-pahaizana 2 izany, saingy mitaky asa sarotra kokoa avy amin'ny grafika izany.
Mba hanazavana izany dia mila manondro ny vertices isika. Andeha hatao hoe vertex ny vertex 2 v, sy ny mpifanolo-bodirindrina aminy - vertex x и y. Manaraka izany dia hanana tranga roa isika.
- rehefa x и y - mpifanolo-bodirindrina. Dia afaka mamaly ianao x и yary v mamafa. Eny tokoa, avy amin'ity telozoro ity dia tokony horaisina ny vertices roa farafahakeliny, ary azo antoka fa tsy ho very isika raha maka x и y: mety manana mpifanolo-bodirindrina hafa izy ireo, ary v Tsy eto izy ireo.
- rehefa x и y - tsy mpifanolo-bodirindrina. Avy eo dia voalaza fa azo apetaka amin'ny iray ny vertices telo. Ny hevitra dia amin'ity tranga ity dia misy valiny tsara indrindra, izay raisintsika na v, na ny vertex roa x и y. Ankoatra izany, amin'ny tranga voalohany dia tsy maintsy mandray ny mpiara-monina rehetra ho setrin'izany x и y, fa amin'ny faharoa dia tsy ilaina. Izany dia mifanitsy amin'ny tranga rehefa tsy mandray ny vertex glued ho valin'ny sy rehefa manao izany. Marihina fotsiny fa amin'ireo tranga roa ireo dia mihena iray ny valin'ny fandidiana toy izany.
Tsara ny manamarika fa ity fomba ity dia sarotra ny mampihatra amin'ny fomba marina amin'ny fotoana ara-drariny. Ny fametahana vertex dia asa sarotra; mila mandika ny lisitry ny mpifanolo-bodirindrina ianao. Raha atao tsy amim-pitandremana izany, dia mety hiafara amin'ny fotoana fandehanana asymptotically suboptimal ianao (ohatra, raha mandika sisiny be dia be ianao aorian'ny fametahana tsirairay). Nipetraka tamin'ny fitadiavana lalana iray manontolo avy amin'ny vertices 2 aho ary namakafaka tranga manokana, toy ny tsingerina avy amin'ny vertices toy izany na avy amin'ny vertices rehetra afa-tsy ny iray.
Fanampin'izany, ilaina ny hamerenana an'io asa io, ka rehefa miverina avy amin'ny recursion isika dia mamerina ny grafika amin'ny endriny voalohany. Mba hiantohana izany dia tsy nesoriko ny lisitry ny sisiny amin'ireo vertices natambatra, ary avy eo dia fantatro hoe iza amin'ireo sisiny tokony halehana any. Mitaky fahitsiana ihany koa ity fampiharana ny kisary ity, saingy manome fotoana ara-drariny. Ary ho an'ny grafika amin'ny sisiny an'aliny maromaro dia mifanaraka amin'ny cache processeur, izay manome tombony lehibe amin'ny hafainganam-pandeha.
Linear kernel
Farany, ny ampahany mahaliana indrindra amin'ny kernel.
Hanombohana, tadidio fa amin'ny sarin'ny bipartite dia azo ampiasaina ny fonon'ny vertex kely indrindra . Mba hanaovana izany dia mila mampiasa ny algorithm ianao mba hahitana ny mifanandrify ambony indrindra ao, ary avy eo dia ampiasao ny theorem .
Ny hevitra momba ny kernel linear dia izao: voalohany dia mizara ny grafika isika, izany hoe, fa tsy ny vertex tsirairay. v ndao asiana tampony roa и , ary ho solon'ny sisiny tsirairay u - v andao asiana taolan-tehezana roa и . Ny grafika aterak'izany dia ho bipartite. Andeha hojerentsika ny fonon'ny vertex kely indrindra ao anatiny. Ny vertices sasany amin'ny grafika tany am-boalohany dia ho tonga any indroa, ny sasany indray mandeha, ary ny sasany tsy. Ny teoria Nemhauser-Trotter dia milaza fa amin'ity tranga ity dia azo atao ny manala ny vertices izay tsy namely na dia indray mandeha aza ary mamerina ireo izay namely indroa. Ambonin'izany, hoy izy fa amin'ireo vertices sisa (ireo izay namely indray mandeha) dia mila mandray ny antsasany farafahakeliny ho valiny ianao.
Vao avy nianatra niala tsy mihoatra ny 2k tampon'isa Eny tokoa, raha ny valiny ambiny dia farafahakeliny antsasaky ny vertices rehetra, dia tsy misy vertices mihoatra ny totalin'ny. 2k.
Eto aho dia afaka nandroso kely. Mazava fa ny kernel namboarina tamin'izany fomba izany dia miankina amin'ny karazana fonon'ny vertex faran'izay kely indrindra noraisintsika tao amin'ny kisary bipartite. Te-haka iray aho mba ho faran'izay kely ny isan'ny vertices sisa. Teo aloha dia ara-potoana ihany no nahavitan’izy ireo izany . Tonga tamin'ny fampiharana an'io algorithm io aho tamin'ny fotoana , noho izany, ity fototra ity dia azo karohina amin'ny sarin'ireo vertices ana hetsiny isaky ny dingana sampana.
vokatra
Ny fanazaran-tena dia mampiseho fa ny vahaolana azoko dia miasa tsara amin'ny fitsapana ny vertices an-jatony sy ny sisiny an'arivony. Amin'ny fitsapana toy izany dia azo atao ny manantena fa hisy vahaolana ho hita ao anatin'ny antsasak'adiny. Ny mety hahitana valiny amin'ny fotoana azo ekena, amin'ny ankapobeny, dia mitombo raha toa ka manana vertices be dia be amin'ny ambaratonga ambony ny grafika, ohatra, ny mari-pahaizana 10 sy ambony.
Mba handraisana anjara amin'ny fifaninanana dia tsy maintsy nandefasana vahaolana . Raha jerena ny fanazavana natolotra tao , ny vahaolana azoko amin'ny andrana misokatra dia laharana fahatelo amin'ny roapolo, misy elanelana lehibe amin'ny faharoa. Raha ny marina, tsy mazava tsara ny fomba fanombanana ny vahaolana amin'ny fifaninanana: ohatra, ny vahaolana azoko dia mandalo fitsapana vitsy kokoa noho ny vahaolana amin'ny laharana fahefatra, fa amin'ireo izay mandalo dia miasa haingana kokoa.
Ho fantatra amin’ny XNUMX jolay izao ny valin’ny andrana mihidy.
Source: www.habr.com