1 пєнініњ ОЌу программасы syllabus

– дәріс тақырыбы. Эйлер және Гамильтон циклдары (2 сағат)

жүктеу 19,56 Mb.

бет	29/34
Дата	31.05.2018
өлшемі	19,56 Mb.
	#18555

1 ... 26 27 28 29 30 31 32 33 34

15-дәріс. Транспорттық желілер (2 сағат)

14 – дәріс тақ ырыбы. Эйлер және Гамильтон циклдары (2 сағат)

Дәріс конспектісі: Графтар теориясына негіз болған есептердің бірі Кенигсберг көпірлері туралы есеп. 1-Суретте Леонард Эйлердің тұсындағы(17 ғасыр) XVII ғасырдағы Кенигсберг қаласының картасы салынған. Қала Прегель өзенінің екі жақ жағалауында және 2 аралда.

орналасқан Аралдар өзара және жағалаулармен 7 көпірмен жалғасқан. Кенигсберг тұрғындарының арасында сол кезде Кенигсберг көпірлері деп аталатын есеп кең тараған: Есеп. Үйден шығып әр көпірмен бір рет қана жүріп үйге қайтып келуге болама ма деген

3-сурет

сұрақ туады? Бұл есеп үшін көпірлерден өтудің маңызы бар. Сондықтан көпірлердің орналасуын 2-суреттегі бағытталмаған мультиграфпен алмастыруға болады. Бұл графта Б,В төбелері өзеннің жағаларына, ал А,Г төбелері аралдар, ал мультиграфтың қабырғалары көпірлерге сәйкес келеді.

Егер G графында оның барлық қабырғалары арқылы өтетін цикл табылса Кенигсберг туралы есеп шешілді деп есептеледі (Цикл деп бірде бір қабырға қайталанбайтын циклды маршрутты айтатынын еске саламыз). Демек графтар тілінде есептін қойылуы төмендегідей: Мультиграфта оның барлық қабырғалары болатындай цикл бар ма? Атақты ғалым-математик Л.Эйлер байланысты, бағытталмаған мультиграфта оның барлық

4-сурет

қабырғалары болатындай цикл болудың шартын анықтап дәлелдеп берді.

Теорема Байланысты бағытталмаған мультиграфтың әр төбесінің дәрежесі жұп сан болса ғана Эйлер циклы болады.

Анықтама. Мультиграфтың барлық қабырғалары болатын цикл Эйлер циклы деп, ал Эйлер циклы бар граф Эйлер графы деп аталады. Жоғардағы суреттегі мультиграфта Эйлер циклы жоқ, себебі онда дәрежесі тақ төбе бар. Айталық ондай цикл бар деп жориық. Олай болғанда бұл циклдың бойымен жүре отыра графтың кез келген төбесіне одан шығу қанша болса сонша рет кіреміз. Демек, G графының әр төбесінің дәрежесі жұп болуы керек. G графында керісінше барлық төбелер тақ дәрежелі.

Бұл тұжырым кез келген бағытталған G графына да жарамды. Сонымен бағытталмаған G графында оның барлық қабырғалары арқылы өтетін цикл бар болу үшін G графының төбелерінің дәрежесі жұп болуы қажетті.

Анықтама. Бағытталмаған (бағытталған) G графындағы цикл оның барлық қабырғалары арқылы өтсе, ол- Эйлер циклы деп аталады. Бағытталмаған графта Эйлер циклы бар болу үшін бұл графтың байланысты болуы қажетті.

2 Анықтама. Еез келген х,у V(G) төбелерін қосатын жол бар болса бағытталмаған G графы байланысты граф деп аталады.

2 Анықтама.Егер С циклы Бағытталмаған G графының барлық қабырғалары арқылы өтетін болса, кез келген х,у€V(G) төбелері үшін C циклының х төбесінен у төбесіне апаратын C(x,y) кесіндісі х-тен у-ке апаратын жол болып табылады. Олай болса G байланысты. Эйлер циклының бар болуы үшін графтың дәрежелерінің жұп болуы және оған қоса графтың байланысты болуы жеткілікті екен.

Эйлер теоремасы. Бағытталмаған графта Эйлер циклы болу үшін оның байланысты болуы және оның барлық дәрежелерінің жұп болуы қажетті және жеткілікті.

