iteratsiya - 15-mavzu. O’rmon. Daraxtlarning xossalari. Ostov daraxti

iteratsiya.
R {1, 2, 3, 5} ,
R {4, 6}
bo‘lgani uchun
(R, R ) {(1, 4), (3, 4), (3, 6), (5, 6)} va
h14 13 ,
h34 13 ,
h36 17 ,
h56 18
hamda
min{ h14 , h34 , h36 , h56} h14 h34 13
bo‘ladi. Demak,
(1, 4)
va (3, 4)
yoylarni ajratamiz
hamda 4 belgili uchga
4 13
qiymatni mos qo‘yamiz. Natijada
R {1, 2, 3, 5, 4} ,
R {6} to‘plamlarga ega bo‘lamiz.
i cij j
munosabatning to‘g‘riligi
(1, 3) ,
(1, 4) ,
(2, 3) ,
(3, 5) ,
(5, 3)
va (3, 4)
yoylar uchun tekshirilib ko‘rilganda, uning barcha yoylar uchun bajarilishi ma’lum
bo‘ladi.
iteratsiya. Endi
( R, R ) {(3, 6), (4, 6), (5, 6)}
bo‘lgani uchun
h36 17 , h46 14 ,
h56 18 va
min{ h36, h46 , h56} h46 14
bo‘ladi. Bu yerda minimum
(4, 6)
yoyda
erishilgani uchun uni ajratib, orgrafning oxirgi 6 belgili uchiga mos qo‘yamiz.
6 14
qiymatni
Oxirgi qadam. Berilgan orgrafda 1 belgili uchdan 6 belgili uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topish maqsadida, algoritmga asosan, grafning oxirgi 6 belgili uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda harakatlanib, uning 1 belgili uchiga kelishimiz kerak. 6 belgili uchga kiruvchi uchta
yoydan faqat bittasi ( (4, 6)
yoy) ajratilgan bo‘lgani uchun
(4, 6)
yoy yo‘nalishiga
qarama-qarshi yo‘nalishda harakat qilib, 6 belgili uchdan 4 belgili uchga kelamiz.
4 belgili uchga kiruvchi ikkala ( (1, 4) va (3, 4) ) yoylar ham ajratilgan bo‘lgani uchun
biz tuzmoqchi bo‘lgan eng qisqa uzunlikka ega yo‘l yagona emas.
Agar harakatni
(1, 4)
yoy yo‘nalishiga teskari yo‘nalishda davom ettirsak, u
holda 4 belgili uchdan 1 belgili uchga kelib, eng qisqa uzunlikka ega yo‘llardan biri
bo‘lgan
1 (1, 4, 6)
marshrutni topamiz.
Agarda harakatni
(3, 4)
yoy yo‘nalishiga teskari yo‘nalishda davom ettirsak,
u holda 4 belgili uchdan 3 belgili uchga kelamiz. 3 belgili uchga kiruvchi ikkita
yoydan faqat bittasi ( (5, 3) yoy) ajratilgan bo‘lgani uchun 3 belgili uchdan 5 belgili
uchga kelamiz. Shu usulda davom etsak, oldin 2 belgili, keyin esa 1 belgili uchga
o‘tib mumkin bo‘lgan eng qisqa uzunlikka ega bo‘lgan yo‘llardan ikkinchisini, ya’ni
2 (1, 2, 5, 3, 4, 6)
marshrutni aniqlaymiz.
Shunday qilib, 2- shaklda tasvirlangan grafda eng qisqa uzunlikka ega
1 va
2 yo‘llar borligini aniqladik. Bu yo‘llarning har biri minimal 6 14
uzunlikka ega.
Muammoli topshiriq va masalalar
Bir-biriga izomorf bo‘lmagan
oltita, b) yettita, d) sakkizta, e) to‘qqizta uchga ega barcha daraxtlarni geometrik ifodalang.
1- shaklda tasvirlangan o‘rmondagi daraxtlarning har biri uchun markaz(lar) bo‘luvchi uchlarni toping.
Keli teoremasining isbotini o‘rganing (masalan, [10] kitobga qarang).
Uchlari uchta va to‘rtta bo‘lgan barcha belgilangan daraxtlarni geometrik ifodalang.
Petersen grafining sinch daraxtlaridan birini aniqlang.
6. K4,5
grafning sinch daraxtlaridan bir nechasini toping.
12ta uchi, 10ta qirrasi va 3ta bog‘lamli komponentasi bo‘lgan, sirtmoqsiz, karrali qirralari bo‘lmagan grafning sinch o‘rmonini hosil qilish uchun uning nechta qirrasini olib tashlash kerakligini aniqlang.
1
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
1
|
0
|
Insidentlik matrisalari quyida berilgan graflarning siklomatik sonlarini toping:
1
|
0
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
1
0
1
0
0
0
, b)
.
0
1
0
0
1 0
0 0
Uchlari qo‘shniligi matrisalari quyida berilgan graflarning sinch daraxtlaridan bir nechasini toping:
0 1
1 1
0 1 1 1 0
1 0 0 1 1
1
1
0
1 0
1
1
0 1
0
1
0 1
1 1 1 0 1
0
0
1
1 1
Muammoli masala va topshiriqlar
3-shaklda ko`rsatilgan ikkita grafning izomorfligini isbotlang.
3-shakl
Bir-biri bilan arazlagan uchta xamsoyaning uchta umumiy quduqlari bor. Har bir uydan xar bir quduqqa bir-biri bilan kеsishmaydigan yo`l o`tkazish mumkinmi? Javobingizni izoxlang.
Bеshta to`g`ri ko`pqirrali graflar uchlarining soni va darajasini aniqlang.
To`g`ri ko`pqirrali graflar uchun qo`shnilik va intsidеntlik matritsalarini tuzing.
|