Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану
жүктеу/скачать 1.12 Mb.
|
- Бұл бет үшін навигация:
- Дәріс №12. Жазық графтар
- Жазық графтар
- 2.Графтарды бояу есебі
| Қолданылған әдебиеттер
[1], [2], [3], [5], [16], [18]. Бақылау сұрақтары: Жұп граф дегеніміз не? Эйлер графы деген қандай граф? Эйлер циклы қалай анықталады? Тең дәрежелі граф деген қандай граф? Дәріс №12. Жазық графтар Дәріс мақсаты:Жазық графтардың қолданылуын,олармен орындалатыноперациялармен таныстыру. Кілттік сөздер:жазық граф,цикломатиялық сан,Гамильтон графы. Жоспары: Жазық графтар Графтарды бояу есебі Жазық графтар G графы деп V(G) шектеулі төбелер жиыны мен R(G) шектеулі қабырғаларжиыны аталады және әрбір қабырғасының ұштары әртүрлі екі төбе болады. Егер граф төбелері жазықтық нүктелері болса, ал қабырғалары осы жазықтықта сынық сызықтар (кесінділерден құралған) болса, онда граф жазық деп аталады. Және жазық граф қабырғаларының ұштары өзара қиылыспайтын, басқа төбелерді енгізбейтін ұштармен шектеледі. Жазық графта ілгектер (басы мен ұшы бір төбе болатын қабырғалар) болмауы керек. Жазық граф жазықтықты D(G) қамтылмайтын көпбұрышты облыстар жиынына бөліктейді, облыстардың шектеулі болуы міндет емес. Егер қолданылған түстерді 1, 2, ..., n деп нөмірлесек, картаға сәйкес жазық графта осы сандармен төбелер (астаналар) нөмірленеді. 2.Графтарды бояу есебі жазық графының дұрыс n-түсті боялуы деп :V(G) {1,2,...,n} бейнесі аталады және егер оның шекарасы v1 мен v2 болатындай r R(G)қабырғасы бар болса, (v1) (v2 ) өрнегі орындалады. Сонымен, төрт бояу проблемасын келесі тұжырым түрінде қорытындылаймыз. 1-теорема. Кез келген жазық граф дұрыс 4 түсті бояуды ұйғарады. Осы проблеманы шешу мәселесіне жүз жылдан астам уақыт жұмсалды. Бірақ бір қарағанда әлсіз болып көрінетін дұрыс 5 түсті бояу туралы тұжырым оңай дәлелденеді. Дәлелдеуге төбелер, қабырғалар және облыстар санын байланыстыратын Эйлер формуласы керек болады. M шектеулі жиыны элементтерінің санын білдірсін. Эйлер теоремасы. Кез келген жазық граф үшін |V(G) |+| D(G)|= 2 + |R(G)| . 2- теорема. Кез келген жазық граф 5 түсті бояуды ұйғарады. Дәлелдеуі. Алдымен графты ықшамдаймыз.Егер небір төбелер жұбынбіріктіретін бірнеше қабырғалар бар болса (бұндай жағдай екі елдің бірнеше өзара байланыспайтын шекара тілімдері бар болғанда туындайды, мысалы Ресей мен Қытай сияқты), онда тек бір қабырға қалтырамыз: осындай кішірейтілген графты дұрыс түстеп бояу, ізделінген түстеп бояудың дұрыс болуына кепілдік береді. Граф төбелері санымен индукция жүргіземіз. Үш төбесі бар граф үшін теорема тұжырымы орындалатыны айқын. Бұл тұжырым n -1 төбелі барлық графтар үшін әділ. D1,D2,...,Dm –түгел m =D(G)граф облыстарының толық жиынтығыболсын, ал N(Di ) – графтың i - інші облысының шекарасын құратын қабырғалар саны. Сонымен қатар кез келген i үшін N(D) >3. Кез келген қабырға екі облыс шекарасына енеді, сондықтан N(D1) + N(D2 ) +...+ N(Dm) = 2R(G) . N(Di ) 3 теңсіздігінен 2R(G) = N(D1) + N(D2 ) +...+ N(Dm) 3m = 3D(G) аламыз, осыдан 2R(G) 3D(G) . Эйлер формуласынан |V (G)|-2 + |D(G) |=|R(G)|, осыдан 3| R(G)| =3|V(G)|-6+3 |D(G)| 3|V(G)|-6+2|R(G)| және |R(G)| 3|V (G)|-6 (1) шығарылады. Екі еселенген қабырғалар санын басқа да граф сипаттамасымен теңдестіруге болады. ... , n=V(G) граф төбелерінің толық жиынтығы болсын, ал M( ) – j нөмірлі төбеге жинақталатын қабырғалар саны. Бірақ әр қабырға екі төбемен шектеледі, сондықтан 2R(G) =M( ) +M( )+ ... +M( ). Сонымен қатар, (1) теңсіздігінен шығарылатындай, 2| R(G)| 6|V(G)|-12. Ендеше,
жүктеу/скачать 1.12 Mb. Достарыңызбен бөлісу:
|