DIRAK VA ORE TEOREMALARI ASOSIDA GAMILTON SIKLINI TOPISH ALGORITMI

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

352.8076171875 KB

Ko'chirib olish

“DIRAK VA ORE TEOREMALARI ASOSIDA GAMILTON SIKLINI
TOPISH ALGORITMI”
Mundarija
.......................................................................................................................................................................... 1
Foydalanilgan adabiyolar ................................................................................................................................ 24

Kirish
Bu kurs ishida “Derak va Ore teoremasining Gamilton siklining ifodalanishi”
mavzusini yoritib berar ekanmiz nazariy qisimda Gamilton siklining ifodalanishi,
Derak va Ore teoremalari mavzulariga to’xtalib o’tamiz. Amaliy qisimda esa
Gamolron sikliga oid misollar, Derak va ore teoremalarining Gamilron seklida
ifodalanishi kabi mavzularda misollar ishlaymiz.
Xulosa qismini hamma ishlarni bajarib bo’lgandan so’ngra yozamiz.

I.BOB.NAZARIY QISM
1.1.Gamilton siklining ifodalanishi.
Gamilton sikli bu algoritm va ma’lumotlar strukturasida keng qullaniladigan
tushunchalardan biridir.
Ta'rif . Agar graf bir marta grafning barcha uchlarini o'z ichiga olgan oddiy siklga
ega bo'lsa, unda bunday sikl Gamilton sikli, graf esa Gamilton grafi deb ataladi. Agar
grafda bir marta grafning barcha uchlarini o'z ichiga olgan oddiy zanjir bo'lsa, bunday
zanjir Gamilton zanjiri, graf esa yarim Gamilton grafigi deb ataladi. Grafning
Gamilton bo‘lishi uchun quyidagi teorema zarur va yetarlidir . Hali zarur sharoitlar
topilmagan.Dirak teoremasi. Agar p ≥ 3 uchlari ∀ v ∈ V d (v) ≥ p / 2 bo'lgan G (V, E)
grafigida G grafigi Gamilton bo'ladi.
Isbot. V = {v1, bo'lsin. ... ... , vp}. Avval e'tibor bering, har qanday grafik unga p
qo'shimcha 2-darajali burchaklarni qo'shish orqali Gamiltonga aylantirilishi mumkin:
bu yerda i = 1,. ... ... , p - 1, qirralari (vi, ui) va (ui, vi + 1) qo'shiladi, qirralarga (vp,
yuqoriga) va (yuqoriga, v1) qo'shiladi. Keyin Gamilton sikli quyidagi ko'rinishga ega
bo'ladi.
v
1 u
1 v
2 u
2 . . . v
p u
p v
1 .
Dastlabki grafikda qo'shimcha u
1 cho'qqisi bo'lmagan holda Gamilton siklini
qurish mumkinligini ko'rsatamiz. Uchta holat bo'lishi mumkin:
1)
v
1 va v
2 cho'qqilari qo'shni, keyin
v
1 va v
2 sikl kesimini v1v2bilan almashtirish
mumkin;
2) )
v
1 va v
2 uchlari qo‘shni emas, lekin vj, vj + 1 juft uchlari borki, vj qo‘shni
bo‘ladi.
v1 va vj + 1 bilan v2 ga ulashgan. Keyin siklning segmenti v2u2 bo'ladi. ... ... vj
kengaytirilishi mumkin, qo'shimcha u1 va uj uchlarini chiqarib tashlang va siklni
oling.
v
1 v
j u
j−1 v
j−1 . . . u
2 v
2 v
j+1 u
j+1 . . . v
p u
p v
1 ;
3) v1 va v2 cho'qqilari qo'shni emas va v1 ga qo'shni bo'lgan har qanday vj cho'qqi
uchun vj + 1 uchi v2 ga qo'shni emas. Keyin v1 (yoki d (v1)) ga ulashgan cho'qqilar

soni v2 ga qo'shni bo'lmagan cho'qqilar sonidan oshmaydi (yoki p - d (v2) - 1 - v2 ga
qo'shni barcha cho'qqilar umumiy cho'qqilar sonidan olib tashlanadi).
d(v
1 ) ≤ p − d(v
2 ) − 1.
Teorema gipotezasi bo'yicha ∀ v ∈ V: d (v) ≥ p / 2 ekanligini hisobga olsak.
p = p/2 + p/2 ≤ d(v
1 ) + d(v
2 ) ≤ p − 1.
Demak, Gamilton siklini qo'shimcha u1 cho'qqisidan foydalanmasdan qurish
mumkin. Barcha qo'shimcha cho'qqilar uchun shunga o'xshash mulohaza yuritib,
dastlabki graf da Buning aksi to‘g‘ri emas, ya’ni Gamilton siklining mavjudligi uchun
teorema shart emas.Gamilton siklini olamiz.Teorema isbotlangan.
Gamilton siklini olish uchun, ya'ni polinom vaqtini talab qiluvchi hisoblash samarali
algoritmlari mavjud emas.
Roberts va Flores qo'pol kuchlar algoritmi ("chuqur" o'tish strategiyasiga asoslangan)
1-qadam. Barcha uchlari v qo'shnilik ro'yxati L (v) uchun kompilyatsiya qiling. X1
boshlang'ich uchini tanlang, i = 1 ni o'rnating.
2-qadam . Agar i = p va {xp, x1} ∈ E bo'lsa, x1x2. ... ... xpx1 - Gamilton sikli, oxiri.
Agar i = 0 bo'lsa, u holda Gamilton sikli yo'q.
3-qadam . x1, x2. ... ... xi - 1, L qo'shni ro'yxatidan (xi - 1). Agar bunday cho'qqi
bo'lmasa, biz i = i - 1 ni o'rnatamiz (bir qadam orqaga qayting) va 3-bosqichni
takrorlang. Aks holda, 2-bosqichga o'ting.
1.2.Derak va Ore teoremsi.
Graflar nazariyasining Ore teoremasi 1960 yilda norvegiyalik matematik Oistin
Ore tomonidan isbotlangan. Teorema graflarning Gamilton bo'lishi uchun yetarli
shartni qanoatlantirishi kerak "yetarlicha ko'p qirralar" bo'lgan graf Gamilton siklini
o'z ichiga olishi kerakligini tasdiqlaydi. Xususan, teorema qo'shni bo'lmagan
cho'qqilar juftliklari darajalarining yig'indilarini ko'rib chiqadi - agar yig'indidagi har
bir bunday juftlik hech bo'lmaganda grafikning uchlari umumiy sonini bersa, grafi
Gamiltondir.