Эйлер теоремасын шамалы өзгеріспен бағытталған графтарға да қолдануға болады. Ол үшін бағытталған графтардың да байланысты болу ұғымын енгізу керек.

Доғаларының бағыттарын алып тастағаннан кейінгі алынған бағытталмаған G графы байланысты болса, бағытталған °G графы байланысты деп аталады.

Теорема .Бағытталған G графында Эйлер циклы болу үшін оның әр төбесіне кіретін дәрежемен шығатын дәрежелердің бірдей болуы қажетті және жеткілікті. дәр.+(х) = дәр.- (х) барлық x  V(G).

Байланысты және тиелген бағытталмаған графтағы белгіленген Vo және Vn төбелерін қосатын ең қысқа жолды іздеуді жүзеге асыратын Форд алгоритмі.

Vo төбесіне λ₀таңбасы беріледі де, қалған төбелердің таңбалары λ=∞ болады.

(Vi , Vj) қабырғаларының ішінен λj - λi > L((Vi , Vj)) орындалатындай қабырғалар ізделеді және олардың λj индекстері λj' = λi + L((Vi , Vj)). алмастырылады. Индекстрді өзгерту процесі одан әрі λj таңбасын азайту мүмкіндігі болмайтын бірде бір қабырға қалмағанша жүргізіледі. Нәтижесінде әр төбенің таңбасы осы төбенің V0 төбесіне дейінгі ең қысқа қашықтықты көрсетеді. Ең қысқа жолдың өзін табу үшін Vn төбесінен екі жағындағы төбелердің таңбаларының айырымы қабырғаның ұзындығына тең қабырғалардың бойымен қозғалу қажет.

Гамильтон циклдары. Гамильтон циклдары туралы есептің интерпритациясы ретінде ең көп тараған коммивояжер туралы есепті қарастыруға болады.

Коммивояжер аралайтын бірнеше қалалардың арақашықтықтары белгілі.

Барлық қалаларда бір реттен ғана болып алғашқы шыққан қаласына қайтып келетін маршрутты табу керек. Егер мұндай маршруттар бірнешеу болса, олардың ең қысқасын табу керек. Мұндай есептер іс жүзінде жиі кездеседі, мысал үшін өндіріс өнімдерін сауда орталықтарына ең қысқа жолмен жеткізу есебі.

Мұндай есептерді шешудің жалпы ортақ теоремалары мен көлемі жөнінен шағын, әрі тиімді алгоритмдердің жоқтығы есепті шешуде қиындықтар туғызады.

Анықтама. Айталық G(V,E) байланысты бағытталмаған граф. G графының барлық төбелері арқылы өтетін, басталуы мен аяқталуы әр түрлі төбелерде болатын қарапайым цикл Гамильтон циклы деп аталады.Графтарда Гамильтон циклдары мен шынжырлары бар болудың жеткілікті шартын келтірейік. Айталық дәр. v – v

V төбесінің дәрежесі болсын.

Теорема. Егер G (V, E), мұндағы | V | =n графында кез келген төбелер vi vj жұбы үшін

дәр.v_i+ дәр.v_j≥n-1, орындалса, графта гамильтон шынжыры бар, ал егер дәр.v_i+ дәр.v_j≥n немесе дәр.v_i≥n /2 графта Гамильтон циклы бар.

Негізгі әдебиет: 2 [20-22]; 3[108-144] .

Қосымша әдебиет. : 7[88-130] .

Бақылау сұрақтары:

Цикл деп нені айтамыз?
Қандай граф Эйлер графы деп аталады?
Графтың Эйлер графы болуының жеткілікті және қажетті шартын атаңыз?
Гамильтон шынжыры, Гамильтон циклы дегендер не?
Коммивояжер есебін шешудің қандай алгоритмі белгілі?

15-дәріс. Транспорттық желілер (2 сағат)

Дәріс конспектісі

Анықтама. Төменде аталған шарттар: а) ілгек жоқ; b) шығу төбесі ( бірде бір доға кірмейтін , тек шығатын ғана төбелері бар ) бар болса; с) кіру төбесі (бірде бір доға шықпайтын, тек кіру төбелері ғана бар ) бар болса; d) доғалардың Е жиынындағы әр доғада мәні өткізу қабілеті деп аталатын теріс емес бүтін мәнді с(е) функциясы анықталған болса; бағытталған, байланысты G(E, V) графы транспорт желісі деп аталады.

