Mustaqil ish 7 Topshirdi: absamatov j

1-teorema. Uchlari soni m va qirralari soni n bo 'Igan G graf uchun quyidagi tasdiqlar ekvivalentdir: G daraxtdir; G asiklikdir va n=m—l; G bog'lamlidir va n=m—\; Induksion o'tish: G daraxt uchun k>2 vam=k bo'lganda, 2) tasdiq o'rinli bo'lsin deb faraz qilamiz. Endi uchlari soni m=k+l va qirralari soni n bo'lgan daraxtni qaraymiz. Bu daraxtning ixtiyoriy qirrasini (vp v2) bilan belgilab, undan bu qirrani olib tashlasak, Vj uchdan v2 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 G daraxtda sikl topilar edi. Bunday bo'lishi esa mumkin emas. Hosil bo'lgan graf ikkita Gl va G2 bog'lamli komponentalardan iborat bo'lib, bu komponentalarning har biri daraxtdir. Yana shuni ham e'tiborga olish kerakki, Gl va G2 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 Gxgraf (m, «)-graf bo'lsa, quyidagi tengliklar o'rinlidir: n=nx+n2+\, k+l=ml+m2 va. n=m — \ (/=1,2). Bu tengliklardan n=nl+n2+l=m]— l+m2—1+1= (mx+m2)—l= (k+l)—lEndi daraxtlar haqidagi asosiy teoremaning 2) tasdig'idan uning 3) tasdig'i kelib chiqishini isbotlaymiz. G graf asiklik, ya'ni u siklga ega bo'lmagan graf van=m— 1 bo'lsin. G grafning bog'lamli bo'lishini isbotlash kerak.

Agar G graf bog'lamli bo'lmasa, u holda uni har bir bog'lamli komponentasi siklsiz graf G. (ya'ni daraxt) bo'lgan qandaydir k ta (k>l) graflar dizyunktiv birlashmasi sifatida ^=U^ tenglik bilan ifodalash mumkin. Har bir i=l,kuchun G.tgraf daraxt bo'lgani uchun, yuqorida isbotlangan tasdiqqa ko'ra, agar unda mj ta uch va «.ta qirra bo'lsa, u holda G. asiklikdir va n=m—1 tenglik Agar qandaydir ikki uch bittadan ko'p, masalan, ikkita turli oddiy zanjir vositasida tutashtirilishi imkoniyati bo'lsa, u holda bu uchlarning biridan zanjirlarning birontasi bo'ylab harakatlanib ikkinchi uchga, keyin bu uchdan ikkinchi zanjir bo'ylab harakatlanib dastlabki uchga qaytish imkoniyati bor bo'lar edi. Ya'ni qaralayotgan graf da sikl topilar edi. Minimal uzunlikka ega yo‘l haqidagi masala. Berilgan bog'lamli grafning har bir qirrasiga (agar berilgan graf oriyentirlangan bo‘lsa — yoyiga) qandaydir haqiqiy son mos qo‘yib, bu sonni qirraning (yoyning) uzunligi, deb ataymiz. Qirraning (yoyning) uzunligi additivlik xossasiga ega deb faraz qilamiz, ya’ni qirralar (yoylar) yordamida tuzilgan zanjiming (yo ‘Ining) uzunligi shu zanjirni (yo‘lni) tashkil etuvchi qirralar (yoylar) uzunliklari yig‘indisiga tengdir. Tabiiyki, qirraning yoki yoyning uzunligi tushunchasi yechilayotgan masalaning mohiyatiga qarab, muayyan bir ma’noga ega bo‘lishi mumkin. Masalan, ikki shahar orasidagi masofa, qandaydir operatsiyani bajarish uchun zarar mablag‘ (xarajatlar) yoki vaqt va boshqalar. Shu nuqtayi nazardan, umuman olganda, bu yerda manfiy uzunlikka ega yoki uzunligi nolga teng qirra (yoy) ham ma’noga ega deb hisoblanadi. Amaliyotda uchraydigan ko‘plab masalalarda marshrut uzunligi maksimallashtirilishi yoki minimallashtirilishi talab etiladi.