|
Reja: Yo’l, zanjir, sikl
|
| bet | 1/2 | | Sana | 15.05.2024 | | Hajmi | 309,71 Kb. | | #236518 |
Bog'liq diskret
MAVZU: GRAFDA ZANJIR, MASHRUT,
SIKL TUSHUNCHALARI. EYLER
GAMILTON SIKLLARI VA GRAFLARI
REJA:
1.Yo’l, zanjir, sikl.
2.Bog’langanlik tushunchasi.Bog’langanlik komponentalari.
3.Eyler graflari.Eyler graflari haqida teoremalar.
1. 1-ta’rif. Oddiy G=(X,U) grafdagi
x0 u1 x1 u2 x2u3 x3 .....xl1 ul xl
ketma-ketlik (bu yerda x0 , x1 ,...xl X ; u1u2 ,..., ul U ) uzunligi l teng bo’lgan va x0 , x1
uchlarni tutashtiruvchi marshrut deyiladi.
Agar x0 xl va l 1 bo’lsa, marshrut tsiklik deyiladi. l 0 marshrut bitta x0
uchdan iborat bo’ladi va u tsiklik hisoblanmaydi.
Marshrutda uchlar va qirralarning har xil bo’lishi talab qilinmaydi. Bitta uch
yoki qirra bir necha marta takrorlanishi mumkin.
2-ta’rif. Qirralari har xil bo’lgan marshrut zanjir deb ataladi. TSiklik zanjir
esa tsikl deyiladi. Agar zanjirda (tsiklda) x0 va x1 lardan tashqari barcha uchlari
har xil bo’lsa, u holda sodda zanjir (tsikl) deyiladi.
10-shakl.
Yuqoridagi grafda (10-shakl) 3v2u1w3p4t5t4t5 va 3w1u2v3p4t5t4t5
marshrutlar bir xil elementlardan tuzilgan bo’lsada, lekin har xildir. Ular tsiklik
emas va zanjir ham emasdir. 3w1u2v3p4 marshrut zanjir, lekin sodda emas va
tsiklni tashkil etmaydi. 3w1u2v3p4s6r7g3 va 3v2u1w3p4s6r7g3 har xil sodda
bo’lmagan tsikllar. 3g7r6s4p3 - marshrut sodda tsikldir. 1u3v2 ketma-ketlik
umuman marshrut emas.
3-ta’rif. Agar G grafning x va y uchlari orasida hech bo’lmaganda bitta
zanjir mavjud bo’lsa, u holda ular tutashtirilgan deyiladi.
Ravshanki, grafning uchlari to’plamida berilgan “tutashtirilganlik”
munosabati refleksivlik, simmetriklik, tranzitivlik xossalariga ega. Demak, bu
munosabat ekvivalentlikdir va grafning X uchlari to’plamini X1 , X2 ,..., Xk sinflarga
ajratadi. Har bir sinfga tegishli bo’lgan uchlar o’zaro tutashtirilgandir (turli
sinflarga tegishli bo’lgan uchlar orasida zanjirlar yo’q).
G (X ,U) grafning Gi (Xi ,Vi ) (i 1,2,..., k) qism grafi uning bog’liqli
komponentasi deyiladi. Agar k(G) 1 bo’lsa, graf bog’likli deyiladi. Agar bog`liqli grafda barcha uchlar juft bo`lsa, bu graf eyler sikliga ega bo`ladi.
Teskari tasdiq ham o`rinli: agar graf eyler sikliga ega bo`lsa, uning barcha uchlari darajalari juft bo`ladi.
Misol.
Agar grafda oddiy cikl mavjud bo`lib, bu ciklda grafning barcha uchlari qatnashsa, bunday sikl Gamilton sikli deyiladi. Oddiy zanjir Gamilton zanjiri deyiladi, agar bunday grafda uchlarning hammasi ishtirok etsa. Boshqacha aytganda, agar zanjir grafning barcha uchlaridan bir martadan o`tsa, bunday zanjirga gamilton zanjiri deyiladi. Unda uch va qirralar takrorlanmasligi kerak. Grafda Gamilton tsikli mavjud bo`lsa, bu graf Gamilton grafi deyiladi. Yoki agar bog`liqli grafda har bir uchdan faqat bir martadan o`tuvchi sikl mavjud bo`lsa, bunday graf gamilton grafi deyiladi. Agar graf tekislikda geometrik ifodalanishga ega
bo`lsa, u holda bunday graf tekis (yassi) graf deb ataladi. Bunday graf tekislikda yotuvchi graf deb ham atalishi mumkin.
Boshqacha so`zlar bilan aytganda, tekis grafning barcha uchlari bir tekislikda yotadi hamda barcha qirralari (yoylari) o`sha tekislikda yotuvchi o`zaro kesishmaydigan uzluksiz chiziqlar bo`lib, ular faqat o`zlari insident bo`lgan uchlardagina umumiy nuqtalarga ega.
Platon jismlariga mos barcha graflar tekis graflardir.
Tekis grafga izomorf graf planar graf deb ataladi.
2. Bog’liqli G grafning uchlari to’plami X da masofa tushunchasini kiritish mumkin: i va j uchlar orasidagi masofa deb
|
| |
