I bob. Keli daraxti ustida garmonik funksiyalarni o’rganishning nazariy va metodologik asoslari

1.2.1-teorema. Agar grafdagi har bir uchning lokal darajasi ikkidan kichik bo‘lmasa, u holda bu graf tsiklga ega.
Isbot. Agarda graf sirtmoqlar yoki karrali qirralardan iborat bo‘lsa, teoremaning isboti ravshan. Shu sababli teorema isbotini graf karrali qirralar va sirtmoqlar bo‘lmagan holda keltiramiz.
Faraz qilaylik, berilgan grafning ixtiyoriy uchi bo‘lsin. Qaralayotgan uchga qo‘shni uchni va bu uchga dan farqli boshqa qo‘shni uchni, uchga esa dan farqli boshqa uchni va hakozo, uchga dan farqli boshqa qo‘shni uchni va hakazo, tanlab,

qirralar ketma-ketligini tuzamiz. Teoremaning shartiga ko‘ra, yuqoridagi ketma-ketlikni tuzish va talab etilgan xossaga ega uchni har doim topish mumkin.
Grafning uchlar to’plami chekli to‘plam bo‘lganligidan, yuqorida bayon etilgan uchlar ketma–ketligini qurish jarayonida chekli qadamdan so‘ng albatta oldin uchragan uchlardan birini tanlashga majburmiz. Agar biror uch ketma–ketlikda ikki marta uchragan birinchi uch bo‘lsa, ketma–ketlikka qirralar qo‘shish jarayonini to‘xtatamiz, chunki tuzilgan qirralar ketma–ketligining uch ikki marta qatnashgan qismi biz izlayotgan tsikldir. Teorema isbot bo‘ldi.
graf yo‘naltirilmagan graf bo‘lsin. Agar oxirlari va uchlardan iborat (1.2.2) ko‘rinishdagi marshrut mavjud bo‘lsa, u holda ikkita va uchlar bog‘langan deyiladi. Agar marshrut qandaydir uchdan bir martadan ko‘p o‘tsa, u holda uning tsiklik qismini o‘chirib tashlash orqali, va uchlarni bog‘lovchi qirralardan iborat yangi marshrut hosil qilinadi. Bundan kelib chiqadiki, marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham bog‘langan bo’ladi. Agar grafda uning ixtiyoriy ikki uchi bog‘langan bo‘lsa, bu holda uni bog‘lamli graf deb ataladi.
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 mavjud 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 funksiyasi metrika aksiomalarini 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.