Kumbuka kazi kutoka utoto - unahitaji kuteka bahasha wazi bila kuinua penseli kutoka karatasi, na bila kupita mara mbili upande wowote?

Kuna chaguzi chache, kwa hivyo, baada ya idadi ndogo ya majaribio ("2-3-4-2-1-5-4-1st ?!", "4-2-1-5-4-3-5th?! ”), mtoto yeyote alipata suluhisho sahihi. Na unahitaji tu kuanza kuchora ama kutoka kwa hatua ya 1 au kutoka kwa hatua ya 5. Baada ya hayo, harakati katika mwelekeo wowote hatimaye ilisababisha ufumbuzi wa tatizo.

Ni nini maalum kuhusu pointi hizi mbili, ya kwanza na ya tano? Ni nini kinawaruhusu kuwa mdhamini wa suluhisho la mafanikio? Nambari "ya lazima" tu ya pande zinazoungana katika kila moja ya nukta hizi za umoja kwa kutatua shida, ambayo ni, nambari isiyo ya kawaida! Hakika, katika pointi 1 na 5 hukutana kwa pande 3, kwa 2 na 4 - kwa 4, na kwa pili - 2. Kwa mujibu wa nadharia ya graph (ni nidhamu hii ambayo hutatua tatizo kwa urahisi), hitaji hili la " bahasha wazi" inaonekana kama hii:

Ikiwa ni muhimu kupata njia katika grafu iliyounganishwa iliyo na kingo zake zote mara moja, ambayo wima za mwanzo na mwisho hazifanani, ni muhimu na ya kutosha kwamba mwanzo na mwisho vertices pekee na digrii isiyo ya kawaida.

Kujua hili, inakuwa wazi kuwa haiwezekani kuteka "bahasha iliyofungwa" chini ya mahitaji sawa ya tatizo - vertices zote zina shahada isiyo ya kawaida.

Na mshtuko wowote juu ya mwanafunzi mwenzako - ni nini, wanasema, ni dhaifu? - imehesabiwa juu ya ujinga wa mwisho katika nadharia ya grafu!

Nadharia ya grafu ni uwanja mkubwa na uliofanyiwa utafiti vizuri hisabati tofauti.Aidha, hisabati bainishi huchanganya taaluma kama vile mantiki ya hisabati, cybernetics ya hisabati, nadharia ya mifumo tendaji na takriban nadharia 30 zaidi, zikiwemo za kigeni kama vile mantiki mfuatano na λ-calculus.

Lakini nyuma kwa grafu. Kwa hivyo - seti ya wima (nodi) zilizounganishwa na kingo. Katika ufafanuzi mkali, grafu ni jozi iliyopangwa G=(V,E), ambapo V ni seti isiyo tupu ya vipeo au nodi, na E ni seti ya jozi za vipeo, zinazoitwa kingo.

Vipeo vinaitwa terminal vipeo (au miisho tu) ya ukingo Ukingo, kwa upande wake, huunganisha wima hizi. Wima mbili za mwisho za makali sawa huitwa majirani.

Mbavu inaweza kuwa kuhusiana(kuwa na vertex ya mwisho ya kawaida) na nyingi(seti za wima zao za mwisho ni sawa). Ikiwa ncha za makali moja zinapatana, basi makali kama hayo huitwa kitanzi.

Digrii ya Vertex(unakumbuka "bahasha iliyofunguliwa"?) Ipe nambari ya tukio la kingo (yaani kingo zilizojumuishwa kwenye kipeo). Katika kesi hii, vitanzi vinahesabiwa mara mbili.

Juu inaitwa kutengwa ikiwa sio mwisho wa makali yoyote; kunyongwa(au karatasi) ikiwa ni mwisho wa makali moja haswa.

Kuna ufafanuzi mwingi katika nadharia ya grafu pekee. Grafu inaweza kuwa iliyoelekezwa(kingo zote zina mwelekeo kama vekta), uzito(kila makali hupewa nambari fulani inayoitwa uzito wa makali), kushikamana(vertices yoyote, kuna njia kutoka kwa) na kadhalika. Kama sheria, upanuzi wa anuwai ya shida zilizotatuliwa kwa njia ya nadharia hii ulisababisha kuibuka kwa ufafanuzi mpya na dhana. Ndio maana sio ufafanuzi mwingi wenyewe ambao ni wa kupendeza (unaweza kuwasoma kwenye kitabu chochote cha maandishi), lakini kazi wanazosuluhisha! Miongoni mwao ni classics kama vile "Tatizo la madaraja saba ya Koenigsberg"(moja ya shida za kwanza katika nadharia ya graph, iliyochapishwa na Euler mnamo 1736), "Tatizo la rangi nne"(iliundwa mnamo 1852, lakini uthibitisho ulipokelewa mnamo 1976 tu), "Tatizo la Wafanyabiashara wa Kusafiri", isomorphism hesabu, mpangilio

Hebu tuzingatie "tatizo la mfanyabiashara anayesafiri." Hebu tuzingatie kazi ya kawaida ya maabara katika hisabati ya kipekee:

Tatua tatizo la muuzaji anayesafiri kwa () miji na "algorithm ya uchoyo". Miji imepewa nasibu. Fikiria tatizo kuwa linganifu. Kigezo cha faida ni umbali kati ya miji. Andika programu.

Kwanza kabisa, nadharia kidogo.

Tatizo mfanyabiashara anayesafiri- moja ya shida maarufu, ambayo ni kutafuta njia yenye faida zaidi kupitia miji iliyoainishwa angalau mara moja na kisha kurudi kwenye jiji la asili. Katika hali ya tatizo, kigezo cha faida ya njia (fupi zaidi, ya bei nafuu, kigezo cha jumla, nk) kinaonyeshwa. Njia lazima ipitie kila jiji mara moja tu (chaguo hufanywa kati ya Kihamilton mizunguko).

Kwa kuwa mfanyabiashara anayesafiri katika kila jiji anakabiliwa na chaguo la jiji linalofuata ambalo bado hajatembelea, kuna njia za shida ya muuzaji anayesafiri. Kwa hivyo, kwa kesi, nambari inayolingana ya njia ni ,,.

Ni dhahiri kabisa kwamba hata kompyuta yenye nguvu zaidi haitasaidia kutatua tatizo kwa kuhesabu moja kwa moja (au "nguvu ya brute")! Sio bahati mbaya kwamba hali inazingatia algorithm ya takriban.

"Algorithm ya uchoyo", ambayo ni "njia ya jirani ya karibu" ni mojawapo ya njia rahisi zaidi za kutatua tatizo la muuzaji anayesafiri. Imeandaliwa kama ifuatavyo:

Miji imejumuishwa kwa mpangilio katika njia, na kila jiji linalofuata lililojumuishwa lazima liwe karibu zaidi na jiji la mwisho lililochaguliwa kati ya mengine yote ambayo bado hayajajumuishwa kwenye njia.

Wacha tufanye algorithm ya maneno.

Mtumiaji anaweka idadi ya miji - mara kwa mara CITIES_COUNT. Umbali kati ya miji huhifadhiwa katika safu ya Umbali ya mraba. Na njia bora, ambayo ni mlolongo bora wa faharisi za jiji, imehifadhiwa katika safu ya mstari wa Njia.

Kuna uanzishaji wa awali wa ramani ya miji. Ili kufanya hivyo, tunatumia algorithm isiyo ya kawaida (kutimiza mahitaji ya tatizo la awali "Miji kuamua nasibu").
Njia ya muuzaji anayesafiri inatafutwa - utaratibu wa CalcPath.
1. Hukokotoa matriki ya umbali wa kuheshimiana kati ya miji Umbali. -1 imehifadhiwa kwa sauti kwenye tumbo, pembetatu ya juu ya tumbo huhesabiwa na kunakiliwa kwa ile ya chini, kwa sababu. tumbo ni ulinganifu kuhusu diagonal kuu.
2. Ifuatayo, "tunaendesha" kupitia miji yote (iCurr variable), kuanzia ile ya awali (iStart), na kwa kila tunatafuta jiji la karibu (ambalo umbali ni mdogo), uihifadhi katika kutofautiana kwa iM na kuongeza. ni kwa Njia ya Njia. Wakati wa kutafuta jiji la karibu, tunapuuza miji hiyo ambayo tumetembelea tayari (umbali ambao = -1). Njiani, tunatafuta urefu wa jumla wa njia (Len);
3. Baada ya kujumuisha jiji linalofuata kwenye njia, tunaifuta kutoka kwa kuzingatia (tunaweka -1 kwenye tumbo la umbali kwenye safu na safu inayolingana na jiji hili).

Chati ya kutafuta njia inaonekana kama hii:

Matokeo ya programu (kupakua) kwa miji mitano (kwa uwazi zaidi) imewasilishwa hapa chini:

Mji wa kuanzia (mji wa nyumbani wa muuzaji) umewekwa alama nyekundu, iliyobaki kwa bluu.

Ikumbukwe kwamba suluhisho inategemea jiji la kuanzia ambalo ziara huanza. Kwa hiyo, mwanzoni mwa programu, orodha ya miji yote huundwa ili mtumiaji aweze kuchagua moja ya awali (iStart). Kila wakati unapobadilisha jiji la kuanzia, njia ya muuzaji anayesafiri inahesabiwa upya, ikitoa suluhisho zifuatazo:

Hata hivyo, hebu tukumbuke mahitaji ya tatizo. Kwa hivyo, kwa idadi ya miji 10, 100, 300, suluhisho zinaweza kuwa kama ifuatavyo.

Mchanganuo wa kuona wa suluhisho zilizopatikana, haswa kwa miji mia tatu (barabara ndefu ambayo mfanyabiashara anarudi katika mji wake kutoka mahali pa mwisho), inathibitisha nadharia kwamba "algorithm ya uchoyo" inaweza kutoa matokeo sio zaidi ya mara mbili ya bora zaidi. njia.. Mojawapo ya vigezo vya kutathmini suluhu ni sheria: ikiwa njia iliyosafirishwa katika hatua za mwisho za algorithm inalinganishwa na njia iliyosafirishwa katika hatua za mwanzo, basi njia iliyopatikana inaweza kuzingatiwa kukubalika kwa masharti, vinginevyo, suluhisho bora zaidi. pengine zipo.

Algorithm inayozingatiwa ni urithi. Katika njia nyingi za heuristic (njia mti wa chini unaozunguka, kuiga njia ya uchujaji, njia matawi na mipaka) sio njia bora zaidi, lakini suluhisho la takriban. Kwa mazoezi, hii ndiyo njia pekee ya kupata, ingawa ni takriban, suluhisho la tatizo. Bila shaka, njia mojawapo inaweza tu kutoa kamili hesabu ya chaguzi, lakini je, ni kweli kufanya hivyo kwa angalau miji 100, ambapo idadi ya chaguo hizi inaonyeshwa kama nambari ya tarakimu 156?!

Fasihi

Aho A., Hopcroft J., Ulman J. Miundo ya Data na Algorithms. - M.: Williams Publishing House, 2001.
Bondarev V.M., Rublinetsky V.I., Kachko E.G. Misingi ya programu. - Kharkiv: Folio; Rostov n / a: Phoenix, 1997.
Kormen T., Leyzerson Ch., Rivest R. Algorithms: ujenzi na uchambuzi. - M.: MTsNMO, 2001.
Romanovsky I.V. Uchambuzi wa Pekee… - Toleo la 2, limerekebishwa. - St. Petersburg: lahaja ya Nevsky, 2000.
Shen A. Programming: nadharia na matatizo. - M.: MTsNMO, 1995.

Suluhisho la hisabati ya kipekee kuagiza

Ikiwa una maswali yoyote - uliza katika maoni. Haja ya kutatua matatizo - utaratibu.
Tutafurahi kukusaidia!

GRAPHS

Grafu zilianza katika karne ya kumi na nane wakati mwanahisabati maarufu, Leonhard Euler, alipokuwa akijaribu kutatua tatizo la daraja la kisasa la Königsberg. Wakati huo katika jiji la Koenigsberg kulikuwa na visiwa viwili vilivyounganishwa na madaraja saba kwenye ukingo wa Mto Pregol na kwa kila mmoja, kama inavyoonyeshwa kwenye mtini. 7.1. Kazi ni kama ifuatavyo: kufanya matembezi kuzunguka jiji kwa njia ambayo, baada ya kupita mara moja kwenye kila daraja, kurudi mahali pale ambapo matembezi yalianza. Kutatua tatizo hili, Euler alionyesha Koenigsberg kama grafu, inayotambulisha wima yake na sehemu za jiji, na kingo zake kwa madaraja yanayounganisha sehemu hizi. Kama tutakavyoonyesha katika § 7.1, Euler alifaulu kuthibitisha kwamba njia inayohitajika kuzunguka jiji haipo.

Kielelezo 7.1. Mpango wa zamani wa Koenigsberg

Katika sura hii, tunatanguliza istilahi sanifu zinazotumiwa katika nadharia ya grafu na kujadili matatizo kadhaa mahususi ambayo grafu zinaweza kutatua. Hasa, tutafahamiana na darasa la grafu inayoitwa miti. Miti ni kielelezo cha asili kinachowakilisha data iliyopangwa katika mfumo wa daraja. Kutafuta kupitia mti ili kutenga vitu vya mtu binafsi na kupanga data kwenye mti ni hatua muhimu za juhudi katika sayansi ya kompyuta. Katika kiambatisho cha sura hii, tutashughulika na kupanga na kutafuta data iliyopangwa katika miti.

Grafu na istilahi

Kwenye mtini. 7.1 inaonyesha madaraja saba ya Koenigsberg kama ifuatavyo. jinsi zilivyopangwa katika karne ya kumi na nane. Shida iliyoshughulikiwa na Euler inauliza: inawezekana kupata njia ya kutembea ambayo hupita mara moja juu ya kila daraja na kuanza na kuishia mahali pamoja katika jiji?

Mfano wa kazi ni grafu, yenye wengi vilele na wengi mbavu, kuunganisha vilele. Vipeo A, B, C na D ishara ya kingo za mto na kisiwa, na mbavu a, c, c,df na g kuwakilisha madaraja saba (ona mchoro 7.2). Njia inayotakiwa (ikiwa ipo) inalingana na kuvuka kingo za grafu kwa namna ambayo kila moja yao inapitiwa mara moja tu. Njia ya ubavu ni wazi inalingana na kuvuka kwa mto juu ya daraja.

Kielelezo 7.2. Mfano wa tatizo la daraja la Königsberg

Grafu ambayo kuna njia, kuna njia inayoanza na kuishia kwenye kipeo kimoja, na kupita kando ya kingo zote za grafu mara moja, inaitwa. grafu ya syler. Mlolongo wa wima (labda na marudio) ambayo njia inayotaka hupita, pamoja na njia yenyewe, inaitwa. Euler mzunguko. Euler aliona kwamba ikiwa kuna mzunguko wa Euler kwenye grafu, basi kwa kila makali inayoongoza kwenye vertex fulani, lazima kuwe na makali mengine yanayotoka kutoka kwenye vertex hii 1, na kutokana na uchunguzi huu rahisi alipata hitimisho zifuatazo: ikiwa kuna mzunguko wa Euler. katika grafu hii , basi idadi sawa ya kingo lazima ifikie kila kipeo.

Kwa kuongezea, Euler alifaulu kuthibitisha dai lililo kinyume, hivyo kwamba grafu ambayo jozi yoyote ya wima imeunganishwa kwa mfuatano fulani wa kingo ni Euler ikiwa na tu ikiwa vipeo vyake vyote vina digrii sawa. Shahada vipeo v inaitwa nambari δ(v) mbavu, yeye tukio 2 .

Sasa ni dhahiri kabisa kwamba mzunguko wa Euler hauwezi kupatikana kwenye grafu inayoiga tatizo la daraja la Königsberg. Hakika, digrii za wima zake zote ni za kushangaza: δ(B) = δ(C)= δ(D) = 3 na δ(A) = 5. Kwa msaada wa Euler, grafu kama ile tuliyojifunza wakati wa kutatua tatizo la daraja ilianza kutumika katika kutatua matatizo mengi ya vitendo, na utafiti wao ulikua eneo muhimu la hisabati.

grafu rahisi inafafanuliwa kama jozi G = (V, E), ambapo V ni seti ya mwisho ya wima, na E ni seti ndogo ya kingo, na haiwezi kuwa na vitanzi(kingo zinazoanza na kuishia kwenye kipeo kimoja) na kingo nyingi(Nyingi ni kingo kadhaa zinazounganisha jozi sawa ya wima). Grafu iliyoonyeshwa kwenye Mtini. 7.2. si rahisi kwa sababu, kwa mfano, wima A na V zimeunganishwa na kingo mbili (kingo hizi tu huitwa nyingi).

vilele viwili u na v katika grafu rahisi huitwa kuhusiana ikiwa zimeunganishwa kwa makali fulani e, ambayo inasemekana kuwa kwa bahati mbaya juu u (na v ). Kwa hivyo, tunaweza kufikiria seti E kingo kama seti ya jozi za vipeo vilivyo karibu, na hivyo kufafanua uhusiano usio wa kurejea, wa ulinganifu kwenye seti. v. Kutokuwepo kwa reflexivity ni kutokana na ukweli kwamba katika grafu rahisi hakuna loops, yaani, kando, mwisho wote ambao ni kwenye vertex sawa. Ulinganifu wa uhusiano unafuata kutokana na ukweli kwamba makali e kuunganisha vertex na Na v, inaunganisha na v Na na(kwa maneno mengine, kingo hazielekezwi, yaani, hazina mwelekeo). Ukingo pekee wa grafu rahisi inayounganisha jozi ya wima u na v, tutaashiria kama na v(au vi).

Matrix ya kimantiki ya uhusiano kwenye seti ya wima ya grafu, ambayo hutolewa na kingo zake, inaitwa. , matrix ya ukaribu. Ulinganifu wa uhusiano katika suala la matriki ya karibu M inamaanisha kuwa M ulinganifu kuhusu diagonal kuu. Na kwa sababu ya kutobadilika kwa uhusiano huu kwenye diagonal kuu ya matrix M inasimama kwa "L".

Mfano 7.1. Chora grafu G(V, E) na seti ya wima V = (a, b, c, d, e) na seti ya kingo E = (ab, ae, bc, bd, ce, de). Andika matrix yake ya ukaribu.

Suluhisho. Grafu G imeonyeshwa kwenye mtini. 7.3.

Kielelezo 7.3.

Matrix yake ya karibu ni:

Ili kurejesha grafu, tunahitaji tu vipengele vya tumbo vya karibu vilivyo juu ya diagonal kuu.

Subgraph grafu G = (V, E) inaitwa grafu G’ = (V’, E’) ambamo E’ C E na V’ C V.

Mfano 7.2 Tafuta kati ya grafu H, K na L iliyoonyeshwa kwenye mtini. 7.4, vifungu vidogo vya grafu G.

Suluhisho. Onyesha wima za grafu G, H na K kama inavyoonyeshwa kwenye Mtini. 7.5. Grafu H na K ni tanzu za G, kama inavyoweza kuonekana kutoka kwa nukuu yetu. Grafu L si tanzu ya G, kwa sababu ina kipeo cha faharasa 4, huku G haina.

njia urefu k katika grafu G inaitwa mlolongo huo wa wima v 0 , v 1 , …, v k , kwamba kwa kila i = 1, ..., k jozi v i – 1 v i huunda makali ya grafu. Tutateua njia kama vile v 0 v 1 … v k . Kwa mfano, 1 4 3 2 5 ni njia ya urefu wa 4 kwenye safu G kutoka kwa Mfano 7.2.

G H

K L

Kielelezo 7.4.

mzunguko katika grafu inaitwa mlolongo wa wima v 0 , v 1 , … , v k , kila jozi ambayo ni ncha za makali moja, na v 0 = v 1 , na vipeo vingine (na kingo) hazirudiwi. Kwa maneno mengine, mzunguko ni njia iliyofungwa inayopitia kila wima na kingo zake mara moja tu.

1 2 1 2 3

Kielelezo 7.5

Mfano 7.3. Tafuta mizunguko kwenye grafu G kutoka kwa Mfano 7.2.

Suluhisho. Kuna mizunguko miwili tofauti ya urefu wa 5 kwenye grafu hii:

1 3 2 5 4 1 na 1 2 5 4 3 1

Tunaweza kupitia mizunguko hii katika mwelekeo mmoja na mwingine, kuanzia kipeo cha kiholela cha mzunguko. Kwa kuongeza, kuna mizunguko mitatu tofauti ya urefu wa 4 kwenye grafu:

1 2 5 4 1, 1 2 3 4 1 na 2 5 4 3 2,

na vitanzi viwili vya urefu wa 3:

1 2 3 1 na 1 3 4 1.

Grafu bila mizunguko inaitwa acyclic. Miundo ya miti inayojitokeza katika kompyuta ni kesi maalum ya grafu za acyclic. Tutazishughulikia baadaye katika sura hii.

Earl, aliita kushikamana, ikiwa jozi yoyote ya wima yake imeunganishwa na njia fulani. Grafu yoyote ya jumla inaweza kugawanywa katika subgraphs, ambayo kila moja inageuka kuwa imeunganishwa. Nambari ya chini ya vipengele vile vilivyounganishwa inaitwa nambari ya uunganisho grafu na inaonyeshwa na c(G) . Masuala ya muunganisho yana umuhimu mkubwa katika matumizi ya nadharia ya grafu kwa mitandao ya kompyuta. Algorithm ifuatayo inatumiwa kuamua nambari ya muunganisho wa grafu.

Algorithm ya uunganisho.

Acha G = (V, E) iwe grafu. Algorithm imeundwa kukokotoa thamani c = c(G), hizo. idadi ya vipengele vilivyounganishwa vya grafu iliyotolewa G.

V':=V;

wakatiV’≠ øfanya

Chagua y Є V’

Tafuta wima zinazounganishwa na njia na y;

Ondoa vertex kutokaV'na

kingo zinazolingana kutoka kwa E;

c:= c+1;

Mfano 7.4. Fuata kazi ya algorithm ya uunganisho kwenye grafu iliyoonyeshwa kwenye Mtini. 7.6.

Kielelezo 7.6.

Suluhisho. Tazama meza. 7.1.

Jedwali 7.1.


Maadili ya awali	{1,2,3,4,5,6,7,8}
Chaguo y = 1
Chaguo y = 2
Chaguo y = 7

Kwa hiyo, c(G) = 3. Vipengele vya uunganisho vinavyofanana vinaonyeshwa kwenye Mtini. 7.7.

Taasisi ya Kielimu ya Jimbo la Shirikisho la Elimu ya Taaluma ya Juu

"Taasisi ya Ufundishaji ya Jimbo la Mordovia iliyopewa jina la M.E. Evsevyeva"

Kitivo cha Fizikia na Hisabati

dhahania

juu ya mada hii:

"Nadharia ya Grafu"

Imekamilika: mwanafunzi

kikundi cha MDM-109

Dobrynkina O.A.

Imeangaliwa na: Lapina I.E.

Saransk 2014

Utangulizi ………………………………………………………………………. 3

1. Dhana za kimsingi za nadharia ya grafu………………………………………………… 4

2. Mifano ya grafu……………………………………………………………………. nane

3. Grafu za Euler………………………………………………………………… 13

4. Mifano ya Matumizi ya Nadharia ya Grafu……………………………………………. kumi na sita

5. Tatizo la njia fupi zaidi……………………………………………………… 18

6. Algorithm ya kutafuta mtiririko wa juu zaidi ………………………….. 27

Hitimisho …………………………………………………………………… 38

Marejeleo………………………………………………………………… 39

Utangulizi

Hivi karibuni, kumekuwa na uingiliaji wa kutosha wa mbinu za hisabati katika matawi mbalimbali ya sayansi na teknolojia. Mchakato wa hisabati pia uliathiri sayansi ya uchumi.

Wazo la grafu, yenyewe ni rahisi sana, liligeuka kuwa na matunda sana katika sayansi na hutumiwa mara nyingi. Nadharia ya grafu huchunguza grafu kama miundo dhahania ya hisabati, bila kujali tafsiri zao mahususi, na matokeo ya jumla yanayopatikana kisha kutumika kwa taaluma mbalimbali.

Neno "hesabu" lilipata haki ya uraia na likaingia katika lugha ya hisabati mnamo 1936, baada ya kuchapishwa kwa monograph ya Koenig, ambayo kwa mara ya kwanza grafu husomwa kama vitu huru vya hisabati, bila kujali yaliyomo.

Utafiti wa grafu ni muhimu leo. Kutafuta njia fupi ya mchepuko au duka la karibu la mboga, kupanga njia bora - hii yote ni mifano kutoka kwa maisha yetu ya kila siku. Shida hizi na zingine nyingi zinaweza kutatuliwa kwa kutumia grafu.

Katika karatasi hii, idadi ya dhana za kimsingi zimeainishwa, mifano ya matumizi ya nadharia ya grafu pia imetolewa na mbinu mbili za kutatua matatizo ya kiuchumi kwa kuzingatia nadharia ya grafu zinazingatiwa.

1. Dhana za kimsingi za nadharia ya grafu

Grafu ni mfumo ambao unaweza kuzingatiwa kwa intuitively kama seti ya miduara na seti ya mistari inayowaunganisha (Mchoro 1).

Miduara inaitwa vipeo vya grafu, mistari yenye mishale inaitwa arcs, na mistari isiyo na mishale inaitwa kingo. Grafu ambayo mwelekeo wa mistari haujatofautishwa (mistari yote ni kingo) inaitwa isiyoelekezwa (Mchoro 1, A); grafu ambayo mwelekeo wa mistari ni ya msingi (mistari ni arcs) inaitwa iliyoelekezwa (Mchoro 1, B).

Def. 1. Seti ya mwisho inatolewa X, inayojumuisha n vipengele ( X={1, 2,…, n)), inayoitwa wima ya grafu, na sehemu ndogo ya V ya bidhaa ya Cartesian X ×X, i.e.
, inayoitwa seti ya arcs, kisha grafu iliyoelekezwa G ni mkusanyiko (X, V).

Def. 2. Grafu ambayo haijaelekezwa ni mkusanyiko wa seti ya X na seti ya jozi za vipengele visivyopangwa, ambayo kila moja ni ya seti ya X.

Safu kati ya wima i na j,
, tutaashiria (i, j). Idadi ya safu za grafu itaonyeshwa na m (V = (
)).

Def. 3. Grafu ndogo ni sehemu ya grafu iliyoundwa na kikundi kidogo cha wima pamoja na kingo zote (arcs) zinazounganisha za wima kutoka kwa seti hii. Ikiwa tunaondoa baadhi ya kingo (arcs) kutoka kwa grafu, tunapata grafu ya sehemu.

Def. 4. Wima mbili huitwa karibu ikiwa zimeunganishwa na makali (arc). Vipeo vya karibu huitwa wima za mpaka wa kingo inayolingana (arc), na ukingo huu (arc) huitwa tukio kwa wima zinazolingana.

Def.5. Njia ni mlolongo wa arcs (katika grafu iliyoelekezwa) hivi kwamba mwisho wa arc moja ni mwanzo wa arc nyingine.

Def. 5.1. Njia rahisi ni njia ambayo hakuna arc hutokea mara mbili.

Def. 5.2. Njia ya msingi ni njia ambayo hakuna vertex hutokea mara mbili.

Def. 5.3. Njia ni njia ambayo kipeo cha mwisho ni sawa na kipeo cha mwanzo.

Def. 5.4 Urefu wa njia (contour) ni idadi ya arcs ya njia (au jumla ya urefu wa arcs yake, ikiwa mwisho hutolewa).

Def.6. Grafu ambayo kutoka (i, j) V inafuata (j, i) V inaitwa ulinganifu.

Def. 7. Ikiwa kutoka (i, j) V inamaanisha kuwa (j, i)
V, kisha grafu inayofanana inaitwa antisymmetric.

Def. 8.1. Mlolongo ni seti ya kingo (katika grafu isiyoelekezwa) ambayo inaweza kupangwa ili mwisho (katika mpangilio huo) wa makali moja ni mwanzo wa mwingine.

Def. 8.2. Mlolongo ni mlolongo wa wima zilizo karibu.

Def. 9. Mzunguko uliofungwa unaitwa mzunguko.

Def. 10.1. Mlolongo wa msingi (mzunguko, njia, contour) kupita kwenye wima zote za grafu inaitwa mnyororo wa Hamilton (mtawaliwa, mzunguko, njia, contour).

Def. 10.2. Mlolongo rahisi (mzunguko, njia, contour) iliyo na kingo zote (arcs) ya grafu inaitwa mnyororo wa Euler (kwa mtiririko huo, mzunguko, njia, contour).

Def. 11. Ikiwa wima mbili za grafu zinaweza kuunganishwa na mnyororo, basi grafu inaitwa kushikamana. Ikiwa grafu haijaunganishwa, basi inaweza kugawanywa katika subgraphs zilizounganishwa, zinazoitwa vipengele.

Def. 12. Kuunganishwa kwa grafu ni idadi ya chini ya kingo, baada ya kuondolewa ambayo grafu inakuwa imekatwa. Kwa grafu zilizoelekezwa, ikiwa wima zozote mbili za grafu zinaweza kuunganishwa na njia, basi grafu inasemekana kuwa imeunganishwa kwa nguvu. Grafu iliyounganishwa ambayo ina mzunguko wa Euler inaitwa grafu ya Euler.

Def. 13. Katika grafu isiyoelekezwa, kiwango cha vertex i ni nambari matukio ya pembeni yake. Ni wazi,
. Grafu ambayo digrii za wima zote ni sawa na n - 1 inaitwa kamili. Grafu ambayo digrii za vertex zote ni sawa inaitwa homogeneous.

Def. 14. Kipeo ambacho hakuna tukio la kingo kwake ( = 0) inaitwa kutengwa. Kipeo ambacho kuna tukio moja tu la makali kwake ( = 1) inaitwa kunyongwa.

Def. 15. Bainisha matriki ya mkabala wa grafu kama matriki ya mraba ya n × n, kipengele ambayo ni sawa na moja ikiwa (i, j) V, na sufuri ikiwa (i, j)
V, mimi, j X. Kwa grafu ambayo haijaelekezwa, matriki ya mkabala huwa ni ya ulinganifu kila wakati.

Def. 16. Tunafafanua matriki ya matukio kwa kingo za grafu kama matriki ya mstatili n × m, kipengele. ambayo ni sawa na moja ikiwa kipeo i ni tukio kwa makali j, na sufuri vinginevyo, i = 1, n, j = 1, m.

Def. 17. Tukio la matukio kwa safu za grafu ni matriki ya mstatili m x n, kipengele cha rij ambacho ni sawa na jumlisha moja, ikiwa arc inatoka kwa vertex i, minus moja, ikiwa arc huingia kwenye vertex i, na sifuri katika hali nyingine, i = 1, n, j = 1, m

Def. 18. Mti ni grafu iliyounganishwa bila mizunguko rahisi na kuwa na angalau vertices mbili. Kwa mti m = n - 1, na idadi ya wima za kunyongwa ni
Ni rahisi kuonyesha kwamba wima mbili kwenye mti zimeunganishwa kwa njia moja.

Def. 19. Mti wa babu ni mti ulioelekezwa, ambapo moja ya wima, inayoitwa mizizi, haina arcs zinazoingia, na digrii za mwelekeo wa vertices iliyobaki ni sawa na moja.

Def. 20. Planar (planar) ni grafu inayoweza kuchorwa kwenye ndege kwa namna ambayo miduara tofauti inalingana na wima tofauti na hakuna kingo mbili zilizo na alama za kawaida isipokuwa mipaka yao (usikatishe). Kwa grafu iliyopangwa, kuna dhana ya uso - sehemu ya ndege iliyofungwa na kingo na isiyo na wima wala kingo ndani.

Def. 21. Kiwango cha uso ni idadi ya kingo zake za mipaka (kingo za kunyongwa huhesabiwa mara mbili).

Grafu yoyote ya ndege iliyounganishwa inaweza kuhusishwa na grafu yake ya ndege iliyounganishwa mara mbili ya G*, ikifafanuliwa kama ifuatavyo: kila uso wa grafu G unalingana na kipeo cha grafu G*, kila ukingo wa V wa grafu G, ambao ni mpaka wa grafu ya G*. nyuso z1 na z2, inafanana na makali ya V * ya grafu G * kuunganisha wima sambamba na nyuso z1 na z2.

2. Mifano ya grafu

Grafu zilizotenganishwa kabisa . Grafu ambayo kingo zake ni tupu inaitwa haiendani kabisa(au tupu) grafu. Tutaashiria grafu iliyokatwa kabisa na wima n na N n; Nambari ya 4 imeonyeshwa kwenye mtini. 1. Kumbuka kwamba katika ya grafu iliyokatwa kabisa, wima zote zimetengwa. Grafu zilizotenganishwa kabisa hazivutii sana.

Kamilisha grafu . Grafu rahisi ambayo wima zozote mbili ziko karibu inaitwa grafu kamili. Grafu kamili iliyo na wima n kawaida huonyeshwa na . Hesabu na inavyoonyeshwa kwenye mtini. 2 na 3. ina kingo n (n – 1)/2 haswa.

Grafu za kawaida . Grafu ambayo wima zote zina digrii sawa inaitwa grafu ya kawaida. Ikiwa kiwango cha kila vertex ni r, basi grafu inaitwa shahada ya kawaidar . Grafu za mara kwa mara za shahada ya 3, pia huitwa ujazo(au tatu) grafu (tazama, kwa mfano, Mchoro 2 na 4). Mfano mwingine unaojulikana wa grafu ya ujazo ni kinachojulikana Hesabu Petersen, inavyoonyeshwa kwenye mtini. 5. Kumbuka kwamba kila grafu iliyokatwa kabisa ni ya kawaida ya digrii 0, na kila grafu kamili K n ni ya kawaida ya digrii n - 1.

Grafu za Plato . Kati ya grafu za kawaida, kinachojulikana kama grafu za Plato zinavutia sana - grafu zinazoundwa na wima na kingo za polihedra tano za kawaida - yabisi ya Plato: tetrahedron, mchemraba, octahedron, dodecahedron na icosahedron. Grafu inalingana na tetrahedron (Mchoro 2); grafu zinazofanana na mchemraba na octahedron zinaonyeshwa kwenye mtini. 5 na 6;

Grafu za pande mbili . Hebu tufikiri kwamba seti ya vipeo vya grafu inaweza kugawanywa katika sehemu ndogo mbili zisizo na intersecting V 1 na V 2 ili kila makali katika G kuunganisha baadhi ya vertex kutoka V 1 na baadhi ya vertex kutoka V 2 (Mchoro 7);

basi G inaitwa grafu ya pande mbili. Grafu kama hizo wakati mwingine huonyeshwa na G (V 1, V 2) ikiwa wanataka kutofautisha seti ndogo mbili maalum. Grafu ya pande mbili pia inaweza kufafanuliwa kwa njia nyingine, kwa suala la kuchorea wima zake na rangi mbili, sema nyekundu na bluu. Zaidi ya hayo, grafu inaitwa bipartite ikiwa kila wima inaweza kupakwa rangi nyekundu au bluu ili ukingo wowote uwe na mwisho mmoja nyekundu na mwisho mwingine wa bluu. Inapaswa kusisitizwa kuwa katika grafu ya bipartite sio lazima kabisa kwamba kila vertex kutoka V 1 imeunganishwa na kila vertex kutoka V 2; ikiwa hii ndio kesi na ikiwa grafu G ni rahisi, basi inaitwa grafu kamili ya sehemu mbili na kawaida huonyeshwa

ambapo m , n ni idadi ya vipeo katika V 1 na V 2 kwa mtiririko huo. Kwa mfano, katika mtini. 8 inaonyesha mchoro K 4 , 3 . Kumbuka kwamba grafu
ina vipeo vya m + n na kingo za mn haswa. Kamilisha grafu ya sehemu mbili za fomu
inaitwa grafu ya nyota; katika mtini. 9 inaonyesha idadi ya nyota
.

Grafu zilizounganishwa . Grafu kushikamana, ikiwa haiwezi kuwakilishwa kama muungano wa grafu mbili, na isiyofuatana vinginevyo. Ni wazi, grafu yoyote G iliyokatwa inaweza kuwakilishwa kama muunganisho wa nambari finyu ya grafu zilizounganishwa - kila moja ya grafu hizi zilizounganishwa huitwa. sehemu (muunganisho) Grafu ya G. (Kielelezo 10 kinaonyesha grafu yenye vipengele vitatu.) Mara nyingi ni rahisi kuthibitisha kauli fulani kwa grafu za kiholela kwanza kwa grafu zilizounganishwa na kisha kuzitumia kwa kila sehemu tofauti.

Grafu za baiskeli na magurudumu . Grafu ya kawaida iliyounganishwa ya shahada ya 2 inaitwa graph ya mzunguko(au mzunguko); graph ya mzunguko. Na P vipeo vinaonyeshwa na C n. Kuunganisha Grafu na
(P≥ 3) inaitwa gurudumu Na P wima na inaashiria W n . Kwenye mtini. 11 iliyoonyeshwa NA 6 na W 6 ; grafu W 4 tayari imeonekana kwenye Mtini. 2.

3. Grafu za Euler

Grafu iliyounganishwa G inaitwa Euler, ikiwa kuna mlolongo uliofungwa unaopitia kila kingo zake; mzunguko kama huo unaitwa Euler mnyororo. Kumbuka kuwa ufafanuzi huu unahitaji kwamba kila ukingo upitishwe mara moja tu. Ikiwa tunaondoa kizuizi juu ya kufungwa kwa mnyororo, basi grafu inaitwa nusu-euler; zaidi ya hayo, kila grafu ya Euler itakuwa nusu-Eulerian. Kwenye mtini. 13,14,15 grafu zisizo za euler, nusu-euler na euler zinaonyeshwa kwa mtiririko huo.

Jina "Eulers" liliibuka kwa sababu Euler alikuwa wa kwanza kutatua shida maarufu ya daraja la Königsberg, ambayo ilikuwa ni lazima kujua ikiwa grafu iliyoonyeshwa kwenye Mtini. 15, mlolongo wa Euler (hauna). Swali linatokea mara moja: inawezekana kupata hali muhimu na za kutosha kwa grafu kuwa Euler?

Hebu tuthibitishe lemma rahisi.

Lemma 1. Ikiwa kiwango cha kila kipeo cha grafu G ni angalau mbili, basi G ina mzunguko.

Ushahidi. Ikiwa grafu G ina vitanzi au kingo nyingi, basi madai ni dhahiri; kwa hivyo tuseme G ni mchoro rahisi. Hebu v iwe kipeo cha kiholela cha grafu G; jenga njia kwa kuingiza chagua kipeo v 1 karibu na v , na kwa i ≥1, kuchagua vi +1 karibu na vi na tofauti na vi -1 (kuwepo kwa vertex vile vi +1 kunahakikishwa na hali ya lema). Kwa kuwa G ina idadi maalum ya vipeo, tunaishia na kipeo ambacho tayari kimechaguliwa hapo awali. Tuseme kwamba v k ndio kipeo cha kwanza kama hicho; basi sehemu ya njia iliyo kati ya matukio mawili ya v h ni mzunguko unaohitajika.

Nadharia ya 1. Grafu iliyounganishwa G ni Euler ikiwa tu kila kipeo katika G kina digrii sawia.

Ushahidi.
Fikiria kuwa P ni njia ya Euler kwenye grafu G. Kisha kwa kila kifungu cha mnyororo P kupitia wima yoyote ya grafu, kiwango cha vertex hii huongezeka kwa mbili. Na kwa kuwa kila makali hutokea mara moja katika P, kila kipeo lazima kiwe na kiwango sawa.

Tunatekeleza uthibitisho kwa kuingiza idadi ya kingo katika G. Kwa kuwa G imeunganishwa, kiwango cha kila vertex ni angalau mbili, na kwa hiyo, kwa lemma iliyopita, tunahitimisha kwamba grafu G ina mzunguko C. Ikiwa C inapita kila makali ya grafu G, basi uthibitisho umekamilika. ; ikiwa sivyo, basi kuondoa kutoka kwa G kingo za mzunguko wa C, tunapata grafu mpya (inawezekana imekatwa) H. Idadi ya kingo katika H ni chini ya G, na vertex yoyote katika H bado ina shahada sawa. Kulingana na nadharia ya kufata neno, kila sehemu ya grafu H ina mnyororo wa Euler. Kwa sababu ya muunganisho wa grafu G, kila sehemu katika H ina angalau vertex moja ya kawaida na mzunguko C, kwa hivyo mnyororo unaohitajika wa Euler wa grafu G unaweza kupatikana kama ifuatavyo: tunaenda kando ya mzunguko C hadi kukutana na kipeo kisichojitenga cha grafu H, kisha tunafuata mnyororo wa Euler wa sehemu hiyo katika H ambayo ina kipeo kilichoonyeshwa; kisha tunaendelea njia kando ya mzunguko wa C hadi tutakapokutana na vertex ya sehemu nyingine ya grafu H, na kadhalika; mchakato unaisha tunaporudi kwenye vertex ya awali (Mchoro 17).

Muhimu 1. Grafu iliyounganishwa ni Euler ikiwa tu familia ya kingo zake inaweza kugawanywa katika mizunguko iliyotengana.

Muhimu 2. Grafu iliyounganishwa ni nusu-Eulerian ikiwa tu ikiwa ina angalau wima mbili za digrii isiyo ya kawaida.

4. Mifano ya Matumizi ya Nadharia ya Grafu

1. Matatizo ya "Usafiri", ambayo wima ya grafu ni pointi, na kando ni barabara (barabara, reli, nk) na / au usafiri mwingine (kwa mfano, anga) njia. Mfano mwingine ni mitandao ya usambazaji (ugavi wa nishati, usambazaji wa gesi, usambazaji wa bidhaa, nk), ambayo wima ni sehemu za uzalishaji na utumiaji, na kingo ni njia zinazowezekana za harakati (laini za umeme, bomba la gesi, barabara; na kadhalika.). Darasa linalolingana la shida za kuongeza mtiririko wa shehena, kupata maeneo ya uzalishaji na matumizi, nk, wakati mwingine huitwa shida za usambazaji au shida za kupata. Madarasa yao ni shida kuhusu usafirishaji wa mizigo.

2. "Kazi za kiteknolojia", ambazo wima zinaonyesha vipengele vya uzalishaji (viwanda, warsha, zana za mashine, nk), na arcs ni mtiririko wa malighafi, vifaa na bidhaa kati yao, ni kuamua upakiaji bora wa vipengele vya uzalishaji na mtiririko unaohakikisha upakiaji huu.

3. Mipango ya kubadilishana, ambayo ni mifano ya matukio kama vile kubadilishana, kukabiliana, nk. Vipeo vya grafu vinaelezea washiriki katika mpango wa kubadilishana (minyororo), na arcs huelezea mtiririko wa nyenzo na rasilimali za kifedha kati yao. Kazi ni kuamua mnyororo wa kubadilishana ambao ni bora kutoka kwa mtazamo wa, kwa mfano, mratibu wa ubadilishanaji na kulingana na masilahi ya washiriki katika mlolongo na vizuizi vilivyopo.

4. Usimamizi wa mradi. (Usimamizi wa mradi ni sehemu ya nadharia ya usimamizi ambayo inasoma mbinu na mifumo ya usimamizi wa mabadiliko (mradi ni mabadiliko ya makusudi katika mfumo fulani, unaofanywa ndani ya mipaka ya muda na rasilimali zinazotumiwa; kipengele cha tabia ya mradi wowote ni upekee wake. , yaani, kutofautiana kwa mabadiliko yanayolingana.)). Kwa mtazamo wa nadharia ya grafu, mradi ni seti ya shughuli na utegemezi kati yao. Mfano wa kitabu cha kiada ni mradi wa ujenzi wa kitu fulani. Seti ya miundo na mbinu zinazotumia lugha na matokeo ya nadharia ya grafu na zinazoelekezwa katika kutatua matatizo ya usimamizi wa mradi huitwa upangaji na usimamizi wa kalenda-mtandao (KSPU). Ndani ya mfumo wa QSPU, kazi za kuamua mlolongo wa shughuli na ugawaji wa rasilimali kati yao, mojawapo kwa mujibu wa vigezo fulani (muda wa mradi, gharama, nk), hutatuliwa.

5. Mifano ya vikundi na vikundi vinavyotumiwa katika sosholojia hutegemea uwakilishi wa watu au vikundi vyao kwa namna ya wima, na mahusiano kati yao (kwa mfano, mahusiano ya kufahamiana, uaminifu, huruma, nk) - katika fomu ya kingo au arcs. Ndani ya mfumo wa maelezo kama haya, kazi za kusoma muundo wa vikundi vya kijamii, kulinganisha, kuamua viashiria vya jumla vinavyoonyesha kiwango cha mvutano, uthabiti, mwingiliano, nk.

6. Mifano ya miundo ya shirika, ambayo vertices ni vipengele vya mfumo wa shirika, na kando au arcs ni uhusiano (habari, udhibiti, teknolojia, nk) kati yao.

5. Tatizo la Njia fupi zaidi

Mfano 1. Tatizo la mbwa mwitu, mbuzi na kabichi. Mbuzi, kabichi na mbwa mwitu wako kwenye kingo za mto; msafirishaji hana budi kuwavusha mtoni, lakini mashua yake ni ndogo sana hivi kwamba hawezi kuchukua zaidi ya mmoja wa "abiria" hawa watatu pamoja naye. Kwa sababu za wazi, mbwa mwitu na mbuzi, na mbuzi na kabichi, hawezi kushoto bila tahadhari. Mtoa huduma afanye nini?

Tatizo hili linalojulikana linatatuliwa kwa urahisi katika akili kutokana na idadi ndogo ya chaguzi zinazozingatiwa, hata hivyo, tuna mfano wa kawaida wa tatizo kuhusu kutafuta njia fupi: grafu iliyoonyeshwa kwenye Mchoro 1 inatolewa na njia inayoongoza. kutoka nafasi A inatafutwa (wakati mbuzi K, kabichi Cap, mbwa mwitu B na carrier P ziko kwenye benki ya kulia) kuweka b (wakati kila mtu anahamishiwa kwenye benki ya kushoto), njia inayotakiwa inaonyeshwa kwenye takwimu na nene. mistari.

Katika kesi ya jumla zaidi, algorithm ya utaratibu inahitajika; tutawasilisha njia kadhaa.

Tatizo la Njia fupi zaidi

Hebu mtandao wa wima n + 1 upewe, yaani, grafu iliyoelekezwa ambayo wima mbili huchaguliwa - pembejeo (sifuri ya vertex) na pato (vertex yenye nambari n). Kwa kila arc, nambari hutolewa, inayoitwa urefu wa arcs. Urefu wa njia (contour) ni jumla ya urefu wa arcs iliyojumuishwa ndani yake

(ikiwa urefu wa arcs haujainishwa, basi urefu wa njia (contour) hufafanuliwa kama idadi ya arcs iliyojumuishwa ndani yake). Kazi ni kutafuta njia fupi zaidi (njia ya urefu mdogo) kutoka kwa pembejeo hadi pato la mtandao.

Kwa kuwepo kwa njia fupi zaidi, ni muhimu na ya kutosha kwamba hakuna contours ya urefu hasi katika mtandao.

Fikiria kuwa hakuna vitanzi kwenye mtandao. Kisha inawezekana kila wakati kuhesabu wima kwa njia ambayo kwa arc yoyote (i, j) tunayo j > i. Nambari kama hiyo inaitwa sahihi. Ni rahisi kuonyesha kuwa kila wakati kuna nambari sahihi kwenye mtandao bila mtaro.

Taja - urefu wa safu (i; j). Njia fupi zaidi katika mtandao ambayo ina nambari sahihi imedhamiriwa na algorithm ifuatayo.

Algorithm 1.

;

Hatua k: weka alama kwenye vertex k na fahirisi
i

exit index itakuwa sawa na urefu wa njia fupi zaidi. (Algorithm ya 1 ya matatizo yanayobadilika ya programu inaonyesha kanuni ya Bellman ya ukamilifu: ikiwa unatafuta njia fupi kati ya pointi mbili, basi urefu wa njia kati ya pointi mbili za njia fupi lazima pia iwe ndogo.) Mchoro 2 unaonyesha mfano. ya kutumia Algorithm 1 ili kuamua njia fupi zaidi (nambari y arcs ni sawa na urefu wa arc, fahirisi za vertex zimewekwa kwenye mabano ya mraba, njia fupi zaidi imewekwa na mistari miwili).

Wakati fahirisi (inayoitwa uwezo wa vertex katika shida zingine) imeanzishwa, njia fupi zaidi imedhamiriwa na njia ya kurudi nyuma kutoka kwa pato hadi kwa pembejeo, ambayo ni, njia fupi zaidi ni.
, vile vile
na kadhalika.

Algorithm ifuatayo inafanya uwezekano wa kuamua njia fupi zaidi katika kesi ya jumla (yaani, na nambari za kiholela za wima).

Algorithm 2 (algorithm ya Ford).

Hatua ya 0: Weka alama kwenye kipeo cha sifuri kwa faharasa
, wima nyingine zote ni fahirisi
, i = 1, n;

Hatua k: Fikiria safu zote. Ikiwa kwa safu (i; j)
>, kisha tunahesabu thamani mpya
;

Fahirisi zimewekwa katika idadi fulani ya hatua. Taja
- thamani za fahirisi za hali thabiti, ambazo zina mali ifuatayo: thamani ni sawa na urefu wa njia fupi zaidi kutoka kipeo sifuri hadi kipeo cha i. Njia fupi zaidi kutoka kwa vertex 0 hadi vertex i imedhamiriwa na njia ya kurudi nyuma.

Ikiwa urefu wa arcs zote sio hasi, basi algorithm ifuatayo inatumika kutafuta njia fupi zaidi.

Algorithm ya 3.

Hatua ya 0: Weka alama kwenye kipeo cha sifuri kwa faharasa
;

Hatua k: Acha baadhi ya seti ya wima iwe tayari kuweka alama. Acha Q iwe seti ya wima zisizo na lebo karibu na zilizo na lebo. Kwa kila vertex
hesabu thamani
ambapo kiwango cha chini kinachukuliwa juu ya wima zote zilizo na lebo i karibu na kipeo k. Tunaweka alama ya vertex k ambayo thamani yake kiwango cha chini, index
.

Tunarudia utaratibu huu mpaka vertex n imewekwa alama. Urefu wa njia fupi ni , na njia fupi yenyewe imefafanuliwa kama ilivyoelezwa hapo juu.

Vile vile kwa tatizo la njia fupi zaidi, tatizo la njia ya juu (ndefu) imeundwa na kutatuliwa - ni ya kutosha kubadili ishara za arcs kwa kinyume chake na kutatua tatizo la njia fupi zaidi. Kwa kuwepo kwa suluhisho la tatizo la juu la njia, ni muhimu na ya kutosha kwamba hakuna contours ya urefu mzuri.

Katika shida ya kupata njia ya kuegemea zaidi, urefu wa arcs hufasiriwa, kwa mfano, kama uwezekano kwamba kuna uhusiano kati ya alama mbili zinazolingana. Kubadilisha urefu wa arcs na logarithm zao zilizochukuliwa kwa ishara kinyume, tunapata kwamba njia ya juu ya kuegemea katika grafu ya asili italingana na njia fupi zaidi katika grafu mpya.

Mfano 1

Mchele. 3. Data ya awali kwa tatizo la njia fupi zaidi.

Hali inaweza kuelezewa sio tu na grafu iliyoelekezwa, lakini pia na meza (Jedwali 1).

Jedwali 1. Data ya awali kwa tatizo la njia fupi zaidi

Arc kuanza

Mwisho wa arc

Wakati wa kusafiri

Swali ni: ni ipi njia fupi zaidi ya kupata kutoka nodi 1 hadi nodi 4?

Suluhisho. Tunatanguliza nukuu: C (T) ni urefu wa njia fupi zaidi kutoka kwa kipeo 1 hadi nambari ya kipeo T., na kiwango cha chini cha idadi ya vipengee hufikiwa kila mara.) Tatizo linalozingatiwa ni kukokotoa C (4) na onyesha njia ambayo kiwango cha chini hiki kinafikiwa.

