Графикалық торлар

Жоспар

Графикалық торлар.бұл техника мен ұйымдастыру жүйелерді графика арқылы көрсету әдісі. Ғылыми жұмыстарды графикамен көркемдеу нақты мәнін көрнекілігімен көрсетеді, кей жағдайда қойылған міндеттің шешімін табуды тіпті жеңілдетеді. Әр түрлі көрнекілікті графикамен көрсетудің әмбебап құралы ретінде граф табылады. Мұнда граф деп, торап пен қырлардың жиынтығын түсінеді. (4.6.сурет). Түрлі торап пен қабырғалардың сан алуан құрамалары ,мүмкін болатын графтар мен олардың қолдану жолдарын көрсетеді. Қабырға бағыттары көрсетілмеген, ал тораптар төртбұрыш түріне келтірілген графтар техникалық жүйелердің құрылымын көрсетуге қолданылатын блоксхемаларды суреттейді. 4.6.суретте көрсетілген графты ағаш деп атайды. Мұндай ағаш.граф арқылы толық санды бағдарламалау міндетін қарастыратын бұтақтар мен шекаралар әдісін қөркемдейді. Егер ағаштағы баоылық тораптар бірнеше деңгейге бөлінсе, онда оны көп деңгейлі иерархия жүйесі деп білеміз. Егер граф қабырғасы бағытқа ие болса, яғни доға арқылы жүзеге асса, ондай графты тор деп атайды. Тор арқылы орын ауыстыру немесе уақыт бойында орындалатын жұмыстардың тиімді шешімін табудың түрлі міндеттері көрсетіледі. Тор доғалардың құрылым мен параметрлері сипатталады. Тор құрылымы, немесе оны топология деп атайды, байланысшы доғалардың юағытын және тораптарын өзара қалай байланысатынын көрсетеді. Әрбір торапты реттік санмен белгілейді. Бастапқы торапты бастау деп,ал соңғысын ағаш деп атайды.

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 21 бет
Таңдаулыға:

Графикалық торлар

Графикалық торлар-бұл техника мен ұйымдастыру жүйелерді графика арқылы
көрсету әдісі. Ғылыми жұмыстарды графикамен көркемдеу нақты мәнін
көрнекілігімен көрсетеді, кей жағдайда қойылған міндеттің шешімін табуды
тіпті жеңілдетеді. Әр түрлі көрнекілікті графикамен көрсетудің әмбебап
құралы ретінде граф табылады. Мұнда граф деп, торап пен қырлардың жиынтығын
түсінеді. (4.6-сурет). Түрлі торап пен қабырғалардың сан алуан құрамалары
,мүмкін болатын графтар мен олардың қолдану жолдарын көрсетеді. Қабырға
бағыттары көрсетілмеген, ал тораптар төртбұрыш түріне келтірілген графтар
техникалық жүйелердің құрылымын көрсетуге қолданылатын блоксхемаларды
суреттейді. 4.6-суретте көрсетілген графты ағаш деп атайды. Мұндай ағаш-
граф арқылы толық санды бағдарламалау міндетін қарастыратын бұтақтар мен
шекаралар әдісін қөркемдейді. Егер ағаштағы баоылық тораптар бірнеше
деңгейге бөлінсе, онда оны көп деңгейлі иерархия жүйесі деп білеміз. Егер
граф қабырғасы бағытқа ие болса, яғни доға арқылы жүзеге асса, ондай графты
тор деп атайды. Тор арқылы орын ауыстыру немесе уақыт бойында орындалатын
жұмыстардың тиімді шешімін табудың түрлі міндеттері көрсетіледі. Тор
доғалардың құрылым мен параметрлері сипатталады. Тор құрылымы, немесе оны
топология деп атайды, байланысшы доғалардың юағытын және тораптарын өзара
қалай байланысатынын көрсетеді. Әрбір торапты реттік санмен белгілейді.
Бастапқы торапты бастау деп,ал соңғысын ағаш деп атайды.

4.6-сурет

Доғаны қосарланған индекспен белгілеиді. Жалпы i-j деп көрсетеді, онда i
доға шығатын тораптың нөмеірі, j-доға кіретін торап нөмірі деп
қабылданады. Әрбір доға өз сипатына ие болады. Мысалы, ti – j доға бойымен
қозғалу мерізімі, ci-j- орын ауыстыру құны, di-j доғаның өткізу қабілеті,
т.б.

.7-сурет

