mi ta uch va
ni ta qirra bo„lsa, u holda Gi
asiklikdir va
ni mi 1 tenglik
o„rinlidir. Tushunarliki,
т тi
i 1
va n ni . Demak,
i1
k k k
n ni (mi 1) mi k m k ,
i 1
i 1
i 1
ortiqdir. Bu esa, isbotlandi.
k 1
bo„lgani uchun,
n m 1
tenglikka ziddir. Zarur tasdiq
Teoremaning 3) tasdig„idan uning 4) tasdig„i kelib chiqishini isbotlaymiz. G
– bog„lamli graf va n m 1 bo„lsin. Avvalo k ta bog„lamlilik komponentalariga
ega karrali qirralari bo„lmagan sirtmoqsiz ( m, n) -graf uchun
m k n ( m k )( m k 1)
2
munosabat o„rinli bo„lishini eslatamiz (ushbu bobning 4- paragrafidagi 7- teoremaga qarang).
n m 1 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 olmaydi. Kerakli tasdiq isbotlandi.
Daraxtlar haqidagi asosiy teoremaning 4) tasdig„idan uning 5) tasdig„i kelib chiqishini isbotlaymiz. G 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. G 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 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„i kelib chiqishini ko„rsatamiz. Berilgan G grafninng o„zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutashtirilishi mumkin 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 grafninng o„zaro ustma-ust tushmaydigan istalgan ikkita uchi faqat bitta oddiy zanjir bilan tutashtirilishi shartiga ziddir.
G grafninng qo„shni bo„lmagan
v1 va v2
uchlarini qirra bilan tutashtirish
amalini qo„llash natijasida faqat bitta siklga ega bo„lgan graf hosil bo„lishini
bilan tutahtirish mumkin. Oddiy zanjir ta‟rifiga ko„ra esa bu zanjir tarkibida sikl
yo„q. Shuning uchun
v1 va v2
uchlarni G grafninng tarkibida bo„lmagan
(v1, 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 baja-rilsa, G grafning daraxt bo„lishini, ya‟ni teoremaning 1) tasdig„i kelib chiqishini isbotlaymiz. Faraz qilaylik, asiklik G 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 ziddir.
| 