Kompyuter ilmlari va dasturlashtirish kafedrasi algoritmlar va berilganlar strukturalari


- teorema. Agar grafdagi har bir uchning lokal darajasi ikkidan kichik bo‘lmasa, u holda bu graf siklga ega. Isboti



Yüklə 1,96 Mb.
səhifə14/47
tarix28.11.2023
ölçüsü1,96 Mb.
#136696
1   ...   10   11   12   13   14   15   16   17   ...   47
Algoritmlar va berilganlar strukturasi(ATTs2)

1- teorema. Agar grafdagi har bir uchning lokal darajasi ikkidan kichik bo‘lmasa, u holda bu graf siklga ega.
Isboti. Agar grafda sirtmoqlar yoki karrali qirralar bo‘lsa, teoremaning tasdig‘i to‘g‘riligi ravshandir. Shuning uchun teorema tasdig‘ini graf sirtmoqsiz va karrali qirralari bo‘lmagan holda isbotlaymiz.
Faraz qilaylik, berilgan sirtmoqsiz va karrali qirralari bo‘lmagan grafning ixtiyoriy uchi bo‘lsin. Qaralayotgan uchga qo‘shni uchni va bu uchga dan farqli boshqa qo‘shni uchni, uchga esa dan farqli boshqa qo‘shni uchni, va hakoza, uchga dan farqli boshqa qo‘shni uchni, va hakoza, tanlab,

qirralar ketma-ketligini tuzamiz. Teoremaning shartlariga ko‘ra yuqoridagi jarayonni amalga oshirish va talab etilgan xossaga ega uchni topish mumkinligini ta’kidlaymiz.
Grafning uchlari to‘plami chekli to‘plam bo‘lganligidan, yuqorida bayon etilgan uchlar ketma-ketligini qurish jarayonida chekli qadamdan so‘ng albatta oldin uchragan uchlardan birini tanlashga majbur bo‘lamiz. Agar uch ketma-ketlikda ikki marta uchragan dastlabki uch bo‘lsa, ketma-ketlikka qirralar qo‘shish jarayonini to‘xtatamiz, chunki tuzilgan qirralar ketma-ketligining uch ikki marta qatnashgan qismi biz izlayotgan sikldir. ■
Grafning bog‘lamliligi tushunchasi. Agar oriyentirlanmagan grafda chetlari va uchlardan iborat marshrut topilsa, bu va uchlar bog‘langan deb, marshrutning o‘zi esa va uchlarni bog‘lovchi marshrut debataladi.
Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf bog‘lamli graf deb ataladi.
Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo‘lsa, u holda bu ikkita uch ekvivalent (bog‘langan) deyiladi. Bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentalari (qisqacha, komponentalari) deb ataluvchi bog‘lamli qismlarning birlashmasi deb qarash mumkin. Bu yerda berilgan graf bog‘lamlilik komponentalariga bo‘laklandi (ajratildi) deb aytish mumkin. Isbotlash mumkinki, har qanday graf o‘zining bog‘lamlilik komponentalarining diz’yunktiv birlashmasi sifatida ifodalanishi mumkin, bunda grafning bog‘lamlilik komponentalariga bo‘laklanishi bir qiymatli aniqlanadi.

Yüklə 1,96 Mb.

Dostları ilə paylaş:
1   ...   10   11   12   13   14   15   16   17   ...   47




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə