216 Bob IV. Graflar nazariyasi

Nazorat uchun savollar:
1. Insidentlik tushunchasini ta’rifini bering.
2. Nol graf nima?
3. Tolerant graf ta’rifini bering.
230 Bob IV. Graflar nazariyasi
4. Planar graf nima?
5. Qanday graflar gomeomorf deyiladi?
6. Yig`indi graf deb nimaga aytiladi?
7. Ko`paytma graf deb nimaga aytiladi?
8. Grafning diametri deb nimaga aytiladi?
9. Pontryagin-Kuratovskiy teoremasini ayting.
Mustaqil yechish uchun masalalar:
1. Quyidagi graflarning yig`indisi va ko`paytmasini toping:
2. Quyidagi graflarning yig`indisi va ko`paytmasini toping:

4.4. Graflarni хarakterlovchi sonlar
Ta’rif 1. Grafning siklomatik soni deb,  N-n+p songa aytiladi, bu yerda N- grafning qirralari soni, n – grafning uchlari soni, P – bog`liqlik komponenti soni. Bog`liq graf uchun N-n+1.
Teorema 1. Grafning siklomatik soni erkli sikllarning eng katta miqdoriga teng.
4.4. Graflarni хarakterlovchi sonlar 231
Misol 1.
Quyidagi chizmada tasvirlangan grafning siklomatik soni 3 ga teng.

Ta’rif 2. Agar grafning uchlar to‘plamini o‘zaro kesishmaydigan shunday ikkita qism to‘plamlarga (bo‘laklarga) ajratish mumkin bo‘lsaki, grafning ixtiyoriy qirrasi bu to‘plamlarning biridan olingan qandaydir uchni ikkinchi to‘plamdan olingan biror uch bilan tutashtiradigan bo‘lsa, u holda bunday graf ikki bo‘lakli graf (bixromatik yoki Kyonig grafi) deb ataladi.
Nazorat uchun savollar:
1. Siklomatik son nima?
2. Siklomatik sonni formula orqali ifodalang.
3. Kyonig grafi deb nimaga ataladi?
232 Bob IV. Graflar nazariyasi
4.5. Daraxtlar
Ta’rif. Agar G grafning u qirrasi kamida bitta siklga tegishli bo`lsa, u siklik qirra, aks holda atsiklik qirra deb ataladi.
G graf uchun

Ifoda uning siklomatik soni deb ataladi, bu yerda m(G) G grafning qirralar soni. n(G)- uchlari soni, k(G)- komponental soni.
Osongina ko`rish mumkinki,
K(G), agar u siklik qirra bo`lsa,
K(G\u)=
K(G)+1, u  atsiklik qirra bo`lsa;
(G)-1, agar u siklik qirra bo`lsa,
(G\u)=
K(G), agar u atsiklik qirra bo`lsa.
O`z-o`zidan ravshanki, n(G\u)=n(G), m(G\u)=  (G)-1,  (G) 0 va faqat sikllari bo`lmagan graf uchun  (G)=0.