G n ≥ 3 cho‘qqi bo‘lsin. G dagi v cho'qqi darajasini, ya'ni v ga to'g'ri keladigan
qirralarning sonini v bilan belgilaymiz.
Bu bayonot har qanday Gamilto bo'lmagan G grafi(*) shartini buzganiga tengdir. G n
≥ 3 ta burchakli Gamilton bo‘lmagan graf bo‘lsin. H grafigi G dan Gamilton siklini
hosil qilmaydigan bir vaqtning o'zida bir chetini qo'shish orqali hosil bo'lsin, chunki
bunday qirralarni qo'shish mumkin. H grafigining ixtiyoriy ikkita qo shni bo lmagan ʻ ʻ
x va y cho qqilarini ko rib chiqaylik. H ga xy chekka qo shilganda kamida bitta
ʻ ʻ ʻ
Gamilton sikli hosil bo ladi va bu sikldagi xy dan boshqa qirralar x bilan H da
ʻ
Gamilton yo li v1v2 ... vn hosil qilishi kerak. y= v1 va y = vn. 2 ≤ i ≤ n oralig'idagi
ʻ
har bir i indeksi uchun H v1 ning vi va vi - 1 vn dan ikkita mumkin bo'lgan qirralarini
ko'rib chiqing. Bu qirralarning ko'pi Hda bo'lishi mumkin, chunki aks holda v1v2 ...
vi - 1vnvn - 1 ... vi sikl Gamilton bo'ladi. Shunday qilib, v1 yoki vn ga tushgan
qirralarning umumiy soni n - 1 ga teng bo'ishi mumkin. Shuning uchun H (*) shartni
qanoatlantirmaydi, bu esa qirralarning umumiy sonini v1 + deg vn) n dan katta yoki
teng. G cho'qqilarining darajalari H dagi darajadan oshmaganligi sababli, G ham
talabni qondirmaydi.

II. BOB. AMALIY QISIM.
2.1. Gamilton sekliga oid misollar.
Sayohatchi sotuvchi muammosi.
Quyidagi muammoni ko'rib chiqing. P va A shaharlar mavjud, ularning
orasidagi masofalar ma'lum. Sayohatchi sotuvchi barcha shaharlarga bir marta tashrif
buyurishi va yana biriga qaytishi kerak.
Umumiy bosib o'tgan masofa minimal bo'lishi uchun marshrutni topish talab
qilinadi. Shubhasiz, muammo to'liq grafikdagi eng qisqa Gamilton siklini topishga
to'g'ri keladi. Keling, ushbu muammoni hal qilish usullarini ko'rib chiqaylik.
1. To'liq qidiruv algoritmi. Sotuvchi har doim bir shaharni tark etadi deb faraz
qilsak, p -1 hosil qiling! qolgan cho'qqilarning almashtirishlari va har bir
almashtirish uchun yo'l uzunligini hisoblang, so'ngra ularning minimalini
tanlang.
2. Sanoqni qisqartirish usullari. Ko'pgina hollarda, ro'yxatga olishni qisqartirish
usullari to'liq qidiruv algoritmiga qaraganda kamroq vaqt ichida yechim topadi.
Biroq, har kim uchun ikkilik Qidiruv bekor qilinmaganda bunday usulning
misoli mavjud, ya'ni oxirgi holatda siz to'liq qidiruvni amalga oshirishingiz
kerak.
3. Taxminiy usullar. Bu usullar taxminiy yechimni topadi, ya'ni bu holda,
Gamilton siklini, eng qisqa vaqt ichida. Taxminan usullar bir-biridan topilgan
yechimning murakkabligi va sifati bilan farqlanadi.
4. Sayohatchi sotuvchi muammosini hal qilishning tarmoqli va bog'langan usuli.
5.Tarmoqli va bog'langan usul g'oyasining mohiyati quyidagicha. Barcha sanab
o'tilgan variantlar sinflarga bo'lingan. Har bir sinf uchun ushbu sinfning barcha
yechimlarining pastki chegarasi topiladi. Agar ball oldingi topilgan yechim
qiymatidan oshsa, barcha sinf variantlari o'chiriladi.
Yechimning dastlabki bahosi sifatida tasodifiy Gamilton siklining narxini olish
yoki har qanday evristik usul bilan yechim topish mumkin.

