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