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


Bu esa, k > 1 bo'lgani uchun, n = m -1 tenglikka ziddir. Zarur tasdiq isbotlandi. Teorernaning 3) tasdig'idan uning 4) tasdig'i kelib chiqishini isbotlayrniz



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

Bu esa, k > 1 bo'lgani uchun, n = m -1 tenglikka ziddir. Zarur tasdiq isbotlandi. Teorernaning 3) tasdig'idan uning 4) tasdig'i kelib chiqishini isbotlayrniz.
G - bog'larnli graf va n = m -1 bo'isin. Avvalo k ta bog'larnlilik komponentlariga ega karrali qirralari bo'lrnagan sirtrnoqsiz (m,n) -graf uchun
k (m -k)(m -k + 1) m - ~ n ~ -'----'-"'----- 2
rnunosabat o'rinli bo'lishini eslatarniz (ushbu bobning 4- paragrafidagi 7- teoremaga qarang). n = m -] bo'lgani sababli G bog'lamli grafdan istalgan qirra olib tashlansa, natijada m ta uch va (m - 2) ta qirralari bo'lgan graf hosil bo'ladiki, bunday graf m - k ~ n shartga binoan bog'lamli bo'la olrnaydi. Kerakli tasdiq isbotlandi.
Daraxtlar haqidagi asosiy teoremaning 4) tasdig'idan uning 5) tasdig'i kelib chiqishini isbotlayrniz. G bog'larnli 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 rnurnkinligini ko'rsatamiz. G bog'lamli graf bo'igani 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 zanjirlaming birortasi bo'ylab harakatlanib ikkinchi uchga, keyin bu uchdan ikkinchi zanjir bo'ylab harakatlanib dastlabki uchga qaytish imkoniyati bor bo'lar edi. Ya'ni qaralayotgan grafda sikl topilar edi. Tabiiyki, tarkibida sikl mavjud bo'lgan grafning siklga tegishli istalgan bitta qirrasini olib tashlash uning bog'lamliligi xossasini o'zgartirmaydi, ya'ni bu holda grafning siklga tegishli istalgan qirrasi ko'prik bo'lmaydi. Bu esa qilingan farazga ziddir.
Teoremaning 4) tasdig'idan uning 5) tasdig'i kelib chiqishi isbotlandi. Endi teoremaning 5) tasdig'idan uning 6) tasdig'j kelib chiqishmi ko'rsatamiz.
Berilgan G grafning o'zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutashtirilishi mum kin bo'lsin. Teskarisini, yaini G graf asiklik emas deb faraz qilamiz. Bu holda, G da sikl topiladi va undagi ixtiyoriy siklga tegishli istalgan turli ikkita uchni kamida ikkita oddiy zanjir vositasida tutashtirish imkoniyati bor. Bu esa G grafning o'zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutashtirilishi shartiga ziddir. G grafninng qo'shni bo'lmagan VI va v~ uchlarini qirra bilan tutashtirish amalini qo'l1ash natijasida faqat bitta siklga ega bo'lgan graf hosil bo'lishini ko'rsatamiz. Shartga binoan qaralayotgan VI va v2 uchlami faqat bitta oddiy zanjir bilan tutahtirish mumkin. Oddiy zanjir ta'rifiga ko'ra esa bu zanjir tarkibida sikl yo'q.
Shuning uchun VI va v2 uchlami G grafning tarkibida bo'lmagan (VI' v2 ) 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 bajarilsa, G grafning daraxt bo'lishini, ya'ni teoremaning I) tasdig'i kelib chiqishini isbotlaymiz. Faraz qilaylik, asiklik G graf bog'lamli bo'lmasin. U holda, bu grafning ixtiyoriy bog'lamli komponentidagi ixtiyoriy uchni uning boshqa bog'lamli komponentidagi ixtiyoriy uch bilan qirra vositasida tutashtirish amalini qo'l1ash natijasida tarkibida sikl bo'lgan graf hosil bo'imaydi. Bu esa 6) tasdiqning ikkinchi qismiga ziddir.

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