E'tibor bering, agar siz 1-qatorning elementlaridan bir xil raqamni ayirsangiz,
har qanday sayohatchi sotuvchining yo'lining narxi bu raqamga kamayadi, chunki i-
qatorning elementlarini i-chi qatorga kirish narxi sifatida talqin qilish mumkin.
boshqa shaharlardan shahar va har qanday shaharda sayohatchi sotuvchi aynan bir
marta kiradi. Xuddi shunday mulohazalarni ustun uchun ham amalga oshirish
mumkin: ustun elementlaridan bir xil raqamni ayirish sayohatchi sotuvchining yo'li
narxining ushbu raqamga pasayishiga olib keladi, chunki i-ustunning elementlari
sifatida talqin qilinishi mumkin. 1-shahardan boshqa shaharlarga ko'chib o'tish narxi
va sotuvchi istalgan shaharni aynan bir marta tark etadi.
Shunday qilib, agar biz har bir satrning barcha elementlaridan ushbu qatorning
minimal elementini va nima uchun har bir ustunning elementlaridan - ushbu
ustunning minimal elementini ayirsak va bu raqamlarning barchasini qo'shsak, biz
xarajatlarning pastroq bahosini olamiz. sayohatchi sotuvchining yo'li. Ushbu
operatsiya matritsani quyish deb ataladi. Matritsaning qisqarishi natijasida unda nol
elementlar paydo bo'ladi. Biz yo'lda aynan shunday elementlarning kiritilishi optimal
echimga olib keladi deb o'ylaymiz.
Har bir masala, dastlabkisidan boshlab, ikkita kichik muammoga bo'linadi: nol
og'irlikdagi ba'zi bir yoyni o'z ichiga olgan variantlar va bu yoyni o'z ichiga olmaydi.
Birinchi holda, sayohatchi sotuvchi i shaharni tark etib, j shahriga kirganligi sababli, i
qator va j ustuni. matritsadan olib tashlanishi mumkin, bu esa muammoning
o'lchamini kamaytiradi. Shundan so'ng, matritsani yana qisqartirish mumkin. Ikkinchi
holda, i shahardan shaharga sayohat qilgandan beri j taqiqlangan, matritsaning
elementi (i, j) cheksizlikka teng deb hisoblanadi. Olingan matritsaga siz yana
qisqartirish amalini qo'llashingiz mumkin, lekin uni faqat i qator va j ustun uchun
bajarish mantiqan.
Olingan vazifalar yana ikkita kichik vazifaga bo'linadi va hokazo.Har qanday
sinf variantlarining past bahosi hozirgi vaqtda topilgan eng yaxshi yechimning
narxidan oshib ketishi bilan bu variantlarning barchasi bekor qilinadi.
Natijada, biz joriy optimal yechimga, ya'ni yangi optimal yechimga qaraganda
o'zgaruvchan xarajatlarning Gamilton siklini olamiz. Algoritm barcha variantlar
bekor qilinganda yoki Gamilton sikliga keltirilsa tugaydi.
Tarmoq va chegara algoritmi.

1-qadam. Biz ixtiyoriy Gamilton siklini µ ∗ quramiz. Uning og'irligi optimal yechim
narxining yuqori bahosi C. Biz siklni va uning og'irligini yodlaymiz. Biz og'irliklar
matritsasini taqdim etamiz W. Pastki chegara C (W) satr va ustunlardagi minimal
elementlarning yig'indisiga teng ravishda o'rnatiladi. Vazifalar ro'yxati bitta vazifadan
iborat - og'irliklarning qisqartirilgan matritsasi.
2-adam . Vazifalar ro'yxati bo'sh bo'lsa, oxirigacha o'ting. Aks holda, ro'yxatdan M
vazn matritsasi ni tanlang.
3-qadam. Matritsaning har bir noli uchun biz uning indeksini topamiz - agar nol
xarajat yoyini {i, j} chiqarib tashlasak, to'lanishi kerak bo'lgan minimal narx:
δ (i, j) = min M(i, k) + min M(k, j).
k6=j k6=i
4-qadam. Maksimal indeks cheksizlikdan kichik bo'lgan {i, j} nol elementini tanlang.
Agar {i, j} yoyi sayohatchi sotuvchining marshrutida allaqachon kiritilgan yoylar
bilan siklni tashkil qilsa, biz M (i, j) = ∞ ni o'rnatamiz, i-qatordan ayiramiz, so'ngra j-
ustundan, minimal elementlar, ularning yig'indisini C (M) ga qo'shing va 3-bosqichga
o'ting.
5-qadam. Joriy masalani ikkita kichik masalaga ajratamiz: yoyni {i, j} sikldagi (M,0
matritsa) va qo'shilmagan (M,0,0 matritsasi) ga kiritamiz. Aks holda, biz M,0 bitta
kichik muammoni olamiz.
6-qadam. M,0 matritsasini tuzamiz: M dan i-qator va j-ustunni o'chiring, matritsani
bering. C (M) ga satr va ustunlarning minimal elementlari yig'indisini qo'shib, biz C
(M0) ni olamiz. Sayohatchi sotuvchining m (M) marshrutiga {i, j} yoyini qo'shing,
biz m (M0) marshrutini olamiz.
7-qadam. Agar M0 matritsasining o'lchami 2 × 2 va C (M0) <C bo'lsa, u holda
yagona yechim bo'lishi mumkin. Sayohatchi sotuvchining marshrutida biz asosiy
diagonalga mos keladigan yoylarni yoki yon diagonalga mos keladigan yoylarni o'z
ichiga olamiz, qaysi yoylar allaqachon marshrutga kiritilgan yoylar bilan Gamilton
siklini tashkil qilishiga qarab (M0). µ (M0) yoylarini sikl bo‘yicha
joylashtiramiz.Tanlangan elementlar yig‘indisini C (M) ga qo‘shing. Sayohatchi
sotuvchining keyingi marshruti mk (M0) olinadi; agar uning og'irligi C (M0) <C
bo'lsa, biz C = C (M0) va m ∗ = m (M0) ni qo'yamiz.