Kwa data ya awali iliyotolewa kwenye Mtini. 3 na kwenye meza. 1, mshale mmoja tu unaingia kwenye kipeo cha 3, kutoka tu kwenye kipeo cha 1, na karibu na mshale huu kuna urefu wake sawa na 1, kwa hiyo С(3)=1. Aidha, ni dhahiri kwamba С(1)=0.

Unaweza kupata vertex 4 ama kutoka vertex 2, baada ya kusafiri njia sawa na 4, au kutoka vertex 5, baada ya kusafiri njia sawa na 5. Kwa hiyo, uhusiano С(4) = min (С(2) + 4; С(5) + 5).

Kwa hivyo, urekebishaji wa tatizo umefanyika - kutafuta С(4) kumepunguzwa kupata С(2) na С(5).

Unaweza kupata vertex 5 ama kutoka vertex 3, baada ya kusafiri njia sawa na 2, au kutoka vertex 6, baada ya kusafiri njia sawa na 3. Kwa hiyo, uhusiano С(5) = min (С(3) + 2; С(6) + 3).

Tunajua kwamba C(3) = 1. Kwa hiyo, C(5) = min(3; C(6) + 3).

Kwa kuwa ni dhahiri kuwa C(6) ni nambari chanya, inafuata kutoka kwa uhusiano wa mwisho kwamba C(5) = 3.

