Guliston davlat

Teorema 3.2. Har bir yo’naltirilmagan graf o’zining bog’lamlilik komponentalarining (3.5) to’g’ri yig’indisiga ajraladi va bu ajralish yagona bo’ladi.

Teorema 3.3. Agar chekli grafda ikkita uchlar toq lokal darajaga ega bo’lsa, u holoda ular bog’langan bo’ladi.

Masofa. yo’naltirilmagan bog’lamli graf bo’lsin. Ixtiyoriy va uchlari bog’langan bo’lsa, u holda oxirlari va bo’lgan bo’lgan oddiy zanjir mavjud bo’ladi. Ushbu oddiy zanjirlarning uzunliklari manfiy bo’lmagan butun sonlardan iborat bo’ladi. Mos ravishda va uchlar orasida eng qisqa uzunlikka ega zanjir majud bo’ladi. Ushbu eng qisqa uzunlik va orasidagi masofa deyiladi va kabi belgilanadi. Ta’rif bo’yicha bu masofalar uchun tenglik bajariladi. Oson ko’rish mumkinki, bu aniqlangan masofa funktsiyasi metrika aksirmalarini qanoatlantiradi:

1.

2. tenglik shunda va faqat shunda bajariladiki, qachonki,

.

3. .

4. Uchburchak tengsizligini qanoatlantiradi: .

Chekli graflar uchun uning ikki uchi orasidagi eng uzun masofani ifodalovchi chegaralangan diametr tushunchasini kiritish mumkin:

Mos ravishda eng uzun masofaga ega ikki uchni bog’lovchi oddiy zanjirni diametrial oddiy zanjir deb ataymiz.

Qandaydir fiksirlangan uchni olamiz va undan ning uchigacha bo’lgan eng uzun masofani

kabi belgilaymiz. Agar (2.1.7) qiymat uchda

eng kichik qiymatga erishsa, u holda bu uchni grafning markazi deb ataladi. (3.8) qiymatni grafning radiusi deb, uchdan eng uzun masofadagi qandaydir uchgacha bo’lgan ixtiyoriy eng qisqa oddiy zanjirni radial oddiy zanjir deb ataladi. Grafda markaz yagona bo’lmasligi mumkin. Faraz qilaylik, – chekli, lokal darajasining yuqori chegarasi bo’lgan graf bo’lsin. Ixtiyoriy uchni olaylik va bu uch uchun uchlar yoyilmasi mavjud bo’lsin. uchdan uchga dan ko’p bo’lmagan qirralar chiqadi. Har bir uchdan uchga dan ko’p bo’lmagan qirralar chiqadi va hakazo. Bundan quyidagi tengsizlik kelib chiqadi:

Bundag esa, quyidagicha tasdiq kelib chiqadi: biror uch ikkita va uchlar orasidagi eng qisqa uchga tegishli bo’ladi shunda va faqat shundaki, qachonki tenglik o’rinli bo’lsa.