Toshkent viloyati Chirchiq Davlat pedagogika instituti Aniq fanlar fakulteti

uch valentli) graf deb ataladi. O_m
graf nol darajali regulyar graf ekanligini,


K_m esa

( m 1) darajali regulyar graf ekanligini ta’kidlaymiz.
Ko‘rinib turibdiki, oriyentirlanmagan grafda barcha uchlar darajalarining yig‘indisi qirralar sonining ikki baravariga teng juft son bo‘ladi, chunki qirralarni sanaganda har bir qirra hisobda ikki marta qatnashadi. Shunday qilib, XVIII asrdayoq L. Eyler tomonidan isbotlangan quyidagi tasdiq o‘rinlidir.

1 . 1 - l e m m a (“ko‘rishishlar” haqida). Ixtiyoriy oriyentirlanmagan grafda barcha uchlar darajalari yig‘indisi qirralar sonining ikki baravariga teng.
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. Ta’rifdan ko‘rinib turibdiki, ikki bo‘lakli grafning har bir bo‘lagidagi ixtiyoriy ikkita uchlar qo‘shni bo‘la olmaydi. Biror bo‘lagida faqat bitta uch bo‘lgan to‘la ikki bo‘lakli graf yulduz deb ataladi.

Agar ikki bo‘lakli grafning turli bo‘laklariga tegishli istalgan ikkita uchi qo‘shni bo‘lsa, u holda bu graf to‘la ikki bo‘lakli graf deb ataladi. To‘la ikki

bo‘lakli grafni

^Km,n
bilan belgilaymiz, bu yerda m va n bilan grafning

bo‘laklaridagi uchlar sonlari belgilangan.

K_m,n  (V ,U )
graf uchun
| V | m  n va

| U | mn

bo‘lishi ravshan, bu yerda
| V | –

^Km,n
grafning uchlari soni,
| U |
– uning

qirralari soni.
Grafning ikki bo‘lakli graf bo‘lishi haqidagi ba’zi qo‘shimcha ma’lumotlar (Kyonig tasdiqsi) ushbu bobning 1.4- bandida keltirilgan.
Ikkidan katta ixtiyoriy natural k son uchun k bo‘lakli graf tushunchasini ham kiritish mumkin.