|
Tayyorladi: 043-22 sto’ guruh talabasi miraxmedov jaxongir mirzayevich toshkent – 2023 y. Reja: Kirish
|
| bet | 5/13 | | Sana | 10.01.2024 | | Hajmi | 125,27 Kb. | | #134127 |
Bog'liq diskretuch valentli) graf deb ataladi. Om
graf nol darajali regulyar graf ekanligini,
Km 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.
Km,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.
|
| |