Unaweza kupata vertex 2 ama kutoka vertex 1, baada ya kusafiri njia sawa na 7, au kutoka vertex 3, baada ya kusafiri njia sawa na 5, au kutoka vertex 5, baada ya kusafiri njia sawa na 2. Kwa hiyo, uhusiano С (2) = dakika (С( 1) + 7; C(3) + 5; C(5) + 2).

Tunajua kwamba С(1) = 0, С(3) = 1, С(5) = 3. Kwa hiyo, С(2) = min (0 + 7; 1 + 5; 3 + 2) = 5.

Sasa tunaweza kupata C(4): C(4) = min (C(2) + 4; C(5) + 5) = min (5 + 4; 3 + 5) = 8.

Kwa hivyo, urefu wa njia fupi zaidi ni 8. Kutoka kwa uhusiano wa mwisho, ni wazi kwamba tunapaswa kwenda kwenye vertex 4 kupitia vertex 5. Kurudi kwenye hesabu ya C (5), tunaona kwamba lazima tuende kwenye vertex 5 kupitia. kipeo 3. Na tunaweza kupata kipeo 3 pekee kutoka nodi 1. Kwa hivyo, njia fupi zaidi ni: 1 → 3 → 5 → 4.

Tatizo la njia fupi zaidi ya data maalum ya awali (Mchoro 3 na Jedwali 1) hutatuliwa kabisa.

