Ìmọ̀ nípa Àwòrán ní Ìṣirò
Ìlànà àwòrán jẹ́ ẹ̀ka ìṣirò onípele-ẹ̀yà tí ó ń ṣe àgbéyẹ̀wò ìṣètò ìbáṣepọ̀ láàrín àwọn ohun. Àwọn ohun wọ̀nyí ni a fihàn gẹ́gẹ́ bí àwọn ìpele (àwọn nodes), àti ìbáṣepọ̀ láàrín wọn ni a fihàn gẹ́gẹ́ bí egbegbe (àwọn arcs). Bó tilẹ̀ jẹ́ pé ó lè dún bí ohun tí ó rọrùn, ìmọ̀ àwòrán àwòrán ń kó ipa pàtàkì ní onírúurú ẹ̀ka, láti ìmọ̀ kọ̀ǹpútà àti ìmọ̀ ẹ̀rọ sí ìmọ̀ nípa ẹ̀dá àti ọrọ̀ ajé, àti àní sáyẹ́ǹsì àwùjọ. Ọ̀pọ̀lọpọ̀ ìṣòro gidi tí ó díjú ni a lè fi àwọn àwòrán ṣe àwòkọ́ṣe, èyí tí ó mú kí wọ́n rọrùn láti ṣàyẹ̀wò àti yanjú nípa lílo àwọn èrò ìṣirò.
Ìtumọ̀ àti Àwọn Ẹ̀yà Pàtàkì ti Àwòrán
Ní ìlànà, a sábà máa ń kọ àwòrán gẹ́gẹ́ bí G = (V, E), níbi tí:
– V (àkójọpọ̀ vertex) jẹ́ àkójọpọ̀ àwọn vertices.
– E (ẹgbẹ́ tí a ṣètò) ni àkójọ àwọn egbò tí ó so àwọn ègé méjì pọ̀.
Fún àpẹẹrẹ, tí V = {A, B, C} àti E = {(A,B), (B,C)}, nígbà náà àwòrán náà fihàn pé A so mọ́ B àti B so mọ́ C. Irú àfihàn yìí wúlò gan-an fún ṣíṣàpèjúwe àwọn nẹ́tíwọ́ọ̀kì ojú ọ̀nà, àjọṣepọ̀ ọ̀rẹ́ lórí àwọn ẹ̀rọ ìbánisọ̀rọ̀ àwùjọ, àwọn ìsopọ̀ kọ̀ǹpútà nínú àwọn nẹ́tíwọ́ọ̀kì, àti àwọn ètò mókúlíkì nínú kẹ́mísírì.
Àwọn nódù lè dúró fún onírúurú nǹkan, bí ìlú, àwọn olùlò, kọ̀ǹpútà, tàbí àwọn jínì. Àwọn etí dúró fún àjọṣepọ̀, bí àwọn ọ̀nà láàárín àwọn ìlú, àwọn ọ̀rẹ́, àwọn okùn nẹ́tíwọ́ọ̀kì, tàbí àwọn ìbáṣepọ̀ ẹ̀dá.
Àwọn Irú Àwòrán
Ìlànà àwòrán àwòrán dá oríṣiríṣi àwọn àwòrán mọ̀, ó sinmi lórí irú àwọn ìbáṣepọ̀ tí a ń ṣe àwòrán wọn:
1. Àwòrán tí kò ní ìtọ́sọ́nà
Àwọn ẹ̀gbẹ́ kò ní ìtọ́sọ́nà kankan. Tí A bá so mọ́ B, B náà ni a so mọ́ A. Àpẹẹrẹ: ìbádọ́rẹ̀ẹ́ ọ̀nà méjì.
2. Àwòrán tí a darí (àwòrán tí a darí / àwòrán)
Àwọn ègé ní ìtọ́sọ́nà, tí a fihàn gẹ́gẹ́ bí àwọn méjì tí a ṣètò (A → B). Èyí dára fún ṣíṣe àwòṣe àwọn ìbáṣepọ̀ “títẹ̀lé” nínú àwọn ìkànnì àwùjọ tàbí ìṣàn iṣẹ́.
3. Àwòrán oníwọ̀n
Etí kọ̀ọ̀kan ní iye tí a fi ìwọ̀n ṣe, bíi jíjìnnà, iye owó, tàbí àkókò ìrìnàjò. A sábà máa ń lo àwọn àwòrán oníwọ̀n láti wá àwọn ipa ọ̀nà tí ó yára jù tàbí tí ó rẹlẹ̀ jùlọ.
4. Àwòrán tó rọrùn
Kò ní ìlù àti kò ní etí méjì tí ó so àwọn ìlù méjì tí wọ́n jọra pọ̀.
5. Ọ̀pọ̀lọpọ̀
Ó gba ju ẹ̀gbẹ́ kan lọ láàyè láti so àwọn nódù kan náà pọ̀, èyí tó wúlò fún ṣíṣe àwòṣe ọ̀pọ̀lọpọ̀ ìbáṣepọ̀ nínú ètò kan.
6. Àwòrán pípé (àwòrán pípé)
Etí kan ṣoṣo ni a so gbogbo àwọn ìpele méjì pọ̀. Àwòrán pípé pẹ̀lú àwọn ìpele n ni a sábà máa ń kọ sí Kₙ. Èyí ni a sábà máa ń lò láti jíròrò àwọn ìdè tó pọ̀ jùlọ ti àwọn ìsopọ̀.
7. Àwòrán méjì
A le pin awọn nodule si awọn ẹgbẹ meji, ati awọn eti kan so awọn nodule lati awọn ẹgbẹ oriṣiriṣi. Awọn apẹẹrẹ: awọn oṣiṣẹ ati awọn iṣẹ ti o baamu, awọn ọmọ ile-iwe ati awọn ikẹkọ.
8. Igi
Àwòrán tí a so pọ̀ láìsí àwọn sílíkì. Àwọn igi ṣe pàtàkì nínú ètò ìṣètò dátà, àwọn ìpele ìṣètò, àti ìṣojú ìpinnu.
Àwọn Ìmọ̀ Pàtàkì Nínú Ìmọ̀ Àwòrán Àwòrán
Àwọn kókó pàtàkì kan nínú ìmọ̀ ẹ̀rọ àgbékalẹ̀ ni wọ̀nyí:
1. Ìpele Node
Ìwọ̀n ìpele ìpele kan ni iye àwọn egbegbe tí a so mọ́ ìpele náà. Nínú àwòrán tí a tọ́ka sí, ìwọ̀n ìpele (iye àwọn egbegbe tí ń bọ̀) àti ìwọ̀n ìpele tí ó kọjá (iye àwọn egbegbe tí ń jáde) wà. Ìpele wúlò fún wíwọ̀n "ìsopọ̀" ìpele kan nínú nẹ́tíwọ́ọ̀kì kan.
2. Àwọn ipa ọ̀nà, ipa ọ̀nà, àti àwọn kẹ̀kẹ́
– Ọ̀nà kan jẹ́ ìtẹ̀lé àwọn ìpele tí a so pọ̀ mọ́ àwọn ẹ̀gbẹ́.
– Ipa ọ̀nà jẹ́ ipa ọ̀nà tí kì í tún ṣe àtúnṣe sí etí.
– Sẹ́ẹ̀lì jẹ́ ipa ọ̀nà kan tí ó padà sí ibi ìbẹ̀rẹ̀ láìsí àwọn ẹ̀gbẹ́ tí ó tún padà (àti nígbà gbogbo láìsí àwọn nọ́ńbà tí ó tún padà àyàfi ìbẹ̀rẹ̀/òpin).
Èrò yìí ṣe pàtàkì fún òye ìlọ kiri nínú àwọn nẹ́tíwọ́ọ̀kì, àwọn ipa ọ̀nà tó ṣeé ṣe, àti wíwá ìlù nínú àwọn ètò.
3. Ìsopọ̀mọ́ra
A sọ pé àwòrán kan sopọ̀ tí gbogbo ìpele méjì bá ní ipa ọ̀nà tí ó so wọ́n pọ̀. Nínú àwọn àwòrán tí a tọ́ka sí, àwọn èrò pàtó kan wà nípa ìsopọ̀, bíi ti ìsopọ̀ tí ó lágbára (ìpele kọ̀ọ̀kan lè dé gbogbo ìpele mìíràn nípasẹ̀ etí kan).
Ìsopọ̀mọ́ra ṣe pàtàkì gan-an nínú ìṣàyẹ̀wò àwọn nẹ́tíwọ́ọ̀kì ìbánisọ̀rọ̀—fún àpẹẹrẹ, bóyá gbogbo àwọn kọ̀ǹpútà tó wà nínú nẹ́tíwọ́ọ̀kì náà ṣì lè bá ara wọn sọ̀rọ̀ bí ìsopọ̀ kan bá pàdánù.
4. Àwọn ìpín-ẹ̀ka àti Àwọn Ẹ̀yà-ẹ̀ka
Àkójọpọ̀ jẹ́ àkójọpọ̀ àwòrán tí a ṣe láti inú àkójọpọ̀ àwọn ìró àti etí. Àkójọpọ̀ tí a so pọ̀ ni àkójọpọ̀ tó ga jùlọ tí ó ṣì wà ní ìsopọ̀. Nínú ìṣàyẹ̀wò nẹ́tíwọ́ọ̀kì àwùjọ, àwọn àkójọpọ̀ lè ṣojú fún àwọn ẹgbẹ́ tí wọ́n sopọ̀ ṣùgbọ́n tí wọ́n yàtọ̀ sí ara wọn.
Àwọn Ìrònú àti Ìṣòro Àtijọ́
Ìlànà àgbékalẹ̀ àwòrán ní ìtàn gígùn, bẹ̀rẹ̀ pẹ̀lú ìṣòro Königsberg Bridges olókìkí tí Leonhard Euler yanjú ní ọ̀rúndún kejìdínlógún. Euler fihàn pé kò ṣeé ṣe láti kọjá gbogbo afárá méje náà lẹ́ẹ̀kan náà kí a sì padà sí ibi ìbẹ̀rẹ̀, èyí sì fi ìpìlẹ̀ ẹ̀kọ́ àgbékalẹ̀ àwòrán òde òní múlẹ̀.
Àwọn kókó ẹ̀kọ́ pàtàkì nínú ìmọ̀ ẹ̀rọ àgbékalẹ̀ pẹ̀lú:
1. Àwọn Ọ̀nà Ìtọ́sọ́nà Euler àti Hamilton
– Ọ̀nà Eulerian kan gba gbogbo ẹ̀gbẹ́ kan náà kọjá lẹ́ẹ̀kan náà. Àdéhùn fún wíwà ipa ọ̀nà Eulerian nínú àwòrán tí kò ní ìtọ́sọ́nà ni ó níí ṣe pẹ̀lú iye àwọn ìpele tí ó yàtọ̀.
– Ọ̀nà Hamiltonian kan máa ń lọ sí gbogbo ìpele kan náà lẹ́ẹ̀kan náà. Láìdàbí ìṣòro Euler, ìṣòro Hamilton le gan-an, àti ọ̀pọ̀lọpọ̀ àwọn ìyàtọ̀ rẹ̀ jẹ́ ti ìṣirò NP-le koko.
2. Àwọ̀ Àwòrán
Àwọ̀ àwòrán ni yíyàn àwọn àwọ̀ sí àwọn ìpele (tàbí etí) kí àwọn ìpele tó wà ní ẹ̀gbẹ́ má baà ní àwọ̀ kan náà. Ohun tí a mọ̀ dáadáa ni ìṣòro àwọ̀ àwòrán, èyí tó ń yọrí sí ìlànà pé gbogbo àwòrán àwòrán ni a lè fi àwọ̀ mẹ́rin kún (Ìlànà Àwọ̀ Mẹ́rin).
3. Àwòrán Pẹ́lẹ́ẹ̀tì
A le ya awọn aworan apẹrẹ lori ilẹ ti o tẹẹrẹ laisi awọn eti ti o ya. Awọn aworan apẹrẹ apẹrẹ ni a lo ni ibigbogbo ninu apẹrẹ awọn iyipo itanna ati iṣeto nẹtiwọọki.
Àwọn Algorithms Pàtàkì Nínú Ìlànà Àwòrán
Nínú ìmọ̀ kọ̀ǹpútà, ìlànà àwòrán ni ìpìlẹ̀ ọ̀pọ̀lọpọ̀ àwọn àlò-ọ̀rọ̀ pàtàkì:
– BFS (Ìwákiri Breadth-First) àti DFS (Ìwákiri Gíjinlẹ̀-First) fún ìyípo àwòrán, wíwá àwọn ẹ̀yà ara, wíwá ìyípo, àti ìpìlẹ̀.
– Dijkstra láti wá ipa ọ̀nà tó kúrú jùlọ nínú àwòrán oníwọ̀n pẹ̀lú àwọn ìwọ̀n tí kò ní òdì.
– Bellman–Ford fún ipa ọ̀nà tó kúrú jùlọ tí ó lè gbé àwọn ìwọ̀n òdì.
– Kruskal àti Prim láti rí igi tó kéré jùlọ tó wúlò fún ṣíṣe àgbékalẹ̀ nẹ́tíwọ́ọ̀kì pẹ̀lú owó tó kéré jùlọ.
Àwọn algoridimu wọ̀nyí fi bí àwọn èrò ìṣirò ti àwọn àwòrán ṣe ń kó ipa tààrà nínú yíyanjú àwọn ìṣòro tó wúlò hàn.
Àwọn Ìlò ti Ìmọ̀ Àwòrán Àwòrán ní Ìgbésí Ayé Gíga
Ìlànà àwòrán jẹ́ alágbára nítorí pé ó lè ṣe àwòkọ́ṣe “ìbáṣepọ̀” ní onírúurú àyọkà:
1. Gbigbe ati lilọ kiri
Àwọn nódù dúró fún àwọn ìtajà, àwọn etí dúró fún àwọn ọ̀nà, àti àwọn ìwọ̀n dúró fún ìjìnnà tàbí àkókò ìrìnàjò. Àwọn ètò ìtọ́sọ́nà ń lo àwọn algoridimu àwòrán láti pinnu ipa ọ̀nà tó dára jùlọ.
2. Àwọn nẹ́tíwọ́ọ̀kì kọ̀mpútà àti ìkànnì ayélujára
Àwọn olùdarí àti àwọn olùpèsè ń ṣiṣẹ́ gẹ́gẹ́ bí àwọn nódù, àti àwọn wáyà tàbí àwọn ìsopọ̀ ń ṣiṣẹ́ gẹ́gẹ́ bí ẹ̀gbẹ́. A ń lo ìṣàyẹ̀wò àwòrán láti mú kí ìtajà dátà sunwọ̀n síi àti láti mú kí agbára ìfaradà nẹ́tíwọ́ọ̀kì sunwọ̀n síi.
3. Àwọn nẹ́ẹ̀tìwọ́ọ̀kì àwùjọ
Àwọn olùlò gẹ́gẹ́ bí àwọn nódù, ìbáṣepọ̀ gẹ́gẹ́ bí àwọn etí. A lo ìlànà àwòrán láti ṣàwárí àwọn àwùjọ, wọ́n wọn ipa (ààrin), àti láti ṣàyẹ̀wò ìtànkálẹ̀ ìwífún.
4. Ìmọ̀ nípa ẹ̀dá àti kẹ́mísírì
A lo awọn aworan lati ṣe apẹẹrẹ awọn nẹtiwọọki jiini, awọn ibaraẹnisọrọ amuaradagba, tabi awọn eto molikula. Pupọ ninu awọn iwadii bioinformatics da lori itupalẹ aworan nla.
5. Iṣẹ́ àgbékalẹ̀ àti ìṣàkóso ilé iṣẹ́
A lo awọn aworan atọka ninu iṣeto iṣẹ-ṣiṣe (fun apẹẹrẹ PERT/CPM) lati wa awọn ilana iṣẹ ti o munadoko ati awọn ipa ọna pataki.
Penutup
Ìmọ̀ nípa àwòrán nínú ìmọ̀ ìṣirò jẹ́ ìkẹ́kọ̀ọ́ nípa ìṣètò ìbáṣepọ̀ nípasẹ̀ àwọn nódù àti etí. Pẹ̀lú onírúurú oríṣiríṣi àwòrán rẹ̀, àwọn èrò bíi ìpele, ipa ọ̀nà, cycle, àti àwọn algoridimu ìwárí àti ìṣàtúnṣe, ìmọ̀ nípa àwòrán jẹ́ irinṣẹ́ tó rọrùn àti tó lágbára. Agbára rẹ̀ wà nínú agbára rẹ̀ láti ṣojú fún àwọn ìṣòro tó díjú nínú àwọn àpẹẹrẹ tó ṣeé ṣe láti ṣàyẹ̀wò . Kò yani lẹ́nu pé ìmọ̀ nípa àwòrán jẹ́ ìpìlẹ̀ pàtàkì fún ìdàgbàsókè ìmọ̀ ìṣirò , ìmọ̀ kọ̀ǹpútà, àti ọ̀pọ̀lọpọ̀ àwọn ohun èlò òde òní tó ní ipa lórí ìgbésí ayé ojoojúmọ́.
Tí o bá fẹ́, mo tún lè fi àpẹẹrẹ ìṣòro kún àwọn ìjíròrò (fún àpẹẹrẹ nípa ipa ọ̀nà Euler, Dijkstra's, tàbí àwọ̀ àwòrán) láti jẹ́ kí àpilẹ̀kọ yìí wúlò sí i.
