Сабақ тақырыбы: Графтағы Эйлер айналымы
жүктеу/скачать 67,5 Kb.
|
№10 практика ТГ 2
- Бұл бет үшін навигация:
- ҚАРАСТЫРЫЛАТЫН НЕГІЗГІ МӘСЕЛЕЛЕР
- НЕГІЗГІ МАҒЛҰМАТТАР
- ЖҰМЫСТЫ ОРЫНДАУҒА ӘДІСТЕМЕЛІК НҰСҚАУЛАР: Мысал.
- ТАПСЫРМАЛАР №1 есеп. "
- Қосымша ақпарат: Қажеттілік.
- Жеткіліктік.
- Қолданылған әдебиеттер
|
№10 ПРАКТИКАЛЫҚ ЖҰМЫС САБАҚ ТАҚЫРЫБЫ: Графтағы Эйлер айналымыСАБАҚ МАҚСАТЫ: Студенттерді графтағы Эйлер айнымалысымен таныстырып, есеп шығару барысында алған білімдерін қолданып, студенттердің графтармен жұмыс істеу дағдыларын қалыптастыру. ҚАРАСТЫРЫЛАТЫН НЕГІЗГІ МӘСЕЛЕЛЕР: 1. Эйлерлік граф 2. Эйлерлік емес граф 3. Кенингсберг көпірінің проблемасы 4. Қажеттілік 5.Жеткіліктілік НЕГІЗГІ МАҒЛҰМАТТАР: Эйлер айналымының есебі келесі түрде тұжырымдалады. байланысқан бағытталмаған граф берілсін делік. Онда G-да мынадай жағдай болса, егерде берілген циклдың C маршрутында, әрбір қыры тек бір рет қана кездессе, онда бастапқы графтың құрамына барлық қабырғалары мен барлық төбелері енетін мынадай C циклды табуға бола ма? – деген сұрақ туындайды.
Егер осы түрде тұжырымдалған анықтама болса, онда ол Эйлер циклы деп аталады, ал құрамына C енетін G графы Эйлер графы деп аталады. 1-суретте Эйлер графына жатпайтын граф көрсетілген. Ал, 2-суретте Эйлер графына жататын граф көрсетілген, себебі оның құрамына С=[1,4,3,5,4,6,1,2,3,1] Эйлер циклы енген. 1736 жылы Эйлер келесі пікірді дәлелдеді. Теорема 1. Граф байланысқан граф және төбелерінің барлық деңгейі жұп болған кезде ғана Эйлер графы бола алады. Сол кездерде кеңінен танымал болған Кенингсберг көпірінің проблемасы деп аталған есеп, граф теориясындағы осы теореманың ең бірінші дәлелі болды. Графтар теориясы, ғылым ретінде осы теоремадан басталды десек те болады, ал Л.Эйлер графтар теориясының негізін салушы болып есептеледі. ЖҰМЫСТЫ ОРЫНДАУҒА ӘДІСТЕМЕЛІК НҰСҚАУЛАР: Мысал. Флёри (Fleury) немесе Хоанг Туи алгоритмін алып қарайық. Флёри алгоритмінің мәні келесіде, G-ға Эйлер циклын бөлу үшін мынадай ережелерді сақтау керек: 10. Берілген графтың G=(V,E) ерікті төбесінен шығып, әр өткен қырды сызып тастаймыз. 20. Қарастырылып отырған кезде eE қыры қылта болса, яғни егер оны графтан азайтсақ, граф сызылып тасталған қырлардан құралып ең дегенде бір қабырғадан тұратын байланысқан екі компонентке бөлінеді. 5.5-теореманың конструктивті дәлелін жүзеге асыра отырып, біз тағы да бір Эйлер циклы алгоритмінің G-ға бөлінуін толық мазмұндап береміз. ТАПСЫРМАЛАР №1 есеп. "Граф байланысқан граф және төбелерінің барлық деңгейі жұп болған кезде ғана Эйлер графы бола алады" теоремасын дәлелдеңіз. Қосымша ақпарат: Қажеттілік. G графының құрамына Эйлер циклы енсе, оның байланысуы қажет екені айқын. G-дағы барлық төбелердің адал деңгейінің қажеттілігі, Эйлер айналымы кезінде әрбір төбеге i еніп, сол сан ki, ki ≥ 1 түрінде одан шығуы керек. Демек, i төбесінің әрбір деңгейі 2ki жұп санына тең. Жеткіліктік. G графын байланысқан граф және оның төбелерінің барлық деңгейі жұп деп алайық. №2 есеп. 2-суретте көрсетілген графта біз деп алып цикл құрастырайық. Онда төбесі ретінде, оның инцидентті қыры бар 1 төбесін алуға болады. Енді осы жолы төбесінен бастап -ге жатпайтын жаңа тізбегін құрастырыңыз. Есеп №3. G – E жиынтық доғаларымен соңғы бағытталған байланысқан графы. E-ден тараған барлық доғалары енетін контуры болуы үшін, әрбір төбеге енетін және енбейтін доғалар саны бірдей болуы керек екендігін дәлелдеңіз. Есеп №4. 1-суретте берілген -ды граф деп алсақ, оның (2, 4) қырына 5 деген салмақ қосымша жазылған, ал қалған қырларына 1-ге тең салмақ қосымша жазылған. Сонда барлық қырларды айналып өтудің ең қысқа маршрутын табыңыз. 3-сурет. Граф үшін бейнеленген Эйлер мультиграфы Қолданылған әдебиеттер: О.И.Мельников. Теория графов в занимательных задачах. Москва:2009. В. Е. Алексеев, В. А. Таланов. Графы. Модели вычислений. Структуры данных. Нижний Новгород 1 , 2005г. Ловас Л . Прикладные задачи теории графов / Л. Ловас, М. Пламмер. М.: Мир, 1998. жүктеу/скачать 67,5 Kb. Достарыңызбен бөлісу:
|