Mfano 2

Tafuta njia fupi zaidi (urefu wa njia) kutoka Akademgorodok (simama Tsvetnoy proezd) hadi kituo cha reli.

Inasimama:

kifungu cha rangi

nyumba ya maisha

3.3" - Taasisi ya Fizikia ya Nyuklia

Bafu 4 №22

5 Kituo cha Mto

6 - Mpanzi

7 - cafe "Spark"

8 - Daraja

9 - Kituo kikuu

Tafuta njia fupi zaidi kutoka nodi 1 hadi nodi 9.

Data ya awali:

Mchele. 4

Kichupo. 2

Arc kuanza

Mwisho wa arc

Urefu wa njia (km.)

3,06

10,9

26,78

21,57

4,26

4,35

2,55

Suluhisho: C(T) ni urefu wa njia fupi zaidi kutoka nodi 1 hadi nodi T. Tunahitaji kupata C(9).

C(1)=0, C(2)=3 (mshale mmoja tu unaingia kwenye kipeo cha 2, urefu wake ni 3).

Kilele cha 9 kinaweza kufikiwa kutoka kwa vertex 5, kupita njia 4.35, kutoka kwa vertex 6, kupita njia 25, na kutoka kwa vertex 8, kupita njia 2.55.

Kwa hiyo, С(9) = min (С(5) + 4.35; С(6) + 25; С(8) + 2.55)

