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



Download 43,54 Kb.
bet4/12
Sana13.07.2022
Hajmi43,54 Kb.
#792119
1   2   3   4   5   6   7   8   9   ...   12
Bog'liq
DISKRET

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.

Download 43,54 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9   ...   12




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish