daraxtlar

DOCX 6 sahifa 218,0 KB Bepul yuklash

6 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 218,0 KB

Fayl turi DOCX

Sahifalar 6

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 6

mavzu: daraxtlar graf. uch. qirra. daraxt. o‘rmon. asiklik graf. marshrut. sikl. zanjir. oddiy zanjir. ko‘prik. grafning sinch daraxti, sinch o‘rmoni, siklomatik soni. 1. daraxt va unga ekvivalent tushunchalar. siklga ega bo‘lmagan orientirlanmagan bog‘lamli graf daraxt deb ataladi[footnoteref:1]. ta’rifga ko‘ra daraxt sirtmoqlar va karrali qirralarga ega emas. siklga ega bo‘lmagan orientirlanmagan graf o‘rmon (asiklik graf) deb ataladi. [1: orientirlangan daraxt tushunchasi ham bor.] 1- misol. 1- shaklda bog‘lamli komponentali soni beshga teng bo‘lgan graf tasvirlangan bo‘lib, u o‘rmondir. bu grafdagi bog‘lamli komponentalarning har biri daraxtdir. ■1- shakl 2- misol. 2- shaklda to‘rtta uchga ega bir-biriga izomorf bo‘lmagan barcha (ular bor-yog‘i ikkita) daraxtlarning geometrik ifodalanishi tasvirlangan. ■2- shakl beshta uchga ega bir-biriga izomorf bo‘lmagan barcha daraxtlar uchta, oltita uchga ega bunday barcha daraxtlar esa oltita ekanligini ko‘rsatish qiyin emas. daraxt tushunchasiga boshqacha ham ta’rif berish mumkin. umuman olganda, - graf uchun daraxtlar haqidagi asosiy teorema deb ataluvchi quyidagi teorema o‘rinlidir. 1- teorema. …

2 / 6

da daraxt faqat bitta uchdan tashkil topgan bo‘ladi. tabiiyki, agar bitta uchga ega bo‘lgan grafda sikl bo‘lmasa, u holda unda birorta ham qirra yo‘q, ya’ni . demak, bu holda tasdiq to‘g‘ridir. induksion o‘tish: daraxt uchun va bo‘lganda 2) tasdiq o‘rinli bo‘lsin deb faraz qilamiz. endi uchlari soni va qirralari soni bo‘lgan daraxtni qaraymiz. bu daraxtning ixtiyoriy qirrasini bilan belgilab, undan bu qirrani olib tashlasak, uchdan uchgacha marshruti (aniqrog‘i, zanjiri) mavjud bo‘lmagan grafni hosil qilamiz, chunki agar hosil bo‘lgan grafda bunday zanjir bor bo‘lsa edi, u holda daraxtda sikl topilar edi. bunday bo‘lishi esa mumkin emas. hosil bo‘lgan graf ikkita va bog‘lamli komponentalardan iborat bo‘lib, bu komponentalarning har biri daraxtdir. yana shuni ham e’tiborga olish kerakki, va daraxtlarning har biridagi uchlar soni dan oshmaydi. matematik induksiya usuliga ko‘ra, bu daraxtlarning har birida qirralar soni uning uchlari sonidan bitta kam bo‘lishini ta’kidlaymiz, ya’ni graf -graf bo‘lsa, quyidagi tengliklar o‘rinlidir: , va (). …

3 / 6

ng 4) tasdig‘i kelib chiqishini isbotlaymiz. – bog‘lamli graf va bo‘lsin. avvalo ta bog‘lamlilik komponentalariga ega karrali qirralari bo‘lmagan sirtmoqsiz -graf uchun munosabat o‘rinli bo‘lishini eslatamiz (ushbu bobning 4- paragrafidagi 7- teoremaga qarang). bo‘lgani sababli bog‘lamli grafdan istalgan qirra olib tashlansa, natijada ta uch va ta qirralari bo‘lgan graf hosil bo‘ladiki, bunday graf shartga binoan bog‘lamli bo‘la olmaydi. kerakli tasdiq isbotlandi. daraxtlar haqidagi asosiy teoremaning 4) tasdig‘idan uning 5) tasdig‘i kelib chiqishini isbotlaymiz. bog‘lamli graf va uning har bir qirrasi ko‘prik bo‘lsin deb faraz qilib, bu grafninng o‘zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutahtirilishi mumkinligini ko‘rsatamiz. bog‘lamli graf bo‘lgani uchun, uning istalgan ikkita uchi hech bo‘lmasa bitta oddiy zanjir vositasida tutashtiriladi. agar qandaydir ikkita uch bittadan ko‘p, masalan, ikkita turli oddiy zanjir vositasida tutashtirilishi imkoniyati bo‘lsa, u holda bu uchlarning biridan zanjirlarning birortasi bo‘ylab harakatlanib ikkinchi uchga, keyin bu uchdan ikkinchi zanjir bo‘ylab harakatlanib dastlabki …

