Mustaqil ish

Lokal darajalar. Agar grafni uni tashkil etuvchi qirralari soni sanoqli bo’lsa, chekli graf, aksincha bo’lsa, cheksiz graf deb ataymiz.

yo’naltirilmagan graf bo’lsin. Bitta uchga intsidient bo’lgan qirralar soni uning lokal darajasi deyiladi va uni (1.2) kabi belgilaymiz. Biror uchning lokal darajasi hisoblanish jarayonida shu uchga intsidient bo’lagan sirtmoq uchun noaniqlik vujudga keladi. Ya’ni, sirtmoqni qanday hisobga qo’shish kerak; bitta qirra sifatidami yoki ikkita. Ushbu holatda qaralayotgan masalaga bog’liq ravishda qanday hisoblash qulaylik tug’dirsa, shunday hisoblagan ma’quldir. Shunga ko’ra, har bir holatda sirtmoqni qanday tartibda hisoblanganligi ko’rastilishi zarur.

Lokal daraja uchun bir necha sodda formulalar keltiramiz. grafdagi va uchlarni tutashtiruvchi qirralar sonini kabi belgilaymiz. Agar grafda karrali qirralar bo’lmasa, u holda quyidagicha hollar bo’lishi mumkin:

Ko’rinib turibdiki, har bir (1.1.2) lokal darajada uch uchun quyidagi yig’indi mavjud:

(1.3)

grafdagi qirralar sonini deb belgilaymiz. Har bir qirra va uch bo’yicha ikkita lokal darajada ishtirok etadi, bundan esa quyidagiga ega bo’lamiz:

(1.4)

yoki (1.3) ga ko’ra esa

(1.5)

(1.4) formuladan ko’rinib turibdiki, chap tomon har doim juft son bo’ladi.

Yuqoridagi formulalardan ko’rish mumkinki, yo’naltirilmagan grafda barcha uchlar lokal darajalar yig’indisi qirralar sonining ikki baravariga teng juft son bo’ladi, chunki qirralarni sanaganda har bir qirra o’zi intsidient bo’lgan uchlarda ikki marta qatnashadi. Shunga ko’ra asrdayoq L.Eyler tomonidan quyidagicha tasdiq isbotlangan.

Lemma–1. Ixtiyoriy yo’naltirilmagan grafda barcha uchlar darajalari yig’indisi qirralar sonining ikki baravariga teng.