Hivyo, ni muhimu kupata С(5), С(6), С(8).

Unaweza kupata vertex 5 kutoka vertex 1, kupita njia 26.78, au kutoka vertex 7, kupita njia 19.

С(5) = dakika (С(1) + 26.78; С(7) + 19)

Inahitajika kupata C (7). Kipeo cha 7 kinaweza kufikiwa kutoka kipeo cha 3 kwa kwenda 7.6 na kutoka 3" kwa kwenda 7.6.

С(7) = dakika (С(3) + 7.6; С(3") + 7.6)= dakika (1.7+7.6; 3.06+7.6)=9.3

С(5) = dakika (26.78; 9.3+ 19)=26.78

Unaweza kupata vertex 6 kutoka vertex 2 kwa kupitisha njia sawa na 0.5

С(6)=С(2)+0.5=3+0.5=3.5

Kilele cha 8 kinaweza kufikiwa kutoka kwa vertex 4 kwa kupitisha njia 21.57 na kutoka vertex 5 kwa kupitisha njia 4.62.

С(8) = dakika (С(4) + 21.57; С(5) + 4.26)

С(4)=10.9 (kutoka kwa hali).

С(8) = dakika (10.09+ 21.57; 26.78 + 4.26)=31.4

Kwa hiyo

С(9)= dakika (26.78+4.35; 3.5+25; 31.4+2.55)= dakika (31.13; 28.5; 33.95)=28.5

Kwa hivyo, urefu wa njia fupi ni 28.5 km.

Njia fupi zaidi: 1 → 2 → 6 → 9.

6. Algorithm ya kutafuta mtiririko wa juu

Wazo la algorithm hii ni kupata njia za mwisho hadi mwisho na mtiririko mzuri kutoka kwa chanzo hadi kuzama.

Fikiria makali (i , j ) yenye uwezo (wa awali).
. Wakati wa utekelezaji wa algorithm, sehemu za bandwidths hizi "zinachukuliwa" na mtiririko unaopita kupitia makali haya, kwa sababu hiyo, kila makali yatakuwa na bandwidth iliyobaki. Kurekodi
- uwezo wa mabaki. Mtandao ambao kingo zote zina uwezo wa mabaki huitwa mabaki.

Kwa nodi ya kiholela j , kupokea mkondo kutoka kwa nodi i , tunafafanua lebo.
, wapi - kiasi cha mtiririko kutoka kwa nodi j hadi nodi i. Ili kupata mtiririko wa juu, fanya hatua zifuatazo.

Hatua ya 1.

Kwa kando zote, tunaweka uwezo wa mabaki sawa na uwezo wa awali, i.e. linganisha
=
. Hebu tuwape
na uweke lebo nodi 1 yenye lebo. Tunaweka i =1.

Hatua ya 2.

- seti ya nodi j , ambayo unaweza kwenda kutoka kwa nodi I kando na uwezo mzuri wa mabaki >0 kwa wote j . Kama
, tekeleza hatua ya 3, vinginevyo nenda kwa hatua ya 4.

Hatua ya 3.

V pata nodi k vile
. Hebu tuweke
na uweke lebo nodi k na lebo
. Ikiwa k =n , njia ya njia inapatikana na kwenda kwenye hatua ya 5, vinginevyo tunaweka i =k na kurudi kwenye hatua ya 2.

Hatua ya 4.

Rudisha nyuma. Ikiwa mimi = 1, kupitia njia haiwezekani, na uende kwa 6. Ikiwa
, pata nodi iliyo na lebo r inayotangulia nodi mara moja i , na uiondoe kutoka kwa seti ya nodi zilizo karibu na nodi r . Tunaweka i =r na kurudi kwenye hatua ya 2.

Hatua ya 5.

Ufafanuzi wa mtandao wa mabaki
. Onyesha kwa seti ya nodi ambazo pth inayopatikana kupitia njia kutoka kwa nodi ya chanzo (nodi 1) hadi nodi ya kuzama (nodi n) hupita. Kisha mtiririko wa juu kupita kwenye njia hii.

Uwezo wa mabaki wa kingo zinazounda njia ya kupita hupunguzwa na thamani katika mwelekeo wa mtiririko na kuongezeka kwa kiasi sawa katika mwelekeo kinyume.

Hiyo. kwa makali (i , j ) iliyojumuishwa kwenye njia, uwezo wa sasa wa mabaki hubadilika:

1)
, ikiwa mtiririko unatoka kwa nodi i hadi j ,

2)
ikiwa mtiririko unatoka kwa nodi j hadi i.

