Графтар теориясы

МАЗМҰНЫ
КІРІСПЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...3
I. ГРАФТАР ТУРАЛЫ НЕГІЗГІ МӘЛІМЕТТЕР ... ... ... ... ... ... ... ... ... ... ... ...7
1.1. Тарихи анықтама ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...7
1.2. Графтар теориясының негізгі терминдері және теоремалары ... ... ... ... 14
1.3. Графтағы әртүрлі есептердің сипаты ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...20
II. ТОРЛЫҚ ЕСЕПТІҢ ЭКОНОМИКАЛЫҚ ҚОЙЫЛУЫ ... ... ... ... ... ... ... 21
2.1. Есептің торлық ұсынылуы және торлық модельдерді құру ережелері ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .21
2.2. Ең кіші жолды табу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .24
2.3. Бір торлық есепті шешу үшін динамимкалық программалау әдісі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..27
2.4. Рационалды тасымалдап . жинақтау маршруттарын анықтау алгоритмі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 36
III. Графтағы ең кіші ара қашықтықты анықтау программасы ... ... ... ... ...48
3.1. Торлық транспорттық есептің қойылымы ... ... ... ... ... ... ... ... ... ... ... ... ..48
3.2. Әдістің және есептеу алгоритмінің сипаты ... ... ... ... ... ... ... ... ... ... ... ... ..49
3.2.1. Бірінші кезең: Ара қашықтықтың алғашқы кестесін құру ... ... ... ... ... .50
3.2.2. Екінші кезең: и анықтау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...50
3.2.3. Үшінші кезең: Ең кіші жолдың ұзындығын табу ... ... ... ... ... ... ... ... ... ..50
3.2.4. Төртінші кезең: Ең кіші жолды табу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..50
ҚОРЫТЫНДЫ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..52
ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ ... ... ... ... ... ... ... ... ... ... ... ... ... .54
ҚОСЫМША 1 Жаттығулар
ҚОСЫМША 2 Ең кіші ара қашықтықты табу туралы есептің программасы
КІРІСПЕ
Дискреттік программалау – ол ақырлы жиындар мен бүтін сандық торларда экстремальдық есептерді зерттейтін математикалық программалаудың бір бөлімі. Математиканың өз ішінді дискреттік программалау мәселесі, оны «дискреттік және бүтін сандық» математикамен (сандар теориясы, дискреттік талдау, математикалық логика, графтар теориясы, комбинаторлық талдау) жақындастыра түседі [1 - 3].
Экономиканың, басқарудың, жоспарлаудың және әскери істердің көптеген есептері дискреттік программалау терминдері арқылы тұжырымдалады. Мысалы: өнеркәсіпті орналастыру мен мамандандыру есебі, ауылшаруашылық есептері және тағы басқалар.
Дискреттілік және бүтін сандық сонымен қатар логикалық шарттары бар есептерде де пайда болады.
Дискреттілік пен бүтін сандықтың тиімдестіру есептерінде пайда болуының бірнеше мысалын қарастырайық[3, 4 - 6]:
а) факторлардың физикалық тұрғыдан бөлінбеушілігі: мысалы, 1,5 домна пешін тұрғызуға немесе 3,8 ұшақ сатып алуға болмайды. Әдетте бүтін сандық программалау есептері келесі түрде қойылады:
(1)
функциясының максималды мәнін келесі шарттарды қанағаттандыратындай етіп табу керек.
(2)
(3)
бүтін сандар (4)
б) комбинаторлық есептер (яғни, ақырлы жиындардағы есептер). Мысалы кезбе саудагер туралы есеп (коммивояжер есебі). Комбинаторлық есептің тағы бір мысалы, ол көпке белгілі кесте теориясының есебі (күнтізбелік жоспарлау есебі). Тағы да бір өте қажетті мысал: әртүрлі өнім өндіретін
ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ
1. Белов Теория Графов, Москва, «Наука»,1968.
2. Новые педагогические и информационные технологии Е.С.Полат, Москва, «Akademia» 1999 г.
3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.
4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.
5. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ, 1992.
6. Оре О. Теория графов. – М.: Наука, 1980.
7. Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по куpсу: Дискpетная математика по теме: Алгоpитмы на гpафах. - М.: МГТУ, 1995
8. Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992
9. Hечепуpенко М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и сетях. - Hовосибиpск: Hаука, 1990
10. Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: Hаука, 1977
11. Писсанецки С. Технология разреженных матриц. - М.: Мир, 1988
12. Севастьянов Б.А. Вероятностные модели. - М.: Наука, 1992
13. Бочаров П.П., Печинкин А.В. Теория вероятностей. - М.: Изд-во РУДН, 1994
14.Вентцель Е.С. «Исследование операций» М.: Сов.Радио 1972 г.
15.Захаров В.Н. «Алгоритмические методы решения задач оптимального планирования и управления» ВАД. 1986 г.
16.Зубов В.С. «Программирование на языке Turbo Pascal» М.: Филин 1997 г.
        
        МАЗМҰНЫ