va C (W) ≥ C bo'lgan W bo'lgan barcha masalalarni ro'yxatdan olib tashlang. Agar
M0 matritsasining o'lchami 2 × 2 dan katta bo'lsa va C (M0) <C bo'lsa, M0
matritsasini muammolar ro'yxatiga qo'shing.
8-qadam . M00 matritsasini tuzamiz: biz M (i, j) = ∞ ni o'rnatamiz, i-qatordan
ayiramiz, so'ngra j-ustundan minimal elementlarni, ularning yig'indisini C (M) ga
qo'shamiz, biz C (M00) oling. Agar C (M00) <C bo'lsa, M00 matritsasini vazifalar
ro'yxatiga qo'shing. Biz 2-bosqichga o'tamiz.
Oxiri. Sayohatchi sotuvchining optimal marshruti m ∗ C qiymatiga ega bo'ladi.
Misol. Og'irlik matritsasi W bo'lgan G (V, E) grafigini ko'rib chiqaylik.
1-Rasm.
1-qadam. Biz abcdefa ixtiyoriy siklini
quramiz, uning og'irligi eritma sifatining
yuqori chegarasi hisoblanadi.
C=8+13+16+3
+13+2=55.
Har bir satrda minimal elementni tanlaymiz, uni o'ng tomonga yozamiz.
2-Rasm.
Har bir satrning elementlaridan mos keladigan minimal elementni ayiring. Har bir
ustunda minimal elementni tanlaymiz, uni pastga yozamiz.

3-Rasm.
Har bir ustunning elementlaridan mos keladigan minimal elementni ayiring.
Og'irliklarning qisqartirilgan matritsasini A bilan belgilaymiz.
4-Rasm.
Keling, barcha minimal elementlarni yig'ish orqali A uchun sifatining pastki
chegarasini hisoblaylik.
C (A)=3+1+2+3+2+2+0+0+1+2+0+0=16.
Vazifalar ro'yxatiga A matritsasini qo'shing. Sayohatchi sotuvchining marshruti
m (A) = ∅ .
Qadam 2. Vazifalar ro'yxati bo'sh emas, biz undan A matritsasini tanlaymiz.
3-qadam. A matritsaning nol elementlari indekslarini hisoblang.
d (a, c) = 0 + 0 = 0;
d (a, f) = 0 + 4 = 4;

d (b, e) = 6 + 0 = 6;
d (c, a) = 4 + 0 = 4;
d (d, e) = 3 + 0 = 3;
d (e, b) = 0 + 5 = 5;
d (e, d) = 0 + 1 = 1;
d (f, a) = 0 + 0 = 0;
d (f, c) = 0 + 0 = 0.
Shunday qilib, matritsa shaklni oladi (indekslar qavs ichida yoziladi).
5-Rasm.
4-qadam. Maksimal indeksga ega nol elementni (b, e) tanlang 6. Yoy (b, e)
sayohatchi sotuvchining marshrutida allaqachon kiritilgan yoylar bilan sikl hosil
qilmaydi.
5-qadam . Joriy masalani ikkita kichik muammoga ajratamiz: yoyni (b, e)
siklda (B matritsasi) o'z ichiga oladi va qo'shmaydi (S matritsasi).
6-qadam. B matritsasini quramiz: A dan b qator va e ustunini o'chirib tashlaymiz,
biz b c d f olamiz.
6-Rasm.
Biz matritsani beramiz, o'ngdagi satrlarning minimal elementlarini yozamiz, ularning
minimal elementlarini qatorlardan ayiramiz. Shundan so'ng, ustunlarning minimal

elementlari nolga teng.
7-Rasm.
Minimal elementlarning yig'indisini C (A) ga qo'shib, biz C () ni olamiz.
C (B)= C (A)+3=16+3=19.
7-qadam. B matritsa 5 × 5 o'lchamga ega va C (B) <C, B matritsasini qo'shing
vazifalar ro'yxati.
8-qadam. C matritsasini tuzing: A (b, e) = ∞ qo'ying ((b, e) katak endi bo'sh),
hisoblang Minimal elementlarni b qatordan, keyin esa e ustunidan chiqaramiz.
8-Rasm.
C (C)= C (A)+6=16+6=22.
C (C) <C bo'lgani uchun vazifalar ro'yxatiga C matritsasini qo'shing. Natijada, daraxt
o'xshaydi (yechimning pastki chegarasi qavs ichida ko'rsatilgan).
9-Rasm.

4-qadam. Maksimal indeksli nol elementni (a, f) tanlang 4. Yoy (a, f) sayohatchi
sotuvchining marshrutida allaqachon kiritilgan yoylar bilan sikl hosil qilmaydi.
5-qadam . Joriy masalani ikkita kichik muammoga ajratamiz: a, f) yoyni sikldagi (D
matritsasi) va shu jumladan emas (E matritsasi).
6-qadam. D matritsasini quramiz: B dan a qator va f ustunini o'chirib tashlaymiz, b c
d ni olamiz.
10-Rasm.
Satrlar va ustunlarning minimal elementlari nolga teng, matritsani olib kelishning
hojati yo'q,
C (D) = C (B) = 19.
m (B) marshrutiga yoy (a, f) qo'shing, biz m (D) = {(b, e), (a, f)} marshrutini olamiz.
7-qadam. D matritsasining o‘lchami 4 × 4 va C (E) <C, E matritsasini qo‘shing.
8-qadam. E matritsasini tuzing: B (a, f) = ∞ ni o‘rnating, a qatoridan ayiring, keyin
esa ustun f minimal elementlar.
Satrlar va ustunlarning minimal elementlari nolga teng, matritsani olib kelishning
hojati yo'q, satrlar va ustunlarning minimal elementlari nolga teng, matritsani olib
kelishning hojati yo'q,
C (D) = C (B) = 19.
m (B) marshrutiga yoy (a, f) qo'shing, biz m (D) = {(b, e), (a, f)} marshrutini olamiz.
7-qadam. D matritsasining o‘lchami 4 × 4 va C (E) <C, E matritsasini qo‘shing.
8-qadam. E matritsasini tuzing: B (a, f) = ∞ ni o‘rnating, a qatoridan ayiring, keyin
esa ustun f minimal elementlari.

11-Rasm.
Ularning yig'indisini C (B) ga qo'shsak, biz C (E) ni olamiz.
C (E)= C (B)+4=19+4=23.
C (E) <C bo'lgani uchun vazifalar ro'yxatiga E matritsasini qo'shing.
12-Rasm.
Biz 2-bosqichga o'tamiz.
2-qadam . Vazifalar ro'yxati bo'sh emas, biz undan D matritsasini tanlaymiz.
3-qadam . D matritsaning nol elementlari indekslarini hisoblang.
13-Rasm.
4-qadam. Maksimal indeksli nol elementni (c, a) tanlang 11. Yoy (c, a) sayohatchi
sotuvchining marshrutida allaqachon kiritilgan yoylar bilan sikl hosil qilmaydi.
5-qadam . Joriy masalani ikkita kichik muammoga ajratamiz: yoyni (c, a) sikldagi (F
matritsasi) va shu jumladan (G matritsasi).
6-qadam. F matritsasini tuzing: D dan c qator va a ustunini o‘chiring. So'ngra o'ng
tomonda nol elementlarni ko'rsatamiz, keyin ularni mos keladigan chiziqlarning
elementlaridan ayiramiz.

14-Rasm.
Eritmaning sifati uchun pastki chegarani hisoblaymiz.
C (F) = C (D) = 19 + 2 = 21.
µ (D) marshrutiga yoyni (c, a) qo'shing, biz µ (F) = {(b, e), (a, f), (c, a)} marshrutini
olamiz.
7-qadam. F matritsasi 3 × 3 o'lchamga ega va C (F) <C, E matritsasini qo'shing.
8-qadam . G matritsasini tuzing: D (c, a) = ∞ o'rnating, c qatordan, so'ngra a
ustunidan minimal elementlarni ayiring.
14-Rasm.
Ularning yig'indisini C (D) ga qo'shsak, biz C (G) ni olamiz.
C (G) = C (D) + 11 = 19 + 11 = 30.
C (G) <C bo'lgani uchun vazifalar ro'yxatiga G matritsasini qo'shing.
15-Rasm.
2 -qadam. Vazifalar ro'yxati bo'sh emas, biz undan F matritsasini tanlaymiz.
3-qadam. F matritsaning nol elementlari indekslarini hisoblang.

16-Rasm.
4-qadam. Maksimal indeksli nol elementni (d, b) tanlang 10- Yoy (d, b) sayohatchi
sotuvchining marshrutida allaqachon kiritilgan yoylar bilan sikl hosil qilmaydi.
Qadam 5. Joriy masalani ikkita kichik muammoga ajratamiz: yoyni (d, b) sikldagi (H
matritsasi) va qo'shilmagan (I matritsasi).
6-qadam. H matritsasini qurish: F dan d qator va b ustunni o'chirish. Har bir satr va
har bir ustun nollarni o'z ichiga oladi, matritsa beriladi.
17-Rasm.
C (H) = C (F) = 21.
Yoyni (d, b) m (F) marshrutiga qo'shamiz va marshrutni olamiz m (H) = {(b, e), (a,
f), (c, a), (d, b)} .
7-qadam. H matritsasi 2 × 2 o'lchamga ega va C (H) <C. Yoy (e, d) sikl edbe hosil
qiladi. yoylari (d, b) va (b, e) allaqachon sayohatchi sotuvchining marshrutiga
kiritilgan. Shunday qilib, biz (e, c) va (f, d) yoylarni sayohatchi sotuvchining
marshruti µ (H) ga qo'shamiz va uning yoylarini tsikl bo'yicha tartibga solamiz:
µ (H) = {(b, e), (a, f), (c, a), (d, b), (e, c), (f, d)}
Tanlangan elementlarning yig'indisini oldingi qiymatiga qo'shib hisoblaymiz.
C (H)=21+9+7=37.
Sayohatchi sotuvchining keyingi marshruti m (H) olinadi; uning og'irligi C (H) = 37
<C, C = 37.
8-qadam. I matritsani tuzing: F (d, b) = ∞ o'rnating, d qatordan minimal elementlarni,
keyin esa b ustunidan ayiring.

18-Rasm
Ularning yig'indisini C (F) ga qo'shsak, biz C (I) ni olamiz.
C (I) = C (F) + 10 = 21 + 10 = 31.
C (I) <C bo'lgani uchun biz I matritsani vazifalar ro'yxatiga qo'shamiz.
19-Rasm
4-qadam. Maksimal indeksli nol elementni (d, e) tanlang 11. Yoy (d, e) sayohatchi
sotuvchining marshrutida allaqachon kiritilgan yoylar bilan sikl hosil qilmaydi.
5-qadam . Joriy masalani ikkita kichik muammoga ajratamiz:
6-qadam. J matritsasini qurish: C dan d qator va e ustunini o'chirish. Har bir satr va
har bir ustun nollarni o'z ichiga oladi, matritsa beriladi.
19-Rasm
Eritmaning sifati uchun pastki chegarani hisoblaymiz.