Тордың құрылымын және доға сипатын біле отырып, ғылыми-ерттеулерде жиі
кездесетін түрлі есептерді шешуге болады.
1. Жылжу есептері.
а) Коммивояжер есебі 4.8-суретте көрсетілгендей, орналасқан 5 пункт бар,
олардың бір-бірімен байланыс арқылы әр бір пункттен кез келген басқа
пунктке өтуге болады. Мұнда қойылатын талап: белгілі бір пункттен шығып
ең аз уақыт ішінде барлық пункттерді айналып шығу.

4.8-сурет

Бұл есепті шешу үшін математикалық модель құраймыз. Ол үшін белгілерді
енгіземіз:i және j-кіру-шығу пункттерір нөмірі, tij- I пунктіне жүру
уақыты 4.10-кестеден көрінетіндей, tij жалпы кері бағыттағы tij уақытына
тең болмайды.

4.10-кесте
I пунктінен J пунктіне
1 2 3 4 5
1 0 10 25 25 10
2 1 0 10 15 2
3 8 9 0 20 10
4 14 10 24 0 15
5 10 8 25 27 0

Математикалық модельді құру үшін бізге белгілі қисынды буль ауыспалы
мәндерді аламыз.

деп қабылдаймыз.

4.9-сурет

4.9-сурет
Модель құраймыз. Пункт 1-ден кез-келген төрт пункттің бірекіне шығуға
немесе осы пункттің өзінде қалуға болады. (4.9-сурет). Бұл жағдайда бір
бағытта шығуға болады. Бұл шартты мынадай түрде жазамыз:

δ 11+δ 12+δ 13+δ14+δ15=1

жалпы бұл шарт былай жазылады:

5
∑δ
j-1

Егер пункт 1-ден кез келген i-пунктіне шығатын болсақ, онда ол былай
көрсетіледі:

5
∑ δij=1,i=1,5 (4.14)

j=1

Бұл тәуелділіктер бастапқы талапты орындауға мүмкіндік береді: әрбір
пункттен тек бір қана және бір бағытта жүруге болады. Бағдартың ең аз
ұзақтық талабын мақсатты функция түрінде жазамыз:

А=t11δ11+t112δ12+t13δ13+t14δ14+t15δ 15t+t21δ21+t22δ22+...+t55δ55→ min,
(4.15)

Мұнда tij мәндері 4.10-кестеден алынады, ал δij ізделіеген ауыспалы
мәндер болып келеді. Жазудың қысқартылған түріне көшсек, ол огсындай
болады:

(4.16.)

Жүйе шешу нәтежесінде (4.16) келесі мәндерді аламыз:
δ15=δ52+δ23+δ34+δ41=1 қалғаны F=10+8+10+20+14=62 болады. Бұл бағдар 4.10-
суретте көрсетілген.

4.10-сурет

4.11-сурет

Егер жеке жағдайдан айырылсақ, есептің n пункттердің айналып шығу жалпы
талабын орындау үшін былай жазамыз:

(4.17.)

