Дәріс тақырыбы: Графтар теориясы (5 сағат) Негізгі сұрақтар

жүктеу 0,75 Mb.

бет	19/23
Дата	03.02.2022
өлшемі	0,75 Mb.
	#35463

1 ... 15 16 17 18 19 20 21 22 23

лекция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

жүктеу 0,75 Mb.

Достарыңызбен бөлісу:

1 ... 15 16 17 18 19 20 21 22 23