Kumumanaʻo Kiʻi ma ka Makemakika
ʻO ke kumumanaʻo kiʻi he lālā ia o ka makemakika ʻokoʻa e aʻo ana i ke ʻano o nā pilina ma waena o nā mea. Hōʻike ʻia kēia mau mea ma ke ʻano he mau vertices (nodes), a hōʻike ʻia nā pilina ma waena o lākou ma ke ʻano he mau edges (arcs). ʻOiai he mea maʻalahi paha ke kani ʻana, he kuleana koʻikoʻi ke kumumanaʻo kiʻi ma nā ʻano like ʻole, mai ka ʻepekema kamepiula a me ka ʻenekinia a hiki i ka biology a me ka hoʻokele waiwai, a me nā ʻepekema pili kanaka. Hiki ke hoʻohālike ʻia nā pilikia paʻakikī he nui o ka honua maoli me ka hoʻohana ʻana i nā kiʻi, e maʻalahi ai ke kālailai a hoʻoponopono me ka hoʻohana ʻana i nā manaʻo makemakika.
Ka Wehewehena a me nā ʻĀpana Kumu o nā Kiʻi
Ma ke ʻano maʻamau, ua kākau pinepine ʻia kahi kiʻi penei: G = (V, E), kahi:
– ʻO V (hui piko) kahi hui o nā piko.
– ʻO E (kaʻe hoʻonohonoho) ka hoʻonohonoho o nā ʻaoʻao e hoʻopili ai i nā hui o nā piko.
Eia kekahi laʻana, inā ʻo V = {A, B, C} a me E = {(A,B), (B,C)}, a laila hōʻike ka pakuhi ua pili ʻo A iā B a ua pili ʻo B iā C. He mea pono loa kēia ʻano hōʻike no ka wehewehe ʻana i nā pūnaewele alanui, nā pilina aloha ma nā pāpili kaiapili, nā pilina kamepiula ma nā pūnaewele, a me nā ʻano molekala i ke kemika.
Hiki i nā kikowaena ke hōʻike i nā mea like ʻole, e like me nā kūlanakauhale, nā mea hoʻohana, nā kamepiula, a i ʻole nā genes. Hōʻike nā lihi i nā pilina, e like me nā alanui ma waena o nā kūlanakauhale, nā pilina aloha, nā kaula pūnaewele, a i ʻole nā pilina olaola.
Nā ʻAno o nā Kiʻi
Hoʻomaopopo ke kumumanaʻo kiʻi i nā ʻano kiʻi he nui, ma muli o ke ʻano o nā pilina e hoʻohālike ʻia nei:
1. Kiʻikuhi i kuhikuhi ʻole ʻia
ʻAʻohe kuhikuhi o nā ʻaoʻao. Inā pili ʻo A iā B, a laila pili pū ʻo B iā A. Laʻana: he pilina pili ʻelua ala.
2. Kiʻi kuhikuhi (kiʻi kuhikuhi / digraph)
Loaʻa i nā lihi ke kuhikuhi, i hōʻike ʻia ma ke ʻano he mau hui i hoʻonohonoho ʻia (A → B). He kūpono kēia no ke kumu hoʻohālike o nā pilina "hahai" ma nā pāpili kaiapili a i ʻole nā kahe hana.
3. Kiʻikuhi kaupaona
Loaʻa i kēlā me kēia lihi kahi waiwai kaupaona, e like me ka mamao, ke kumukūʻai, a i ʻole ka manawa huakaʻi. Hoʻohana pinepine ʻia nā kiʻi kaupaona e ʻike i nā ala wikiwiki loa a makepono paha.
4. Kiʻi maʻalahi
ʻAʻohe ona puka lou a ʻaʻohe ona ʻaoʻao pālua e hoʻopili ana i nā hui o nā puʻupuʻu like.
5. Multigraph
ʻAe i nā lihi he nui e hoʻohui i nā pūʻulu like, he mea pono no ke kumu hoʻohālike o nā pilina he nui i loko o kahi ʻōnaehana.
6. Kiʻi piha (kiʻi piha)
Hoʻopili ʻia kēlā me kēia pālua o nā piko e kekahi lihi. ʻO ka maʻamau, kākau ʻia kahi kiʻi piha me n mau piko ma ke ʻano he Kₙ. Hoʻohana pinepine ʻia kēia e kūkākūkā i ka palena kiʻekiʻe loa o nā pilina.
7. Kiʻikuhi bipartite
Hiki ke hoʻokaʻawale ʻia kahi hui o nā kikowaena i ʻelua mau pūʻulu, a hoʻohui wale nā ʻaoʻao i nā kikowaena mai nā hui like ʻole. Nā laʻana: nā limahana e hoʻohālikelike ana a me nā hana, nā haumāna a me nā papa.
8. Lāʻau
He kiʻi i hoʻopili ʻia me ka ʻole o nā pōʻaiapuni. He mea nui nā lāʻau i nā ʻōnaehana ʻikepili, nā hierarchies hoʻonohonoho, a me ka hōʻike hoʻoholo.
Nā Manaʻo Koʻikoʻi ma ke Kumumanaʻo Kiʻi
Eia kekahi mau manaʻo koʻikoʻi i loko o ke kumumanaʻo kiʻi:
1. Kekelē o ke kikowaena
ʻO ke kekelē o kahi kikowaena ka helu o nā lihi i hoʻopili ʻia i kēlā kikowaena. Ma kahi kiʻi kuhikuhi ʻia, aia ke kekelē-in (ka helu o nā lihi e komo mai ana) a me ke kekelē-out (ka helu o nā lihi e puka ana). He mea pono ke kekelē no ke ana ʻana i ka "pili" o kahi kikowaena i loko o kahi pūnaewele.
2. Nā Ala Kaʻa, nā Alahele, a me nā Paikikala
– He ala kahi moʻo o nā piko i hoʻopili ʻia e nā lihi.
– He alahele ke alahele ʻaʻole ia e hana hou i nā kihi.
– He ala ka pōʻaiapuni e hoʻi ana i ke kikowaena hoʻomaka me ka ʻole o nā lihi e hana hou ana (a ʻo ka maʻamau me ka ʻole o nā kikowaena e hana hou ana koe wale nō ka hoʻomaka/hopena).
He mea nui kēia manaʻo no ka hoʻomaopopo ʻana i ka hoʻokele ʻana i nā pūnaewele, nā ala hiki ke hele mai, a me ka ʻike ʻana i ka loop i nā ʻōnaehana.
3. Hoʻohui
Ua ʻōlelo ʻia he pili kahi kiʻi inā loaʻa i kēlā me kēia pālua o nā piko kahi ala e hoʻopili ana iā lākou. Ma nā kiʻi i kuhikuhi ʻia, aia nā manaʻo kikoʻī o ka pili ʻana, e like me ka pili ikaika (hiki i kēlā me kēia piko ke hiki i kēlā me kēia piko ʻē aʻe ma o kahi lihi).
He mea nui loa ka pilina i ka nānā ʻana i nā pūnaewele kamaʻilio—no ka laʻana, inā hiki i nā kamepiula āpau i loko o ka pūnaewele ke kamaʻilio pū kekahi me kekahi inā ua nalowale kekahi pilina.
4. Nā Subgraphs a me nā ʻĀpana
ʻO kahi subgraph kahi ʻāpana liʻiliʻi o kahi pakuhi i hana ʻia mai kahi ʻāpana liʻiliʻi o nā piko a me nā lihi. ʻO kahi ʻāpana i hoʻopili ʻia ka subgraph nui loa e pili mau ana. I ka nānā ʻana i nā pūnaewele kaiapili, hiki i nā ʻāpana ke hōʻike i nā hui i hoʻopili ʻia akā kaʻawale kekahi i kekahi.
Nā Kumumanaʻo Kuʻuna a me nā Pilikia
He mōʻaukala lōʻihi ko ke kumumanaʻo kiʻi, e hoʻomaka ana me ka pilikia kaulana ʻo Königsberg Bridges i hoʻoponopono ʻia e Leonhard Euler i ke kenekulia 18. Ua hōʻoia ʻo Euler ʻaʻole hiki ke hele i nā alahaka ʻehiku a pau i hoʻokahi manawa a hoʻi i kahi hoʻomaka, a pēlā e hoʻokumu ai i ke kahua o ke kumumanaʻo kiʻi hou.
ʻO kekahi mau kumuhana kuʻuna i ke kumumanaʻo kiʻi:
1. Nā Alahele ʻo Euler lāua ʻo Hamilton
– Hele kekahi ala Eulerian ma kēlā me kēia lihi i hoʻokahi manawa. ʻO ke kūlana no ke ola ʻana o kahi ala Eulerian i loko o kahi kiʻi kuhikuhi ʻole ʻia e pili ana i ka helu o nā piko o ke kekelē ʻē.
– Ke kipa aku nei kahi ala Hamiltonian i kēlā me kēia vertex i hoʻokahi manawa. ʻAʻole e like me ka pilikia o Euler, ʻoi aku ka paʻakikī o ka pilikia o Hamilton, a he nui nā ʻano like ʻole he NP-paʻakikī computationally.
2. Ke kala ʻana i nā kiʻi
ʻO ke kala ʻana o nā kiʻi ka hāʻawi ʻana i nā kala i nā piko (a i ʻole nā lihi) i ʻole e like ke kala o nā piko e pili ana. ʻO kahi noi kaulana ʻo ia ka pilikia kala palapala ʻāina, kahi e alakaʻi ai i ka theorem e hiki ke kala ʻia kēlā me kēia palapala ʻāina planar me ka nui o ʻehā mau kala (ka Four Color Theorem).
3. Kiʻi Planar
Hiki ke kaha kiʻi ʻia nā kiʻi planar ma kahi pālahalaha me ka ʻole o nā kihi e hui pū ana. Hoʻohana nui ʻia nā kiʻi planar i ka hoʻolālā kaapuni uila a me ka hoʻonohonoho pūnaewele.
Nā Algorithms Koʻikoʻi ma ke Kumumanaʻo Kiʻi
I ka ʻepekema kamepiula, ʻo ke kumumanaʻo kiʻi ke kumu o nā algorithms koʻikoʻi he nui:
– BFS (Breadth-First Search) a me DFS (Depth-First Search) no ke kaha kiʻi ʻana, ka ʻimi ʻāpana, ka ʻike ʻana i ke kaʻina hana, a me ka topology.
– ʻO Dijkstra e ʻimi i ke ala pōkole loa ma kahi kiʻi kaupaona me nā kaupaona ʻaʻole maikaʻi ʻole.
– Bellman–Ford no ke ala pōkole loa e hiki ke lawelawe i nā kaumaha maikaʻi ʻole.
– ʻO Kruskal lāua ʻo Prim e ʻimi i ka lāʻau spanning liʻiliʻi loa, he mea pono no ka hoʻolālā pūnaewele me ke kumukūʻai liʻiliʻi loa.
Hōʻike kēia mau algorithms pehea e pāʻani pololei ai nā manaʻo makemakika o nā kiʻi i ka hoʻoponopono ʻana i nā pilikia maoli.
Nā Hoʻohana o ke Kumumanaʻo Kiʻi ma ke Ola Maoli
He mana ko ke kumumanaʻo kiʻi no ka mea hiki iā ia ke hoʻohālike i nā "pilina" ma nā ʻano like ʻole:
1. Ka halihali a me ka hoʻokele ʻana
Hōʻike nā kikowaena i nā huina, hōʻike nā lihi i nā alanui, a hōʻike nā kaumaha i ka mamao a i ʻole ka manawa huakaʻi. Hoʻohana nā ʻōnaehana hoʻokele i nā algorithms kiʻi e hoʻoholo ai i ke ala maikaʻi loa.
2. Nā pūnaewele kamepiula a me ka pūnaewele
Hana nā mea hoʻohele a me nā kikowaena ma ke ʻano he mau kikowaena, a hana nā kaula a i ʻole nā pilina ma ke ʻano he mau lihi. Hoʻohana ʻia ka loiloi kiʻi e hoʻomaikaʻi i ka hele ʻana o ka ʻikepili a hoʻomaikaʻi i ke kūpaʻa o ka pūnaewele.
3. Nā pūnaewele kaiapili
ʻO nā mea hoʻohana ma ke ʻano he mau kikowaena, nā pilina ma ke ʻano he mau lihi. Hoʻohana ʻia ke kumumanaʻo kiʻi e ʻike i nā kaiāulu, ana i ka mana (centrality), a kālailai i ka hoʻolaha ʻike.
4. ʻO ke olaola a me ke kemika
Hoʻohana ʻia nā kiʻi e hoʻohālike i nā pūnaewele gene, nā pilina protein, a i ʻole nā ʻano molekala. Hilinaʻi ka nui o ka noiʻi bioinformatics i ka nānā ʻana i nā kiʻi nui.
5. Hoʻokele papahana a me nā ʻoihana
Hoʻohana ʻia nā kiʻi i kuhikuhi ʻia i ka hoʻonohonoho ʻana i nā hana (e like me PERT/CPM) e ʻike i nā kaʻina hana kūpono a me nā ala koʻikoʻi.
Pani
ʻO ke kumumanaʻo kiʻi ma ka makemakika ke aʻo ʻana i ke ʻano o nā pilina ma o nā kikowaena a me nā lihi. Me kona ʻano like ʻole o nā ʻano kiʻi, nā manaʻo e like me ke kekelē, ke ala, a me ke kaʻina hana, a me nā algorithms huli a me ka hoʻonui ʻana, he mea hana maʻalahi a ikaika loa ke kumumanaʻo kiʻi. Aia kona ikaika i kona hiki ke hōʻike i nā pilikia paʻakikī i nā hiʻohiʻona i hoʻonohonoho ʻia a hiki ke kālailai ʻia. ʻAʻole ia he mea kupanaha ua lilo ke kumumanaʻo kiʻi i kahua koʻikoʻi no ka hoʻomohala ʻana i ka makemakika discrete, ka ʻepekema kamepiula, a me nā noi hou he nui e hoʻopilikia i ke ola o kēlā me kēia lā.
Inā makemake ʻoe, hiki iaʻu ke hoʻohui i nā pilikia hoʻohālike me nā kūkākūkā (no ka laʻana e pili ana i ke ala o Euler, ʻo Dijkstra, a i ʻole ke kala ʻana o ka pakuhi) e ʻoi aku ka pili o kēia ʻatikala.
