O‘zbekiston respublikasi axborot texnologiyalari va

chetki (yoki osilgan) uch deb ataladi. Chetki (osilgan) uchga insident qirra ham chetki (yoki
osilgan) qirra deb ataladi.
r r Agar grafning barcha uchlari bir xil darajaga ega bo‘lsa, u holda bunday graf darajali
regulyar graf deb ataladi. Uch darajali regulyar graf kubik (yoki uch valentli) graf deb ataladi.
m O K  m m 1 graf nol darajali regulyar graf ekanligini, esa ( ) 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 - l e m m a (“ko‘rishishlar” haqida).Ixtiyoriyoriyentirlanmagan 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
Km, n bu graf to‘la ikki bo‘lakli graf deb ataladi. To‘la ikki bo‘lakli grafni bilan belgilaymiz, bu
K m m n , n  (V,U) yerda va bilan grafning bo‘laklaridagi uchlar sonlari belgilangan. graf uchun
| | | V K U U V | | m m mn ,  n | | n va bo‘lishi ravshan, bu yerda – grafning uchlari soni, – uning qirralari soni. Grafning ikki bo‘lakli graf bo‘lishi haqidagi ba’zi qo‘shimcha ma’lumotlar (Kyonig teoremasi) ushbu bobning 4- paragrafida keltirilgan.
k k Ikkidan katta ixtiyoriy natural son uchun bo‘lakli graf tushunchasini ham kiritish mumkin.
V 1- m i s o l . O‘zbekiston Respublikasi hududidagi aeroportlar to‘plamini bilan, bu shaharlar orasida belgilangan vaqt mobaynida amalga oshirilayotgan samolyotlarning uchib qo‘nish
( U V,U) hodisalari kortejini bilan belgilaymiz. U holda juftlikni graf deb qarash mumkin. Bu yerda grafning uchlariga aeroportlar, yoylariga esa samolyotlarning uchib qo‘nish hodisalari mos
(V,U) keladi. Tabiiyki, grafda karrali yoylar bo‘lishi mumkin, agar, qandaydir sababga ko‘ra, samolyot uchgan aeroportga qaytib qo‘nsa, u holda bu hodisaga qaralayotgan grafdagi sirtmoq mos keladi.