m (C) marshrutiga yoy (d, e) qo'shing, biz m (I) = {(d, e)} marshrutini olamiz.
20-Rasm
7-qadam. J matritsasi 5 × 5 o'lchamga ega va C (I) <C, ro'yxatga I matritsasini
qo'shing.
8-qadam. K matritsasini tuzing: C (d, e) = ∞ ni o'rnating, d qatordan, keyin esa dan
ayiring.
ustun e minimal elementlar.
Ularning yig'indisini C (C) ga qo'shsak, biz C (K) ni olamiz.
C (K) = C (C) + 11 = 22 + 11 = 33.
C (K) <C bo'lgani uchun vazifalar ro'yxatiga K matritsasini qo'shamiz.
21-Rasm
4-qadam . Maksimal indeksga ega nol elementni (e, b) tanlang 5. Yoy
(e, b) sayohatchi sotuvchining marshrutida allaqachon kiritilgan yoylar
bilan sikl hosil qilmaydi.

5-qadam .
Joriy
masalani
ikkita kichik
muammoga
ajratamiz:
6-qadam. L
matritsasini
qurish: J dan
e qator va b
ustunini
o‘chirish. Har
bir satr va har
bir ustun
nollarni o'z
ichiga oladi,
matritsa
beriladi.
Pastki
chegarani
hisoblaymiz.
C (L) = C (J) =
22.
µ (J) yoyni
(e, b)
qo'shing, biz
µ (L) = {(d,
e), (e, b)}
marshrutini
olamiz. 7-qadam. L matritsasi 4 × 4 o'lchamga ega va C (L) <C, L matritsasini
ro'yxatga qo'shing.
8-qadam. M matritsasini tuzing: J (e, b) = ∞ ni qo'ying, e qatoridan
airing.

22-Rasm
4-qadam. Maksimal indeksli nol elementni (f, a) tanlang 6. Yoy (f, a) sayohatchi
sotuvchining allaqachon kiritilgan yoylar bilan sikl hosil qilmaydi.
5-qadam . Joriy masalani ikkita kichik muammoga ajratamiz.
6-qadam. N matritsasini tuzing: L dan f qator va a ustunini o‘chiring. O'ng
tomonda nol elementlarni ko'rsatamiz, keyin ularni mos keladigan chiziqlarning
elementlaridan ayiramiz.

2.2 Derak va ore teoremalarining Gamilton seklida ifodalanishi.
Palmer [1] Ruda shartini qanoatlantiradigan grafda Gamilton siklini qurish
uchun quyidagi oddiy algoritm kerak bo’ladi
1. Grafdagi qo‘shnilikka e’tibor bermay, cho‘qqilarni ixtiyoriy tartibda siklda
joylashtiramiz.
2. Agar siklda ketma-ket ikkita qo shni bo lmagan uchlari bo lsa, vi va vi + 1, ʻ ʻ ʻ
quyidagi amallarni bajaring:
Buning uchun vi, vi + 1, vj va vj + 1 to'rtta uchlari bir-biridan farq qiladi va
grafikda vj dan vj + 1 dan v gacha bo'lgan qirralar mavjud. o siklning vi + 1 va vj
(shu jumladan) o'rtasidagi qismi teskari tartibda qurilgan..
Har bir qadam ketma-ket qo'shni juftliklar sonini bir yoki ikki juftga oshiradi
(vj va vj + 1 allaqachon qo'shni ekanligiga qarab), algoritmning tashqi sikli
uzilishidan oldin eng ko'p n marta ishlashi mumkin, bu yerda n - berilgan
grafikning uchlari soni. Siklning bir qismini keyinchalik inversiyasi bilan i va j ni
qidirish O (n) vaqtida amalga oshirilishi mumkin. Shunday qilib, algoritmning
umumiy ishlash vaqti O (n2) ga teng.
Tegishli natijalar
Ruda teoremasi Dirak teoremasining umumlashmasi bo lib, unda
ʻ
aytilishicha, har bir cho qqi kamida n/2 darajaga ega bo lsa, grafik Gamiltonian
ʻ ʻ
bo ladi. Ko'rinib turibdiki, agar grafik Dirac shartini qanoatlantirsa, cho'qqilar
ʻ
juftlik darajalarining yig'indisi kamida n bo'ladi.
O'z navbatida, Ore teoremasi Bondi-Xvatal teoremasiga umumlashtiriladi.
Grafi yopilishini har bir juft qo shni bo lmagan cho qqilarga umumiy darajasi
ʻ ʻ ʻ
kamida n bo lgan bu cho qqilarni bog lovchi chekka qo shish orqali belgilashingiz
ʻ ʻ ʻ ʻ
mumkin. Agar graf Ruda teoremasining shartini qanoatlantirsa, uning yopilishi
to‘liq grafik hisoblanadi. Bondi-Xvatala teoremasi shuni ko'rsatadiki, agar uning

yopilishi Gamilton grafigi bo'lsa, grafik Gamiltonian hisoblanadi. To'liq grafik
Gamilton bo'lganligi sababli, Ore teoremasi darhol shu teoremadan kelib chiqadi.
Ore teoremasining yo‘naltirilgan grafiklarga tegishli ekanligini ham topadi
topdi. Faraz qilaylik, G grafasi har qanday ikkita u va v uchlari uchun yo u dan v
gacha yoy bo‘lishi yoki u natijaning yarim darajasi va v kiritishning yarim darajasi
sonidan kam bo‘lmagan xususiyatga ega bo‘lsin. uchlari G. Keyin, Vudall
teoremasiga ko'ra, G yo'naltirilgan Gamilton siklini o'z ichiga oladi. Ruda
teoremasini Vudall teoremasidan har bir chetni bir juft yo‘naltirilgan yoylar bilan
almashtirish orqali olish mumkin yaqin teoremasi shuni ko'rsatadiki, n ta burchakli
kuchli bog'langan digraf, har qanday qo'shni bo'lmagan u va v uchlari uchun u yoki
v ga tushadigan qirralarning umumiy soni kamida 2n - 1 ga teng bo'lgan
xususiyatga ega, Gamiltonlik bo'lishi kerak.
2n - 1, Gamiltonian bo'lishi kerak.
Ruda teoremasini teoremadagi cho'qqilarning darajalari sharti natijasida
Gamiltoniy bo'lishdan ko'ra qattiqroq talab qo'yish orqali mustahkamlash mumkin.
Xususan, Ore teoremasining shartlarini qanoatlantiradigan har qanday graf
muntazam to‘liq ikki qismli graf yoki pantsiklikdir .

Foydalanilgan adabiyolar
1. M.O‘. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV,
“ALGORITMLAR” , «Fan va texnologiya» nashriyoti, 2018.
2. H.To’rayev,“Kombinatorika va graflar nazariyasi”, “Ilm ziyo”, 2009 ,
3. Akbaraliyev B.B., Yusupova Z.Dj. , “MA LUMOTLAR TUZILMASI VA ‟
ALGORITMLAR”, Toshkent 2013
4. Toirov Sh.A., Raximov R.T., Karimov M.M ,” “ALGORITMGA KIRISH”
fanidan laboratoriya ishlarini bajarish bo’yicha USLUBIY KO’RSATMA”,
Samarqand 2015,
5. Xayitmatov O’.T., Inogomjonov E.E., Sharipov B.A., Ro’zmetova N.,
Rahimboboeva D,” MA'LUMOTLAR TUZILMASI VA
ALGORITMLARI”, Toshkent – 2011
6. Л.И.Домнин, “ЭЛИМЕНТЫ ТЕОРИИ ГРАФОВ” , “ Пенза Издательство
Пензенского государственного университета“ ,2007
7. Никлаус Вирт ,”Алгоритмы и структуры данных Новая версия для
Оберона + CD “, Москва, 2010.
Foydalanilgan internet saytlar:
1) https://deru.abcdef.wiki/wiki/Hamiltonkreisproblem
2) https://deru.abcdef.wiki/wiki/Hamiltonkreisproblem
3) https://foxford.ru/wiki/informatika/postroenie-gamiltonova-tsikla
4) https://intuit.ru/studies/courses/58/58/lecture/1716?page=3
5) https :// portal . tpu . ru / SHARED / t / TRACEY / Courses / English / Tab 1/
graph _ lec _08. pdf
6) https://ru.wikipedia.org/wiki/Теорема_Оре
7) https :// neerc . ifmo . ru / wiki / index . php ?