КІРІСПЕ...................................................................
....................................................3
I. ГРАФТАР ... ... ... ... ... негізгі терминдері және
теоремалары................14
1.3. ... ... ... ... ЕСЕПТІҢ ЭКОНОМИКАЛЫҚ ҚОЙЫЛУЫ............................21
2.1. Есептің торлық ... және ... ... ... Ең кіші ... ... Бір ... есепті шешу үшін ... ... ... ...... ... анықтау
алгоритмі.................................................................
...................................................36
III. Графтағы ең кіші ара ... ... ... ... ... ... және ... алгоритмінің
сипаты..................................................49
3.2.1. Бірінші ... Ара ... ... ... ... ... и ... Үшінші ... Ең кіші ... ... ... ... Ең кіші ... ... 1 ... 2 Ең кіші ара ... табу туралы есептің программасы
КІРІСПЕ
Дискреттік программалау – ол ақырлы жиындар мен бүтін сандық торларда
экстремальдық есептерді зерттейтін ... ... ... ... өз ... ... программалау мәселесі, оны
«дискреттік және бүтін сандық» математикамен (сандар теориясы, ... ... ... ... ... ... ... түседі [1 - 3].
Экономиканың, басқарудың, жоспарлаудың және әскери істердің көптеген
есептері дискреттік программалау терминдері арқылы тұжырымдалады. ... ... мен ... ... ауылшаруашылық есептері
және тағы басқалар.
Дискреттілік және ... ... ... ... ... ... ... де пайда болады.
Дискреттілік пен бүтін сандықтың тиімдестіру есептерінде ... ... ... ... 4 - ... факторлардың физикалық тұрғыдан бөлінбеушілігі: мысалы, 1,5 домна
пешін ... ... 3,8 ұшақ ... ... ... ... ... сандық
программалау есептері келесі түрде қойылады:
(1)
функциясының максималды мәнін ... ... ... ... ... ... ... ... ... ... жиындардағы есептер). Мысалы
кезбе саудагер туралы есеп (коммивояжер есебі). Комбинаторлық ... бір ... ол ... ... кесте теориясының есебі (күнтізбелік
жоспарлау есебі). Тағы да бір өте қажетті мысал: әртүрлі өнім
өндіретін ... ... ... есебін
қарастырайық. Әрбір өнімнен сәйкесінше - нен кем емес өнім өндіру
керек. Әрбір кәсіпорын өнім ... ... және ... нұсқасы кәсіпорын үшін өндірудің ... ... ... өнім ... сәйкесінше
мөлшерде; келтірілген шығындар .
Шығын көлемі ең аз ... ... ... өнім түрлерінің
қажеттіліктерін қанағаттандыру керек.
айнымалысын енгізе отырып, математикалық моделін жазамыз.
(5)
функциясын
(6)
(7)
(8)
- ... ... ... отырып минимизациялау керек.
Дискреттік программалау есептерін шешу ... ... ... қолданылуы мүмкін:
1) (1) – (4) бүтін сызықтық программалау есебінің орнына, оған ... (1) – (3) ... ... есебін шешу керек;
2) толық алмастыру;
3) (1) – (4) бүтін сызықтық прогаммалау есебінің орнына, оған сәйкес
келетін (1) – (3) ... ... ... ... ... жақын
болатын бүтін санға «жуықтау» арқылы шешу керек.
Бірінші тәсіл шешімнің бүтіндігіне кепілдік бермейді. Екінші тәсіл
өлшемі үлкен ... үшін өте ... ... ... дәл ... ... ... сонымен бірге мүмкін болатын шешімдер жиынынан шығып кетуі
мүмкін.
Сонда да осы қысқартылған ... ... ... ... қима, комбинаторлық, жуық әдістерінің негізін қалайды.
Дискреттік программалаудың пайда болуын, қима әдісінің ... ... ... және ... ... ... дискреттік программалаудың нағыз дамуы, қима
әдісінің алгоритмін алғаш рет ұсынған Гоморидің еңбегінен кейін басталды.
Дискреттік программалауға Ю. ... ... бір ... ... пайда болуына дейін ... ... іске ... ... жоспарлаудың көпке белгілі құралы,
уақыттың көлденең шкаласында әрбір амалдың басы және ... ... ... ... Ганта. Қазіргі заманғы ... ... ... ... іске ... ... тиімділеуді қамтамасыз ететін, жоспарлаудың ең айқын және тиімді
әдістерін өңдеу қажет етілді. Сонымен қатар тиімділік қорларды қолданудың
экономикалық факторларының ... мен ... ... ... ... ... ... екі аналитикалық әдіс, құрылымдық
және күнтізбелік жоспарлауды өңдеу арқасында ... және ... жаңа ... болды. Бұл әдістер 1956 – 1958 жылдары ең кіші ара
қашықтық ... ... ... математика пәні ретінде Эйлермен оның Кенигсберг көпірі
туралы әйгілі талқылауында салынды. Бірақ Эйлердің бұл ... 1736 ... ... ... ... ... Графтар теориясының мәселесіне қызығушылық
өткен жүз жылдың ортасында жандандырылды және ... ... ... ... ... үшін ... себептер болды. Электр
тізбегін, кристалдар моделін, молекулалар құрылымын зерттеудің арқасында
жаратылыс ғылымдары өз ... ... ... ... ... графтар
теориясында бинарлық қатынасты үйренуге әкелді. Осы есептердің ішіндегі ... – 1850 жылы ... ... Де ... ... ... ... Графтар теориясы облысында ешқандай мәселе көп және күрделі
жұмыстар тудырған жоқ.
Осы жүз жылдың ... ...... ... ... жаңа ... ... графтар теориясының ауытқымай дамуының
куәгері болды. Бұл программалау, хабарламаларды жіберу теориясы, ... және ... ... ... қатар психология және биология
мәселелерін қамтиды.
Бұл дипломдық жұмыс үш тараудан тұрады: 1) Графтар ... ... 2) ... ... ... ... 3) Графтағы ең кіші
ара қашықтықты анықтау ... ... ... ... ... ... негізгі терминдері және теоремалары; Екінші тарауда:
Есептің торлық ұсынылуы және торлық модельдерді құру ... ең ... ... бір ... ... шешу үшін ... программалау әдісі,
рационалды тасымалдап – жинақтау маршруттарын анықтау алгоритмі, торлық
бөлшек – ... ... ... шешу ... ... ... тарауда: торлық транспорттық есептің қойылымы, әдістің және
есептеу алгоритмінің сипаты, бірінші кезең: ара қашықтықтың ... ... ... ... и ... ... кезең: ең кіші
жолдың ұзындығын табу, төртінші кезең: ең кіші жолды табу қарастырылады.
I. ГРАФТАР ТУРАЛЫ ... ... ... ... ... – бұл ... объектілерді зерттеуге геометриялық
жақындау болатын дискреттік математика облысы. Графтар теориясы ... ... оны ... ... ... ол ... ... математиканың, алгебраның, геометрияның, матрицалар
теориясының, ойындар ... ... ... және ... басқа да көптеген бөлімдерімен қиылысады[1].
Төбелері мен ... ... ... ... ... граф деп ... доғалары бар графтарды тор деп атайды.
Графтар теориясының алғашқы ... ... ойын – ... ... ... ... ... алғашқы нәтижелерінің
бірі Кенигсберг көпірі туралы есепті шешу кезінде Л. ... ... ... ... ... ... шығудың болу критерилері
болды. 1736 жылы 13 ... ... ... ... ... Кенигсберг
қаласында орналасқан арал туралы есеп ұсынылды, одан жеті көпір ... ... ... ... бір рет өтіп, ... ... ... ... ... Дәл осы ... маған оны әлі ешкім жасай алмағандығы
хабарланды, бірақ ешкім дәлелдеген жоқ, бұл ... ... Бұл ... ... да, ... оны шешу үшін геометрия, алгебра, комбинаторлық
өнер қажет емес болғанымен назар аударуды қажет ететін ... ... ... ... мен дәлелденген дәлелдемеге негізделген жеңіл ... оның ... ... ... ... кез келген сан арқылы және
қалай болса ... ... ... ... айналып шығу мүмкін бе немесе
жоқ па екендігін анықтайды”. Кенигсберг ... ... ... ... болады:
Эйлер ережесі
1. Тақ дәрежелі төбесі жоқ графта графтың кез келген ... ... ... ... шығу болады.
2. Тек қана екі тақ дәрежелі төбесі бар графта басы тақ ... ... және соңы ... ... айналып шығу бар.
3. Екіден көп тақ дәрежелі төбесі бар графта айналып шығу ... ... ... ... тағы бір есеп бар. ... ... рет өтетін жолды іздеу қажет етілетін есептер ... ... ... тек қана бір рет ... цикл гомильтонды сызық деп аталады.
Өкінішке орай, берілген граф гомильтонды ... ... ... және
егер болса, онда осындағы барлық гомильтонды ... ... ... ... ... ... ... тұжырымдалған төрт бояу мәселесі ойын – ... ... ... оны шешу үшін ... ... және қолданбалы мәндері
бар кейбір графтарды зерттеуге әкелді. Төрт бояу ... ... ... ... картаның облысын кез келген екі көршілес
облыстары әртүрлі түстерге ... төрт ... ... бола ... туралы болжам XIX ғасырдың ортасында тұжырымдалды. 1890 жылы
әлсіз тұжырым дәлелденді, кез келген жазық карта бес ... ... ... ... ... оған екі ... жазық графты салыстырып, графтар
терминінде эквивалентті тұжырымды алады: кез ... ... ... кіші ... дұрыс па әлде төртке тең бе? Есепті шешудің
көптеген ... ... ... бағытталған қатардың дамуына әсерін
тигізді. 1976 жылы дербес компьютердің қолданылуымен есептің оң ... жылы ... Э. ... оған ... тұжырым берді. Суретте
бейнеленген әрбір үш үйден газ, ... және суды ... ... су ... бір – ... ... әрбір үйді электр, газ және суды
қайнар көздерімен қосылуы үшін ... ... бола ма? ... айтқанда
көрсетілген алты нүктеде төбелері бар жазық граф ... бола ма? ... ... болмайды екен. Бұл туралы Куратов теоремасы деп аталатын –
маңызды теоремалардың бірінде айтылады. Теорема жазық емес ... граф ... ... ... ... ішкі графы ... ... ... ... ... шешу ... ... теориясына
қатысты нәтижелер алынатын жұмыстар пайда болды. Мысалы, Г. Кинхгоф токтар
және ... ... қуат үшін ... ... ... құру кезінде
графтардың осындай схемасын ұсынуды және осы графта қалған ... ... А. Кэли ... ... ... ... санау есебінен
шығып, берілген қасиеттермен басқаратын ... ... және ... келді және олардың кейбіреулерін шешті.
XX ғасырда графтарға байланысты есептер физикаға, химияға, биологияның
электротехникасына, экономикаға, ... ғана емес және ... ... ... ... ... сандар теориясы сияқты
бөлімдерінде пайда бола бастады. XX ғасырдың басында графтар ... ... ... және ... ... ... қойылуы үшін қолданыла бастады; сонымен қатар “граф” терминдер
қатарында басқа терминдер қолданылады, мысалы, карта, ... ... ... Д. Кениг монографиясы 1936 жылы жарыққа шыққаннан кейін
“граф” ... ... ... ең көп ... ... Бұл ... уақытта әйгілі фактілер жүйелендірілді. 1936 жылы Ойстен Ордың графтар
теориясына элементар кіріспесі мазмұндалатын кішкене кітапшасы ... ... ... ... математигі Клод Бердждың “Графтар теориясы және ... ... ... Екі ... та математикамен шұғылданатын
жанкүйерлер үшін назар аудартады.
XX ... ...... ... ... ... ... қатарының қалыптасуына әкелген, графтардың ... ... ... ... ... ... нәтижелер пайда
болды.
Қырықыншы жылдардың аяғы елуінші жылдардың басында графтар ... ... ... кең ... ... есептеу техникасы және
кибернетика дамыды. Есептеу техникасының дамуының, күрделі кибернетикалық
жүйелерді ... ... ... теориясына назар аударылды, графтар
теориясының мәселесі маңызды образбен толықтырылды. Сонымен қатар ... ... ... ... есептеудің көп мөлшерімен
байланысты практикада ... ... ... ... ... ... теориясының экстермальды есептерінің қатары үшін ... ... ... мысалы, осындай әдістердің біреуі тор ... ... құру ... ... ... ... ... Бұрын зерттелген
графтардың жеке кластары үшін ... ... ... үшін ... ... ... осы ... оңай табылады.
Графтар теориясының мәселесін сипаттап, кейбір бағыттар ... ...... ... ... ерекшелеуге болады.
Біріншіге мыналар жатады, мысалы, тағайындалған қасиеттерімен графтарда
атап өту және ... ... ... ... ... салу ... Геометриялық сипат графтар теориясы есептерінің көптеген циклдарын
тасиды, ... ... шығу ... ... графтары. Графтардың әртүрлі
классификациясымен байланысты бағыттар бар, ... ... ... қасиеті
бойынша.
Қасиеті тағайындалған графтардың болуы туралы нәтиженің мысалы, кейбір
графтардың төбелерінің деңгейлермен жүзеге асу критериінің ... ... ... ... ... ... ... төбелерін деңгейлермен қысқа
қыр және тұзақсыз жүзеге асыруға болады, егер кез келген үшін ... ... ... ... ... ... ... мысалы қырлар және
төбелерінің саны бірдей изоморфты емес графтардың ... табу ... ... бар изоморфты емес ағаштардың саны үшін асимтотты
формула алынды
Тұзақсыз изоморфты емес графтардың саны және ... ... үшін ... ... ... ... ... графтар теориясында есептің
арнайы циклдары бар. Олардың біреуінде графтардың байланыстылығының әртүрлі
қасиеттері зерттеледі, ... ... ... ... ... ... желісінің, электрлі схеманың, коммуникациялық тордың
сенімділігін талдау ... ... ... төбелерін біріктіретін,
қиылыспайтын тізбектер санын табу туралы ... ... ... ... қатары алынған. Мысалы, графтың екі аралас емес төбелерін бөліп
тұратын ... ең аз саны осы ... ... ... қарапайым
тізбектердің ең үлкен санына тең. ... ... ... ... ... ... және критериі табылды.
Басқа бағыттағы графтар ... ... ... қырлары немесе
барлық төбелері бар маршруттар оқытылады: барлық қырлары бар және әрбір
қырдан бір рет ... ... ... цикл ... ... ... жұп деңгейлері болғанда. Графтың төбелер жиынын ... ... ... ... төбелерінен бір рет өтетін циклдың болуының ... ... ... ... ... Графты бояумен байланысты
анықталған қасиеті бар, (қыр) ... ... ... ... аралас төбелер (қыр) әртүрлі жиындарға жатуы керек есептердің циклы
графтар теориясының арнайы сипаттамалық бағыты болады. Түстердің ең аз ... ... кез ... ... ... ... бояу ... тең, ал кез келген тұзақсыз графтың төбесін және ... бояу үшін түс ... ... да ... бар, ... ... ... бөлімдерінің әсерімен қосылды. Топологияның әсерімен әртүрлі
кеңістікте графтарды енгізу өңделеді. Мысалы, ... ... ... және ... ... ... граф жазық болады, егер ол бес төбелі
графтан қырларды бөлу ... ... ... ... ... графтардың автоморфизмдерінің топтары оқытылды. Әрбір соңғы топ
кейбір графтың автоморфты тобына ... ... ... теориясының әсері кездейсоқ графтарды ... ... ... ... ... үшін ... мысалы, барлық графтар
төбелермен байланысқан, диаметрі екі, ... ... ... ... ... ... есептерді шешудің арнайы әдістері бар.
Олардың біреуі төбесінен төбесіне тор ... ... ... ағын және ... ... қималардың минимал өту
қабілеттілігіне тең екендігін тұжырымдайтын, минимал қима және ... ... ... ... ... ... табудың әртүрлі тиімді
алгоритмдері құрылған.
Графтар теориясында алгоритмдік сұрақтар үлкен мәнге ие. Ақырлы графтар
үшін, қырлар және ... ... жиын ... ... ... ... ... шешудің алгоритмінің бар болу мәселесі, соның ішінде
экстремальды, оң шешіледі. Ақырлы графтармен байланысты ... ... ... нұсқаларының толық жиналуының көмегімен орындалуы мүмкін.
Бірақ, осындай әдіспен тек қана төбелер және ... саны көп ... үшін ... ... ... Сонымен графтар теориясы үшін маңызды
мән нақты және жуық шешімді ... ... ... ... ... үшін мұндай алгоритмдер құрылған, мысалы, максимал ағынды табу,
изоморфты ағашты анықтау, графтың жоспарлануын орнату үшін.
Графтар ... ... және ... тасымалдау туралы
транспорттық есепті шешу кезінде, тағайындау туралы есептің тиімді шешімін
табу үшін ... ... және ... өңдеу кезінде, жүктерді
тасудың тиімді маршрутын құру кезінде, сонымен қатар ... ... ... ... ... ... ... кезінде “тар орындарды” белгілеу үшін қолданылады.
1.2. Графтар теориясының негізгі терминдері және теоремалары
1. Граф - ... ... - ... жиын, ал -
тура туындының ақырлы жиыны. Сонымен қатар ... ... ... ал - ... ... ... ... кез келген ақырлы жиыны (төбе), олардың бағытталған жұп –
жұбымен біріктірілгендерін, граф ретінде қарастыруға болады.
3. Егер ... ... ... ... ... онда мұндай граф
бағытталған граф деп аталады.
4. Доға – бағытталған ... ... Граф ... деп ... егер оның қыры ... төбесі қырына инцидентті деп аталады, егер қыр ... ... ... да бір ... ... ... ... ішкі графы деп төбелер жиыны және
қырлар (доға) жиыны бар ... ... - дің ... ... дің төбелеріне инцидентті. Басқаша айтқанда ішкі графтар ... ... ... және ... ... Екі ... - ға жататын, тек қана сол қырлары бар, төбелер жиыны
болатын ішкі граф төбелер жиынымен ... ішкі граф ... Ішкі граф ... ішкі граф деп ... егер оның төбелер жиыны
графтың төбелер жиынына сәйкес келсе.
10. Төбелер аралас деп аталады, егер ... ... ... бар
болса.
11. және екі қыр аралас деп ... егер бір ... ... төбе бар ... ... ... қырларға сәйкес келетін сызықтармен біріктірілген,
төбелерге сәйкес келетін нүктелер жиынының кеңістігінде ұсынуға болады ... ... ... ... деп аталады.
13. Үш өлшемді кеңістікте кез келген графты тегістеу ретінде ұсынуға
болатындығы ... ... ... ... ... ... ... қиылыспайды. Екі өлшемді кеңістік үшін бұл мүлдем дұрыс емес.
Екі өлшемді кеңістікте тегістеу ретінде ұсынуға болатын ... ... ... Басқаша айтқанда, қырлары қиылыспайтын болып жазықтықта бейнеленуі
мүмкін граф жоспарланған деп аталады.
14. Графтың ... ... ... ... ... ... жағы деп аталады.
Берілген жақ ұғымы, маңызы бойынша, көпжақты жақ ұғымына сәйкес ... ... ... ... ... ... шығады. Егер көпжақ дөңес
болса, барлық ... ... оны ... ... ... ... әдіспен ұсынуға болады: көпжақтың бір жағын созамыз, ал ... осы ... ... ... ... ... ... граф аламыз. Біз созған жақ “жоғалады”, бірақ оған ... ... ... ... жақ ... келеді.
Сонымен, төбелер қырлар және көпжақтың жақтары туралы айтуға болады.
15. Қыры жоқ граф бос деп аталады. Әрбір екі төбесі ... граф ... ... ... емес әртүрлі қырлардың ақырлы ... ... ... деп аталады, егер төбелері әртүрлі болуы міндетті ... бар ... ... ... онда ... ... Барлық қырлары әртүрлі жұпты маршрут тізбек деп аталады.
19. ... ... ... ... цикл деп ... Егер тізбектің немесе
циклдың барлық төбелері әртүрлі болса, онда мұндай тізбек ... ... деп ... ... төбелері әртүрлі жақты маршрут қарапайым тізбек деп ... ... ... ... ... ... ... әртүрлі жұпты цикл
қарапайым цикл деп аталады.
22. Граф ... деп ... егер кез ... екі төбе үшін осы
төбелерді біріктіретін жол болса.
23. графының кез ... ... ... ішкі ... байланыс деп аталады.
24. Граф - байланысқан деп аталады, егер - дан аз ... ... ... ... ... ... Графтың барлық төбелерінен және қырларынан тұратын және ... бар ... ... айналма жолы деп аталады.
26. Маршруттың ұзындығы қырының жүру ... тең. ... ... біріктіретін қарапайым ең кіші ... және ... ара ... деп ... Төбе ... - төбесі инцидентті қырлар саны ... ... ... ... граф ... ... өтуге, графтарды қарапайым графтарға бөлуге болады.
Бір орынды амалдардың ішінде ең көп ... төбе ... ... және ... қырлардың бөлінуі.
Екі орынды амалдар белгілі: біріктіру, қосу, ... ... ... екі граф ... деп аталады, егер және төбелер
жиынының арасында және және қырлар ... ... ... ... ... ... үшін изоморфизм ұғымының көрнекі түсіндірмесі бар. Графтың
қырларын төбелердің түйіндерін біріктіретін оралымды жіп деп ... ... ... орын ... және ... ... ... ұсынуға
болады.
Теорема 1. графы берілсін, - төбелер жиыны, - қырлар
жиыны, онда ... екі ... саны ... ... тең.
Теорема 2. Ақырлы графта дәрежесі тақ төбелер саны жұп.
Теорема 3. Әрбір ... екі ... ... бір ғана жиында
болатындай оның төбелер жиынын екі бос емес ішкі жиындарға бөлуге болмайтын
жағдайда граф ... ... екі ... ... ара ... деп ... ... ең кіші тізбектің ұзындығы аталады.
Байланысқан графтың қасиеттері:
1. Байланысқан граф циклда бар қыр өшірілгеннен кейін байланысқан болып
қалады.
2. ... бар ... ... қыры ... ... ... ... максимал кез келген екі қарапайым
тізбектің бір жалпы төбесі бар.
4. ... және ... бар ... ... ... - ден ... ... төбесі бар болсын. бұл графтың төбелерінің
дәрежелерінің минимумы болсын. Онда .
29. Циклсыз байланысқан граф ағаш деп ... ... ... бейнелеу практикасында пайда ... ... ... ... ... ... ... библиялық генеалогиялық ағаш
көрсетілген.
Ағаштың эквивалентті ... ... граф ағаш деп ... егер оның ... бар ... қыры және ... ... Байланысқан және қыры бар.
4. Байланысқан және кез ... бір ... ... оны ... Төбелердің кез келген жұбы жалғыз тізбекпен біріктіріледі.
6. Циклы жоқ және кез келген екі төбелердің арасына бір қырды қосу ... ... ... алып келеді.
Графтардың бояуы
графының бояуы деп кескіні аталады. Бояу дұрыс деп ... кез ... екі ... ... ... әртүрлі болса: , егер
. Графтың хроматикалық саны деп графтың дұрыс ... үшін ... ... ... 4. Келесілердің біреуіне изоморфты ішкі графтары болса ... ...... графтары)
Қасиеті: Кез келген жоспарлы графта дәрежесі төбесі болады.
Графтың берілу тәсілі:
1. Геометриялық
2. Араластыру матрицасы
| |a |В |c |d |
|A |0 |1 |1 |0 |
|B |1 |0 |1 |0 |
|C |1 |1 |0 |1 |
|D |0 |0 |1 |0 ... ...... ... тең шаршы матрица,
өлшемділіктер. Сонымен ... - ші, - ші ... ... ... тең ... сан. Егер графта тұзақ болмаса,
онда диагонал элементтері 0 – ге ... ... ... онда ... ... 0 немесе 1.
3. Инциденттілік матрицасы:
| |a |В |с |d |
|A |1 |1 |0 |0 |
|B |0 |1 |1 |0 |
|C |1 |0 |1 |0 |
|D |0 |0 |1 |1 |
4. ... ... жүйе ... ... қана ... ... ... бізге графтың
тасымалдаушысы төбелер ... ал ...... ... ... болатын модель ретінде анықтау оңай. Онда ... граф ... ... ұсынылуына берілген қырға инцидентті және
төбесінің екі жұбы ... ... ... ... беру ... ... ... екі элементті жиынын көрсету жеткілікті – оны біз ... ... граф үшін қыр ... ... және ... , - ... жиыны, ал - қырлар жиыны жұбы ... ... ... ... ... ... болады.
1.3. Графтағы әртүрлі есептердің сипаты
Графтар теориясының дамуы негізінен барлық әртүрлі қосымшалардың ... ... ... ... ... ... ... жүйелердің формальды модельдер ретіндегі алғашқы орындардың
біреуінің орнын алады.
Графтар ғылыми ... ... ... ... ... ... ... әлеуметтік ғылымдарда, техникада және
тағы басқа. Ең көп ... ...... ... ... ... ... химиялық және генетикалық құрылыстарды,
электрлік тізбектерді және торлық құрылыстың басқа да жүйелерін ... ... ... ... теориясының кейбір типтік ... және ... атап ... Ең кіші ... ... ... ... айырбастау
• транспорттық құралдың жүру кестесін құру
• жедел жәрдем пункттерін ... ... ... ... ... ағын ... ... коммуникациялық тордың өту қабілеттілігін талдау
• динамикалық торды жүруді ұйымдастыру
• жұмыстың орындалу интенсивтілігін тиімді таңдау
• құрылымдық сенімділігімен ... екі ... ... ... ... ... ... есеп
- Орауыш және бүркеу туралы есеп
• тұрақты есте ... ... ... ... ... ... тордың диспетчерлік пункттерін орналастыру
- Графтардағы бояу
• дербес компьютерде ... ... ... ... ... Графтардың және торлардың байланыстылығы
• ең кіші коммуникациялық торды жобалау
• циркуляциялық байланыстың құрылымды – сенімді ... ... ... стохастикалық торының сенімділігін талдау
- Графтардың және торлардың изоморфизмі
• сызықтық талданған тізбектің құрылымдық синтезі
• жобалау кезіндегі қадағалаудың автоматизациясы
- ... ... және ... ... ... ... ... түзелмеуді ықшамдау
• типтік ішкі схемалардың жиынымен берілген схемаларды жабу
- Графтардың изоморфизмі
• туынды ... ... үшін ... ... атап өту
• цифрлық құралдардың тесттерінің синтезі.
II. ТОРЛЫҚ ЕСЕПТІҢ ЭКОНОМИКАЛЫҚ ҚОЙЫЛУЫ
2.1. Есептің торлық ұсынылуы және торлық ... құру ... ... ... ... ... ... және олардың
орындалу ретін бейнелейді. Ереже бойынша, амалды түсіндіру үшін ... ... ... ... ... ... сәйкес келетін
бағытталған доға пайдаланылады. Амалдар арасында реттеу ... ... ... ... бір амал ... және ... ... моменті түрінде анықталады. Кез келген амалдың бастапқы және ақырғы
нүктелері болады, әдетте бастапқы оқиға және ақырлы ... деп ... ... ... ... шығатын амалдар осы оқиғаға
кіретін барлық амалдар аяқталмайынша басталмайды. Доға ұзындығы амалдың
ұзақтығына пропорционал ... ... ... ал доғаның графикалық
кескіні түзу сызықты бөлікті көрсетуі міндетті емес.
(а)
(б)
1 – сурет.
(1а) – суретте ... ... i және ... ... (ji), ... ... ... мысалы көрсетілген. (1б) – суретте басқа
мысал көрсетілген, онда (3,4) амалының ... ... үшін (1,3) ... ... ... қажет етілетіндігі көрсетілген. Уақыт бойынша
амалдың орындалуы оқиғалардың нөмірлену жолымен ... ... ... ... ... оқиғаның нөмірінен кіші. Нөмірлеудің
мұндай тәсілі ЭЕМ – де есептеулерді орындау кезінде қолайлы.
Тордағы әрбір амал тек қана бір ... ... ... бір де біреуі екі рет ... ... ... қатар,
қандай да бір амалдың бөліктерге бөліну жағдайын ... онда ... жеке ... ... бір де ... ... және ақырлы оқиғалармен анықталмауы
керек. Екі немесе одан да көп амалдарды бір уақытта ... ... ... ... ... бір ... емес анықталу мүмкіндігі
пайда болады. Бұл жағдайдың мысалы (2а) – ... ... А ... ... ... ... немесе В және ақырлы (бастапқы)
оқиғалар арасында ... ... үшін ... амал ...... D жалған амалын енгізудің әр ... ... Енді A және B ... ... оқиғаның бастапқы
нөмірінен немесе ақырлы нөмірмен ерекшеленетін оқиғалар бір ... ... ... ... ... ... ... назар аудару керек.
2 - сурет
Сонымен қатар жалған амалдар логикалық байланыстарды дұрыс бейнелеуге
мүмкіндік береді. Кейбір программаларда A және B ... ... ... ... ал E ... алдында тек қана B болу керек.
(3а) – ... бұл ... қате ... ... A, B және ... ... дұрыс көрсетілген, осы үзіндіден E A және B ... ... болу ... екені шығады. Көрсетілген шарттың дұрыс
тұжырымы (3б) – суреттегі фрагментте ... онда D ... ... D амалына қордың да, уақыттың да шығыны қажет етілмейтіндіктен
, ... ... ... ...... ... ең кіші жолды табу
Доғаларына салмақтар жазылған бағытталған графтарды ... ... ... ... ... салмағы деп аталатын кейбір
нақты саны сәйкес қойылған.
Бізді белгіленген төбелердің ... ең кіші ... ... ... ең кіші ... ... біз деп ... және
- тан - ға дейінгі ара қашықтық деп ... Егер - ... ға ... ... жол ... онда деп аламыз. Егер біздің
графтың әрбір контурының оң ұзындығы болса, онда ең кіші жол ... жол ... ... ... ... егер ... ұзындығы жалған контур бар болса, онда
төбелердің кейбір ... ... ара ... ... ... біз ... ... саннан ұзындығы кіші төбелердің арасындағы жолды
көрсете аламыз, осы контурды аралағандағы ... сан бір. ... ең кіші ... ... ... ... айтуға болады, бірақ есеп
мынадай әдіспен қойылған, онда гамильтонды жол ... ол ... ... кіші жол туралы есептің көптеген интерпретацияларын беруге болады.
Мысалы, ... ... ... ... мүмкін, әрбір доға – ұзындығы
доғаның салмағымен берілген кейбір ... ... ... Біз ... кейін
қалалар арасындағы ең кіші жолды іздейміз. Доғаның ... ... ... беру ... сәйкес келеді. Мұндай жағдайда біз
ақпаратты берудің ең ... ... ... ... ... ... арнасының апатсыз жұмысының ықтималдылығына тең болғанда, тағы
бір жағдайды аламыз. Егер арналардың апаты бір – ... ... ... онда ақпаратты беру жолын түзетудің ықтималдылығы оның ... ... ... тең. Ең сенімді жолды табу есебін
салмақтарын - ауыстырып, ең кіші жол ... ... ... ... ... төбелер арасындағы ара қашықтықты ... ... ... ара ... ... біз ұзындығы оң
барлық контурлардың шарты кезіндегі ең кіші жолдарды анықтау жеңіл. ... ... ... үшін төбесінің бар ... ... тан - ға ... ... ең кіші ... ... ... қасиетімен басқарады.
Әрі қарай үшін төбесін таба аламыз.
Барлық контурлардың ұзындықтары оң ... ... ... тізбегі қайталанбайды және төбесімен аяқталады.
Ол - тан - ға ... ең кіші ... ... біз ... ... ... кіші жолды табу алгоритмі
Мәліметтер: белгіленген төбеден барлық қалған төбеге дейінгі
ара қашықтық, белгіленген төбе , ... ... ... СТЕК – тің - тан - ға ... ең кіші ... төбелер тізбегі бар.
begin
CTEK := ∅ ; CTEK ⇐ t; v:= ... v ╧ s ... := ... D[v] = D[u] + A[u, v] ... ⇐ u;
v:= u
end
end.
- бағытталған граф болсын, . Егер ... ... ... ... ... ... болса, онда біздің алгоритмнің
күрделілігі - . сияқты - дың ... ... ... тізімін ғана қарастыратын болсақ, онда бұл жағдайда ... оң ... ... ... ... ең кіші жол ... ... бағытталған графтарға ұқсас есепке оңай келтірілетінін атап
өтейік. Осы мақсатпен әрбір және екі ... ... ... оң ... ... бұл ... оң емес ... пайда
болуына әкеледі,
Әрі қарай бағытталған граф, болады деп ... ... ... кезіндегі азғындалған жағдайларды
болдырмау және баяндауды ықтималдау мақсаты ... ... ... ... ... ... доғалардың салмағы салмағы массивінде
сақталады.
Белгіленген төбедегі ең кіші жолдар
және екі ... ... ... ара ... ... әйгілі алгоритмдері жалпы келесі үлгіде ұсынуға болатын
әрекетке сүйенеді: берілген доғалар массасы ... - ... ... ... ара ... ... жоғарғы шектеулер
есептелінеді. орнатқанда бағасын жақсартамыз.
Әрі қарай шектеулердің бірде – ... ... ... ... ... ... мәні тең екендігін көрсету жеңіл, онда -
ға дейінгі ара қашықтыққа тең.
2.3. Бір торлық есепті шешу үшін динамикалық программалау әдісі
Бүтін ... ... ... ... ... ... ... сандар жиынын ауыстырумен сипатталатын ... ... ... ... ... ... түрдегі сызықтық есептерді шешу кезінде біз
есептің шешуі болмайтын жағдайға ... ... Бұл ... ... ... ... қолданумен және осыған байланысты ... ... ... ... ... шектеулерді
құрумен түсіндіріледі.
Нұсқалардың тізбекті талдау әдісінде мұндай кемшіліктер жоқ.
Нұсқалардың тізбекті талдау ... ... Р. ... ... динамикалық программалау әдісі жатады; Корел, ... ... ... жақ ... ... ... ... әдісінің қию әдісінен айырмашылығы сызықтық
программалау аппаратын қолданбайды және есептеу қателігі болмайды.
Динамикалық программалау әдісі – мүмкін болатын ... ... мен ... ... есебінде тиімді шешімді тез табуға
мүмкіндік береді, яғни әртүрлі нәтижелердің ішінен ең тиімдісін таңдайтын,
әртүрлі ... бар ... ... түрдегі кез келген есеп барлық
мүмкін ... ... ... ... және солардың ішінен ең тиімдісін
таңдаумен шешілуі мүмкін. Мұндай іздеу өте ... ... ... тиімді
шешімді қабылдау процесі қадамдарға бөлінуі және ... ... ... ... ... ... ... қадамдарға бөлінсін. Әрбір қадамда айнымалының
екі түрін анықтау керек - күй ... және ... ... ... - шы қадамда жүйе қандай
жағдайда болатынын анықтайды. - ке ... осы ... ... сипатталатын кейбір басқаруларды қолдануға болады. - шы
қадамда басқаруын қолдану нәтижесін ... және ... ... күйге ауыстырады. Сонымен қатар жүйе ... ... ол ... ... және ... ... және ... қалай ауысқанына тәуелді емес барлық мүмкін
болатын басқарулар ортасында - шы ... ... ... ... ... - ші ... ... нәтижелер тиімді болу үшін
тиімді басқару таңдап алынады.
Әрі қарай, егер - шы ... ... ... жүйенің
алғашқы жағдайына және таңдалған басқаруға байланысты және (1)
ұтыс немесе белгілі кіріс қамтамасыз етіледі деп ... ... ... ... ... ... ... екі шартты
қарастырдық. Бірінші шарт салдардың болмау шарты, ал ...... ... ... деп аталады.
Динамикалық программалау есебін орындау үшін бірінші шарт Беллман
тиімділігінің принципін орындауға мүмкіндік береді. Бұны ... ... ... ... ... береміз. Осындай стратегиямен
басқарудың жиынтығы түсіндіріледі, нәтижесінде қадам ... ... ... ... ... көшеді және сонымен қатар (1)
функция үлкен мән қабылдайды.
Тиімділік принципі
Жүйе қандай жағдайда болмасын келесі қадамның алдында берілген қадамдағы
ұтыс және ... ... ... ұтыс ... ... осы ... ... керек.
Шартты тиімді басқару немесе шартты тиімділік деп аталатын есепті
шешудің бірінші кезеңінде Беллман функциясы және ... ... ... ... ... ... ... үшін тиімді басқару ізделінеді.
Осыны практикада жүзеге асыру үшін ... ... ... беру ... Ол үшін ... ... белгілеулерді енгіземіз.
арқылы қадамда ... ... ... ... ... ... ... кезіндегі соңғы күйге
ауысуы кезінде алынатын максимал кіріс, ал арқылы кез ... ... ... ... басқарудың тиімді стратегиясы кезіндегі
соңғы күйге ауысу ... ... ... ... ... ... ... өрнек тиімділік принципінің математикалық жазуын ұсынады және
Беллман негізгі функционал ... ... ... ... деп ... теңдеуді қолданып, динамикалық программалау есебінің ... ... ... толығырақ қарастырайық.
(3) рекуренттік қатынастағы деп болжап, келесі функционалдық
теңдеуді аламыз:
(4).
Бұл теңдеуді белгілі деп ... (4) ... ... ... ... барлық мүмкін болатын жағдайларын қарастырып,
шартты тиімді шешімді және (4) ... ... ... - ші ... жүйенің қадамынан кейінгі кез ... ... ... ... ... ... ... теңдеуді қарастырамыз:
(5).
барлық мүмкін болатын мәндері үшін мәнін табу ... ... білу ... ... біз ... ... ... және
мәндерінің жиынында үшін есептеу жүргізу керек. Бұл есептеулер
әрбір үшін шартты тиімді басқаруға мүмкіндік ... ... ... ... ... бірге соңғы қадамда
максимал мәнді кірісті соңғы екі ... ... ... сипатталған итерациялық процесті жүзеге асырып, бірінші қадамға
көшеміз. Бұл қадамда жүйе қандай жағдайда болатындығы белгілі. Сондықтан
жүйенің мүмкін ... ... ... ... ... ... жоқ, ... қабылданған шартты тиімді басқаруы болатын басқаруды таңдау
керек.
Барлық - шіден ... ... үшін ... ... ... ... функциясы табылғаннан кейін, шартсыз тиімділеу деп аталатын есепті
шешу үшін екінші кезең жасалады. Бірінші қадамда ... ... ... – бұл оның ... ... ... ... барлық
қадамда, сонымен қатар осы нәтижені беретін бірінші ... ... ... табуға болады. Осы басқаруды қолданғаннан кейін жүйе ... ... ... ... ... ... ... қолданып,
екінші қадамда тиімді басқаруды табу және ... - ... ... ... түсінігі үшін мазмұны күйдің айнымалысын таңдауды
және әртүрлі басқаруды қажет ететін есептің шешуін қарастырамыз.
Есептің қойылымы
Транспорттық тор ... ... ... кейбіреулері
магистральмен байланысқан. Осындай әрбір магистральдың жол жүру құны
белгілі және схемада ... 1 – ші ... - ші ... жол ... ... маршрутын табу қажет.
Берілген есептің шешуі жалпы жағдайда есептеудің жеткілікті көлемімен
түйіндескен.
Мысал. Тор 4 – суретте бейнеленген магистральдармен байланысқан ... ... ... ... жүру құны ... осы ... элементтері (сур.1) схемаға енгізілген.
1 – ші пункттен 10 – шы пунктке дейінгі тиімді маршрутты табу қажет.
Берілген ... ... ... ... солдан оңға қарай жылжу
шектеуі бар, яғни 7 – ші пунктке, біз 10 – шы ... көше ... Бұл ... ... 4 ... біреуіне апаруға мүмкіндік береді. Пункт
- шы ... ... деп ... егер одан ... ... (10 ... ... баруға болса. Сонымен 7, 8 және 9 пункттері бірінші өріске, 5
және 6 ... 2, 3 және 4 ... және 1 ... ... жатады. - шы
қадамда қалалардың - шы ... ... ... ... ... ... Сонымен тиімділеуді процестің соңынан бастаймыз және
- шы қадамға жетіп, біз 1 ... ... - шы ... қандай
қаласына баратынымызды белгілейміз. Сондықтан осындай қалалардың әрбіреуі
үшін соңғы пунктке дейінгі тиімді маршрутты табу керек. - шы ... 10 ... ... ... ... болатын минимал құны біз ... қай ... ... ... - шы ... ... номері - шы қадамда берілген жүйенің айнымалысы деп
атаалады. - шы ... ... біз - ші ... кез ... ... ... көшу бойынша тиімді маршрутты таптық. - ші
өрістің қаласының номері - шы ... ... ... ... ... шешудің - шы қадамында Беллман функциясы деп қаладан соңғы
пунктке жүрудің минимал ... ... – 4. ... ... ... үшін бұл ... табу қиын емес – бұл 1 – ші ... соңғы пунктке дейінгі жүру құны: .
Бірінші тәсіл.
I кезең. ... ... ... ... |10 | |J* |
|7 |7 |7 |10 |
|8 |9 |9 |10 |
|9 |11 |11 |10 ... ... үшін жол жүру құны екі қосылғыштан жиналады - - шы
өрістің қаласынан - ші өрістің J қаласына жол жүру ... ... J ... соңғы пунктке жол жүрудің минимал құны, яғни .
2 қадам.
|S\J |7 |8 |9 | |J* |
|5 |8+7 |6+9 |- |15 |7.8 |
|6 |6+7 |- |4+11 |13 |7 ... ... ... ... ... ... басқаруларды тауып,
соңғы пунктке дейінгі жол журудің мүмкін болатын минимал ... ... .
3 ... ... |5 |6 | |J* |
|2 |4+15 |- |19 |5 |
|3 |- |3+13 |16 |6 |
|4 |- |9+13 |22 |6 ... ... J* кейбір мәндерінде алынады, ол пункттен соңғы
пунктке барудың тиімді бағыты болып табылады.
Төртінші қадамда біз 4 ... ... және ... күйі ... -
. (1) ... функциясы 1 – ші пункттен 10 – шы пунктке ... ... ... ... ... ұсынады. Тиімді маршрутты барлық
қадамдардың нәтижелерін ... ... ... ... ... -
шы қадамда J басқаруын ... - ші ... ... ... – ші қадам.
|S\J |2 |3 |4 | |J* |
|1 |7+9 |5+16 |6+22 |21 |3 |
II ... ... ... ... 10 ... жол ... ... құны . Ол егер 1 – ... 3 – ші ... ... ... Оған жетіп, 6 пунктке, сосын 7
пунктке және одан соңғы пунктке бару ... яғни ... ... 5 – ... ... магистральдармен байланысқан 10 ... ... ... шешу ...... деп ... – қадам. Екі жақты бағалар айнымалысының ... ... ... ...... ... мәндерін тордың сәйкес төбесіне қойып, оны
тіктөртбұрышпен қоршап ...... ... доғаларды кері ретімен қарастырамыз. Егер
(7)
шарты орындалса, онда доғасын маршрутқа кіргіземіз, ... бұл ... алып ... ... ең ... бір, ... ... қалаға келетін, ең кіші ара қашықтық бар болады.
Есептеу алгоритмі
1 – қадам. деп ... - 3 – ... ... ... тексереміз.
Сурет 5.
Мұндағы (+) таңбасы шартының орындалатынын және осы доға ... кіру ... ие ... ал (-) ... шарттың
орындалмайтындығын білдіреді. Сонымен (+) таңбасы бар барлық ... ... ... ... ... ... ... ең кіші ара қашықтықты
беретін маршрутты келесі түрде анықтаймыз: М(1 – 3 – 6 – 7 - 10). ... ... ... қол жеткіздік.
Жауабы: М(1 – 3 – 6 – 7 - 10). ... ... ... – жинақтау маршруттарын анықтау алгоритмі
Көптеген ұсақ ... ... ... көлік жүргізушісі бір
жіберушіден жүкті қабылдап, оны саны ... ... ... ... бір ... тастайды, немесе керісінше оған жүкті
бірнеше жіберушіден жинау және бір ... ... ... ... ... пункттерді аралау тізбегінің уақыт және жолдың
қысқаруының пайда болуы. Оған жету үшін ... ... ... ... керек, немесе басқаша айтқанда ... ... ... Тасымалдау маршрутизациясы – бұл жылжитын құрамның
қозғалу ... ... ... және ... ... жұмысының нақты шарттарымен
шақырылатын қойылым практикасы және жүктерді тасымалдау маршрутизациясы
есебінің ... ... ... ... Оған мыналар жатады:
берілген көптеген жіберу пункттері және жүкті тұтыну, жүкті тұтынушылардың
және ... жүк ... ... ... сипаты, оларды
жеткізу уақыты, жылжымалы құрамның паркінің бар ... және ... ... ... және ... ... ... мәні.
Кішкене топтық тасымалдау кезінде жүкті жіберушілер немесе алушылар
арасында автокөліктер қозғалысының ... ... ... ... деп ... ... автокөлік бір мезгілде тасымалдау мен бірге
жүктерді жинайды. Онда есептің шешімі қиындатылады, ... оның ... жоқ. Егер ... бір ... ... ұсақ ... және жинақтаса, онда маршрут тасымалдап – жинақтау деп ... жол ... ... ... ... ... әртүрлі
маршруттардың нұсқаларының саны өте көп болуы ... және ең кіші ... ... ... көп ... ... ... олардың қысқартылуымен
математикалық әдісті қолдануға жетуге болады.
Бұл есепті шешудің бірнеше математикалық әдісі белгілі. Мұнда «сумм»
әдісі деп ... жуық әдіс ... Б, В, Г, Д, Е, Ж, З, И, К, Л, М ... А ... ... Осы ... қоймаға саны 1 кестеде көрсетілген жүктер
түседі.
1 кесте.
Пункттердің жүк айналымы
|Пункттер | | ... |5 |5 ... |3 |10 ... |2 |4 ... |4 |6 ... |9 |- ... |7 |8 ... |2 |3 ... |5 |4 ... |4 |- ... |5 |5 ... |5 |6 ... |51 |51 ... ... жол ... ... 2 ... көрсетілген.
Сур 6. Жол торының схемасы.
Бір автокөліктің сыйымдылығы бір уақытта жүктің отыздан көп ... ... ... ... жолы минимал болатындай ұйымдастыру.
Жол торының схемасында пункттер А нүктесінің ... ... ... тілі ... ең көп ... ... нөмірленеді. А
нүктесіне нөл нөмірі тағайындалады.
Осымен ... ... ... ... ... тұратын есептерді
шешу басталады.
Бірінші кезең. Бұл кезеңде әрбір маршрут үшін пункттер жиыны ... ... ... ... оған А ... ... 1 ... басталады. Содан кейін осы пунктпен байланыстырылған жол торының
буындары қарастырылады.
Мұндай буындар ... ... ... ... – 8 ... 6 км және 1 – 9 ... 15 км. Осы ... арасынан
ең қысқа буын таңдап алынады және осының екінші төбесі 9 бірінші маршрутқа
енгізіледі.
Әрі қарай буын маршрутпен 1 және 9 ... ... ... және ... ... ... төбесі ... ... кіші буын ... алынады.
1 және 9 пункттерінің ... ... ... бес ... ... ... 1 – 8; 9 – 8; 9 – 10; 9 – 2 және 9 – 3; 9 – ... ұзындығы ең кіші (2 км). Сондықтан, 2 пункті бірінші маршруттың
үшінші ... ... үлгі ... ... ... ... ... жиынына дейін таңдап
алынады, яғни жылжымалы құрамның жүк ... ... ... максимал болғанға дейін. Сонымен қатар маршрутқа ... ... бір ... ... болатын жүктің саны оның жүк
сыймдылығынан аспау керектігін қадағалау керек.
Маршрутқа пункттерді жинау жұмысы жеңіл болу үшін 2 ... ... ... ... ... ... тасталады. 1 маршрутқа
пункттерді ... ... 1, 9, 2, 8, 10, 3 ... сызылып тасталады.
2 кесте
|Пункттер нөмірі |
|1 |2 |3 |
| |1 |9 |2 |8 |10 |3 | |
| |5 |4 |5 |2 |3 |9 | |
| |6 |- |5 |4 |10 |- |25 |
4 ... жүк ... ... ... |
|айналымы | | |
| |4 |11 |5 |7 |6 | |
| |5 |7 |4 |5 |2 |23 |
| |5 |8 |6 | 4 |3 |26 ... ... ... кезінде қандай да пункт бұрын таңдалған
пункттерден ең кіші ара қашықтықта болса да, ... ... ... барлық жүкті сыйдыра алмағандықтан маршрутқа енгізілмеуі мүмкін.
Бұл жағдайда берілген пунктті таңдалған пунктке жақын, бірақ ... ... ... ... ... керек. Бұл автокөліктің жүк
сыйымдылығын жақсы қолдануға мүмкіндік береді, бірақ сонымен ... оның ... ... ... ... ... жинау 2 кестеде барлық
пункттер сызылғанда аяқталмады, ал тасымалдау көлемінің қосындысы ... ... ... Бұл ... ... (А қоймасы) 0 пунктінен бастап
маршрут ... ... ең кіші ... табу ... ... Бұл ... ... пунктерінің аралығында арнайы қашықтық матрицасы салынады.
Матрица симметриялы болуы мүмкін, егер жол ... ... ... ... ... ... немесе симметриялы емес, тордың қандай да бір
бөлімшесінде бір ... ... ... симметриялы және симметриялы
емес матрицаны есептеу бірдей шығарылады. Қарастырылып отырған мысалда жол
торының қозғалысы бойынша шектеулер көрсетілмеген, ... ара ... ... ... ... маршрут бойынша ара қашықтық
матрицасы 5 кестеде көрсетілген.
5 кесте
Маршруттың ара қашықтық матрицасы
|0 |10 |5 |7 |4 |2 |5 ... |1 |5 |7 |6 |9 |11 |
|5 |5 |9 |2 |3 |4 |6 |
|7 |7 |2 |2 |5 |6 |8 |
|4 |6 |3 |5 |8 |6 |9 |
|2 |9 |4 |6 |6 |10 |3 |
|5 |11 |6 |8 |9 |3 |3 ... |48 |25 |35 |33 |30 |42 ... ... ... ... нөмірлері жазылған. i – ші ... j – ші ... ... i және j ... арасындағы ара
қашықтық көрсетілген. Матрицасының қорытынды жолы сумма жолы деп ... ... ... ... ара ... ... ... Алғашқыда
сумма жолында үлкен мәндер сәйкес болатын 3 пункттің аралау маршруты
көрсетіледі. ... ... ... 1, 3 және 2 пункттеріне сәйкес болады.
Бұл 3 ... ... ... ... жасайды: 3 – 2 – 1 – 3.
Бұл маршрутқа сумма жолында келесі максимал мәні бойынша ара қашықтық
суммасы ... ... 4 ... енгізіледі. 0 пунктін алайық.
Оны бастапқы маршруттың қандай пункттерінің арасында қоюды анықтау үшін
осы пунктті маршрутқа енгізумен шақырылатын ... ... ... болатын минимал ұзындығын ... ... ... ... ... ... жұбы үшін ... 3 – 2, 2 – 1, 1 – 3
үшін келесі формула бойынша мәні ... ... ... ара ... км; i – буынның бірінші ... j – ... ... ... ... k – ... пункттің
нөмірі.
1 маршрутының 3 – 2 пункттерінің бірінші жұбы үшін:
немесе
2 – 1 пункттері үшін:
1 – 3 пунктері ... ... ... ... ... алынған мәнінің ең кішісін таңдаймыз
және оған ... ... ... ... 0 пунктін қоямыз. Берілген
жағдайда ... ... 1 – 3 ... 3 – 2 ... 0 ... ... ... ... кез ... біреуін алайық. Мысалы, 1 – 3 буыны.
Онда ... ... ... ... ... 3 – 2 – 1 – 0 – 3 ... ... 0 пунктінен басталатындықтан және сонымен аяқталады, ... ... ... ... ... ... 0 – 3 – 2 – 1 – 0. Содан
кейін 5 кестеде сумма ... ... ... ара ... ... ... ... пунктті таңдаймыз. Ол 8 пункті келесі маршруттың барлық
буындарын талдап, 8 пунктін 1 және 0 ... ... ... рационалды
болатынына сенімді болуға болады. Көрсетілген әрекеттерді 10 және ... үшін ... 1 ... барлық пункттерінің аралауының
рационалды реті: 0 – 10 – 3 – 9 – 2 – 1 – 8 – 0.
2 ... ... ... тізбегін анықтау үшін 2 маршрутынының
ара қашықтық матрицасын алдын ала құрып, ұсақ есептеулерін жүргізу ... ... ... ... ... ... рационал
маршрут бойынша жылжымалы құрамның жұмысы өндірістік емес жол жүрісін
минмумға дейін ... ... ... және ең аз ... ... ... ... береді.
III. ГРАФТАҒЫ ЕҢ КІШІ АРА ҚАШЫҚТЫҚТЫ АНЫҚТАУ АЛГОРИТМІ
3.1. Торлық ... ... ... ... ... ... тор бойынша берілген ең кіші
маршрутты анықтау есебі көп кездеседі. ... тор ... 1) ... ... ... ...... магистраль, түйіндері –
жөнелту және тағайындау пункттері. Графикалық транспорттық тор ... ... ... бейнеленеді, сонымен қатар ... ... ... ... ... ... біріктірілген. Кейбір немесе барлық доғалар бағытталуы мүмкін,
солар ... ... тек қана бір ... жүру ... суретте өзара байланысқан сегіз транспорттық жолмен байланысқан ... ... ... ... ... тор құрылған. пунктінен
пунктіне дейінгі ең кіші маршрутты табу керек. Ең кіші ... ... ... ... және ... ... арқылы маршруттың
тізбекті өтуінің көрсетілуінен тұрады.
Мысалы, пунктінен пунктіне дейінгі маршрут: ... ... ... мына ... ... егер ... соңғы пунктке дейінгі маршруттың бірнеше нұсқалары бар болса. Бұл
жағдайда ... ... ... ... - ден ... ең кіші жолды табудан, маршруттың жалпы ... ... ... және шешу алгоритмінің сипаты
Форда әдісі торлық транспорттық есепті шешу үшін арнайы зерттелген ... ... ... принципіне негізделген.
Форда әдісінің алгоритмінің төрт кезеңі бар(схема 1). ... ... ... - ші пункттен кез келген басқа пунктке дейінгі ара ... ... ... ... ... Әрі қарай үшінші кезеңде
ең кіші ара қашықтық анықталады. Соңында, төртінші кезеңде ... кез ... ... ... ... ... ең кіші
маршрут табылады.
Осы төрт кезеңнің әрбіреуін толық қарастырамыз.
3.2.1. Бірінші кезең: Ара қашықтықтың алғашқы ... ... ... жол және ... бар; - ... ... тағайындау пункттері. Екінші жолда және екінші бағанда мәні есепті
шешудің екінші ... ... және ... ... ... ... ... пунктінен - ші
пунктке дейінгі ара ... мәні ... ... диагональдан жоғары
жатқан кестенің торларын толтырамыз. Егер пункті жолдың ... ... ... онда кестенің сәйкес торы
толтырылмайды.
3.2.2. Екінші ... және ... ... ... мәні анықталады.
Бұл мәндер екінші жолда немесе екінші бағанда толтырылады.
3.2.3. Үшінші кезең: Ең кіші жолдың ұзындығын ... ... ... ең кіші ... ұзындығын
анықтаудың екі жағдайы бар.
Бірінші жағдайда, егер (2) теңсіздігі орындалса, онда
параметрлерінің мәні ... ... ...
әәрбір мән, пунктінен пунктәне дейінгі ең кіші ара ... ... егер ... тор үшін ... теңсіздік
орындалса: (3) онда және мәні ... ... (3) тура ... онда ... келесі формула бойынша есептеп,
түзетеміз:
(4)
3.2.4. Төртінші кезең: Ең кіші жолды табу
Ең кіші ... ... ... табу, Осы мақсатпен әрбір баған
үшін шаманы анықтайды:
(5)
кестеден алынады, (5) теңдігі орындалатындай етіп ... ... Әрі ... Осы ... ... ... ... ал деп санаймыз. болғанша жалғастырамыз.
Сонымен, арқылы ең кіші ... ... ал ... ... ... ... Borland lnc ... “Turbo Pascal 7.0” өңдеуінің
интегералданған ортасында жоғарғы деңгейлі – Pascal тілінде жазылған.
Программа ... ... ... графта ең кіші жолды табу ... ... ... ... ... меню және достық
интерфейсті қолданумен алынады. Программаның басында мәліметтер енгізіледі,
содан ... ең кіші ... табу және оның ... ... әрі ... ... ... шешімі қайталануы басқа мәліметтермен қарастырылуы
мүмкін.
ҚОРЫТЫНДЫ
Бұл дипломдық жұмысымды жүзеге ... үшін мен ... ... ... ... торлық есептерді шешу кезінде, ең кіші ара
қашықтық есебін шешу ... ... ... Дискреттік программалаудың
кейбір сызықтық есептері бағытталған графтардағы ең кіші ара қашықтықты
табуға келтіріледі. Төбелері мен ... ... ... ... ... ... ... кіші ара қашықтық есебі келесі түрде қойылады: бір нүктеден бастау
алып, бір нүктеге құятын тор ... Егер ... ... ... ара ... деп алсақ, онда бастапқы нүкте мен соңғы нүктелерді
қосатын ең кіші маршрутты ... ... ... ... ... және ... әртүрлі облысында кеңінен қолданылады.
Ең кіші ара қашықтық есебінің бірнеше тиімді шешімі бар болуы мүмкін.
Бірақ ... ... ... ... тең болады.
Ең кіші ара қашықтық есебі торлық ... ... ... ... ... ... газ ... мұнай құбырларын, темір және
авто жолдарды тиімді құру есебі және тағы ... ... Ең кіші ... есебін максимальды ағын есебінің дербес ... ... ... кіші ара ... ... ... ... сонымен қатар оны
шешудің әр түрлі әдістерін ... ... ... ... екі ... ... ... мысал үшін, ең кіші ара
қашықтықтыанықтау программасын Fream Work ... ... Си++ ... ... ... ... ... сәйкес келеді, бұл
құрылған прогамманың дұрыстығын дәлелдейді.
Бұл дипломдық жұмысты графтар теориясы бйынша арнаы курсты оқу ... ... ... ... ... ... ... Москва, «Наука»,1968.
2. Новые педагогические и информационные технологии Е.С.Полат, Москва,
«Akademia» 1999 г.
3. Кузнецов О.П., ... Г.М. ... ... ... – М.: Энергоатомиздат, 1988.
4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.
5. ... В.Н., ... В.А. Курс ... ...... МАИ, ... Оре О. Теория графов. – М.: Наука, 1980.
7. Исмагилов Р.С., Калинкин А.В. ... к ... ... ... Дискpетная математика по теме: Алгоpитмы на гpафах. - М.: ... ... Э.Р. ... в ... ... М.: ... 1992
9. Hечепуpенко М.И. Алгоpитмы и пpогpаммы pешения задач на гpафах и ... ... ... ... Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: ... ... С. ... ... ... - М.: Мир, 1988
12. Севастьянов Б.А. Вероятностные модели. - М.: Наука, 1992
13. Бочаров П.П., Печинкин А.В. Теория ... - М.: ... ... Е.С. ... ... М.: ... 1972 ... В.Н. «Алгоритмические методы ... ... ... и ... ВАД. 1986 ... В.С. ... на языке Turbo Pascal» М.: Филин 1997 г.
ҚОСЫМША 1 Жаттығулар
1)
2)
3)
4)
5)
6)
7)
8)
9) ... ... ... 2 ... жұмыс істеу принципі
-----------------------
2
3
4
1