4 / 6

mkoniyati bor. bu esa grafninng o‘zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutashtirilishi shartiga ziddir. grafninng qo‘shni bo‘lmagan va uchlarini qirra bilan tutashtirish amalini qo‘llash natijasida faqat bitta siklga ega bo‘lgan graf hosil bo‘lishini ko‘rsatamiz. shartga binoan qaralayotgan va uchlarni faqat bitta oddiy zanjir bilan tutahtirish mumkin. oddiy zanjir ta’rifiga ko‘ra esa bu zanjir tarkibida sikl yo‘q. shuning uchun va uchlarni grafninng tarkibida bo‘lmagan qirra bilan tutashtirish, albatta, tarkibida sikl topiladigan va bu sikl yagona bo‘lgan grafni hosil qiladi. teoremaning 5) tasdig‘idan uning 6) tasdig‘i kelib chiqishi ham isbotlandi. nihoyat, 1- teoremaning 6) tasdig‘idagi shartlar baja-rilsa, grafning daraxt bo‘lishini, ya’ni teoremaning 1) tasdig‘i kelib chiqishini isbotlaymiz. faraz qilaylik, asiklik graf bog‘lamli bo‘lmasin. u holda, bu grafning ixtiyoriy bog‘lamli komponentasidagi ixtiyoriy uchni uning boshqa bog‘lamli komponentasidagi ixtiyoriy uch bilan qirra vositasida tutashtirish amalini qo‘llash natijasida tarkibida sikl bo‘lgan graf hosil bo‘lmaydi. bu esa 6) tasdiqning ikkinchi qismiga …

5 / 6

n tashkil topgan bo‘lsa, teorema tasdig‘i to‘g‘riligi oydindir. daraxt tarkibida ikkitadan ko‘p uch bor deb faraz qilamiz. 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 daraxtdan olib tashlaymiz. natijada uchlari va qirralari soni berilgan daraxtdagi uchlar va qirralar sonidan kam bo‘lgan qandaydir daraxtni hosil qilamiz. daraxtdagi har bir uch ekssentrisiteti 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 turashtiruvch qirradan tashkil topgan qandaydir daraxtni hosil qilamiz. ■ uchlari soni ma’lum, o‘zaro izomorf bo‘lmagan va qandaydir shartlarni qanoatlantiruvchi daraxtlar sonini aniqlash masalasi daraxtlarni o‘rganishda muhim masala hisoblanadi. yuqorida 4, 5 va 6ta uchlarga ega o‘zaro izomorf bo‘lmagan daraxtlar mos ravishda 2, 3 va 6ta ekanligi ta’kidlangan edi. a. keli …

Ko'proq o'qimoqchimisiz?

Barcha 6 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"daraxtlar" haqida

mavzu: daraxtlar graf. uch. qirra. daraxt. o‘rmon. asiklik graf. marshrut. sikl. zanjir. oddiy zanjir. ko‘prik. grafning sinch daraxti, sinch o‘rmoni, siklomatik soni. 1. daraxt va unga ekvivalent tushunchalar. siklga ega bo‘lmagan orientirlanmagan bog‘lamli graf daraxt deb ataladi[footnoteref:1]. ta’rifga ko‘ra daraxt sirtmoqlar va karrali qirralarga ega emas. siklga ega bo‘lmagan orientirlanmagan graf o‘rmon (asiklik graf) deb ataladi. [1: orientirlangan daraxt tushunchasi ham bor.] 1- misol. 1- shaklda bog‘lamli komponentali soni beshga teng bo‘lgan graf tasvirlangan bo‘lib, u o‘rmondir. bu grafdagi bog‘lamli komponentalarning har biri daraxtdir. ■1- shakl 2- misol. 2- shaklda to‘rtta uchga ega bir-biriga izomorf bo‘lmagan barcha (ular bor-yog‘i ikkita) daraxtlarning geometrik ifodalani...

Bu fayl DOCX formatida 6 sahifadan iborat (218,0 KB). "daraxtlar"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: daraxtlar DOCX 6 sahifa Bepul yuklash Telegram