Осыны тексеру үшін графтың w
1
ерікті шыңын таңдаймыз, сосын
w
2
→w
1
болатын қандай да бір w
2
шыңын, сосын w
3
→ w
2
болатын қандай да
бір w
3
шыңын т.с.с. таңдаймыз. Шектеулі қадам ішінде біз ешқандай доға
өтпейтін, себебі граф контурсыз болғандықтан w
1
, w
2
, w
3
,... тізбегінде ешбір
шың қайталанбайды, қандай да бір w
i
шыңына жету керекпіз.
Біздің алгоритмде ешбір доға өтпейтін шыңдар стекте жиналады. 10-
жолда стектің жоғарғы элементі таңдалып, сол шыңға ең кіші, әлі
қолданылмаған номерлердің біреуі беріледі. Сөйтіп, осы шыңнан шығатын
барлық доғалар үлкен номерлі шыңдарға апарады. Сосын u шыңы одан
шығатын доғалармен бірге графтан жойылады. Бұл u → v болатын әрбір v
шыңына кіретін доғалар санын 1-ге кемітеді. Бұл сан nz[v] ішінде сақталады.
Егер v шыңдарының қайсыбірі үшін бұл сан 0-ге ұмтылса, онда v стекке
орналастырылады.
Графтың контурсыздығына және жоғарыда айтылып кеткен
жағдайларға байланысты стек толық босап, алгоритм өз жұмысын барлық
шыңдар өз номерлерін алғаннан соң аяқтайды.
Әрбір доға 4-жолда бір рет және 12-жолда бір рет анализделеді. Сөйтіп,
алгоритм күрделілігі O(m) болады.
Енді көздерден контурсыз графтың барлық шыңдарына дейінгі
арақашықтықты табу алогритмін қарастырайық. Сонымен қатар, граф
шыңдары номерленген деп есептейміз, сондықтан әрбір доға кіші номерлі
шыңнан үлкен номерлі шыңға бағытталады. Бұдан басқа, граф ТІЗІМ[v], v
∈
V инциденттілік тізімімен берілген деп есептейміз.
Алгоритм жұмысының нәтижесі - V
1
-ден графтың барлық шыңдарына
дейінгі, нақтырақ айтсақ, D[v
i
]=d(v
1
,v
i
), i=1..n дейінгі арақашықтық болады.
1 BEGIN
2 D[v
1
]:=0;
3
FOR j := 2 TO n DO D[v
j
]:=
∞
;
4
FOR j := 2 TO n DO
5
FOR v
i
∈
ТІЗІМ[v,] DO D[v
j
] := mid(D[V
j
], D[v
i
] + a[v
i
, v
j
]
6
END
j индукциясы арқылы 4-цикл орындалғаннан кейін қандай да бір j мәні
үшін келесі теңдік орындалатындығын дәлелдеуге болады
D[v
i
]=d(v
1
,v
i
), i=1..j.
Бұл v
i
–ден v
j
-ға апаратын ең қысқа жолдың барлық аралық
шыңдардың номерлері j-ден кіші болатындығы шығады.
Алгоритм күрделілігі O(m), себебі әрбір (v
i
,v
j
) доғасы 5-жолда бір рет
талданады.
Соңғы екі алгоритм қандай да бір жобаның орындалуын басқару
әдістерінде қолданыс табады. Бұл әдістер салмақтары жеке міндеттерді
шешуге кететін уақытты көрсететін, жобаны құратын қандай да бір
міндеттерге сәйкес доғалары бар графты құруға негізделген. Бұдан басқа,
осы графтың (u, v) мен (v, t) ерікті доғалары үшін (u, v) доғасымен
бейнеленетін міндет (v, t) доғасымен бейнеленген міндет шешілмей тұрып
орындалу керек. Ондай граф, әрине контурсыз болады. Біздің мақсатымыз
жобаның басталуына сәйкес s шыңынан жобаның аяқталуына сәйкес t
шыңына дейінгі ең ұзын жолды табу (33-суреттегі жолды қараңыз). Мұндай
жол кризистік деп аталады. Оның ұзындығын жобаны толық орындауға
кеткен уақыт анықтайды. Бұл міндет ең қысқа жолдың әрбір а[u, v], мұндағы
u → v салмағының таңбасын қарама-қарсыға ауыстыру міндетіне
ұмтылатыны анық.
Ұсынылатын әдебиет
1. Костин А.В., Шаньгин В.Ф. Организация и обработка структур
данных в вычислительных системах. – М. Высш. шк., 1987.
2. Вирт Н. Алгоритмы и структуры данных.- М.: Мир, 1988.
3. Вирт Н. Алгоритмы+ структуры данных= программы.-М.: Мир, 1985.
4. Ленгстайм Й., Огенстайм М., Тененбаум А. Структуры данных для
персональных ЭВМ.- М.: Мир,1989.
5. Флорес И. Структуры и управление данными.- М.: Финансы и
статистика,1982.
6. Стоун Г. С., Сиворек Д. П. Введение в организацию ЭВМ и
структуры данных. – М.: Машиностроение, 1980.
7. Бауэр Ф. Л., Гооз Г. Информатика. Вводный курс. В двух частях.-
М.: Мир, 1990.
8. Яворский В. В., Богушевская А. А. Структуры данных и алгоритмы
их обработки.- Қарағанды: ҚарМТУ, 2004.- 150б.
СӨЖ-на арналған тапсырмалар
1. Графтардың машиналық көрінісі.
2. Графта тереңдікке іздеу.
3. Графта кеңдікке іздеу.
4. Керуші ағаштар.
5. Кеңдікке іздеу әдісімен ерікті ағашты табу.
6. Тереңдікке іздеу әдісімен ерікті ағашты табу.
7. Графтағы циклдердің фундаменталды жиынтығы.
8. Графтағы циклдердің фундаменталды жиынтығын табу.
9. Эйлер жолдары мен циклдері. Эйлер жолдарының қажетті және
жеткілікті шарты.
10. Эйлер циклін графтан табу.
11. Гамильтон циклін графтан табу.
12. Графтан ең қысқа жолдарды табу.
13. Форд-Беллман алгоритмі.
14. Дейкстра алгоритмі.
4 Практикалық (семинарлық) сабақтарды орындауға әдістемелік
нұсқаулар
1-тақырып (1 сағ.) Курстық жобалаудың жеке тапсырмаларын
талдау.
Практикалық (семинарлық) сабақ жоспары
1. Жеке тапсырма тақырыбын талдау
2. Жеке тапсырманы орындау кезеңдерін анықтау
3. Бағдарламалық өнімге қойылатын талаптар
4. Жеке тапсырма бойынша есеп беру графигі.
Ұсынылатын әдебиет
1. Костин А.В., Шаньгин В.Ф. Организация и обработка структур
данных в вычислительных системах. – М. Высш. шк., 1987.
2. Вирт Н. Алгоритмы и структуры данных.- М.: Мир, 1988.
3. Вирт Н. Алгоритмы+ структуры данных= программы.-М.: Мир, 1985.
4. Ленгстайм Й., Огенстайм М., Тененбаум А. Структуры данных для
персональных ЭВМ.- М.: Мир,1989.
5. Флорес И. Структуры и управление данными.- М.: Финансы и
статистика,1982.
6. Стоун Г. С., Сиворек Д. П. Введение в организацию ЭВМ и
структуры данных. – М.: Машиностроение, 1980.
7. Яворский В. В., Богушевская А. А. Структуры данных и алгоритмы
их обработки.- Қарағанды: ҚарМТУ, 2004.- 150б.
8. М. Сибуя ,Т. Ямамото Алгоритмы обработки данных.- Москва,
Мир,1986.
9. Богушевская А. А. Структуры данных и методы доступа.
Электронды оқулық.- ҚарМТУ, 2004.
11. Попов С.Н. «Деректерді өңдеудің құрылымдары мен әдістері» пәні
бойынша курстық жобаға арналған әдістемелік нұсқаулар.
СӨЖ-на арналған бақылау тапсырмалары (1-тақырып) [1,2,4,7,8,11]
1. Курстық жобаға арналған әдістемелік нұсқаулардың теориялық
материалын оқу.
2. Жеке тапсырма нұсқасын таңдау және талдау.
3. Курстық жобаның талаптарымен танысу.
2-тақырып (2 сағ.) Жеке тапсырманың математикалық моделін
жасау.
Практикалық (семинарлық) сабақ жоспары
1. Жеке тапсырманы формализациялау
2. Математикалық модельді құру
3. Іске асыру әдісін таңдау
Достарыңызбен бөлісу: |
