Graflar ustida amallar. Marshrutlar va zanjirlar

Grafning bog‘lamliligi tushunchasi. Agar oriyentirlanmagan grafda chetlari a va b uchlardan iborat marshrut topilsa, bu a va b uchlar bog‘langan deb, marshrutning o‘zi esa a va b uchlarni bog‘lovchi marshrut debataladi.

_Tabiiyki, agar qandaydir uchlarni bog‘lovchi marshrut biror a_i

uchdan bir necha marta o‘tsa, u holda marshrutning siklik qismini olib
_tashlab (bunda siklik qismning o‘rniga marshrutda faqat a_i




uch
qoldiriladi) yana o‘sha uchlarni bog‘lovchi oddiy zanjir ko‘rinishdagi marshrutni hosil qilish mumkin. Shuning uchun, marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham bo‘glangan bo‘ladi degan xulosaga kelamiz.

Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf bog‘lamli graf deb ataladi.
Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo‘lsa, u holda bu ikkita uch ekvivalent (bog‘langan) deyiladi. Bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentalari (qisqacha, komponentalari) deb ataluvchi bog‘lamli qismlarning birlashmasi deb qarash mumkin. Bu yerda berilgan graf bog‘lamlilik komponentalariga bo‘laklandi (ajratildi) deb aytish mumkin. Isbotlash mumkinki, har qanday graf o‘zining bog‘lamlilik komponentalarining diz’yunktiv birlashmasi sifatida ifodalanishi mumkin, bunda grafning bog‘lamlilik komponentalariga bo‘laklanishi bir qiymatli aniqlanadi.
Keyingi ma’lumotlarni bayon etish uchun yoq tushunchasi zarur bo‘ladi. Tekislikda geometrik ifodalanuvchi grafni qaraymiz. Bu grafga tegishli bo‘lmagan (ya’ni grafning hech qaysi uchi bilan ustma- ust tushmaydigan va uning hech qaysi qirrasida yotmaydigan) biror A nuqtani hech qaysi nuqtasi grafga tegishli bo‘lmagan uzluksiz chiziq bilan tutashtirish mumkin bo‘lgan barcha nuqtalar to‘plami grafning A nuqtani o‘zida saqlovchi yoqi deb ataladi.

Yoq tushunchasiga berilgan ta’rifga ko‘ra yoq grafning geometrik ifodalanishi yordamida tekislikning “qirqib” olinadigan qismidan iboratdir. Tekislikda geometrik ifodalanuvchi ixtiyoriy grafning hech bo‘lmaganda bitta yoqi bo‘lishi va uning bitta yoqi chegaraga ega emasligi (cheksizligi) o‘z-o‘zidan ravshandir.

• 
  teorema (Eyler 1752). Tekis va bog‘lamli
  

G  (V ,U )




graf uchun
m  r




 2  n




tenglik o‘rinlidir, bu yerda m  V




, n  U




, r – yoqlar soni.
Isboti. Teoremani isbotlash uchun matematik induksiya usulini grafdagi qirralar soni n bo‘yicha qo‘llaymiz. Induksiya usulining
bazasi sifatida




n  0




bo‘lgan holni qaraymiz. Bu holda teoremaning
tasdig‘iga ko‘ra




m  r  2




bo‘lishi kerak. Haqiqatdan ham, G tekis va
bog‘lamli graf bo‘lgani uchun, u yagona uchdan tashkil topadi va bu
uch yagona (cheksiz) yoqda yotadi, ya’ni holda teoremaning tasdig‘i to‘g‘ridir.




m  1 va




r  1. Demak, bu
Induksion o‘tish: teoremaning tasdig‘i n  k uchun to‘g‘ri bo‘lsin
deb faraz qilib, uning




n  k 1




uchun ham to‘g‘ri ekanligini
ko‘rsatamiz. Farazimizga ko‘ra .. tenglik o‘rinlidir. k ta qirraga ega G tekis va bog‘lamli grafga (k 1)- qirrani (uni e bilan belgilaymiz) shunday qo‘shish kerakki, bunda e qirra G graf joylashgan tekislikda yotsin va hosil bo‘lgan graf ham bog‘lamli bo‘lsin. Bu amalni bajarganda quyidagi uchta holdan biri ro‘y beradi:

• 
  qo‘shilayotgan qirra sirtmoqdir – bu holda e qirra, albatta, G grafdagi uchlardan biriga insident bo‘lib, yoqlardan birida yotadi va bu yoqni ikkiga (sirtmoq yotgan yoqning sirtmoq chizig‘i bilan chegaralangan ichki va tashqi qismlari) ajratadi, ya’ni uchlar soni
  

o‘zgarmaydi, yoqlar soni esa birga oshadi: m  r 1  2  k 1;

• 
  qo‘shilayotgan qirra G grafda bor bo‘lgan ikkita uchlarni tutashtiradi – bu holda ham grafning biror (e qirra yotgan) yoqi ikkiga
  

ajraladi, uchlari soni esa o‘zgarmaydi: m  r 1  2  k 1;

• 
  qo‘shilayotgan qirra sirtmoq emas va u G grafdagi uchlardan faqat bittasiga insidentdir – bu holda grafning biror yoqida e qirraga insident bo‘lgan bitta boshqa uch yasaladi (grafning uchlari soni bittaga oshadi) va e qirra joylashgan yoq yaxlitlikni saqlagan holda e
  

qirrani o‘z ichiga oladi (yoqlar soni o‘zgarmaydi):

■




m 1 r




 2  k 1.
2- teoremaning tasdig‘idagi deb ataladi.




m  r




 2  n




tenglik Eyler formulasi
Eyler formulasi stereometriyada ham qo‘llaniladi: uchlari ..ta, yoqlari r ta va qirralari n ta ixtiyoriy ko‘pyoqli uchun Eyler formulasi o‘rinlidir. Bu tasdiqning negizida isboti o‘quvchiga havola qilinayotgan quyidagi tasdiq yotadi: stereometriyada berilgan ta’rifga ko‘ra aniqlangan ixtiyoriy ko‘pyoqliga mos tekis izomorf graf mavjuddir.

Eyler teoremasidan bir qator natijalar kelib chiqadi. Masalan, bu teoremadan foydalanib uni osonlik bilan bog‘lamli bo‘lmagan graflar uchun quyidagicha umumlashtirish mumkin.

• 
  natija. Tekis
  

G  (V ,U )




graf uchun




m  r




 1 n  k




tenglik
o‘rinlidir, bunda m  V

komponentalar soni.




, n  U




, r – yoqlar soni, k – bog‘lamlilik

• 
  natija. Karrali qirralari bo‘lmagan sirtmoqsiz tekis (m, n)-graf
  

uchun




n  3m  6




tengsizlik o‘rinlidir.
Isboti. Haqiqatdan ham, har bir yoq hech bo‘lmaqanda uchta qirra bilan chegaralanganligi va yoqlarni chegaralovchi qirralarni sanaganda har bir qirra ikki marta hisobda qatnashganligi uchun

3r  2n tengsizlik o‘rinlidir (ta’kidlaymizki, agar grafda uchta uch va
ikkita qirra bo‘lsa, u holda




n  3m  6




tengsizlik bajariladi). 3r




 2n
tengsizlikdan Eyler formulasini




r  2  n  m




ko‘rinishda qo‘llab,
n  3m  6 tengsizlikni hosil qilamiz. ■
Ushbu bobning 2- paragrafida




_{K5 va K3,3}




graflarning planar
emasligi ta’kidlangan (isbotsiz keltirilgan) edi. Endi bu tasdiqlarni qat’iy isbotlash mumkin.

• 
  teorema.
  

K₅ graf planar emas.
Isboti.




K₅ planar graf bo‘lsin deb faraz qilamiz. Planar graf uchun
n  3m  6




tengsizlik o‘rinlidir.




K₅ graf uchun




m  5 va




n  10
bo‘lganligidan bu tengsizlik 10  9 ko‘rinishdagi noto‘g‘ri
munosabatga olib keladi. Demak,




K₅ graf planar emas. ■

• 
  teorema.
  

^K3,3




graf planar emas.
Isboti.




^K3,3




planar graf bo‘lsin deb faraz qilamiz. Bu grafda 6ta uch
(m  6) va 9ta qirra (n  9) bo‘lgani uchun, Eyler teoremasiga ko‘ra,
unda 5ta (r




 2  n  m  2  9  6  5) yoq bo‘lishi kerak.




^K3,3




grafning
har bir yoqi kamida to‘rtta qirra bilan chegaralanganligi sababli bu graf
uchun 4r




 2n