Пән: Математика, Геометрия
Жұмыс түрі: Дипломдық жұмыс
Көлемі: 50 бет
Бұл жұмыстың бағасы: 1 100 теңге









Ұқсас жұмыстар
Тақырыб Бет саны
Графтар теориясы және оның элементтері5 бет
Графикалық торлар20 бет
Графтар мен ағаштар8 бет
Графтардағы Гамильтон циклы мен жолы17 бет
Графтардағы тиімділеу есептерін шешу әдістері15 бет
Динамикалық жүйелер5 бет
Леонард Эйлер циклы14 бет
Модельдеу туралы түсінік25 бет
Эйлерлік графтың кейбір есептерінің теориясы10 бет
12-жылдық білім берудегі компьютерлік графиканын мүмкіншіліктері13 бет


+ тегін презентациялар
Пәндер
Көмек / Помощь
Арайлым
Біз міндетті түрде жауап береміз!
Мы обязательно ответим!
Жіберу / Отправить


Зарабатывайте вместе с нами

Рахмет!
Хабарлама жіберілді. / Сообщение отправлено.

Сіз үшін аптасына 5 күн жұмыс істейміз.
Жұмыс уақыты 09:00 - 18:00

Мы работаем для Вас 5 дней в неделю.
Время работы 09:00 - 18:00

Email: info@stud.kz

Phone: 777 614 50 20
Жабу / Закрыть

Көмек / Помощь