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

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 6 бет
Таңдаулыға:

Графиктегі ең қысқа жолды табу
КІРІСПЕ
1. Теориялық бөлім
1.1 Графтар теориясының негіздері
1.2 Темір жол стансаларынан тұратын граф салу
2. Дейкстра алгормін игеру
2.1 Қысқа жолды іздеу алгоритмдері
2.2. Қысқа жолды іздеу процесі
3. Практикалық бөлім
3.1 Екі стансаның арасындағы тарифтік арақашықтықты
КІРІСПЕ

Жергілікті тарифтерді тeмip жолдың басшылары белгілейді. Жүктерді тасымалдағаны үшін төленетін ақы және түрлі жинақ, қойылымдары кіретін бұл тарифтер берілген темір жол шеңберінде қызмет етеді.
Темір жол бойымен жүк үлкен, жолаушылар немесе жүктік жылдамдықпен тасымалдануы мүмкін. Жылдамдық түpi жүктің тәулігіне қанша килoметр жүруі тиіс екенін анықтайды.
Тарифтік қашықтық осы тасымалдау ара қашықтығы болып табылады. Тасымалдау ақысы ең қысқа бағыттағы ара қашықтық бойынша алынуы мүмкін, жүктік немесе үлкен жылдамдықпен жүктерді тасымалдау кезінде тарифтік қашықтыққа немесе габариттік емес жүктерді немесе жүктерді жолаушылар жылдамдығымен тасымалдау кезінде нақты өткен кашықтық үшін алынуы мүмкін.
Жүктердің тасымалдауы жүргізілетін вагон типі түрліше келеді.Темір жол бойымен жүктер әртүрлі, арнайы немесе изотермиялық вагондарда, цистерналарда немесе платформаларда тасымалдануы мүмкін. Тасымалдау ақысы әр жағдайда әр түрліше болады.Тасымалданатын жүктердің саны -- тасымалдауға маңызды әсер ететін фактор.
Дипломдық жұмыстың мақсатына орай бұл тарифтік қашықтықты есептеуге графтар көмекке келеді.Яғни,Дейкстра алгоритмін тақырыпқа сәйкес темір жол логистикасында қолданылу аясында графтар негізгі рөл атқарады.
Графтар теориясы - графтардың қасиетін оқытатын дискретті математиканың бір бөліміне жатады. Графтар теориясының практикалық мүмкіндіктері өте зор. Түрлі білім салаларында, мысалы психология, химия, электротехника, сонымен қатар көлік тасымалдауда, басқаруда, сауда-саттықта жəне білім беруді жоспарлауда туындайтын кейбір проблемалар графтар теориясының мəселесі ретінде қалыптасуы мүмкін. Осы жағдайларға байланысты графтар теориясы өз алдына қызықты деп қана саналмай, алынған нəтижелерін жинақтайтын, біліктендіретін, жалпылайтын жəне жан-жақты тарататын білімнің түрлі аймағындағы басты негіздерін көрсетеді.Мысалы, графтар теориясы геоақпараттық жүйелерде де қолданылады. Жаңадан жоспарланған немесе салынған үйді қайта жоспарлауда, құрылыстарда, нысандарда жəне т.б. ол төбелері ретінде қарастырылса, олардың жолдарының бірігуін, инженерлік желілер, электротасымалдау желілері жəне т.б. - оның қабырғасы ретінде қарастырылады. Сонымен қоса, ең қысқа айналу жолын немесе ең жақын азық-түлік дүкенін табу сияқты графтардан шығатын түрлі есептеулерді қолдану тиімді бағдарларды жоспарлауға мүмкіндік береді.
Бүгінгі таңда көптеген адамдар маршрутты құру үшін навигаторларды, электронды карталарды пайдаланады. Бұл уақытты қысқартуға, жолды алдын-ала жоспарлауға мүмкіндік береді. Қала масштабындағы навигациядан бастап ғимарат ішіндегі навигацияға дейін бәрі мобильді немесе веб - қосымшалар арқылы жүреді.
Web-қосымшаның қарапайым сайттан айырмашылығы пайдаланушының ресурстағы деректермен өзара әрекеттесуі болып табылады. Ол әр түрлі нысандарды толтыра алады, жеке кабинет арқылы тапсырмаларды орындай алады және т. б.
Бұл жұмыстың мақсаты Дейкстер әдісімен екі станция арасындағы тарифтік қашықтықты табу бойынша сервисті әзірлеу және іске қосу болып табылады. Осы міндетке сәйкес іске асырудың оңтайлы әдістерін таңдау қажет, олардың өлшемдері пайдалану ыңғайлылығы, деректерді өңдеу жылдамдығы, нәтижелердің көрінуі мен дәлдігі болып табылады. Ол үшін таңдау керек:
1) бағдарламалау тілі
2) web-сервер
3) ең қысқа жолды табу алгоритмі
4) қосымшаны әзірлеу құралдары
Теориялық бөлім
1.1 Графтар теориясының негіздері

