|
Daraxtning bunday tasvirlanishidan kelib chiqadiki, u chetki (faqat bitta qirraga intsident bo’lgan) uchlarga ega
|
| bet | 2/4 | | Sana | 24.05.2024 | | Hajmi | 3,11 Mb. | | #251746 |
Bog'liq M20 O‘rmon Daraxtning bunday tasvirlanishidan kelib chiqadiki, u chetki (faqat bitta qirraga intsident bo’lgan) uchlarga ega. Daraxtning bunday tasvirlanishidan kelib chiqadiki, u chetki (faqat bitta qirraga intsident bo’lgan) uchlarga ega. Masalan, oxirgi pog’onaning uchlari. Bog’likli G grafdan ketma-ket barcha tsiklik qirralarni olib tashlaymiz. Natijada, hamma qirralari atsiklik bo’lgan bog’likli H grafni-daraxtni hosil qilamiz. Bu daraxt G grafning asosi deyiladi. Grafning asosi yagona tanlanmaydi, lekin barcha atsiklik qirralar istalgan asosga kiradi. H asosga nisbatan G \ H bo’lakning barcha qirralari - vatarlar deb ataladi. H daraxtdan chetki uchni (avtomatik tarzda bitta qirrani) olib tashlasak, H daraxtdan chetki uchni (avtomatik tarzda bitta qirrani) olib tashlasak, yana daraxtni hosil qilamiz. Agar H chekli bo’lsa, n(H) - 2 qadamlardan keyin bitta qirra va ikkita uchga ega daraxtni hosil qilamiz. Daraxtdan olib tashlangan uchlar va qirralar soni bir xil bo’lganligi sababli quyidagi xulosaga kelamiz: har qanday chekli daraxtda qirralar soni uchlar sonidan bitta kam. Aksinchasi ham o’rinlidir, ya’ni Teorema. Chekli bog’likli G graf daraxt bo’lishi uchun, uning qirralari Teorema. Chekli bog’likli G graf daraxt bo’lishi uchun, uning qirralari soni uchlari sonidan bittaga kam bo’lishi zarur va yetarli. Uchlari 1,2,3,..., n raqamlar bilan tartiblangan n uchli daraxt berilgan bo’lsin. Uchlari 1,2,3,..., n raqamlar bilan tartiblangan n uchli daraxt berilgan bo’lsin. Daraxtning chetki uchlari orasidagi eng kichik nomerlisi va u bilan qo’shni bo’lgan yagona uch bo’lsin. Daraxtdan uchni, demak qirrani olib tashlaymiz. Hosil bo’lgan daraxtda eng kichik nomerli chetki uchni va qirrani olib tashlaymiz va hokazo. Bu protsessni n-2 marta takrorlab ikki uch va bitta qirrali daraxtni hosil qilamiz. Olib tashlangan uchlarni
|
| |
