|
Isboti. 1 - teorema isbotining 2) tasdiqdan 3) tasdiq kelib chiqishiga bag‘ishlangan qismiga qarang.
2- teorema
|
| bet | 4/5 | | Sana | 29.05.2023 | | Hajmi | 0.8 Mb. | | #66430 |
Bog'liq Karimova Gavhar diskret tuzilmalar tarmoqXavfszligi, Operatison Tizim(MI), Operatsion Tizim(MI), Firdavs(komp tarmoq), Fast Scan 18-09-2021 0710, OperatsionTizim(2)Isboti. 1 - teorema isbotining 2) tasdiqdan 3) tasdiq kelib chiqishiga bag‘ishlangan qismiga qarang.
2- teorema. Istalgan daraxtning markazi uning bitta uchidan yoki ikkita qo 'shni uchlaridan iborat bo 'ladi. Isboti. Agar daraxt bitta uch yoki ikkita qo'shni uch va ularni tuashtiruvchi qirradan tashkil topgan bo'lsa, teorema tasdig‘i to‘g‘riligi oydindir.
G daraxt tarkibida ikkitadan ko‘p uch bor deb faraz qilamiz. G 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 G daraxtdan olib tashlaymiz. Natijada uchlari va qirralari soni berilgan G daraxtdagi uchlar va qirralar sonidan kam bo'lgan qandaydir G' daraxtni hosil qilamiz. G ’ daraxtdagi har bir uch ekssentrisiteti G daraxtdagi mos uch ekssentrisitetidan bitta kam bo'lishi va bu daraxtlaming 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 turashtiruvchi 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 6 ta uchlarga ega o'zaro izomorf bo'lmagan daraxtlar mos ravishda 2, 3 va 6 ta ekanligi ta’kidlangan edi. A. Keli uglerod atomlari soni berilgan va CnH2n+2 tenglik o'rinlidir.
Daraxtning ta’rifiga ko'ra, u ko‘rinishdagi kimyoviy formula bilan ifodalanuvchi to'yingan uglevodorodlar sonini topish masalasini har bir uchining darajasi bir yoki to‘rt bo‘lgan daraxtlar sonini topish masalasiga keltirib hal qilgan. Quyidagi teorema Keli nomi bilan yuritiladi.
3- t e o r e m a (Keli). Uchlari soni m bo 'Igan belgilangan daraxtlar soni m^(m- 2)ga teng.
Grafning siklomatik soni.
Faraz qilaylik, G sirtmoqsiz va karrali qirralari bo‘lmagan qandaydir bog‘lamli graf bo‘lsin. Bu gfafdan uning biror sikliga tegishli bitta qirrasini olib tashlash natijasida hosil bo'lgan graf bog‘lamli graf bo‘lishi ravshandir. Grafdan uning biror 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, qobirg‘asi) deb ataladi. Tabiiyki, bitta grafning bir necha sinch daraxtlari mavjud bo‘lishi mumkin.
|
| |