tengsizlik o‘rinlidir. Lekin bu tengsizlik




^K3,3




graf uchun
20  18




ko‘rinishdagi noto‘g‘ri munosabatga olib keladi. Demak,




^K3,3
graf planar emas. ■

Isbotlash mumkinki, quyidagi tasdiq o‘rinlidir.

• 
  teorema. Agar biror graf
  

_{K5 yoki}




^K3,3




grafga gomeomorf
bo‘lgan qism grafga ega bo‘lsa, u holda bu graf tekislikda yotuvchi bo‘lmaydi.
1930 yilda K. Kuratovskiy² bu tasdiqqa teskari tasdiqni isbot qildi:
agar graf tekislikda yotuvchi bo‘lmasa, u holda u




_{K5 yoki}




^K3,3




grafga
gomeomorf bo‘lgan qism grafga ega bo‘ladi. Umuman olganda, graflarning planarligi haqidagi bu asosiy natija K. Kuratovskiydan oldin 1922 yilda L. S. Pontryagin³ tomonidan isbotlangan, lekin bu natija o‘sha vaqtda matbuotda e’lon qilinmagan edi.

• 
  teorema (Pontryagin-Kuratovskiy). Graf planar bo‘lishi
  

uchun u




_{K5 yoki}




^K3,3




grafga gomeomorf qism graflarga ega bo‘lishi
zarur va yetarlidir.

• 
  teorema. Agar karrali qirralari bo‘lmagan sirtmoqsiz grafda mta uch, n ta qirrai va k ta bog‘lamlilik komponentalari bo‘lsa, u holda quyidagi munosabat o‘rinlidir:
  

m  k




 n 




₍m  k)(m  k 1) _.

2


² Kuratovskiy (Kuratowski Kazimej, 1896-1980) – Polsha matematigi.

³ Pontryagin Lev Semyonovich (Понтрягин Лев Семенович, 1908-1988) – rus matematigi, akademik.
Isboti. Avval qirralar soni n bo‘yicha matematik induksiya usulini

qo‘llab m  k  n tengsizlikni isbotlaymiz. Agar grafda qirralar

bo‘lmasa (ya’ni, matematik induksiya usulining bazasi sifatida n  0

deb olinsa), u holda grafdagi uchlar soni uning bog‘lamlilik
komponentalari soniga tengdir: k




 m . Demak,




n  0




bo‘lganda
m  k  n munosabat to‘g‘ridir.
Induksion o‘tish. Grafdagi qirralar sonini n₀




bilan belgilab, bu son
minimal bo‘lsin, ya’ni grafdan istalgan qirrani olib tashlash amali bog‘lamlilik komponentalari soni o‘zgargan graf hosil qilsin deb faraz qilamiz. Bundan tashqari, matematik induksiya usuli talabiga binoan
_n  n₀




uchun isbotlanishi kerak bo‘lgan tengsizlik o‘rinli bo‘lsin deb
faraz qilamiz. Tabiiyki, bu holda grafdan istalgan qirrani olib tashlasak (bunda olib tashlangan qirraning chetlaridagi uchlar grafga tegishli bo‘lib qolaveradi), hosil bo‘lgan grafning uchlari soni m ga, qirralari
soni (n₀

bo‘ladi.




1)ga, bog‘lamlilik komponentalari soni esa (k 1)ga teng
Induksiya faraziga binoan




m  (k 1)  n₀ 1




tengsizlik o‘rinlidir.
Bu tengsizlikdan




m  k




_ n₀




kelib chiqadi. Shunday qilib, m  k  n
tengsizlik isbotlandi.
Endi




_{n  (m  k)(m  k 1)}

2




tengsizlikni isbotlaymiz. Buning uchun
grafning har bir bog‘lamlilik komponentasi to‘la graf bo‘lsin deb faraz

_qilamiz. Berilgan grafning uchlari sonlari mos ravishda m_{i va mj}
bo‘lgan ikkita bog‘lamlilik komponentalari




_{Di va Dj}




graflardan iborat
_bo‘lsin, bu yerda m<sub>i




</sub> m_j

• 
  
  
• 
  1. Tushunarliki,
  

_{Di va Dj}




graflarning uchlari
_umumiy soni (m_i

• 
  
  
• 
  _{mj )ga tengdir. Bu}
  

_{Di va Dj}




