Graflar ustida amallar. Marshrutlar va zanjirlar
Yüklə 1,35 Mb.
|
- Bu səhifədəki naviqasiya:
- 8- teorema (D. Kyonig).
- ko‘ndalangiga izlash
| 3- misol. 1- shaklda tasvirlangan (15,14)-grafni G bilan
belgilaymiz. 5 8 9 6 Bu graf bog‘lamli graf emas, uning to‘rtta bog‘lamli komponentalari bor: 1 G G1 , bu yerda G1 – 14 1- shakl 15 uchlari to‘plami {1, 2,3, 4,5,6} bo‘lgan oriyentirlanmagan (6,7)-graf, G2 – bitta 7 belgili uchga ega oriyentirlanmagan (1,0)-graf, G3 ham bitta 10 belgili uchga ega oriyentirlanmagan (1,0)-graf, G4 esa uchlari to‘plami {8,9,11,12,13,14,15} bo‘lgan oriyentirlanmagan (7,7)-grafdir. Agar G grafning G4 bog‘lamli komponentasini alohida graf deb qarasak, bu grafda {(8,9),(14,15)} ko‘rinishdagi ajratuvchi qirralar to‘plamini ko‘rsatish mumkin. Bu qirralar kesim tashkil etadi. G grafning G1 va G4 bog‘lamli komponentalari ko‘priklarga egadir. Masalan, (2,5) va (5,6) qirralar G1 graf uchun ko‘priklardir. ■ Endi D. Kyonig tomonidan 1936 yilda isbotlangan ushbu teoremani grafning ikki bo‘lakli bo‘lishi yoki bo‘lmasligini tekshirish alomati (mezoni) sifatida keltiramiz. 8- teorema (D. Kyonig). Grafning ikki bo‘lakli bo‘lishi uchun uning tarkibida uzunligi toq son bilan ifodala-nuvchi sikl bo‘lmasligi zarur va yetarlidir. Berilgan .. grafning ikki bo‘lakliligini aniqlashning sodda usuli bor. Bu usul ko‘ndalangiga izlash deb ataluvchi soddagina izlash g‘oyasiga asoslangan. Ko‘ndalangiga izlash usuliga ko‘ra grafning uchlari 0,1, 2,3,... raqamlar bilan quydagi qoida bo‘yicha belgilanadi. Dastlab grafning ixtiyoriy uchi 0 raqami bilan belgilab olinadi. Shu 0 belgili uchga qo‘shni barcha uchlarga 1 belgisi qo‘yiladi. Endi 1 belgili har bir uchga qo‘shni uchlarni aniqlab, ular orasidagi belgisi yo‘q uchlarga 2 belgisini qo‘aymiz. Keyin 2 belgisiga ega barcha uchlarni aniqlab, ular uchun ham yuqoridagiga o‘xshash ish yuritamiz. Bu jarayonni mumkin bo‘lgan qadar davom ettiramiz. Tushunarliki, agar G graf bog‘lamli bo‘lsa, u holda ko‘ndalangiga izlash usuli grafning barcha uchlarini raqamlab chiqish imkonini beradi. Bog‘lamli graf uchlarini belgilash jarayoni tugagandan so‘ng, uning uchlari to‘plami V ni ikkita Vj va Vq to‘plamga quyidagicha ajratamiz: juft raqamli uchlarni Vj to‘plamga, qolgan uchlarni esa Vq to‘plamga kiritamiz (0 raqamli uch Vj to‘plamga kiritiladi). G grafning ikkala uchi ham Vj to‘plamga tegishli barcha qirralari kortejini U j bilan, uning ikkala uchi ham Vq to‘plamga tegishli barcha qirralari kortejini esa Uq bilan belgilaymiz. Agar U j va Uq kortejlar bo‘sh bo‘lsa, u holda berilgan G graf ikki bo‘laklidir, aks holda u ikki bo‘lakli emas. Hozirgacha k 2 bo‘lgan hol uchun grafning k bo‘lakliligini aniqlash bo‘yicha oddiy usul topilmagan. Yüklə 1,35 Mb. Dostları ilə paylaş:
|