Дәріс тақырыбы: Графтар теориясы (5 сағат) Негізгі сұрақтар



жүктеу 0,75 Mb.
бет18/23
Дата03.02.2022
өлшемі0,75 Mb.
#35463
1   ...   15   16   17   18   19   20   21   22   23
лекция

Анықтама.a1, a2,…,an, an+1 маршрутының салмағы деп санын айтады. (a, b)- маршрутының салмақтарының ең кішісі а және b төбелерінің салмақтанған арақашықтығы деп аталады болып белгіленеді.

Анықтама. Салмағы арақашықтығына тең (a, b) маршруты салмақтанған G графындағы ең қысқа маршрут деп аталады.

Анықтама. а төбесінің салмақтанған эксцентриситеті деп max{ │b M} санын айтады, оны деп белгілейді.

=max{ │b m}

Анықтама. G графының салмақтанған орталық төбесі деп =min{ │b M} а төбесін айтады.

Анықтама. Орталық төбенің салмақтанған эксцентриситеті G графының салмақтанған радиусы деп аталады , болып белгіленеді.

Мысалы: Салмақтанған орталық төбе Новосибирск =274, ал =681

Графтағы ең қысқа маршрутты анықтайтын өте қарапайым әрі тиімді алгоритм бар.

Оны бұрыннан белгілі бас қатырғыш жұмбақ есеп мысалында қарастырайық. Екі адамда вино құйылған 8 литрлік бір құмыра және 5 литрлік, 3 литрлік екі бос құмыра бар. Виноны құмыралар не толық, не бос болатындай құйып, екі адам барлық виноны тең бөлісуі керек.

Алдымен екі мүмкіндікті қарастырамыз: 8 литрлік құмырадан вино 5 литрлік және 3 литрлік құмыраларға құйылады. Бұл мүмкіндіктерді символдық түрде 800→350 және 800→503 деп белгілейік. Құмыраларға виноны құюдың әртүрлі мүмкіндіктерін (х,у,z) үштігімен немесе қысқаша хуz деп белгілейміз. Мұндағы х – 8 литрлік құмырадағы вино, у–5 литрлік құмырадағы вино және z – 3 литрлік құмыраға құйылатын вино. 350 жағдайында 3 түрлі құю мүмкіндігі бар: 350→323, 350→053, 350→800. Осындай ситуацияларға талдау жасай келе және құмыраларды түрліше толтыра отыра суретте көрсетілгендей бағытталған граф аламыз. Алынған графтың төбелері ретінде әртүрлі жағдайларды сипаттайтын үштіктер ал виноны түрліше құюлар доғаларға сәйкес келеді. Әрине, бұлграфта еселі доғалар жоқ, яғни бұл диграф. Жалпы, ең қысқа маршрутты анықтау есептеріндегі графтарда ілгектер мен еселі қабырғалар (доға) жоқ деп алынады. 800 төбеден 440 төбесіне апаратын маршрут табылса есеп шешілді деп есептейміз. Суреттен мұндай жол оңай табылатындығын көреміз: 800, 350, 323, 620, 152, 143, 440. Бұл жолға есептің шешімін беретін төмендегідей құюлар сәйкес келеді.

Вино 8 литрлік құмырадан 5 литрлік құмыраға толтырылады.



1-Сурет. Түрлі жағдайлар мен құюлар графы.

Содан кейін 5 литрлік құмырадан вино 3 литрлік құмыра толғанға дейін құйылады. 3 литрлік құмырадан вино түгелдей 8 литрлікке құйылады. 5 литрліктегі 2 литр 3 литрлікке құйылады. 8 литрліктегі 5 литрлікке толтырылады. 5 литрліктен 1 литрді 8 литрлік құмыраға құю керек (толғанға дейін). Соңында 3 литрліктен барлық виноны 8 литрлік құмыраға құйылады. Нәтижесінде 8 литрлік құмырада 4 литр вино және сонша литр 5 литрлік құмырада болады. Вино тең бөлінді.

Осы 800 төбеден  440 төбеге апаратын жол ең қысқа болады. Бұл жолды графтардағы ең қысқа маршрутты анықтайтын алгоритмді пайдаланып та табуға болады. Енді осы алгоритмнің жұмысын формальды түрде сипаттап көрейік:

Алгоритмнің жұмысы барысында х0=800 алғашқы төбеден бірдей қашықтықтағы төбелер жиыны құрылады. Бұл жиындарды вертикаль түзулер яғни ярустарға (2 сурет) орналастырамыз (2-сурет). Нөлінші яруста бір ғана х0=800 төбесі орналасқан. Бірінші яруста 800-ден шығатын доғалар кіретін төбелер орналасқан (350 және 503). Екінші ярусқа 350 және 503 төбелерге сыбайлас, бірақ 0-ші немесе 1-ші ярустарға кірмейтін төбелерді белгілейміз. Егер k-шы ярус құрылған болса (k+1)-ярусқа G графының алдыңғы ярустарда жоқ және k-шы ярустағы төбелерге сыбайлас төбелерді енгіземіз. Ярус құру у0=440 төбесі алынған сәтте тоқталады.

Осыдан кейін құрылған графтың у0=440 төбесінен х0=800 төбесіне қайту барысында маршрутты анықтаймыз. Бұл маршрутпен кері жүру барысында х0=800 төбесінен у0=440 төбесіне апаратын ең қысқа жол табылады.



2-сурет "Ярусты" граф

Біз ең қысқа жолды табу алгоритмін 1-суреттегі графқа қолданылатындай сипаттадық. Нақтылы бір мысалға жазылған бұл алгоритмді кез келген графқа қолдануға болатындай алгоритмнің сипаттамасын келтірейік: Al1 алгоритмін графтың берілген екі төбесін қосатын ең қысқа маршрутын табу үшін сипаттаймыз. Бұл алгоритмнің негізіне берілген графтың бір төбесінен шығатын ең қысқа жолдардың графы деп қарастыруға болатын ярустық граф құру алгоритмі жатады. Сондықтан алдымен ең қысқа жолдардан құралған ішкі граф құратын Al2 алгоритмін сипаттайық:

Al2 алгоритмі (ең қысқа жолдар графын құрады).

Басы. Бағытталған G графы және оның бір х0V(G) төбесі берілген. G графын кіретін және шығатын аймақтар{O+(х), O-(х)|xV(G)} үйірімен берейік.

1. L:={x0}, M:=, Г(x0):=, h(x0):=0, t:=0;

Мұндағы L мәндері құрылғалы тұрған ағымдағы яруста жатқан төбелер жиыны болатын айнымалы; М-мәндері құрылғалы тұрған ағымдағы ярустың алдындағы яруста орналасқан төбелер жиыны болатын айнымалы; Г әрбір х төбесіне құрылатын графтың х–ке апаратын төбелер жиынын белгілейтін функция; h xo төбесінен x төбесіне дейінгі аралықты көрсететін натурал санды кез келген x төбесіне белгілейтін функция; t- h функциясын есептеуге қолданылатын бүтін мәнді айнымалы t.

2. M:=MUL;

3. Әрбір zL, t:=t+1; L:={O-(x)|xL}\M, Г(z):=O+(z)М, Г(z):=t+1;

4. Тексеру: L=. Егер дұрыс болса 2 пунктке көш.

Соңы. М, h және Г баспаға бер.

Мұнда М xo төбесінен шығатын ең қысқа жолдар графының төбелер жиыны; Г(х) ең қысқа жолдар графынан шығатын х төбесінің аймағы.

h(х)–G графындағы ρ(х0, х) арақашықтығы(х пен у төбесінің арақаш-ықтығы деп х пен у-ті қосатын ең қысқа жолды айтады).

1-кесте


X

800

350

503

053

323

530

620

233

602

251

152

701

143

710

440

413

Г




800

800

350

350

503

323

530

620

233

602

251

152

701

143

710

H

0

1

1

2

2

2

3

3

4

4

5

5

6

6

7

7

AL2 алгоритмін х0-800 төбесімен G басқатырғыш графына қолданғанда 26 қадам жүргізіледі, оған қоса М айнымалысының ең соңғы мәні Г және h функцияларының мәндерімен берілген 1-кестеде көрсетілген жиын болады. 1-кестеде шын мәніндех0-800 төбесінен шығатын ең қысқа жолдар графы көрсетілген. (Г(х) бұл графта х төбесінің кір етін аймағы).

х0 төбесінен у0 төбесіне жеткізетін ең қысқа жолды табу үшін кестеден Г(у0) мәнін табамыз және одан қандай да бір у1Г(у0) төбесін аламыз. у1 төбесі үшін Г(у1) мәнін табамыз да, одан қандай да бір у2Г(у1) төбесін аламыз. Осылай жалғастыра келе х0 төбесіне келеміз ( бұл төбе үшін Г(х0)=0). Мысалы, у0=440 алсақ мынадай тізбек аламыз: у0=440, у1=143Г(440), у2 =152Г(143), у3=602Г(143), у4=620Г(602),у5=323Г(620), у6=350Г(323), у7=800, Г(800)=0.Демек, 800 төбесінен 440 төбесіне жеткізетін ең қысқа маршрут: 800, 350, 323, 620, 602, 152, 143, 440.

