Graflar ustida amallar. Marshrutlar va zanjirlar

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)^<sub> 


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


_{2 i i j j j i i j j
} 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.