Mavzu: daraxtlarda yurish, tayanch daraxtlar. Reja: Daraxt va unga ekvivalent tushunchalar. Grafning siklomatik soni tushunchasi

Natija. Bittadan ko 'p uchga ega bo '/gan istalgan dara_'ada hech bo 'lmasa ikkita darajasi birga teng uch/ar mavjud.
Isboti. Haqiqatdan ham, agar VI' v2' . .. , V m berilgan daraxtning uchlari bo'lsa, "ko'rishishlar" haqidagi lemmaga binoan m LP(v,)=2(m-l) tenglik o'rinlidir. Daraxtning ta'rifiga ko'ra, u ,=1 bog'lamlidir, shuning uchun p(v,) ~ I (i = I,m). Bundan yuqoridagi tengl1k o'rinli bo'lishi uchun p(v,),p(vJ, ... ,p(vm ) ketma-ketlikdagi hech bo'lmaganda ikkita son birga teng bo'lishi kelib chiqadi. _ 2- nat i j a. m ta uch va k ta bog'lamli komponentli 0 'rmondagi qirralar soni (m - k) ga tengdir. Is bot i.
1-teorema isbotining 2) tasdiqdan 3) tasdiq kelib chiqishiga bag'ishlangan qismiga qarang.
2- teo rem a. lstalgan daraxtning markazi uning billa uchidan yoki ikkita qo 'shni uchlaridan iborat bo 'ladi.
Isboti. Agar daraxt bitta uch yoki ikkita qo'shni uch va ularni tuashtiruvchi qirradan tashkil topgan bo'lsa, teorema tasdig'i to'g'riligi oydindir. G daraxt tarkibida ikkitadan ko'p uch bor deb faraz qilamiz. G daraxtdagi darajalari birga teng barcha uchlarni (ya'ni, daraxtning barcha chetki uchlarini) bu uchlarga insident barcha qirralar (ya 'ni, daraxtning barcha chetki qirralari) bilan birgalikda G daraxtdan olib tashlaymiz.
Natijada uchlari va qirralari soni berilgan G daraxtdagi uchlar va qirralar sonidan kam bo'lgan qandaydir G' daraxtni hosil qilamiz. G' daraxtdagi har bir uch ekssentrisiteti G daraxtdagi mos uch ekssentrisitetidan bitta kam bo'lishi va bu daraxtlarning markazlari ustma-ust tushishi ravshandir. Berilgan graf chekli bo'lgani uchun, yuqoridagi bayon etilgan jarayonni yetarlicha marta takrorlash natijasida bitta uch yoki ikkita qo'shni uch va ularni turashtiruvchi qirradan tashkil topgan qandaydir daraxtni hosil qilamiz. _ Uchlan soni ma'lum, o'zaro izomorfbo'lmagan va qandaydir shartlami qanoatlantiruvchi daraxtlar somm aniqlash masalasi daraxtlami o'rganishda muhim masala hisoblanadi. Yuqorida 4, 5 va 6 ta uchlarga ega o'zaro izomorf bo'lmagan daraxtlar mos ravishda 2, 3 va 6 ta ekanligi ta'kidlangan edi. A. Keli uglerod atomlan soni berilgan \'a CnH21i+2 ko'rinishdagi kimyoviy formula bilan ifodalanuvchi to'yingan uglevodorodlar sonini topish masalasini har bir uchining darajasi bir yoki to'rt bo'lgan daraxtlar sonini topish masalasiga keltirib hal qilgan. Quyidagi teorema Keli nomi bilan yuritiladi.
3- teo rem a (Keli). Uchlari soni m ba'lgan belgilangan daraxtlar . m-2 sam m ga teng. I sb oti o'quvchiga havola qilinadi. Grafning siklomatik soni. Faraz qilaylik, G sirtmoqsiz va karrali qirralari bo'lmagan qandaydir bog'lamli graf bo'lsin. Bu gfafdan uning biror sikliga tegishli bitta qirrasini olib tashlash natijasida hosil bo'lgan graf bog' lamli graf bo' lishi ravshandir. Grafdan uning biror sikl iga tegishli bitta qirrasini olib tashlash amalini hosil bo'lgan graflarga, imkoni boricha, ketma-ket qo'Hash natijaslda G grafning barcha uchlarini bog'lovchi graf - daraxtni hosil qilish mumkin. Bunday daraxt G grafning sinch daraxti (sinchi, karkasi, qobirg'asi) deb ataladi.