Сонымен қоса 4.16 және 4.17 шарттарды қанағаттандыратын бағдар бар: жылжу
барысында үзілістер болады, бірақ әр пункттен бір рет кіріп-шығу шарты
орындалады (4.11-сурет). (4.16) және (4.17( жүйесі қажетті, бірақ
жеткіліксіз шарттарды қамтиды. Ол үшін қосымша N шектеулер енгізіледі:
N=(n-1)²-(n-1), әр бір шектеу мынадай түрде болады:

Yi-yjnδij≤n-1; i=2,n; j=2,n-∞yij∞.

(4.18)

Біздің мысалда мұндай қосымша шектеулер саны N=(5-1)²-(5-1)=12 тең
болады. Олардың түрі мынадай болып келеді.

Y2 − y3 + 5δ23 ≤ 4 ; y2 − y4 + 5δ2 4≤ 4 ; y2 – y5 + 5δ25 ≤ 4 ;
Y3 – y2 + 5δ32 ≤ 4 ; ...; y5 – y4+5δ54≤4.

Сонымен есептің математикалық моделі ретінде (4.17) жүйесі мен қосымша
шектеулер (4.18) сеналады. Осындай коммивояжер есебі тәріздес ғылыми
мәселерді шешуде туындайтын көптеген есептер бар-қайсыбір бұйымды
өндеудің технологиялық үрдісін тиімді ұйымдастыру, базаларды
қамтамасыздандыру,ұйымдастыру және т.б.
б) Ең қысқа жолды іздеу есебі. 4.12-суретте көрсетілгендей А пунктінен В
пунктіне көп жолдар барады.

4.12-сурет

Кейбір жолдарда қозғалыс бір жақты, кейбіреуінде екі жақты. Екі пунктің
арасындағы жол ұзындығы әрбір доғада көрсетілген. сонда А пунктінен В
пунктіне ең қысқа жол табу қажет. Математикалық модель құраймыз. 4.13-
суретте көрсетілгендей пунктіне кіретін-шығатын доғаларды болжаймдайық:

4.13-сурет

Бағдар үзіліссіз болу үшін әрбір пунктке тек бір доға кіріп-шығу керек.
Бұл талап егер төмендегідей шарттар болса орындалады: Пунктке кіретін
доғалар үшін:

p
Nibx=∑δkj=1 (4.19)
k=1

Мұнда δki k пунктінен шығатын және i пунктіне кіретін доғағак сәйкес
келеді.

(4.19) шарт i пункітінен шығатын және j тіне кіретін доғаға сәйкес
келеді:

(4.20) шарты i пунктіне тек бір доғамен шығуды қамтиды.
Бағдардың барлық пунктерін бастапқы, өткелі және соңғы деп бөлуге болады.

Бұл пункттер үшін келесі шарт орындалу керек.

(4.21)

Шынымен, бастапқы пуект Nвх =0. Демек, бастапқы пункттен тек бір доға
шығу керек. Өткелі пункттер үшін Niвх=Niвых шарт бір доғамен шеғу-кіруді
қамтиды. Соңғы пункт үшін Nвых= 0 кіруді бір

доғамен қамтиды. Сонымен (4.20-4.21) шарттары үзіліссіз бағдар талабын
орындайды. Мұнымен қатар бағдар ең аз ұзындыққа ие болу үшін мақсатты
функцияны қосамыз:

F=∑ ∑ Cijδij (4.22)
i j

Мұнда Cij –жол ұзындығы, ол барлық доғаларды қамтиды "Шектеулер" мен
мақсатты функцияны қосқанда жүйені былай жазамыз:

F= ∑ ∑Cijδij→min

i j

δij ≥ 0

бұл ауыспалы мәндерге теріс емес талабының қойылғаны жеткілікті, яғыни
δij ≥ 0.

δij= 0 немесе δij= 1 талабын қоймаса да болады, себебі мұндай
есептерде шектеулер арқасында шешу барысында δij тек 0 немесе 1 мәнін
алуды қамтиды.

4.12 берілген суреттегі есепке 4.23 жүйесін құраймыз, ыңғайлы болу үшін
бұл жүйені 4.11-кесте ретінде көрсетеміз.

Пункт δ12 δ13 δ14 δ23 δ25 δ32 Δ34 δ35 δ43 δ45 белгі Оң жол
F 2 6 8 3 7 5 1 5 4 2 min 1 -1 -1 -1 = -
1 2 1 -1 -1 1 = 0 3 1 1 -1 -1 -1 1 =
0 4 1 -1 -1 = 0 5 1 1 1 = 1
Мұндай әрбір доғаға ауыспалы мән, әрбір пунктке шектеу сәйкес келеді.
Кестеде көрсетілген шамалар ауыспалы мәндердің шектеулерге кіретін
коэффициентерін нұсқайды. Мысалға, 2

пунктін шектер түрі δ12 – δ23 – δ25 +δ32 = 0 болады, мұнда (+) белгісі
кіретін доғалар алынада, (-) белгісі шығатын доғалар алынада қойылған.
Есепті шешу нәтежесінде келесі мәндерді аламыз: δ12=δ23=δ34=δ45= 1.
Қалған δij= 0 ең қысқа бағдар δij= 1 доғаларды қамтиды. Бұл бағдар 4.14-
суретте көрсетілген. барлық пункттерден өтуіне қарамастан, оның ұзындығы
ең аз мәнге
F=2+3+1+2=8. Байқауға болатындай, бір өтпелі пункттен өтетін бағдартар ең
ұзын болып келеді. (1-2-5=2+7+9=1-3-5=6+4=10, 1-4-5=8+2=10).

4.14-сурет

Практикалық есептерде үлкен бағдарларды байқау қиын, ал мүмкін варианттарды
жалпы терудің күрделілігі бар. Сондықтан қысқа жолды жолды табудың бұл
тәсілі ең тиімді және қарапайым болып табылады. Жалпы жағдайларда түрлі
практикалық есептерді шешуде i-j доғаларға түрлі мағыналарды беруге болады:
ұзақтық, құны, еңбек көлемі т.б. Осындай қысқа бағдар таңдау есептері
тәріздес деп, ғылыми техникалық мәселелерді шешуде туындайтын түрлі
есептерді қабылдауға болады.

Граф теориясының негізгі түсініктері.

Формальдық көзкарас бойынша граф G=(V,E) жиындарының реттелген жұбы,
олардың біріншісі төбеле мен түйіндерден тұрады, ал екіншісі – олардың
қабырғаларынан. Қабырға екі төбені қосады. Біз графтармен жұмыс істеген
кезде, графтың бір төбесінен екінші төбесіне қабырғалардан тұратын жолды
қалай жүргізу керектігі жиі қызықтырады. Сондықтан біз қабырға бойымен
қозғалысты айтқан кезде, біз АВ қабырғасымен қосылған А төбесінен басқа В
төбесіне өті деп түсінеміз. Осы жағдайда біз төбесі В төбесі көрші бір
бірімен түйіседі деп айтамыз.
Граф бағдарланған әлде бағдарланбаған болады. Бағдарланбаған графта
қабырғаны екі бағытта да өтуге болады. Осы жағдайда қабырға реттелмеген екі
төбе, олардың соңы. Егер қабырға соңы дөп келсе, онда қабырға төбені өз-
өзімен қосатын тұзақ деп түсініледі. Бағдарланған графта немесе оргафта
қабырға екі төбенің қосады: біріншісі оның басы, екіншісі – соңы. Әрі қарай
біз қысқарту үшін тек жай қабырға туралы айтамыз, олардың бағдарланғаны
әлде бағдарланбағаны мазмұны арқылы түсінікті болады.
Кешірек біз графтарды жиындар арқылы емес жай сурет арқылы
көрсетеміз. Төбелер дөңгелектермен, ал қабырғалар сызықтармен бейнеленеді.
Дөңгелектер ортасында төбелердің белгісі жазылады. Орграфтың қабырғалары
жүруге болатын бағыттарды көрсететін жебелермен белгіленеді.
1.1 суретінде бағдарланған (а) және бағдарланбаған (б) графтар
олардың формалдық сипаттамасымен бірге көрсетілген.

Терминология

Толық граф – бұл әр төбе басқа төбелермен түгел қосылған граф. N
төбесі бар толық графтағы қабырғалар саны (N2-N)2 тең. Толық бағдарланған
графта бір төбеден екінші кез келген төбеге өту рұқсат етіледі. Графта
қабырғалар бойынша өту екі бағытта да рұқсат етілгендіктен, ал орграфта тек
бір бағытта болғандықтан, толық орграфта қабырға саны екі есе көп немесе
олар саны (N2-N)тең.
Графтың (Vs, Es) ішкі графы әлде (V, E) орграфы Vs(V ішкі жиыннан
және оларды қосатын қабырғалардың кейбір ішкі жиынан Es(E тұрады.
Графтағы әлде орграфтағы жол дегеніміз кезекпен өтетін қабырғалар
қатары.
Басқаша айтқанда А төбесі В төбесіне дейінгі жол А-дан басталып В
төбесіне жеткенге дейінгі қабырғалар тізбегімен өтеді. Формалдық көзқарас
бойынша Ui төбесінен Uj төбесіне дейінгі жол бұл графтың UiUj+1, Ui+1Uj+2
...Uj-1Uj қабырғалар тізбегі. Сонымен қатар, осы жолда кез келген төбе бір
реттен артық кездеспеуін талап етемыз. Кез келген жолдың ұзындығы –
олардағы қабырғалар саны AB, BC, CD, DE жолының ұзындығы 4-ке тең.
Орграфта әр қабырғаға қабырға салмағы деп аталатын сан бекітілген.
Графты бейнелеу барысында қабырға жанына қабырға салмағын жазамыз.
Формалды сипаттау кезінде салмақ реттелген әлде реттелмеген төбелер жұбына
қосымша элемент болады. Бағдарланған графтармен жұмыс істеген кезде қабырға
салмағын онымен өту бағасы деп санаймыз Мысалы, егер P1 жолы жалпы салмағы
24 болатын бес қабырғадан тұрса, ал P2 жолы – жалпы салмағы 36 болатын үш
қабырғадан болса, онда P1 жолы қысқалау деп саналады.
Егер кез келген түйін жұбын кем дегенде бір жолмен қосуға болатын
болса, онда граф әлде орграф байланысты деп аталады. Цикл дегеніміз бұл бір
тқбеден басталатын және осында аяқталатын жол.

Графтарды көрсетудегі мәліметтер құрылымы.

Графтар және орграфтар туралы ақпаратты екі әдіспен сақтауға болады:
түйіскен матрицалар түрінде әлде түйісулер тізімі ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.