“DIRAK VA ORE TEOREMALARI ASOSIDA GAMILTON SIKLINI TOPISH ALGORITMI” Mundarija .......................................................................................................................................................................... 1 Foydalanilgan adabiyolar ................................................................................................................................ 24

Kirish Bu kurs ishida “Derak va Ore teoremasining Gamilton siklining ifodalanishi” mavzusini yoritib berar ekanmiz nazariy qisimda Gamilton siklining ifodalanishi, Derak va Ore teoremalari mavzulariga to’xtalib o’tamiz. Amaliy qisimda esa Gamolron sikliga oid misollar, Derak va ore teoremalarining Gamilron seklida ifodalanishi kabi mavzularda misollar ishlaymiz. Xulosa qismini hamma ishlarni bajarib bo’lgandan so’ngra yozamiz.

I.BOB.NAZARIY QISM 1.1.Gamilton siklining ifodalanishi. Gamilton sikli bu algoritm va ma’lumotlar strukturasida keng qullaniladigan tushunchalardan biridir. Ta'rif . Agar graf bir marta grafning barcha uchlarini o'z ichiga olgan oddiy siklga ega bo'lsa, unda bunday sikl Gamilton sikli, graf esa Gamilton grafi deb ataladi. Agar grafda bir marta grafning barcha uchlarini o'z ichiga olgan oddiy zanjir bo'lsa, bunday zanjir Gamilton zanjiri, graf esa yarim Gamilton grafigi deb ataladi. Grafning Gamilton bo‘lishi uchun quyidagi teorema zarur va yetarlidir . Hali zarur sharoitlar topilmagan.Dirak teoremasi. Agar p ≥ 3 uchlari ∀ v ∈ V d (v) ≥ p / 2 bo'lgan G (V, E) grafigida G grafigi Gamilton bo'ladi. Isbot. V = {v1, bo'lsin. ... ... , vp}. Avval e'tibor bering, har qanday grafik unga p qo'shimcha 2-darajali burchaklarni qo'shish orqali Gamiltonga aylantirilishi mumkin: bu yerda i = 1,. ... ... , p - 1, qirralari (vi, ui) va (ui, vi + 1) qo'shiladi, qirralarga (vp, yuqoriga) va (yuqoriga, v1) qo'shiladi. Keyin Gamilton sikli quyidagi ko'rinishga ega bo'ladi. v 1 u 1 v 2 u 2 . . . v p u p v 1 . Dastlabki grafikda qo'shimcha u 1 cho'qqisi bo'lmagan holda Gamilton siklini qurish mumkinligini ko'rsatamiz. Uchta holat bo'lishi mumkin: 1) v 1 va v 2 cho'qqilari qo'shni, keyin v 1 va v 2 sikl kesimini v1v2bilan almashtirish mumkin; 2) ) v 1 va v 2 uchlari qo‘shni emas, lekin vj, vj + 1 juft uchlari borki, vj qo‘shni bo‘ladi. v1 va vj + 1 bilan v2 ga ulashgan. Keyin siklning segmenti v2u2 bo'ladi. ... ... vj kengaytirilishi mumkin, qo'shimcha u1 va uj uchlarini chiqarib tashlang va siklni oling. v 1 v j u j−1 v j−1 . . . u 2 v 2 v j+1 u j+1 . . . v p u p v 1 ; 3) v1 va v2 cho'qqilari qo'shni emas va v1 ga qo'shni bo'lgan har qanday vj cho'qqi uchun vj + 1 uchi v2 ga qo'shni emas. Keyin v1 (yoki d (v1)) ga ulashgan cho'qqilar