Транспорт желісінің шығу,кіру деп аталатын төбелерден басқа төбелері аралық төбелер деп аталады. 1-суретте v0-басталу төбесі, , z- аяқталу төбесі, v1, v2, v3, v4-аралық төбелер, ал әр доғада өткізу қабілеті көрсетілген.

2 Анықтама. Айталық,

желінің v V төбесінен қосылатын, а

- төбесінен шығатын доғалар жиыны болсын. G(V,E) желісінің Е доғалар жиынында берілген бүтін мәнді теріс емес φ(е) функциясы а), b) , c) шарттарын қанағаттандырса ағын деп аталады. φ(е) функциясының мәнін х төбесінен у төбесіне баратын v(x,y) доғасымен уақыт бірлігінде өтетеін заттың саны деп қарауға болады. Бұл сан доғаның өткізу қабілетінен аспайды. Желінің басталатын және аяқталатын төбелерінен басқа төбелерде келетін заттардың саны одан шығатын заттарға тең болатындықтан еш жерде олар жиналып қалмайды

vv₀, vz;

b) (e)c(e);
c)

5-сурет

3 анықтама.

ағын шамасы деп аталады және φz болып белгіленеді.

4 анықтама. е доғасы үшін φ(е)=с(е) болса,ол толыққан доға деп, ал әрбір жолдың басынан бастап ағына дейін ең болмаса бір қаныққан доғасы болса z ағыны толық деп аталады.

5 анықтама. Айталық, v0 A, ал zA шарты орындалатындай транспорт желісі төбелерінің ішкі жиыны AV болсын. А-ға енбейтін төбелерді А-ның төбелерімен қосатын доғалар жиыны

G(V, E) желісінің Т қимасы деп аталады. Мысалы, 1-суретте көрсетілген желідегі төбелердің A={v1,v2,v4, z } ішкі жиыннан бөлек,

= {(v0, v1),(v0, v2),(v3, z)} доғалар жиыны қима болады.

6 анықтама.

қимасының өткізу қабілеті c (

) деп қимаға кіретін доғалардың өткізу қабілеттерінің қосындыларын айтады,

деп белгілейді.

Теорема. G(V, E) транспорт желісіндегі v0A, zA орындалатындай төбелердің ішкі жиыны AV арқылы анықталатын G(V, E) транспорт желісінен алынған φ ағыны мен кез келген Т қимасы үшін z  c(

), орындалса, яғни желідегі кез келген ағынның шамасы (оның ішінде ең үлкені де) кез келген қиманың өткізу қабілетінен артық емес (оның ішінде ең кішісі де).

Салдар. Егер кез келген φ ағыны мен

қимасы үшін z= с(

), орындалса, онда φ ағыны – ең үлкен, ал

қимасының өткізу қабілеті ең аз болады.

Транспорт желісінің ең үлкен ағынын анықтайтын Форд-Фалкерсон алгоритмін қарастырайық. Ол алгоритм бойынша ағын біртіндеп ең үлкен мән қабылдағанша үлкейтіле береді.

AL алгоритмі. (транспорт желісіндегі ең үлкен ағынды табу ға арналған).

Басы. Транспорт желісі V төбелер жиыны, доғалар жиыны E және желінің басы v0  V, соңы z V арқылы беріледі. Доғалардың өткізу қабілеті c(е), е  Е беріледі.

G(V,E) желісінің v0 мен z.төбелерінен басқаларын еркін түрде нөмірлейміз.

2. Барлық e  E. үшін φ(e)=0 деп алып кез келген ағын тұрғызамыз.

3. Транспорт желісінің басталу төбесі v0 мен соңғы z төбелерін қосатын барлық жолдарды қарап шығу. Егер φ ағыны толық болса 4 пунктке көш. Болмаса v0 төбесін z қосатын барлық доғалары қаныққан емес μ жолын қарастыру керек те мына формула бойынша

φ' ағынын құрыңыз. Мұндағы

. 3 –пунктті қайталаңыз.

Желінің төбелеріне бүтін мәнді таңбалар және желі доғаларын "+" және "-" таңбаларымен мына ережелер бойынша белгілейміз:

а) v0 басталу төбесін е 0;