Графтар ғылым мен практиканың түрлі салаларындағы математикалық модельдердің маңызды элементтері болып саналады. Графтың көмегімен автоматика, электроника, физика, химия жəне т.б. сияқты білім аймақтарында жинақталған мəселелерді шешуді жеңілдетуге болады. Графтың көмегімен жол, газ құбырлары, жылу жəне электр желілерінің сұлбалары бейнеленеді. Сонымен қатар графтар математикалық жəне экономикалық есептерді шешуде үлкен көмек көрсетеді.
1.1. Граф жəне оның түрлері
Бөлімімізді графтар теориясының негізгі ұғымдарынан бастайық. Осы ұғымдарға негізделген бірнеше нəтижелерді келтірейік.
Граф анықтамасын қарапайым сөзбен түсіндірсек ол нүктелер жиынынан (графтың төбелері) тұратын жəне осы нүктелер жиынын қосатын түзу немесе қисық кесінділерден (граф қабырғалары) тұратын сұлбаны айтамыз. Граф G=(V, E) екі жиыннан, яғни шекті жиындар элементтерінен тұрады. Бұл жерде G - граф, ал V - графтың төбелері, E - графтың қабырғалары деп аламыз.

Графтар, негізінен, геометриялық фигура түрінде бейнеленеді, сондықтан графтың төбелері нүкте арқылы, қабырғалары нүкте- лерді бір-бірімен қосатын сызықтар арқылы бейнеленеді .
Графтың шеткі төбелері бірдей болса, онда барлық қабырға- лары параллель болып табылады. Ал, егер қабырғасының басы мен соңы бір төбеде орналасса , онда оны ілмек деп атаймыз. Жалпы айтқанда, ілмектің бағыты болмайды. Бірақ бағытталған графтарды аралас графтардан ажырату үшін бағытталған графтарда ілмектің бағыты көрсетіледі.
Ілмек - бұл бастапқы жəне шеткі доғаның бір-бірмен сəйкес- тенуі.
Ілмексіз жəне параллель қабырғасыз графтар қарапайым граф деп аталады. Графтың төбелерінің жиыны n элементтен тұратын болса, онда G граф n-ретті граф болады.
Қабырғалары жоқ графтар бос граф деп аталады . Ал, егер графтың төбелері жоқ болса (онда əрине қабырғалары да жоқ), онда мұндай граф нөл-граф деп аталады.
Графикалық графтар диаграмма түрінде де берілуі мүмкін, онда төбелері нүктемен немесе дөңгелекпен, ал қабырғалары сəйкес қабырға төбелерінің шеттеріндегі нүктелер немесе дөң- гелектерді қосатын сызық кесінділермен бейнеленеді .
Графтарды суретте немесе сұлбада бейнелегенде кесінділері түзу сызық немесе қисық сызық түрінде, ал кесінділердің ұзындықтары мен нүктелердің арақашықтықтары əртүрлі түрде берілуі мүмкін. Əрбір қабырға жұптасқан төбелер арқылы анықталады. Егер графтың қабырғалары реттеліп жұптасқан төбелер арқылы анықталса, онда G бағытталған граф (сызықтары доға түрінде болады) деп аталады. Кері жағдайда, оны G бағытталмаған граф (сызықтарының бəрі қабырғасы болып табылады) деп атаймыз.
Егер графтың əртүрлі екі төбесі бір-бірімен тек қана бір қабырға арқылы қосылған болса, онда ол толық граф деп аталады. Əртүрлі төбелерінің əрбір жұбы көршілес болатын қарапайым графты толық граф деп те атауымызға болады. n төбесі бар
толық граф n(n−1) қабырғадан тұрады жəне K деп белгіленеді 2n
n - 1 дəрежелі граф тұрақты граф болып табылады.

Графтың толық болуы немесе болмауы оның жалпы сипаттама- сына байланысты болады.
Графтың төбелерінің əрбір жұбы бір бағытталған қабырғамен дəл қосылған болса, ондай графтарды толық бағытталған граф деп атаймыз. Егер толық бағытталған графтың əрбір қабырғасында көрсетілген бағыттарын алып тастасақ, онда ол бағытталмаған қабырғалары бар толық графқа айналады.
Графтың төбелері бір-бірінен олардың қанша қабырғаға жататындығына байланысты ажыратылады.
Егер графтың қабырғасының ұштарының орналасу реті еске- рілмейтін болса, онда оны бағытталмаған қабырға деп атайды.
Егер графтың қабырғасының ұштарының орналасу реті ескерілетін болса, онда оны бағытталған қабырға деп атайды. Бұл жағдайда g(xi, xj) қабырғасының басы xi төбесі, ал соңы xj төбесі деп аталады.
Бағытталған қабырға графтың доғасы деп те аталады.
Егер графта бағытталған жəне бағытталмаған да қабырғалар бар болса, онда оны аралас граф деп атайды.
G(X) графындағы əрбір қабырғаның бағытын қарама-қарсыға (керіге) өзгерту арқылы оған кері граф G-1(X) аламыз. Яғни, əрбір бағытталған графқа кері граф бар.
Бағытталмаған толық граф деп кез келген xi, xj О X (i!=j) үшін қабырғалары əртүрлі g(xi, xj) жұптары болатын U(X) графын атайды .
Кез келген екі төбесі бірнеше қабырғалармен немесе доғалармен қосылған графты мультиграф деп атайды.
Қабырғалары G(X) графымен бірге толық U(X) графын беретін Gk(X) графын G(X)-тің толықтаушы граф деп атайды.
Графтағы барлық қабырғалары əр түрлі болатын жолдың бағытын тізбек деп атаймыз. Егер графтың барлық ... жалғасы

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