Grafda zanjir, marshrut, sikl tushunchalari. Eyler, gamilton sikllari va graflari

Download 489,84 Kb. Pdf ko'rish
bet	4/6
Sana	19.05.2024
Hajmi	489,84 Kb.
	#244547

1 2 3 4 5 6

Bog'liq
GRAFDA ZANJIR, MARSHRUT, SIKL TUSHUNCHALARI EYLER, GAMILTON SIKLLARI

Flyori algoritmini 1

oriyentirlangan Eyler yo'li,
deb ataladi. Tarkibida oriyentirlangan Eyler yo'li bor
bo'lgan oriyentirlangan graf
oriyentirlangan Eyler grafi,
deb ataladi.
Endi qirralari soni
n
ga teng bo'lgan berilgan Eyler grafida Eyler zanjirini
tuzishning
Flyori algoritmini
1
keltiramiz. Bualgoritmga ко'ra, grafning qirralari
Eyler siklida uchrashi tartibi bo'yicha 1 dan
n
gacha raqamlab chiqiladi.
Berilgan Eyler grafi uchun Flyori algoritmiga binoan quyidagi ikkita qoida
asosida ishlar ketma-ket bajariladi:
1.
Grafning ixtiyoriy v uchidan boshlab, bu uchga insident bo'lgan istalgan
qirraga (masalan,^ qirraga) 1 raqami beriladi. Bu qirra grafdan olib tashlanadi va v
uchdan
V
uchga (ya'ni olib tashlangan qirraga insident uchga) o'tiladi.
2.
Oxirgi o'tishdan oldingi o'tish natijasida hosil bo'lgan uch
w
bo'lsin va oxirgi
o'tishda biror qirraga
к
raqami berilgan deylik.
w
uchga insident istalgan qirra
imkoniyati boricha shunday tanlanadiki, bu qirrani olib tashlash grafdagi
bog'lamlilikni buzmasin. Tanlangan qirraga navbatdagi
(k+l)
raqami beriladi va bu
qirra grafdan olib tashlanadi. ■
Flyorialgoritmigako'ra,
ishyuritishEylergrafiuchundoimocheklijarayonekanligivabujarayondoimografdanb
archaqirralarningolibtashlanishi, ya'niEylerzanjirinituzishbilantugashiisbotlangan.
Shunihamta'kidlashkerakki,
Flyorialgoritminiqo'llashjarayonidaqirralarnitanlashimkoniyatlariko'pbo'lganiuchu
n,
bundayvaziyatlarda,
algoritmniqo'llashmavjudEylersikllaridanbirinitopishbilancheklanadi.Tushu-
narliki,
Flyorialgoritminitakrorqo'llab
(bundaqirralarnitanlashjaroyonialgoritminiawalgiqo'llashlardagidekaynantakror-
lanmasligikerak) grafdamavjudbo'lganbarchaEylersikllarinitopishmumkin.
1-misol.
1-shaklda tasvirlangan grafni qaraymiz.Awalo, bu grafning Eyler grafi
bo'lishi shartini, ya'ni 1-teorema shartlarining bajarilishini tekshiramiz.
Berilgan grafda to'qqizta uch bo'lib, 1, 3, 7, 9 belgili uch-larning darajasi
ikkiga, 2, 4, 6, 8 belgili uchlarning darajasi to'rtga,
5 belgili uchning darajasi esa
oltiga
teng.Xullas,
bu
grafdagi barcha uchlarning
darajalarijuftdir.
Shu-ning
uchun, 1-teoremaga ko'ra, 1 -
shaklda
tasvirlangan
graf
Eyler
grafidir
va
uning
tarkibida Eyler sikli mavjud.

Berilgan grafga flyori algoritmini qo'llab, mavjud
Eyler sikllaridan birini aniqlaymiz.
Dastlabki uch sifatida grafdagi 1 belgili uch
olingan bo'lsin. Bu uchdan ikki yo'nalishda: (1;2)
qirra bo'ylab yoki (1;4) qirra bo'ylab harakatlanish
mumkin. Masalan, (1;2) qirra bo'ylab harakatlanib
2
belgili uchga o'tamiz. Endi harakatni 3 yo'nalishda: yo (2;3) qirra bo'ylab, yo
(2;4) qirra bo'ylab, yoki (2;5) qirra bo'ylab davom ettirish mumkin. Aytaylik, (2;3)
qirra bo'ylab harakatlanib
3
belgiliuchgao'tganbo'laylik.
Shuusuldadavometishmumkinbo'lganEylersikllaridanbirini,
masalan,
quyidagisiklnihosilqilamiz:
((1,2), (2,3),(3,5), (5,4), (4,6), (6,9), (9,8), (8,6), (6,5),(5,8), (8,7), (7,5),
(5,2), (2,4),(4,1)). ■
Gamilton graflari.
Graflar
nazariyasining
natijalari
muayyan
shartlarni
qanoatlantiravchi
marshratlarni topish masalasiga kelti-riluvchi bir qator muammolarni hal etishda
qo'llanilishi mumkin. Shunday muammolardan biri sifatida Uilyam Gamilton nomi
bilan bog'Uq masalani keltiramiz. U. Gamilton dodekaedrni tekshirib, uning har
bir uchidan faqat bir marta o'tadigan siklni izlab topgan va shu asosda 1859-yilda
«Olam bo'ylab sayohat» nomli o'yirmi topgan.
Grafning har bir uchidan faqat bir marta o'tadigan zanjir

Download 489,84 Kb.

1 2 3 4 5 6

Download 489,84 Kb.

Pdf ko'rish