soni v2 ga qo'shni bo'lmagan cho'qqilar sonidan oshmaydi (yoki p - d (v2) - 1 - v2 ga qo'shni barcha cho'qqilar umumiy cho'qqilar sonidan olib tashlanadi). d(v 1 ) ≤ p − d(v 2 ) − 1. Teorema gipotezasi bo'yicha ∀ v ∈ V: d (v) ≥ p / 2 ekanligini hisobga olsak. p = p/2 + p/2 ≤ d(v 1 ) + d(v 2 ) ≤ p − 1. Demak, Gamilton siklini qo'shimcha u1 cho'qqisidan foydalanmasdan qurish mumkin. Barcha qo'shimcha cho'qqilar uchun shunga o'xshash mulohaza yuritib, dastlabki graf da Buning aksi to‘g‘ri emas, ya’ni Gamilton siklining mavjudligi uchun teorema shart emas.Gamilton siklini olamiz.Teorema isbotlangan. Gamilton siklini olish uchun, ya'ni polinom vaqtini talab qiluvchi hisoblash samarali algoritmlari mavjud emas. Roberts va Flores qo'pol kuchlar algoritmi ("chuqur" o'tish strategiyasiga asoslangan) 1-qadam. Barcha uchlari v qo'shnilik ro'yxati L (v) uchun kompilyatsiya qiling. X1 boshlang'ich uchini tanlang, i = 1 ni o'rnating. 2-qadam . Agar i = p va {xp, x1} ∈ E bo'lsa, x1x2. ... ... xpx1 - Gamilton sikli, oxiri. Agar i = 0 bo'lsa, u holda Gamilton sikli yo'q. 3-qadam . x1, x2. ... ... xi - 1, L qo'shni ro'yxatidan (xi - 1). Agar bunday cho'qqi bo'lmasa, biz i = i - 1 ni o'rnatamiz (bir qadam orqaga qayting) va 3-bosqichni takrorlang. Aks holda, 2-bosqichga o'ting. 1.2.Derak va Ore teoremsi. Graflar nazariyasining Ore teoremasi 1960 yilda norvegiyalik matematik Oistin Ore tomonidan isbotlangan. Teorema graflarning Gamilton bo'lishi uchun yetarli shartni qanoatlantirishi kerak "yetarlicha ko'p qirralar" bo'lgan graf Gamilton siklini o'z ichiga olishi kerakligini tasdiqlaydi. Xususan, teorema qo'shni bo'lmagan cho'qqilar juftliklari darajalarining yig'indilarini ko'rib chiqadi - agar yig'indidagi har bir bunday juftlik hech bo'lmaganda grafikning uchlari umumiy sonini bersa, grafi Gamiltondir.

G n ≥ 3 cho‘qqi bo‘lsin. G dagi v cho'qqi darajasini, ya'ni v ga to'g'ri keladigan qirralarning sonini v bilan belgilaymiz. Bu bayonot har qanday Gamilto bo'lmagan G grafi(*) shartini buzganiga tengdir. G n ≥ 3 ta burchakli Gamilton bo‘lmagan graf bo‘lsin. H grafigi G dan Gamilton siklini hosil qilmaydigan bir vaqtning o'zida bir chetini qo'shish orqali hosil bo'lsin, chunki bunday qirralarni qo'shish mumkin. H grafigining ixtiyoriy ikkita qo shni bo lmagan ʻ ʻ x va y cho qqilarini ko rib chiqaylik. H ga xy chekka qo shilganda kamida bitta ʻ ʻ ʻ Gamilton sikli hosil bo ladi va bu sikldagi xy dan boshqa qirralar x bilan H da ʻ Gamilton yo li v1v2 ... vn hosil qilishi kerak. y= v1 va y = vn. 2 ≤ i ≤ n oralig'idagi ʻ har bir i indeksi uchun H v1 ning vi va vi - 1 vn dan ikkita mumkin bo'lgan qirralarini ko'rib chiqing. Bu qirralarning ko'pi Hda bo'lishi mumkin, chunki aks holda v1v2 ... vi - 1vnvn - 1 ... vi sikl Gamilton bo'ladi. Shunday qilib, v1 yoki vn ga tushgan qirralarning umumiy soni n - 1 ga teng bo'ishi mumkin. Shuning uchun H (*) shartni qanoatlantirmaydi, bu esa qirralarning umumiy sonini v1 + deg vn) n dan katta yoki teng. G cho'qqilarining darajalari H dagi darajadan oshmaganligi sababli, G ham talabni qondirmaydi.

O'xshashlar

Dirak va Ore teoremalari asosida

Eyler yo’li va Eyler siklini aniqlash algoritimi

Fenvik daraxti va algoritmi

KRASKAL ALGORITMI

Deykstra Algoritmi