Hatua ya 6.

Suluhisho.

a) kwa m kupatikana kwa njia, mtiririko wa juu unaonyeshwa na

b) Kuwa na maadili ya awali
na ya mwisho
uwezo wa makali (i , j ), tunaweza kuhesabu mtiririko bora kupitia makali haya kama ifuatavyo. Hebu . Kama >0, mtiririko unaopita kwenye ukingo (i , j ) ni sawa na . Kama >0, basi mtiririko ni . (kesi wakati huo huo >0 na >0, haiwezekani).

Mfano 1. Pata mtiririko wa juu katika tini ya mtandao. moja

Marudio 1.
=

1)
na uweke lebo nodi 1 yenye lebo
. i=1

3) k =3 tangu . Kadiria
na uweke lebo nodi 3 yenye lebo
. i =3 na kurudi kwa 2)

5) k =5 na . Weka nodi 5 yenye lebo
. Tunapata njia ya kupitia.

6) njia ya kupitia imedhamiriwa na lebo, kuanzia nodi 5 na kuishia na nodi 1: .
:

Marudio 2.

1)
na uweke lebo nodi 1 yenye lebo
. i=1

3) k =2, na uweke lebo nodi 2 kwa lebo
. i = 2 na kurudi kwa 2)

2")

3") k =3 na
. Weka nodi 3 yenye lebo
. i =3 na kurudi kwa 2)

