Ozizi eserese na mgbakọ na mwepụ
Ozizi eserese bụ ngalaba mgbakọ na mwepụ dị iche iche nke na-amụ nhazi nke mmekọrịta dị n'etiti ihe. A na-anọchite anya ihe ndị a dị ka vertices (nodes), a na-egosipụtakwa mmekọrịta dị n'etiti ha dị ka nsọtụ (arcs). Ọ bụ ezie na ọ nwere ike ịda ka ihe dị mfe, ozizi eserese na-arụ ọrụ dị mkpa n'ọtụtụ ngalaba, site na sayensị kọmputa na injinia ruo na bayoloji na akụnụba, yana ọbụna sayensị mmekọrịta mmadụ na ibe ya. Enwere ike iji eserese mee ihe nlereanya ọtụtụ nsogbu dị mgbagwoju anya n'ụwa, na-eme ka ha dị mfe inyocha na idozi site na iji echiche mgbakọ na mwepụ.
Nkọwa na Ihe Ndị Dị Mkpa nke Eserese
N'ụzọ nkịtị, a na-edekarị eserese dịka G = (V, E), ebe:
– V (nhazi vertex) bụ otu vertices.
– E (nha nke etiti) bụ otu akụkụ nke na-ejikọ ụzọ abụọ nke oghere.
Dịka ọmụmaatụ, ọ bụrụ na V = {A, B, C} na E = {(A,B), (B,C)}, mgbe ahụ eserese ahụ na-egosi na A jikọtara na B na B jikọtara na C. Ụdị nnọchite anya a bara ezigbo uru maka ịkọwa netwọk okporo ụzọ, mmekọrịta enyi na mgbasa ozi mmekọrịta, njikọ kọmputa na netwọk, na ọbụna nhazi molekul na kemistri.
Nọdụ nwere ike ịnọchite anya ihe dị iche iche, dịka obodo ukwu, ndị ọrụ, kọmputa, ma ọ bụ mkpụrụ ndụ ihe nketa. N'akụkụ ya na-anọchite anya mmekọrịta, dịka ụzọ dị n'etiti obodo ukwu, ọbụbụenyi, eriri netwọk, ma ọ bụ mmekọrịta dị n'ime ya.
Ụdị eserese
Ozizi eserese na-amata ọtụtụ ụdị eserese, dabere na ọdịdị nke mmekọrịta a na-eme:
1. Eserese na-enweghị nduzi
Akụkụ ndị ọzọ enweghị ụzọ. Ọ bụrụ na A na-ejikọ B na B, mgbe ahụ B na-ejikọkwa A. Ihe atụ: ọbụbụenyi abụọ.
2. Eserese e duziri (eserese / digraph e duziri)
Akụkụ nwere ntụziaka, nke a na-egosi dị ka ụzọ abụọ e si hazie (A → B). Nke a dabara adaba maka ịme ihe nlereanya mmekọrịta "na-eso" na mgbasa ozi ọha ma ọ bụ usoro usoro.
3. Grafụ dị arọ
Ọnụ ụzọ ọ bụla nwere uru dị arọ, dịka anya, ọnụ ahịa, ma ọ bụ oge njem. A na-ejikarị eserese dị arọ achọta ụzọ kachasị ọsọ ma ọ bụ dị ọnụ ala.
4. Eserese dị mfe
O nweghị mkpọda na nsọtụ abụọ nke jikọtara eriri abụọ ahụ.
5. Ọtụtụ eserese
Na-enye ihe karịrị otu akụkụ ohere ijikọ otu ụzọ abụọ nke nodes, nke bara uru maka ịme ihe nlereanya nke ọtụtụ njikọ na sistemụ.
6. Eserese zuru oke (eserese zuru oke)
A na-eji otu akụkụ jikọọ akụkụ abụọ nke oghere abụọ ahụ. A na-edekarị eserese zuru oke nwere n vertices dị ka Kₙ. A na-ejikarị nke a atụle oke njikọ kachasị.
7. Eserese nke abụọ
Enwere ike kewaa otu n'ime otu abụọ, akụkụ ya na-ejikọkwa naanị n'etiti otu dị iche iche. Ihe atụ: ndị ọrụ na ọrụ ndị ọzọ, ụmụ akwụkwọ na ọmụmụ ihe.
8. Osisi
Grafụ ejikọtara na-enweghị okirikiri. Osisi dị oke mkpa n'usoro data, usoro nhazi, na nnọchite anya mkpebi.
Echiche Dị Mkpa n'Ozizi Eserese
Ụfọdụ isi echiche dị na ozizi eserese bụ ndị a:
1. Ogo Node
Ogo nke nodu bụ ọnụọgụgụ akụkụ ejikọtara na nodu ahụ. Na eserese e duziri, e nwere in-degree (ọnụọgụ nke nsọtụ na-abata) na out-degree (ọnụọgụ nke nsọtụ na-apụ apụ). Ogo bara uru maka ịtụ "njikọ" nke nodu na netwọk.
2. Ụzọ, Ụzọ, na Okirikiri
– Ụzọ bụ usoro nke oghere ndị e jikọtara site na nsọtụ.
– Ụzọ bụ ụzọ nke na-anaghị emegharị akụkụ ya.
– Okirikiri bụ ụzọ nke na-alaghachi na node mmalite na-enweghị nsọtụ ugboro ugboro (ọ na-abụkarịkwa na-enweghị node ugboro ugboro ma e wezụga mmalite/ngwụcha).
Echiche a dị mkpa maka nghọta nke ụzọ dị na netwọk, ụzọ ndị nwere ike ime, na nchọpụta loop na sistemụ.
3. Njikọta
A na-ekwu na eserese na-ejikọ ma ọ bụrụ na akụkụ abụọ nke oghere abụọ ahụ nwere ụzọ jikọtara ha. Na eserese ndị a na-eduzi, e nwere echiche ndị ọzọ gbasara njikọ, dị ka njikọ siri ike (akụkụ ọ bụla nwere ike iru akụkụ ọ bụla ọzọ site na nsọtụ).
Njikọ dị oke mkpa n'inyocha netwọk nkwukọrịta—dịka ọmụmaatụ, ma kọmputa niile dị na netwọk ahụ ka nwere ike ịkparịta ụka na ibe ha ma ọ bụrụ na otu njikọ efuo.
4. Ndepụta na Akụkụ
Akara bụ obere eserese nke e si na obere akụkụ na nsọtụ mepụta. Akụkụ ejikọtara bụ obere eserese kachasị elu nke ka na-ejikọ. Na nyocha netwọkụ mmekọrịta, ihe mejupụtara nwere ike ịnọchite anya otu ndị ejikọtara mana ha dị iche na ibe ha.
Usoro na Nsogbu Ndị Ochie
Echiche eserese nwere akụkọ ihe mere eme dị ogologo, malite na nsogbu Königsberg Bridges a ma ama nke Leonhard Euler doziri na narị afọ nke 18. Euler gosipụtara na ọ gaghị ekwe omume ịgafe àkwà mmiri asaa niile otu ugboro kpọmkwem wee laghachi na mmalite, si otú a guzobe ntọala nke ozizi eserese nke oge a.
Ụfọdụ isiokwu ndị a ma ama na ozizi eserese gụnyere:
1. Ụzọ Euler na Hamilton
– Ụzọ Eulerian na-agafe n'akụkụ ọ bụla kpọmkwem otu ugboro. Ọnọdụ maka ịdị adị nke ụzọ Eulerian na eserese na-enweghị nduzi metụtara ọnụọgụ nke vertices nke ogo dị iche iche.
– Ụzọ Hamiltonian na-eleta akụkụ ọ bụla kpọmkwem otu ugboro. N'adịghị ka nsogbu Euler, nsogbu Hamilton siri ike karịa, ọtụtụ n'ime ụdị ya dịkwa ike n'ịgụkọ NP.
2. Ịcha eserese
Agba eserese bụ itinye agba n'akụkụ (ma ọ bụ nsọtụ) ka akụkụ ndị dị n'akụkụ ghara inwe otu agba. Ihe a maara nke ọma bụ nsogbu agba maapụ, nke na-eduga na tiori na enwere ike iji agba anọ kacha agba maapụ planar ọ bụla (tiori agba anọ).
3. Eserese Planar
Enwere ike ise eserese planar n'elu ala dị larịị na-enweghị nsọtụ na-ejikọta ọnụ. A na-ejikarị eserese planar eme ihe n'ọtụtụ ebe na nhazi sekit eletrọniki na nhazi netwọk.
Algọridim dị mkpa na ozizi eserese
Na sayensị kọmputa, ozizi eserese bụ ntọala nke ọtụtụ algọridim dị mkpa:
- BFS (Nchọgharị Breadth-First) na DFS (Nchọgharị Omimi-First) maka ngagharị eserese, nchọta akụkụ, nchọpụta okirikiri, na topology.
– Dijkstra ịchọta ụzọ kacha mkpụmkpụ na eserese dị arọ nke nwere ibu arọ na-abụghị nke na-adịghị mma.
– Bellman–Ford maka ụzọ kacha mkpụmkpụ nke nwere ike ijikwa ibu arọ na-adịghị mma.
– Kruskal na Prim ga-achọta osisi kacha nta, nke bara uru maka imewe netwọk na obere ọnụ ahịa.
Algọridim ndị a na-egosi etu echiche mgbakọ na mwepụ nke eserese si arụ ọrụ kpọmkwem n'idozi nsogbu ndị bara uru.
Ojiji nke Echiche Eserese na Ndụ N'ezie
Ozizi eserese dị ike n'ihi na ọ nwere ike ịmepụta "mmekọrịta" n'ọtụtụ ọnọdụ:
1. Njem na njem
Nọdụ na-anọchite anya ebe ndị mmadụ na-aga, nsọtụ ha na-anọchite anya ụzọ, ebe ibu ha na-anọchite anya oge dị anya ma ọ bụ oge njem. Sistemụ nhazi ụzọ na-eji algọridim eserese iji chọpụta ụzọ kacha mma.
2. Netwọk kọmputa na ịntanetị
Ndị na-ahụ maka rawụta na sava na-arụ ọrụ dị ka nodes, eriri ma ọ bụ njikọ na-arụkwa ọrụ dị ka nsọtụ. A na-eji nyocha eserese eme ka okporo ụzọ data dịkwuo mma ma melite iguzogide netwọk.
3. Netwọk mmekọrịta
Ndị ọrụ dịka nodes, mmekọrịta dịka nsọtụ. A na-eji usoro eserese achọpụta obodo, tụọ mmetụta (etiti), na inyocha mgbasa ozi.
4. Bayọlọji na kemistri
A na-eji eserese eme ihe nlereanya maka netwọk mkpụrụ ndụ ihe nketa, mmekọrịta protein, ma ọ bụ nhazi molekul. Ọtụtụ nnyocha bioinformatics na-adabere na nyocha eserese buru ibu.
5. Ọrụ na njikwa ụlọ ọrụ mmepụta ihe
A na-eji eserese ndị a na-eduzi eme ihe n'usoro nhazi ọrụ (dịka ọmụmaatụ PERT/CPM) iji chọta usoro ọrụ dị irè na ụzọ dị mkpa.
Penutup
Ozizi eserese na mgbakọ na mwepụ bụ ọmụmụ nke nhazi nke mmekọrịta site na n'ọnụ na nsọtụ. Site na ụdị eserese dị iche iche ya, echiche dị ka ogo, ụzọ, na okirikiri, na algọridim ọchụchọ na nhazi, ozizi eserese bụ ngwaọrụ dị ike ma dị ike nke ukwuu. Ike ya dị n'ikike ya ịnọchite anya nsogbu dị mgbagwoju anya na ụdị nhazi na nyocha. Ọ bụghị ihe ijuanya na ozizi eserese aghọwo ntọala dị mkpa maka mmepe nke mgbakọ na mwepụ dị iche iche, sayensị kọmputa, na ọtụtụ ngwa ọgbara ọhụrụ nke na-emetụta ndụ kwa ụbọchị.
Ọ bụrụ na ịchọrọ, enwere m ike itinye ihe atụ nsogbu yana mkparịta ụka (dịka ọmụmaatụ gbasara ụzọ Euler, Dijkstra's, ma ọ bụ agba eserese) iji mee ka isiokwu a dịkwuo irè.
