1 пєнініњ ОЌу программасы syllabus

Мысалы: Салмақтанған орталық төбе Новосибирск =274, ал =681 Графтағы ең қысқа маршрутты анықтайтын өте қарапайым әрі тиімді алгоритм бар.

Алдымен екі мүмкіндікті қарастырамыз: 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-Сурет. Түрлі жағдайлар мен құюлар графы.

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

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

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

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

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

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

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

1. 
   Положить L := {x₀}, M :=  , Г(x₀) := , h(x₀) := 0, t:=0;
   

2. M: = M UL;

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

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

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

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

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

х₀ төбесінен у₀ төбесіне жеткізетін ең қысқа жолды табу үшін кестеден Г(у₀) мәнін табамыз және одан қандай да бір у₁  Г(у₀) төбесін аламыз. у₁ төбесі үшін Г(у₁) мәнін табамыз да, одан қандай да бір у₂  Г(у₁) төбесін аламыз. Осылай жалғастыра келе х₀ төбесіне келеміз ( бұл төбе үшін Г(х₀)=0). Мысалы, у₀=440 алсақ мынадай тізбек аламыз: у₀ = 440, у₁ = 143  Г(440), у₂ = 152  Г(143), у ₃ = 602  Г(143), у₄ = 620  Г(602), у₅ = 323  Г(620), у₆ =350  Г(323), у₇ = 800, Г(800) = 0. Демек, 800 төбесінен 440 төбесіне жеткізетін ең қысқа маршрут: 800, 350, 323, 620, 602, 152, 143, 440.

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

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

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

1. 
   Al2 алгоритмін (G, х₀) жұбына қолдану.
   
2. 
   у:=у₀, u:u=у₀.
   

3. 
   Г(у) табу және Г(у)=0 екендігін тексеру. Егер шарт дұрыс болса, «х₀-ден у₀-ге апаратын жол жоқ» деген хабар баспаға шықсын.
   
4. 
   x₀  Г(у). екендігін тексеру. Егер дұрыс болса, соңына көш.
   
5. 
   Қандай да бір zГ(у) төбесін алу. Анық болу үшін Г(у) тізіміндегі бірінші төбені аламыз да у:=z және u:=z,u 3 қадамға көш.
   
6. 
   Мұндағы z,u z-ті u тізбегінің басына қосқандағы нәтижені білдіреді.
   

Қосымша әдебиет: 7[88-130] .

Бақылау сұрақтары:

1. 
   Маршруттың, шынжырдың, қарапайым шынжырдың, тұйық маршруттың, циклдың, қарапайым циклдың анықтамаларын беріңіз.
   
2. 
   Маршрут ұзындығы не?
   

4. Граф төбелерінің арасындағы ұзындығы к-ға тең маршруттың бар екендігін қалай анықтауға болады?

5. Графтың екі төбесін қосатын ең қысқа жолды табудың алгоритмі.