|
20-mavzu. O„rmon. Daraxtlarning xossalari. Daraxtlar haqidagi teoremalar. Rеja
|
| bet | 6/7 | | Sana | 25.05.2024 | | Hajmi | 32,13 Kb. | | #253167 |
Bog'liq 20-mavzu. O„rmon. Daraxtlarning xossalari. Daraxtlar haqidagi te-fayllar.orgt e o r e m a (Keli). Uchlari soni m bo‘lgan belgilangan daraxtlar soni
mm2 ga teng.
Isboti talabaga havola qilinadi.
Yasovchi daraxtlar 16 tasi mavjud bo`lib quyida tasvirlangan.
Grafning siklomatik soni. Faraz qilaylik, G sirtmoqsiz va karrali qirralari bo'lmagan qandaydir bog'lamli graf bo'lsin. Bu grafdan uning biron sikliga tegishli bitta qirrasini olib tashlash natijasida hosil bo'lgan graf bog'lamli graf bo'lishi ravshandir.Grafdan uning biron sikliga tegishli bitta qirrasini olib tashlash amalini hosil bo'lgan graflarga, imkoni boricha, ketma-ket qo'llash natijasida G grafning barcha uchlarini bog'lovchi graf-daraxtni hosil qilish mumkin.Bunday daraxt G grafning sinch daraxti (sinchi, karkasi, qovurg'asi), deb ataladi.
Tabiiyki, bitta grafning bir necha sinch daraxtlari mavjud bo'lishi mumkin.
misol.3-shaklda tasvirlangan graf sinchlaridan birining qirralari berilgan grafning boshqa qirralariga qaraganda qlinroq chiziqlar vositasida ifodalangan.
Endi G sirtmoqsiz va karrali qirralari bo'lmagan mta uch, nta qirra va kta bog'lamli komponentalardan tashkil topgan graf bo'lsin.
4.3-shakl.
Agar yuqorida tavsiflangan usul yordamida G grafdan qirralarni ketma-ket olib tashlash amalini qo'llash natijasida uning har bir komponentasi big'lamliligi buzilmasa, u holda berilgan G grafning sinch o'rmoni deb ataluvchi grafni xosil qilishi mumkin.
Berilgan G grafdan uning sinch o'rmonini hosil qilish maqsadida olib tashlanishikerak bo'lgan qirralar soni ( ) bu qirralarni olib tashlash tartibiga bog'liq emasligi va bo'lishi ravshandir. Qaralayotgan G graf uchun tengsizlik o'rinli bo'lganligidan, ( ) bo'ladi.
( )sonniG grafning siklomatik soni (siklik rangi), deb ataymiz.
Grafning sikomatik soni tushunchasi, qandaydir ma'noda, grafning bog'lamlilik darajasini ifodalovchi vositadir.Ravshanki, daraxt uchun bo'ladi.
Grafning o'rmon bo'lishi uchun uning siklomtik soni nolga teng bo'lishi zarur va yetarlidir (2-natijaga qarang).
Grafning yagona siklga ega bo'lishi uchun uning siklomatik soni birga teng bo'lishi zarur va yetarli. Qirralari soni uchlari sonidan kichik bo'lmagan graf siklga egadir. Bu tasdiqlar ham1-teoremaning natijasidir.
misol. 3-shaklda tasvirlangan graf (6,9)-graf bo‟lib, uning bog‟lamlilik komponentalari soni birga teng. Bu grafning siklomatik sonini aniqlasak,
b‟ladi.Olib tashlangan qirralar 3-shaklda shtrix chiziqlar bilan ifodalangan.
|
| |