2")
(
, kwa hivyo nodi 5 haijajumuishwa

3") k=4,
na uweke lebo nodi 4 yenye lebo
. i =4 na kurudi kwa 2)

2""")
(kwa sababu nodi 1 na 3 zimeandikwa, hazijajumuishwa )

3""") k=5 na
. Weka nodi 5 yenye lebo
. Imepokea njia ya kupitia. Nenda kwa 5)

5)
na. Kukokotoa Bandwidth Zilizobaki Kando ya Njia :

Marudio 3.

1)
na uweke lebo nodi 1 yenye lebo
. i=1

3) k=2,
na uweke lebo nodi 2 yenye lebo
. i = 2 na kurudi kwa 2)

2")

Mchele. 2. Data ya awali kwa mfano 2

Data ya awali juu ya mfumo wa usafiri, kwa mfano, katika mmea, iliyoonyeshwa kwenye tini. 2 pia inaweza kutajwa kama jedwali (Jedwali 2).

Jedwali 2. Data ya awali kwa tatizo la juu zaidi la mtiririko

Hatua ya kuondoka

Lengwa

Bandwidth

Kwa wazi, uwezo wa juu wa mfumo wa usafiri hauzidi 6, kwani hakuna zaidi ya vitengo 6 vya mizigo vinaweza kutumwa kutoka kwa kuanzia 0, yaani, vitengo 2 hadi 1, vitengo 3 hadi 2 na kitengo 1 hadi 3. Kisha, unahitaji kuhakikisha kwamba vitengo vyote 6 vya mizigo vilivyoacha hatua 0 vimefikia hatua ya mwisho 4. Ni wazi, vitengo 2 vya mizigo vilivyofika kwenye hatua ya 1 vinaweza kutumwa moja kwa moja kwa uhakika 4. Bidhaa zilizofika kwenye hatua ya 2 zitatumwa. zinapaswa kugawanywa: vitengo 2 mara moja huenda kwenye hatua ya 4, na kitengo 1 - kwa hatua ya kati ya 3 (kutokana na uwezo mdogo wa sehemu kati ya pointi 2 na 4). Mizigo ifuatayo ilitolewa kwa hatua ya 3: kitengo 1 kutoka kwa hatua ya 0 na kitengo 1 kutoka kwa hatua ya 3. Tunawapeleka kwenye hatua ya 4. Kwa hiyo, uwezo wa juu wa mfumo wa usafiri unaozingatiwa ni vitengo 6 vya mizigo. Wakati huo huo, sehemu za ndani (matawi) kati ya pointi 1 na 2, pamoja na kati ya pointi 1 na 3 hazitumiwi. Tawi kati ya pointi 1 na 4 haijapakiwa kikamilifu - vitengo 2 vya mizigo vinatumwa pamoja nayo upitishaji wa vitengo 3. Suluhisho linaweza kuwasilishwa kwa namna ya meza (Jedwali 3)

Jedwali 3. Kutatua shida ya mtiririko wa juu

Hatua ya kuondoka

Lengwa

Mpango wa usafiri

Bandwidth

Tatizo la upangaji wa laini kwa uboreshaji wa mtiririko. Wacha tuunda shida ya kiwango cha juu cha mtiririko katika suala la upangaji wa mstari. Hebu X KM iwe kiasi cha trafiki kutoka kwa uhakika K hadi kumweka M. Kulingana na mtini. 2 K = 0.1.2.3, M = 1.2.3.4, na usafiri inawezekana tu kwa uhakika na idadi ya juu. Hii ina maana kwamba kuna vigezo 9 X KM kwa jumla, yaani, X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. Tatizo la upangaji wa mstari unaolenga kuongeza mtiririko. ina fomu:

F → upeo,

X 01 + X 02 + X 03 = F(0)

– X 01 + X 12 + X 13 + X 14 = 0 (1)

– X 02 - X 12 + X 23 + X 24 = 0 (2)

– X 03 - X 13 - X 23 + X 34 = 0 (3)

– X 14 - X 24 - X 34 \u003d - F (4)

Х 01 ≤ 2

Х 02 ≤ 3

Х 03 ≤ 1

X 12 ≤ 4

X 13 ≤ 1

X 14 ≤ 3

X 23 ≤ 1

X 24 ≤ 2

X 34 ≤ 2

X KM ≥ 0, K, M = 0, 1, 2, 3, 4

F ≥0.

Hapa F ni kazi ya lengo, hali (0) inaelezea kuingia kwa bidhaa kwenye mfumo wa usafiri. Masharti (1) - (3) kuweka uwiano wa usawa kwa nodes 1-3 za mfumo. Kwa maneno mengine, kwa kila nodi za ndani, mtiririko unaoingia wa bidhaa ni sawa na mtiririko unaotoka, mizigo haikusanyiko ndani ya mfumo na "haijazaliwa" ndani yake. Masharti (4) ni hali ya "kutoka" kwa bidhaa kutoka kwa mfumo. Pamoja na hali (0), inajumuisha uwiano wa mizani kwa mfumo mzima ("ingizo" ni sawa na "pato"). Kutokuwepo kwa usawa tisa ijayo kuweka mipaka juu ya uwezo wa "matawi" ya mtu binafsi ya mfumo wa usafiri. Kisha kutokuwa na hasi ya kiasi cha trafiki na kazi ya lengo inaonyeshwa. Ni wazi kwamba ukosefu wa usawa wa mwisho unafuata kutoka kwa aina ya kazi ya lengo (uhusiano (0) au (4)) na kutokuwa na hasi ya kiasi cha trafiki. Walakini, usawa wa mwisho hubeba habari fulani ya jumla - ama kiwango chanya cha bidhaa kinaweza kupitishwa kupitia mfumo, au sifuri (kwa mfano, ikiwa kuna harakati kwenye duara ndani ya mfumo), lakini sio hasi (haifanyi kiuchumi. maana, lakini mfano rasmi wa hisabati kuhusu hili "haujui").

Hitimisho

Katika karatasi hii, tumezingatia kima cha chini kabisa cha dhana zinazoturuhusu kuendelea na utafiti wa nadharia ya grafu. Baada ya yote, tumegusa tu juu ya ncha ya barafu kubwa, baada ya kuchambua mbinu kadhaa za kutatua matatizo ya kiuchumi. Nadharia ya grafu haikomei katika uchunguzi wa matukio au michakato fulani ya mtu binafsi; hupata matumizi katika nyanja mbalimbali za sayansi na teknolojia.

Algorithms ya kutatua tatizo la njia fupi zaidi na kutafuta mtiririko wa juu zilizingatiwa, mifano ilichambuliwa. Mfano wao ulionyesha umuhimu wa nadharia ya graph kwa kuongeza matatizo ya kiuchumi.

Kwa njia hiyo hiyo, mfano wa njia fupi zaidi inayohusiana moja kwa moja na maisha yetu ya kila siku ilikusanywa na kutatuliwa. Kazi ilikuwa kutafuta njia fupi zaidi (barabara ni ndefu katika km) kutoka Akademgorodok (Tsvetnoy proezd stop) hadi Kituo Kikuu.

Bibliografia

"Soros Educational Journal" No. 11 1996 (Kifungu "Flat Graphs");

"Kusaidia mwalimu wa hisabati", Yoshkar-Ola, 1972, p. "Kusoma vipengele vya nadharia ya graph"