Графтың екі төбесінің арасындағы ең қысқа жолды анықтайтын Al1 алгоритмін Al2 алгоритмінен жеңіл шығарып алуға болады.

Al1 алгоритмі (графтың екі төбесінің арасындағы ең қысқа жолды анықтайды)

Басы. G бағытталған граф, х0, у0 оның екі төбесі

Al2 алгоритмін (G, х0) жұбына қолдану.

у:=у0, u:u=у0.

Мұнда құрылып жатқан ең қысқа жолдың ағымдағы төбесі у-тің мәні болады.

Г(у) табу және Г(у)=0 екендігін тексеру. Егер шарт дұрыс болса, «х0-ден у0-ге апаратын жол жоқ» деген хабар баспаға шықсын.

x0Г(у). екендігін тексеру. Егер дұрыс болса, соңына көш.

Қандай да бір zГ(у) төбесін алу. Анық болу үшін Г(у) тізіміндегі бірінші төбені аламыз да у:=z және u:=z,u 3 қадамға көш.

Мұндағы z,u z-ті u тізбегінің басына қосқандағы нәтижені білдіреді.

Соңы. U тізбегін баспаға шығару.

Графтар теориясына негіз болған есептердің бірі Кенигсберг көпірлері туралы есеп. 1-Суретте Леонард Эйлердің тұсындағы(17 ғасыр) XVII ғасырдағы Кенигсберг қаласының картасы салынған. Қала Прегель өзенінің екі жақ жағалауында және 2 аралда. орналасқан Аралдар өзара және жағалаулармен 7 көпірмен жалғасқан. Кенигсберг тұрғындарының арасында сол кезде Кенигсберг көпірлері деп аталатын есеп кең тараған:



Есеп. Үйден шығып әр көпірмен бір рет қана жүріп үйге қайтып келуге болама ма деген сұрақ туады?

3-сурет

Бұл есеп үшін көпірлерден өтудің маңызы бар. Сондықтан көпірлердің орналасуын 2-суреттегі бағытталмаған мультиграфпен алмастыруға болады. Бұл графта Б,В төбелері өзеннің жағаларына, ал А,Г төбелері аралдар, ал мультиграфтың қабырғалары көпірлерге сәйкес келеді. Егер G графында оның барлық қабырғалары арқылы өтетін цикл табылса Кенигсберг туралы есеп шешілді деп есептеледі (Цикл деп бірде бір қабырға қайталанбайтын циклды маршрутты айтатынын еске саламыз). Демек графтар тілінде есептін қойылуы төмендегідей: Мультиграфта оның барлық қабырғалары болатындай цикл бар ма? Атақты ғалым-математик Л.Эйлер байланысты, бағытталмаған мультиграфта оның барлық қабырғалары болатындай цикл болудың шартын анықтап дәлелдеп берді.

4-сурет


ТеоремаБайланысты бағытталмаған мультиграфтың әр төбесінің дәрежесі жұп сан болса ғана Эйлер циклы болады.


жүктеу 0,75 Mb.

Достарыңызбен бөлісу:
1   ...   15   16   17   18   19   20   21   22   23




©g.engime.org 2024
әкімшілігінің қараңыз

    Басты бет
рсетілетін қызмет
халықаралық қаржы
Астана халықаралық
қызмет регламенті
бекіту туралы
туралы ережені
орталығы туралы
субсидиялау мемлекеттік
кеңес туралы
ніндегі кеңес
орталығын басқару
қаржы орталығын
қаржы орталығы
құрамын бекіту
неркәсіптік кешен
міндетті құпия
болуына ерікті
тексерілу мемлекеттік
медициналық тексерілу
құпия медициналық
ерікті анонимді
Бастауыш тәлім
қатысуға жолдамалар
қызметшілері арасындағы
академиялық демалыс
алушыларға академиялық
білім алушыларға
ұйымдарында білім
туралы хабарландыру
конкурс туралы
мемлекеттік қызметшілері
мемлекеттік әкімшілік
органдардың мемлекеттік
мемлекеттік органдардың
барлық мемлекеттік
арналған барлық
орналасуға арналған
лауазымына орналасуға
әкімшілік лауазымына
инфекцияның болуына
жәрдемдесудің белсенді
шараларына қатысуға
саласындағы дайындаушы
ленген қосылған
шегінде бюджетке
салығы шегінде
есептелген қосылған
ұйымдарға есептелген
дайындаушы ұйымдарға
кешен саласындағы
сомасын субсидиялау