в) Егер vi төбесі таңбаланса, ал v әлі таңбаланбаса,онда егер v -ға vi төбесінен((vi,v) c((vi,v)), қанықпаған доға келсе, v төбесіне i таңбасы ,ал (vi,v) доғасына "+" таңбасы беріледі; немесе v төбесінен нөлдік емес ағынмен vi төбесіне (((v, vi))>0) баратын доға бар болса, (v, vi) доғасы "-" белгісімен таңбаланады. Қалған белгіленбеген доғалар мен төбелерге таңба берілмейді;

с) 4в пунктегі сипатталған процесс жаңа таңбаланған доға мен төбенің пайда болуы тоқталғанға дейін қайталанады. Осы процестің нәтижесінде z таңбаланбаса, онда құрылған ағын ең үлкен болғаны одан соңына көшу керек, керісінше болса 5 пунктке көшіңіз.

5. Әрқайсысы келесі төбенің нөмірімен таңбаланған

төбелердің және

жиынынан алынған төбелерді қосатын μ (не обязательно маршрут болуы міндетті емес) доғалар тізбегін қарастырамыз.Төменде көрсетілгендей жаңа ағын құрасыз.

4 пунктке көш.Соңы.

Енді сипатталған алгоритммен құрылған ағынның ең үлкен екендігін көрсетейік. А арқылы желінің белгіленбеген төбелер жиынын белгілейміз. болғандықтан А жиыны желісінің қимасын анықтайды. Әрбір

доғасы таңбаланған төбені таңбаланбаған төбесімен қосады. V төбесі шартында таңбаланбай қалуы мүмкін. Екінші жағынан А () шығатын әрбір доғада теңдігі орындалады, сондықтан

өрнегі орындалады. Ендеше теореманың салдары бойынша φ_z ең үлкен ағын болып табылады.Мысал. 2-суретте өрнектелген транспорт желісінің ең үлкен ағыны анықтау керек.Әр доғада жазылған сандар осы доғаның өткізу қабілетін білдіреді. Жолдың басы v₀төбесін соңы z-пен қосатын барлық жолды тізіп шығайық: 1 = (v0, v1, v4, z); 2 = (v0, v1, v2, v4, z); 3 = (v0, v2, v3, z); 4 = (v0, v1, v3, z); 5 = (v0, v1, v2, v3, z); 6 = (v0, v2, v4, z). Желідегі алғашқы ағынды 0 деп алып, оны

әр жолдың ең болмаса қаныққан бір доғасы болғанға дейін біртіндеп көбейтеміз. Ол үшін әр жолдан доғалардың өткізу қабілеті мен осы доғалардағы ағынның ең кіші айырымын анықтаймыз және бүкіл жолдағы ағынды осы шамаға арттырамыз. Бұл процесс 6а,6b,6с,6d суреттерде көрсетілген,доғаларда әрқайсысының өткізу қабілетімен бірге жақша ішінде

осы доғаның ағыны көрсетілген. 6d суреттегі құрылған ағын толық және

ол _z = 9 (6а –6d) суреттерде қаныққан доғалар жуан сызықтармен бейнеленіп тұр).

k₁ = min(7-0, 3-0, 7-0)=3

6а-сурет

k₂ = min(7-3, 2-0, 2-0, 7-3)=2

6b-сурет

k₃ = min(8-0, 2-0, 9-0)=2

6c-сурет

k₄ = min(7-5, 6-0, 2-0, 9-2)=2

6d-сурет

Құрылған ағынның ең үлкен болу шартын тексереміз.Ол үшін доғалар мен төбелерді таңбалаймыз,

нәтижесінде z төбесі таңбаланған болып шығады( 6d-сурет). Бұл 6d-суреттегі ағынның ең үлкен емес екендігін көрсетеді."+" -белгісімен таңбаланған ағын шамасын көбейту, "-"- белгісімен таңбаланған ағын шамасын азайту 6e- суретте көрсетілгендей шамасы _z = 11 болатын ағынға әкеледі. Бұл ең үлкен ағын болады.

Негізгі әдебиет: 1[249-257]; 3[172-193]

Қосымша әдебиет : 7[50-80].

Бақылау сұрақтары: 1.Транспорт желісі дегеніміз не?

v₃

6e-сурет

2. Транспорт желісінде қандай доға қаныққан доға деп аталады?

3. Транспорт желісінде қима деп нені айтады?

4. Қандай ағын толық деп аталады?

5. Ең үлкен ағын табудың Форд – Фалькерсон алгоритміне сипаттама беріңіз.