Berge, nadharia ya Grafu ya K.S. na matumizi yake./K. S. Berzh.- M.: IL, 2007.-178s.

Burkov, V.N. Vipengele vya nadharia ya grafu./V. N. Burkov. - M.: Mwangaza, 2010.-352s.

Gardner, M. S. "Burudani ya hisabati". / M. S. Gardner.- M.: "Mir", 2004.-347p.

Gardner, M. S. "Mafumbo ya hisabati na burudani." / M S gardner.-M. : "Mir", 2005.-221s.

Zykov, A. A. Nadharia ya grafu finite./ A. A. Zykov - Novosibirsk: "Nauka", 2006.-257p.

Kasatkin, V. N. "Matatizo yasiyo ya kawaida ya hisabati"/ V. N. Kasatkin.-Kiev: "Shule ya Radyan", 2007.-232p.

Olekhnik, S. N. "Matatizo ya kale ya burudani" / C .N. Olechnik.- M. "Sayansi", 2008.-431s.

Ore, O. S. "Grafu na matumizi yake"./O. S. Ore - M .: "Mir", 2005-269s.

Renyi, A. N. "Trilojia ya Hisabati" / A. N. Renyi.- M .: "Mir", 2010-198s.

Kamilisha grafu . Grafu rahisi ambayo wima zozote mbili ziko karibu inaitwa grafu kamili. Grafu kamili iliyo na wima n kawaida huonyeshwa na. Grafu na zinaonyeshwa kwenye mtini. 2 na 3. ina kingo za n (n - 1)/2 haswa.

Grafu za kawaida . Grafu ambayo wima zote zina digrii sawa inaitwa grafu ya kawaida. Ikiwa kiwango cha kila vertex ni r, basi grafu inaitwa shahada ya kawaida r. Grafu za mara kwa mara za shahada ya 3, pia huitwa ujazo(au tatu) grafu (tazama, kwa mfano, Mchoro 2 na 4). Mfano mwingine unaojulikana wa grafu ya ujazo ni kinachojulikana Hesabu Petersen, inavyoonyeshwa kwenye mtini. 5. Kumbuka kwamba kila grafu iliyokatwa kabisa ni ya kawaida ya digrii 0, na kila grafu kamili K n ni ya kawaida ya digrii n - 1.

Grafu za Plato . Kati ya grafu za kawaida, kinachojulikana kama grafu za Plato zinavutia sana - grafu zinazoundwa na wima na kingo za polihedra tano za kawaida - yabisi ya Plato: tetrahedron, mchemraba, octahedron, dodecahedron na icosahedron. Grafu inafanana na tetrahedron (Mchoro 2); grafu zinazofanana na mchemraba na octahedron zinaonyeshwa kwenye mtini. 5 na 6;

kisha G inaitwa grafu ya pande mbili. Grafu kama hizo wakati mwingine huashiriwa na G(V 1, V 2) ikiwa wanataka kutofautisha seti ndogo mbili zilizobainishwa. Grafu ya pande mbili pia inaweza kufafanuliwa kwa njia nyingine, kwa suala la kuchorea wima zake na rangi mbili, sema nyekundu na bluu. Zaidi ya hayo, grafu inaitwa bipartite ikiwa kila wima inaweza kupakwa rangi nyekundu au bluu ili ukingo wowote uwe na mwisho mmoja nyekundu na mwisho mwingine wa bluu. Inapaswa kusisitizwa kuwa katika grafu ya bipartite si lazima kwamba kila vertex kutoka V 1 imeunganishwa na kila vertex kutoka V 2; ikiwa hii ndio kesi na ikiwa grafu G ni rahisi, basi inaitwa grafu kamili ya sehemu mbili na kwa kawaida huashiria ambapo m, n ni idadi ya vipeo katika V 1 na V 2 mtawalia. Kwa mfano, katika mtini. 8 inaonyesha mchoro K 4 , 3 . Kumbuka kuwa grafu ina wima m + n na kingo za mn haswa. Grafu kamili ya kuona pande mbili inaitwa grafu ya nyota; katika mtini. 9 inaonyesha grafu ya nyota.

Grafu zilizounganishwa . Grafu kushikamana, ikiwa haiwezi kuwakilishwa kama muungano wa grafu mbili, na isiyofuatana vinginevyo. Ni wazi, grafu yoyote G iliyokatwa inaweza kuwakilishwa kama muunganisho wa nambari finyu ya grafu zilizounganishwa - kila moja ya grafu hizi zilizounganishwa huitwa. sehemu (muunganisho) grafu G. (Kielelezo 10 kinaonyesha grafu yenye vipengele vitatu.) Mara nyingi ni rahisi kuthibitisha kauli fulani kwa grafu za kiholela kwanza kwa grafu zilizounganishwa, na kisha kuzitumia kwa kila sehemu tofauti.

Wakati wa kupata milinganyo ya kiwango cha athari za enzymatic, idadi ya mawazo ya kurahisisha hutumiwa. Hasa, kama sheria, inadhaniwa kuwa mmenyuko wa enzymatic unaendelea chini ya hali ya mchanganyiko bora, hali ya joto na pH ikisema, na kwamba majibu haraka sana huanzisha hali ya kusimama (tazama Sehemu ya 2.1), ambayo aina zote za kati za kimeng'enya kiko katika usawa na kila mmoja. Kiambishi awali "quasi" kinamaanisha kuwa ni sehemu tu ya viambishi hufikia viwango vya kusimama, huku vingine vikiendelea kubadilika polepole. Matumizi ya dhana kwamba sehemu ya viwango (ya mfumo wa biochemical) hufikia maadili ya hali ya kawaida inajulikana katika fasihi kama njia ya Bodenstein-Semenov. Njia hii hukuruhusu kurahisisha sana uchambuzi wa (bio) kemikali. Badala ya kutatua mifumo ya milinganyo isiyo ya mstari ambayo inaelezea mabadiliko ya vitu vya kati wakati wa mmenyuko, kwa mujibu wa njia hii inaweza tu kutatua mifumo ya milinganyo ya aljebra inayohusiana na kila mmoja.

viwango vya quasi-stationary ya vitu vya kati. Sababu kuu kwa nini hali ya quasi-stationary imeanzishwa katika mmenyuko wa enzymatic ni kwamba mkusanyiko wa enzyme kawaida ni amri kadhaa za ukubwa wa chini kuliko viwango vya substrates zinazoingiliana na enzyme.

Kama sheria, mifumo ya equations ya algebraic inayoelezea hali ya quasi-stationary ya athari za enzymatic ni ya mstari, kwani ubadilishaji kati ya fomu za kati na tata zinawakilishwa na athari za monomolecular. Kwa hiyo, mbinu za aljebra za mstari hutumiwa kuamua viwango vya quasi-stationary ya vitu vya kati. Katika miaka ya hivi karibuni, mbinu za nadharia ya grafu zimetumika sana kwa kusudi hili.

Grafu ya mmenyuko wa enzymatic ni seti ya nodi zinazolingana na viwango vya quasi-stationary vya complexes zote za enzyme na matawi yaliyoelekezwa yanayowaunganisha, yenye sifa ya thamani fulani sawa na kiwango cha mara kwa mara cha mabadiliko. Mkusanyiko wa dutu hii inachukuliwa kuwa mara kwa mara katika hali ya quasi-stationary.

Kwa mfano, mmenyuko wa enzymatic

inapita kwa njia ya malezi ya kati ya tata mbili za enzyme-substrate

inaweza kuwakilishwa katika hali ya quasi-stationary na grafu yenye nodi tatu na matawi sita yaliyoelekezwa. Safu (1.11) inaonyesha maadili ya matawi; wawili kati yao hutegemea viwango vinavyozingatiwa kuwa vya mara kwa mara katika hali ya quasi-stationary.

Mti wa grafu unaoelekezwa kwa nodi ni seti isiyofungwa ya matawi iliyoelekezwa kutoka kwa nodi zote za grafu hadi nodi. Mti hauna mlolongo wa kufungwa au sambamba. Thamani ya mti ni zao la maadili ya matawi yake yote. Kwa mfano, nodi za grafu (1.11) zina miti ifuatayo (maadili yao yamepewa):

(angalia scan)

Kwa kuwa grafu ya awali ina taarifa zote muhimu kwa mahesabu, wakati wa kuchora miti, notation ya nodes na ukubwa wa tawi kawaida haitumiwi. Zaidi ya hayo, wakati ujuzi fulani unafikiwa, ukubwa wa miti huandikwa moja kwa moja kulingana na grafu ya awali - bila kuchora miti.

Seti (kwenye ukurasa wa 24) sio miti ya nodi kwa sababu a ni mlolongo uliofungwa wa matawi (mzunguko), ina safu mbili sambamba za matawi yanayounganisha nodi, na c ina tawi la mzunguko kutoka nodi hadi nodi haijaunganishwa na nodi.

Kiamuzi cha msingi cha nodi ni jumla ya maadili ya miti yote iliyoelekezwa kwenye nodi ya msingi. Kiamuzi cha grafu ni jumla ya vibainishi vyote vya msingi vya grafu. Kwa mfano, viashiria vya nodi na katika grafu (1.11) ni hesabu zifuatazo za maadili ya miti (1.12):

(angalia scan)

na kibainishaji cha grafu hii ni sawa na jumla ya viambajengo vitatu vya msingi:

Kiwango cha awali cha quasi-stationary cha mmenyuko wa enzymatic huonyeshwa kulingana na viashiria vya grafu ya majibu kama ifuatavyo:

ambapo kiwango cha mara kwa mara cha uundaji au kufungwa kwa bidhaa kwa nodi ni kiashiria cha msingi cha nodi na mkusanyiko wa jumla wa kimeng'enya. Wakati wa kuhesabu katika kesi ya uundaji wa bidhaa zinazoweza kubadilishwa, mkataba wa ishara unaofuata hutumiwa: ikiwa node inatupa bidhaa, na ikiwa node inafunga bidhaa.

Kwa mfano, kwa grafu (1.11) kulingana na formula (1.14) mtu anapaswa kuandika