| Қолданылған әдебиеттер
[1], [2], [3], [5], [16], [18].
Бақылау сұрақтары:
Жұп граф дегеніміз не?
Эйлер графы деген қандай граф?
Эйлер циклы қалай анықталады?
Тең дәрежелі граф деген қандай граф?
Дәріс №12. Жазық графтар
Дәріс мақсаты:Жазық графтардың қолданылуын,олармен орындалатыноперациялармен таныстыру.
Кілттік сөздер:жазық граф,цикломатиялық сан,Гамильтон графы.
Жоспары:
Жазық графтар
Графтарды бояу есебі
Жазық графтар
G графы деп V(G) шектеулі төбелер жиыны мен R(G) шектеулі қабырғаларжиыны аталады және әрбір қабырғасының ұштары әртүрлі екі төбе болады. Егер граф төбелері жазықтық нүктелері болса, ал қабырғалары осы жазықтықта сынық сызықтар (кесінділерден құралған) болса, онда граф жазық деп аталады. Және жазық граф қабырғаларының ұштары өзара қиылыспайтын, басқа төбелерді енгізбейтін ұштармен шектеледі. Жазық графта ілгектер (басы мен ұшы бір төбе болатын қабырғалар) болмауы керек.
Жазық граф жазықтықты D(G) қамтылмайтын көпбұрышты облыстар жиынына бөліктейді, облыстардың шектеулі болуы міндет емес.
Егер қолданылған түстерді 1, 2, ..., n деп нөмірлесек, картаға сәйкес жазық графта осы сандармен төбелер (астаналар) нөмірленеді.
Достарыңызбен бөлісу: |
