Fanidan mavzusida

T e o r e m a (Eyler 1752). Tekis va bog‘lamli
G(V,U)
grafuchun

mr2n
tenglik o‘rinlidir, bu yerda
m V,
n U
, r – yoqlar soni.

1.5-teoremaning tasdig‘idagi ataladi.
mr2n
tenglik Eyler formulasi deb

Eyler teoremasidan bir qator natijalar kelib chiqadi. Masalan, bu teoremadan foydalanib uni osonlik bilan bog‘lamli bo‘lmagan graflar uchun quyidagicha umumlashtirish mumkin.
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 debataymiz.
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.
Bog‘lamli graf uchlarini belgilash jarayoni tugagandan so‘ng, uning uchlari

to‘plami V ni ikkita V_j
va V_q
to‘plamga quyidagicha ajratamiz: juft raqamli

uchlarni V_j
to‘plamga, qolgan uchlarni esa V_q
to‘plamga kiritamiz (0 raqamli uch

V_j to‘plamga kiritiladi). G grafning ikkala uchi ham V_j to‘plamga tegishli barcha

qirralari kortejini U _j
bilan, uning ikkala uchi ham V_q
to‘plamga tegishli barcha

qirralari kortejini esa U_q
bilan belgilaymiz. Agar U _j
va U_q
kortejlar bo‘sh bo‘lsa, u

holda berilgan G graf ikki bo‘laklidir, aks holda u ikki bo‘lakli emas.

Hozirgacha

k  2
bo‘lgan holuchun grafning k bo‘lakliligini aniqlash bo‘yicha oddiy usul topilmagan.