graflarni uchlari sonlari
_{mos ravishda (}m<sub>i




</sub>1) va (m_j




1) bo‘lgan to‘la graflar bilan
almashtirsak, uchlar umumiy soni o‘zgarmaydi, lekin qirralarning
umumiy soni




2

(C

_{mi 1}




2

• 
  C
  

_{mj 1}




)  (C²

m

i




 C² )

m

j




miqdorga o‘zgaradi. Oxirgi
ifodaning ko‘rinishini quyidagicha o‘zgartiramiz:
(C

2

_{mi 1}




2

• 
  C
  

_{mj 1}




)  (C²

m

i




 C² ) 

m

j
_ ^{1 }<sub>(m 1)m  (m 1)(m  2)  m (m 1)  m (m




</sub>1)^_{ 
2 i i j j i i j j}

^{ 1 (m2  m  m2  m  2m  2  m2  m  m2  m ) }
<sub>2 i i j j j i i j j

</sub> m_{i  mj 1  0.}

Shunday qilib, uchlari soni m va bog‘lamlilik komponentalari soni k bo‘lgan grafda maksimal sondagi qirralar bo‘lishi uchun u (k 1)ta yakkalangan uchlar va (m  k 1)ta uchga ega to‘la graf birlashmasidan tashkil topishi kerak ekan. Bu yerdan isbotlanishi kerak bo‘lgan tengsizlik kelib chiqadi. ■
7- teoremaning tatbiqi sifatida quyidagi tasdiqni keltiramiz.

^3- natija. mta uchga ega, qirralari soni ^{(m 1)(m  2) dan katta,}

2

karrali qirralari bo‘lmagan sirtmoqsiz graf bog‘lamlidir.

^Isboti. Birinchidan, agar sirtmoqsiz va karrali qirralari bo‘lmagan grafning bog‘lamlilik komponentalari soni k ga teng bo‘lsa (k  N ), u holda, 7- teoremaga binoan, bunday grafning qirralari soni ^{(m  k)(m  k 1) dan katta emas. Ikkinchidan,}

2
₍m 1)(m  2) _{ (m  k)(m  k 1)}




tengsizlik faqat




k  1




bo‘lsagina
2 2

to‘g‘ridir. ■
Tabiiyki, bog‘lamli grafdan qirrani yoki bir necha qirralarni olib tashlash natijasida hosil bo‘lgan graf bog‘lamli bo‘lishi ham bo‘lmasligi ham mumkin. Agar bog‘lamli grafdan qirrani olib tashlash amali grafning bog‘lamlilik xususiyatini buzsa, u holda bunday qirrani ajratuvchi qirra deb ataymiz.

Ravshanki, berilgan bog‘lamli grafda ajratuvchi qirralar ko‘p bo‘lishlari mumkin. Ajratuvchi qirralar to‘plamining hech qaysi qism to‘plami elementlari ajratuvchi qirralar bo‘lmasa, bu qirralar to‘plamini kesim deb ataymiz. Grafdan kesimga tegishli qirralar olib tashlansa, natijada ikki bog‘lamli komponentalari bo‘lgan graf hosil bo‘lishi ravshandir. Agar kesim yagona qirradan iborat bo‘lsa, u holda bu qirra ko‘prik deb ataladi.
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  G}₁




, 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, G₃




ham bitta 10
belgili uchga ega oriyentirlanmagan (1,0)-graf, G₄




esa uchlari to‘plami
{8,9,11,12,13,14,15} bo‘lgan oriyentirlanmagan (7,7)-grafdir. Agar G
grafning G₄




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 G₁ va

G₄ bog‘lamli komponentalari ko‘priklarga egadir. Masalan, (2,5) va
(5,6) qirralar G₁




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 V<sub>j




va</sub> V_q




to‘plamga quyidagicha ajratamiz: juft raqamli
_uchlarni V<sub>j




to‘plamga,</sub> qolgan uchlarni esa V_q




to‘plamga kiritamiz (0 raqamli uch
_{Vj to‘plamga kiritiladi). G grafning ikkala uchi ham Vj}




to‘plamga tegishli barcha
_qirralari kortejini U <sub>j




bilan,</sub> uning ikkala uchi ham V_q




to‘plamga tegishli barcha
_qirralari kortejini esa U<sub>q




bilan</sub> belgilaymiz. Agar U <sub>j




va</sub> U_q




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.