Программа кұру және нәтижесін алу
Download 408.68 Kb.
|
Исмоилов Б. Антиплагиат
|
Мазмұны Кіріспе............................................................................................................4 1 Теориялық бөлім 1.1 С++ тілінде бағдарламалау негіздері..................................................5 1.2 С++ программалау тілінде қарапайым есептер құру.........................7 1.3 Графтар теориясының негіздері..........................................................10 1.4 Дейкстра алгоритмі 2 Тәжірибелік бөлім 2.1 Дейкстра алгоритмі 2.2 Программа кұру және нәтижесін алу Қорытынды Пайдаланылған әдебиеттер және интернет ресурстар тізімі КІРІСПЕ
Менің курстық жұмысымның тақырыбы Графтарда ең қысқа жолды анықтау – Дейкстра алгоритмі.
1.1 С++ тілінде бағдарламалау негіздері С++ тiлi BCPL жəне B тiлдердiң негiзiнде құралған жəне Си тiлiнен дамыған. BCPL тiлi компилятордан жазуға жəне операциялық жүйенi бағдарламамен қамтамасыз етуге арналған. Бұл тiлдi 1967 жылы Мартин Ричард ойлап тапқан. Кен Томпсон В тiлiнiң көптеген мүмкiндiктерiн BCPL дубликатында жəне В тiлiн UNIX операциялық жүйелерiнiң алғашқы версияларын құру үшiн 1970 жылы Bell Laboratories-те DEC PDP-7 компьютерiнде қолданылды. BCPL жəне В тiлдерi қолдануға тиiмсiз болды. Онда мəлiметтiң əрбiр элементi жадыда бiр сөздiң орнын алады жəне мəлiмет элементтерiн өңдеуде бағдарламашыларға ауыртпалығын тигiздi. Си тiлi В тiлiнiң негiзiнде дамыды. Си тiлiн Bell Laboratories-те 1972 жылы Деннис Ритчи DEC PDP-11 компьютерiнде жасады. Си BCPL жəне В тiлдерiнiң көптеген маңызды концепцияларын жəне мəлiмет типтерiн жəне басқа да қасиеттерiн қолданды. Си тiлi UNIX операциялық жүйесiн өңдеудегi тiл ретiнде кеңiнен танымал болды. Қазiргi таңда барлық операциялық жүйелер Си жəне Си++ тiлдерiнде жазылған. Соңғы он жылдықта Си тiлi көптеген компьютерлерде қолайлы болды. C++ C тілінің кеңейтілген түрі. Оны 1980 жылдың басында Бьерн Строустроп Bell-Labaratories-сында өндеп шығарған. C++ тілі C тілінің бiрқатар қасиеттерiн реттеудi қамтамасыз етедi жəне ең маңыздысы объектiбағдарланған бағдарламалық мүмкiндiгiн қамтамасыз етедi. Бұл бағдарламамен қамтамасыздандыру əлемiндегi революциялық идея болып табылады. Басқада бағдарламалық тiлдер көптеген қажеттi эффект бере алмағандықтан, Си++ алғашқыда ең жоғарғы деңгейдегi нақтылы оқиғалар үлгiлерiн өңдеу мақсаты үшiн құрылған тiл болды. Си++ тiлiн құруда Си тiлiнiң сəйкестiгiн сақтап қалуға ерекше көңiл бөлiндi. Си++ тiлiнiң көмегiмен кең көлемдi бағдарламалық проектiлер құруға болады. Си++ тiлiнiң арқасында берiлген мəлiметтер типтерiне бақылауды күшейтуге жəне көптеген қосымша эффектiлердi жеңе алатын болдық. Си++ тiлiнiң ең маңызды табысы объектi-бағдарланған бағдарламалау болып табылады. Си++-тiң барлық жеңiлдiктерiн пайдалану үшiн негiзгi объектiлердi жəне олармен байланысқан операцияларды анықтап алу керек.1 Си++ тiлiнiң негiзгi түсiнiктерi Си++ тiлiн 1972 жылы Денис Ритчи ашты. 1982 жылы осы тiлдiң стандарты пайда болды. Си++ Си тiлiнiң кеңейттiлген түрi. Сондықтан да Си-де жазылған бағдарламалар Си++ тiлiнiң компиляторы арқылы өңделуiне болады. Компилятор дегенiмiз – 3 процессордан тұратын, əрқайсысы жеке-жеке тəуелсiз бағдарламалар: 1. Препроцессор 2. Си++ компиляторының алдыңғы жобасы 3. Объектi кодтың генераторы Си++ - тегi кез-келген бағдарлама 3 жағдайда болады. 1. Бастапқы файл *.c; *.cpp; *.c++; Бұл файлды оқуға, қағаз бетiне түсiруге, өңдеуге болады. 2. Компиляциядан өткен бағдарлама объектi файл болады. *.obj; *.o; 3. Орындалу файлы. Компоновщик қосылғаннан кейiн орындалатын файл болады. *.ехе; Бұл файлды компютерде орындауға болады. Кітапханалық файлдар *.lib. Кейбір кітапханалық файлдардың компиляцииядан өткен кодтары болады. ол екiлiк жүйеде жазылған. Сондықтан оның сұлбасын былай көрсетуге болады: MYP.CPP – MYP.OBJ – MYP.EXE Бағдарламаға қажеттi функциялар компилятормен бiрге келедi. Олар мына тақырыптар файлында (header file) болады: *.h; Си алгоритмдiк тiлдiң компиляторлары интеграцияланған ортада – IDE немесе UCP-де жұмыс жасайды. ол дегенiмiз бiр бағдарламаны өңдеу үшiн редакторға, компиляторға, компоновщикке жəне басқа көмекшi құралдарға менюдiң керектi пунктерi арқылы жетуге болады. Си++ тiлiнiң ерекшелiктерi Бүтiн тұрақтылар ондық жүйеде сегiздiк жүйеде жəне он алтылық жүйеде болуы мүмкiн. Бұл тiлде модифиикатор деген түсiнiк бар. Бүтiн тұрақтыларға қолданылатын екi модификатор бар: Unsigned (таңбасыз); Signed (таңбамен); С++ өте ықшамды. Басқа да маңызды ерекшелiктерi бар: 1. С++ енгiзу шығаруды қамтамасыз ету үшiн сыртқы стандарттық библиотекаға қарайды. Бұл библиотеканы қолдану үшiн қажеттi программа iostream.h файлында орналасқан. 2. include сияқты дерективалар жиынын өңдеу үшiн С++ препроцессордi қолданады. Ол программаны алдыңғы формадан таза С++ синтаксисi формасына айналдыру үшiн қажет. Бұл дерективалар # символынан басталады. 3. С++ программасы əртүрлi файлдарда орналасқан хабарламалардан тұрады. Əрбiр файл сыртқы немесе ауқымды деңгейде орналасқан жəне енгiзiлген əдiс түрiнде хабарлануы мүмкiн емес. Файлдар модульдер сияқты қызмет атқарады жəне жеке компиляциядан өтуi мүмкiн. 1.2 С++ программалау тілінде қарапайым есептер құру Таңдау операторлары Си жəне С++ тiлдерiнде 4 базалық таңдау инструкциялары бар: if , if else, switchcase жəне whileforgoto операторы. Бұлардың əрқайсысына жеке тоқталу алдында, шартты өрнектердi құрудың жалпы принциптерін еске салайық. Таңдау инструкциясы бір немесе бірнеше қатардан құралған программада анықталған блоктарының таңдаулы орындалуы үшін қолданылады. if операторы жəне if else операторы if жалғыз инструкциясы берiлген шарт шын немесе жалған екендiгiн тексеретiн коммандаларды немесе коммандалар блогын орындауға арналған. Төменде if операторының қарапайым түрi көрсетiлген: if (шарт) өрнек; Назар аударыңыз, мұнда шарт жақшаға алынған. Егер шартты тексерi нəтижесiнде true мəнi қайтарылса, онда өрнек орындалады, сонан кейiн басқару программаның келесi жолына берiледi. Егер шарт нəтижесi false болса, онда өрнектен аттап өтедi. if else операторы шартқа тəуелдi екi əрекеттiң бiреуiн таңдаулы орындауға мүмкiндiк бередi. Төменде берiлген инструкцияның синтаксисi көрсетiлген: if (шарт) өрнек1; else өрнек2; Егер шартты тексеру нəтийжесi true болса, онда өрнек1 орындалады, қарсы жағдайда - өрнек2. While for goto операторы While (өрнек) оператор Басында өрнек есептелінеді. Егер де ол ақиқат болса онда ол операторлар орындалады цикл басына қайта өтеді нəтежесінде цикл while оператор жалған болғанша орыналады.Осы нүктеден келесі операторға көшеді.Солар бойынша,оператор бірнеше рет орындалады. Мысалы оператор While: int=1,sum=0; while (I=10){ sum+=1; ++1 } Оператор for For (өрнек1;өрнек2;өрнек3) Оператор Келесі оператор Бірінші өрнек 1 есептеледі əдетте өрнек 1 қолданылады айнымалыны инициализациялау үшін циклде пайдаланынады.Содан кейін өрнек 2 есептеледі.Егер де ақиқат болмаса,онда операторлар орындалады, өрнек 3 есептеледі басқару тағыда for циклініің басына көшеді, шығарып тастауға өрнек 1 есептеп өткізеді.Осы интерация жалғаса береді өрнек 2 жалған болғанша осыдан кейін келесі операторларға көшеді. for(int i=1, sum=0; i=10; ++1) sum+=1; Оператор for бүкіл өрнекте қатыспауындамүмкін,міндетті түрде нүкте үтір қою керек.Егер де өрнек 1 қатыспаса онда цикл бөлімі сияқты қадам орындалмайды.Егер де өрнек 3 қатыспаса цикл бөлімі өсім қадам сияқты орындалмайды. Арнайы ерекшебар егерде өрнек 2 қатыспаса. Осы жағдайда тексерімей нəтеже - əрқашанда ақиқат осыған байланысты цикл for кодта for(i=1, sum=0; sum+=I++) coutsumend1; шексіз болып келеді. Оператор Goto Оператор goto-шартсыз көшу еріктігі белгілеу операторлары функция деп аталады. Тамға-идентификатор Goto операторы мына формада орындалғанда goto тамға; шартсыз басқару белгіленген операторға беріледі. Мысалы, if (d==0.0) goto error else ratio=hd; error:cerr’’error:division by zero\n’’; жəне goto операторы,белгіленгенге сай оператор сол функцияның денесінде болу міндетті. switchcase операторы Көбiне айнымалыны тұтас мəндер қатарына теңдiгiн тексеру қажеттiгі туады. Бұны if else if конструкциясы көмегімен орындауға болады, немесе ұқсас switchcase конструкциясының көмегңмен орындауға болады. Көңiл аударыңыз, switch инструкциясы Си тiлiнде бiрнеше қатар ерекшелiгi бар. Оның синтаксисi келесi: switch (бүтiнсанды_өрнек) { case тұрақты1: өрнек1; break; case тұрақты2: өрнек2; break; case тұрақты -n: өрнек -n; break; default: үнсiз_келiсiм_бойынша_əрекет; } Ескерту:break операторы соңғысынан басқа барлық тарамдарда қайталанады. Егер бiрiншi тарамда бұл инструкцияны жоятын болсақ, онда өрнек1-ден кейiн өрнек2 орындалады, ол арқашан тиiмсiз. Осылайша, break операторы case тарамдарының бiреуi орындалғаннан кейiн басқа тарамдарынан аттап өтедi. Массивтер Массив дегенiмiз – бiр типтi реттелген мəлiметтер жиынын қамтитын айнымалы. Массивтiң əрбiр элементiне оның адресi бойынша қатынас құруға болады. Си жəне С++ тiлдерiнде массив мəлiметтердiң стандартты типi болып саналмайды.Си жəне С++ тiлiнде массивтi құру жəне онымен жұмыс iстеу негiзiнде бiрдей болады. Массивтердiң қасиеттерi Төменде массивтiң қасиетiн анықтайтын төрт негiзгi принциптер келтiрiлген: • Массивте жеке мəндер сақталынады. Олар элементтер деп аталады. • Массивтiң барлық элементтерi бiр типтi болу қажет. • Массивтiң барлық элементтерi жадыда тiзбектi түрде сақталынады жəне бiрiншi элемент адрестiң нольдiк жылжуын алады, яғни нөлiншi индекс. • Массив аты тұрақты болып саналады және Массивті баяндау Төменде массивтi баяндау мысалдары берiлген: int array[12]; * 12 бүтiн саннан тұратын массив * char carray[20]; * 20 символдан тұратын массив * Қарапайым айнымалыларды сипаттағандай массивтердi баяндау, оның мəлiметтер типiн көрсету арқылы орындалады. Одан кейiн массив аты жəне екi тiк жақша қою керек. Олар массив размерiн анықтайды. Тiк жақшалар iшiнде тек тұрақтылар тұруы мүмкiн. Компилятор массивке қанша көлем жадыдан бөлу керектiгiн дəл бiлуi қажет. Сондықтан массив размерi алдын ала берiледi жəне программаның орындалу уақытында өзгертiлуi мүмкiн емес. Массивтердi инициалдауды 3 тəсiлдiң бiреуiн қолдану арқылы жүзеге асырамыз: • Массивтi құру кезiнде – инициализациялауды үнсiз келiсiм бойынша қолдану арқылы (бұл тəсiл тек ауқымды жəне статикалық массивтер үшiн қолданылады); • Массивтi құру кезiнде – бастапқы тұрақты мəндi анық көрсету арқылы жүзеге асады. • Программаның орындалу процессiнде – массивке мəлiметтердi жазу жолы арқылы жүзеге асады. Массивтер көлемiне қарай бiр өлшемдi, екi өлшемдi жəне көп өлшемдi болады.2 1.3 Графтар теориясының негіздері Табиғаттың кез-келген объектісінен алынған төбелер деп аталатын V – жиыны (оларды жазықтықта нүктелер түрінде көрсетуге болады) және қабырға деп аталатын, ei=(vi1, vi2), vijÎV, төбелер жұбының жиыны (оларды доғалармен, немесе екі төбе арасындағы бағыттармен көрсетеді) - E болатын екі жиыннан тұратын G = (V,E) жұбы граф деп аталады. V –төбелер жиыны, E –қабырғалар жиыны деп аталады. Егер ei қабырғасын беретін төбелер ретінің мәні болса, онда граф бағдарланған (ориентирациялы) граф қысқаша – орграф деп деп аталады. Бұл жағдайда графтың доғасына (қабырғасына) бағыт көрсетеді және бір төбесін басы екіншісін –соңы деп айтады. Қарсы жағдайда граф бағдарланбаған (ориентирациясыз, бағдарсыз) деп аталады. Алдағы жағдайларда бағдарланғандығы көрсетілмеген, нақтыланбаған «граф» сөзін бағдарланбаған граф деп есептейміз Қарапайым графтың ілгегі және еселі қабырғасы болмайды. Қарапайым графты жай граф деп те айтады. Оларды еселі қабырғалары бар графтардан ажырату үшін еселі қабырғасы бар графтарды мультиграф деп айтады. Ары қарай тек ақырлы графтарды ғана қарастырамыз. G = (V,E) –графы толық болады, егер кез-келген екі төбесі бір қабырғамен түйіскен (бір ғана қабырғамен байланысқан) болса, яғни, кез-келген төбелер жұбы сыбайлас (қандайда бір қабырғамен байланысқан) болатын бағдарсыз граф. Kp деп белгіленеді, мұндағы р = |V| - төбелер саны, мұнда қабырғалар саны |Е| = p(p-1)/2 –ге тең болады. Қабырғасы жоқ G = (V,E) – графы бос деп аталады, Е = Æ [белгіленуі - Nm]. Байланысты граф деп кез-келген төбелер жұбынан бір-біріне өтуге болса, яғни кез-келген төбеден екінші төбеге өтетін жол (маршрут) болса. Граф байланысты болады, сонда және тек қана сонда, егер оның төбелер жиынын әр қабырғасының екі шеткі нүктелері бір жиында қалатындай екі бос емес жиындарға бөлуге болса. Байланысты графтардың қасиеттері. а) байланысты граф бір қабырғасын жойғаннан кейін де байланысты болып қала береді, егер бұл қабырға циклде болса. б) К төбесі бар байланысты графтың К-1-ден аз емес қабырғасы болады. в) байланысты графта кез-келген максималды ұзындықты қарапайым екі тізбесінің тым болмаса бір ортақ төбесі болады. г) N төбесі бар және К байламдық компоненттері бар графтың қабырғалар саны 1/2(N-K)(N-K+1)-ден артпайды. Байланысты графтың екі төбесінің ара қашықтағы деп осы төбелерді қосатын ең қысқа тізбенің (жолдың, маршруттың) ұзындығын айтамыз, яғни қысқа жолдағы қабырғалар саны. Мысалы, Сурет-1 де көрсетілген G1 графының А төбесінен D, E және F төбелеріне дейінгі қашықтық 1-ге тең ал, В және С төбелеріне дейінгі қашықтық 2-ге тең: r(A,D) = r(A,E) = r(A,F) = 1, r(A,B) = r(A,C) = 2. Графтың төбесінің эксцентриситеті деп берілген төбеден басқа төбелерге дейінгі қашықтықтардың ең үлкенін айтамыз. G1 графы үшін А төбесінің эксцентриситеті 2-ге тең: е(А) = 2, басқа төбелердің де эксцентриситетін табу қиын емес: е(В) = е(С) = е(D) = e(E) = e(F) = 2. Графтың радиусы ретінде төбелерінің эксцентриситеттерінің ең кішісін алады, ал диаметрі – максималды эксцентриситет. G1 графында радиус пен диаметр беттеседі: R(G1) = D(G1) = 2. Графтың төбесінің дәрежесі деп осы төбеге тиісті болатын (түйіскен) қабырғалар санын айтамыз. Графтың төбелерінің дәрежелерінің өсу ретімен немесе кемі ретімен берілген тізімі вектор-дәрежесі деп аталады. Мысалы, G1 графында ол (3,3,4,4,4,4) –ге тең, сурет-2 де көрсетілген G2 графында ол (1,2,2,2,3). Дәлелдеуі өте қарапайым. Графтың барлық төбелерінің дәрежелерінің қосындысы қабырғаларының екі еселенген санына тең. G2 графын сурет-2 ден басқа етіп, мысалы 6.3 суреттегідей салуға болады. Бұған көз жеткізу үшін G2 графтың А1 төбесіне- сурет-3 дегі графтың А төбесін сәйкес қоюға болады, А2 төбесіне–D төбесін А3 төбесіне – Е төбесін, А4 төбесіне –В төбесін, А5 төбесіне –С төбесін сәйкес қоюға болады. Нәтижесінде, екі графтың төбелерінде өзара бірмәнді сәйкестік орнады. Мұндай жағдайда бұл суреттердегі графтарды өзара изоморфты деп те айтады. Изоморфты графтардың вектор-дәрежесі бірдей. Кері тұжырым дұрыс емес. Мысалы, Сурет-4 дегі G4 пен G5 изоморфты емес, себебі G4 графында ұзындығы 3-ке тең цикл жоқ, ал G5 графында ол бар, А1А2А3-ке тең. Бірақ, бұл графтарда вектор–дәрежелері тең: (2,2,2,2,3,3). Граф жазық деп аталады, егер жазықтықта оның қабырғалары тек төбелерде ғана қиылысса. Граф планарлы деп аталады, егер оның жазық кескіні болса. 3 және 4 суреттерде –жазық графтар, 2 суретте планарлы граф, себебі оның изоморфты жазық кескіні бар, ол G3 графы. Ал 1 суреттегі граф планарлы да болмайды. Оны келесі теоремадан көруге болады. 6.3 теорема. Граф планарлы болмайды,сонда және тек қана сонда егер келесі шарттардың бірі орындалса: а) (Понтрягин-Куратовский) Графтың толық бес төбелі К5 немесе К3,3 графына (төменде айтылады) гомеоморфты болатын ішкі графы болады; б) (Харари-Татта) Графты қабырғасын созу арқылы немесе кейбір элементтерін жою арқылы К5 немесе К3,3 графтарына гомеоморфты графқа айналдыруға болады. Графтар гомеоморфты болады, егер біреуі екіншісінен қабырғаларын желімдеу немесе бөлу операцияларының көмегімен алынатын болса (6.6 сурет). АВ қабырғасын созу, АВ қабырғасы жойылады, А және В төбелері бір төбеге айналады және осы жаңа төбе А және В төбелерімен сыбайлас болған барлық төбелермен жалғасады (6.7 суретті қараңыз). Графтардың матрицалық берілуі Графтарды сурет түрінде беру үнемі ыңғайлы бола бермейді. Мысалы, ЭЕМ-де оларға операциялар қолдануда. Бұл үшін графтың матрицалық берілу тәсілдері қолайлы. Одай әдістердің бірі сыбайлас матрица әдісі. Егер G графында n төбе болса, онда оның сыбайлас матрицасының M(G) = n жолы және бағанасы болады. Ол үшін i,j орнына яғни, i-жол мен j-бағанаға 1-ді қоямыз, егер G-да i-жолдан j–бағанаға қабырға болса; қарсы жағдайда 0 қоямыз: 2 және 3 суреттердегі графтар үшін матрицалар келесідей болады: M(G2) = ; M(G3) = , Мұнда G3 графында төбелер алфавиттік түрде реттелген деп есептедік, янғи А-бірінші, В-екінші, С-үшінші, т.с.с. G2 пен G3 графтары изоморфты ( белгіленеді) болса да, олардың сыбайлас матрицалары әртүрлі. Бірақ осы графтардың изоморфтығын дәлелдеуде біз G2 графының бірінші төбесіне G3 графының бірінші төбесін сәйкестікке қойдық, екіншіге – төртіншісін, үшінші-бесіншісін, төртіншіге – екіншісін, ал бесіншіге – үшіншісін. M(G2) матрицасында алдымен, жолдарын ауыстырамыз, біріншісін орнында қалдырамыз, екіншісін төртіншісінің орнына, үшіншісін – бесіншісінің, төртіншісін – екіншісінің, ал бесіншісін – үшіншісінің орнына қоямыз. Содан кейін дәл осы түрлендіруді бағандарға жасаймыз. Нәтижесінде, M(G3) матрицасын аламыз: M(G2)= =M(G3). Сыбайлас матрицаны қарапайым граф түрінде де беріге болады, бұнда негізгі диагоналі нөлдер болатын, симметриялы матрица және фультиграф түрінде жазуға болады. Соңғы жағдайда (i,j)-дің орнына басы i-төбеде болатын, соңы j-төбеде болатын қабырғалар санын жазамыз. Мұндағы матрица симметриялы емес болуы мүмкін. Кері есеп - сыбайлас матрицасы бойынша графты салу қиын емес. Жазықтықта n нүкте (жолдары мен бағандарының санына байланысты) белгілейміз, нүктелерді шеңбер бойымен орналастырған ыңғайлы. Егер берілген матрица симметриялы болмаса, онда сәйкес нүктелер бағыттармен жалғанады, қарсы жағдайда – граф бағдарсыз, сондықтан нүктелерді тек сызықтармен қоса саламыз. Егер граф жазық болып кескінделетінін көруге болса, онда олай да салуға болады, бұл сурет графтың планарлығын негіздеуге жеткілікті болады. Графтардың көптеген қолдануларында қандай төбелері сыбайлас екенін білу аздық етеді, сонымен қатар қайсыбір төбесі мен қабырғасының салмағын білу де маңызды рөл атқарады. Бұл салмақтар берілу жағдайларына байланысты әртүрлі жағдайды білдіреді: ара қашықтық, шығындар, кіріс, жұмыс істеуге кететін уақыт, жағдайдан шығу ықтималдығы т.с.с. Бізге, ереже ретінді қабырғаларының салмағы ғана қажет болады. Егер қосымша төбелер мен қабырғалар енгізсе, онда 6.8 суретте осы операцияға сипатттама береді. Қабырғаларының салмағы берілген графтарды (өлшенетін графтар) салмақтар матрицасы түрінде беру ыңғайлы. Оның сыбайлас матрицадан айырмашылығы i–жолдың j–орнында i–төбеден j–ге баратын қабырғасының салмағы тұрады. Сонымен қатар, i–төбеден j–бағанаға сәйкес келсе, онда салмақтар матрицасындағы сәйкес орында ереже бойынша 0 емес, берілі жағдайына байланысты сызықша, немесе шексіздік немесе минус шексіздік белгісі тұрады. Мысалы, 6.2 суреттегі G2 графта салмақтар келесідей: u1 = 3, u2 = 4, u3 = 2, u4 = 7, u5 = 0, онда оның салмақтар матрицасы келесідей болады: 6.2.3 Кейбір жағдайларда графты инцидент (түйісу) матрицасы арқылы берген ыңғайлы болады. Бұл матрица тік бұрышты, онда графта қанша төбе болса, сонша жол болады, ал бағандар саны қабырғалар санымен тең. Оны толтырғанда төбелері ғана емес, қабырғалары да нөмірленеді, және i–ші және j–ші жолдарының k–шы бағаналарына бірлер қойылады, егер k нөмірлі қабырға i–ші және j–ші төбелерді біріктірсе. Қалған орындарға нөлдер қойылады. Графта ілгек (бастапқы және соңғы төбелері беттесетін қабырға) болса, оған сәйкес бағанаға тек бір ғана «1» жазылады. Кейде ыңғайлы болу үшін, оның орнына «2» қояды. L(G) матрицасы 6.9 суреттегі G графының инцидент матрицасы болады. Іздер мен өтулер 6.3.1 Жол (тізбе) – деп графтың қабырғалары екі рет кездеспейтін ізді айтамыз. Мысалы, 6.4 суреттегі G5 графында А1А2А3А1А6АА4А3А1 ізі жол болмайды, себебі мұнда А1А3қабырғасы екі рет кіріп тұр. Графта Эйлер жолы (өтуі) деп графтың барлық қабырғаларын құрайтын жолды айтады, яғни жолда графтың әр қабырғасы бір рет кездесу керек (төбелеріне қатысты ештеңе айтылған жоқ, сондықтан кез-келген жолда төбелер қайталанып кездесуі мүмкін). Эйлер жолы бар граф эйлер графы деп аталады, егер осы жолдың басы мен соңы беттессе, онда граф эйлер циклі деп аталады. Жеңіл дәлелденеді. 6.4 теорема. а) Байланысты граф эйлер циклі деп аталады, сонда және тек қана сонда, егер оның барлық төбелері жұп дәрежелі болса. б) Байланысты графта басы А төбесінде, соңы В төбесінде болатын эйлер өтуі болады, сонда және тек қана сонда, егер А мен В төбелерінің дәрежелері тақ, ал қалған төбелерінің дәрежесі жұп болса. 6.3.2 Мағынасы бойынша жақын болатыны – гамильтондық граф. Гамильтондық цикл (жол) деп бастапқа төбені қоспағанда, графтың әрбір төбесінен бір реттен өтетін (кейбір қабырғалардан мүлдем өтпеуі де мүмкін) циклді (жолды) айтамыз. Эйлер циклі есебінің сыртқы ұқсастығына қарамастан, гамильтондық цикл бар граф анағұрлым күрделі. Қазіргі таңға дейін гамильтондық белгілердің біраз ғана жеткілікті белгілері бар ал, қажетті бергілері әлі де аз. Байланысты графтың n төбесі болсын. а) (Оре). Егер кез-келген төбелер жұбының дәрежелерінің қосындысы n-1 –ден аз емес болса, онда берілген графта гамильтон циклі болады. б) (Дирак). Егер графтың әр төбесінің дәрежесі n/2-ден аз емес болса, степень каждой вершины графа не менее n/2, берілген графта гамильтон циклі болады. в) (Хватал) (d1,d2,…,dn) – G графының вектор-дәрежесі болса және ,және кез-келген k үшін және және теңсіздігі орындалса, онда G графы – гамильтондық цикл болады. Аспалы төбелері бар графтар, яғни дәрежесі 1-ге тең болатын графтар, гамильтондық емес цикл болып табылады. Сонымен қоса, 6.10 суретте көрсетілген графта гамильтондық цикл жоқ. Одан біртіндеп қабырғаларын бөлу арқылы алынған графғ яғни дәрежесі екіге тең төбелер қосылғанда, тэтта-граф деп аталады. Бұдан төмендегі теореманы алуға болады. 6.6 теорема. Егер графта тэтта-ішкіграф болса, онда ол гамильтондық цикл емес. Қарапайым жағдайларда, есептердегі графтар қандай болады, осы екі белгілер графтың гамильтондық еместігін анықтауға толығымен жеткілікті. Егер сызбадан гамильтондық өту көре алсаңыз, оны көрсетіңіз, бірақ, егер 5-теореманы қолдана алсаңыз онда бұл сізге қосымша артықшылықтар болады. Ағаштар мен қаңқа 6.4.1 Ағаш–циклсіз байланысты граф. Ағаштар тәжірибеде әртүрлі иерархияларды салуда кездеседі. Графта циклдің болуы оның цикломатикалық санын (әрине, мұнда графтың сызбасымен жұмыс істемейміз) анықтауда көп көмегін тигізеді: , мұндағы m–қабырғалар саны, n – төбелер саны, k – байланыстылық компоненттерінің саны. Мысалы, 6.10 суретте көрсетілген графта бір ғана байланыстылық компоненті болғандықтан, оның цикломатикалық саны 6–5+1=2 болады. 6.11 суреттегі графта байланыстылық компоненттері екеу: G1 мен G2 ішкі графтары, сондықтан оның цикломатикалық саны: (6+6)–(7+5)+2=2. Егер әрбір байланыстылық компоненттерін жеке-жеке граф деп қарастырсақ, онда олардың цикломатикалық сандары: және . G1 ағаш болатынын көреміз. Келесі теорема теңдігі кездейсоқ емес болғандығын көрсетеді. 6.7 теорема. Кез –келген графтың цикломатикалық саны –теріс емес сан болады, және ол нөлге тең болады, сонда және тек қана сонда, егер графта цикл болмаса. Ағаштардың келесі қасиеттері жиі қолданылады. 6. 8 теорема. N төбелі ағаштардың эквивалентті анықтамалары. а) N-1 қабырғасы бар және циклсіз граф. б) N-1 қабырғасы бар және байланысты граф. в) Байланысты граф және кез-келген қабырғасын жою оны байланыссыз етеді. г) Кез-келген төбелер жұбы жалғыз ғана жолмен (тізбемен) жалғанады. д) Циклсіз граф және кез-келген екі төбенің арасына қабырға қосу тек бір ғана цикл қосуға келтіреді. Байланысты графтың қаңқасы (арқау, арқаулы ағаш) деп графтың барлық төбелері ағаштар болатын, ішкі графты айтамыз. Қаңқаны көрсетерде оны құрап тұрған қабырғаларды жазып шығаыд. Мысалы, 6,11 суреттегі G2 графта (AB), (BD), (DC), (BE) ағашы қаңқа болып табылады. Бір графта бірнеше қаңқа болуы мүмкін екенін көру қиын емес. 6.4.2 Тәжірибелік сабақтар үшін бірқатар маңызды тапсырмаларда (сабақ кестесін құру, құрылғыларды бөліп беруде т.с.с.) графтың төбелерін немесе қабырғаларын бояуға әкеледі. Біз дұрыс төбелік бояуларды ғана қарастырамыз, яғни графтың кез-келген сыбайлас төбелері әртүрлі түске боялған жағдайлар. Мұндай дұрыс төбелік бояуларды қысқаша бояулар деп қана айтамыз. Мысалы, 6. 11 суретте G2 графын үш түске бояуға болады: А, Е және D төбелерін бір түспен бояймыз, В мен С төбелерін – басқа түспен бояймыз, үшінші түс қолданылмай қалды. Сонымен, G2 графы 2-бояулы және 3-бояулы болады. G графы k-бояулы болса, онда k-ның минималды саны осы графтың хроматикалық саны деп аталады және деп белгіленеді. Жалпы жағдайда хроматикалық санды табуға арналған есептер өте күрделі келеді. Бірақ, төбелер саны аз (10-ға дейін) болса, оны «қолмен» санап есептеуге болады. Мысалы, біз G2 графының нақты екі бояуын көрдік, кез-келген бос емес, яғни тым болмаса бір қабырғасы бар графты екіден аз түспен бояуға болмайды, сондықтан Басқа жағдайларда, нақты бір бояулары көрсетілген соң, қандай жолмен түстер санын кемітуге болатыны көрінбейді, минималды бояу алғанымызды негіздеп алуымыз керек. Бұған келесі жағдай көмектесе алады: 1) n төбесі бар Kn толық графтың хроматикалық саны n-ге тең; 2) Kn толық графының бір қабырғасын жою арқылы алынған графтың хроматикалық саны n – 1-ге тең; 3) жұп төбелі жай циклдің хроматикалық саны 2-ге тең, ал тақ болса – 3-ке тең; 4) тұтас бір графтың хроматикалық саны оның кез-келген ішкі графының хроматикалық санынан кем емес. Сондықтан, мысалы, графы 4түске бояуға мүмкіндік болса және одан К4 ішкі графын (диагональдары жүргізілген төртбұрыш) көрсеңіз, онда осы графтың хроматикалық саны 4-ке тең болады. Келесі хроматикалық санды бағалаулардың пайдасы зор. 9 теорема. белгісі G графының төбелерінің ең үлкен дәрежесін білдірсін. Онда келесі теңсіздіктер орынды болаыд: а) ; б) (Брукс) егер G – байланысты және толық емес граф болса және , онда . 6.4.3 Келесі келтірілетін графтар туралы ұғымдардың тәжірибелік маңызы өте зор. Белгіленген граф деп – қабырғасы және/немесе төбесі нөмірленген графтарды айтамыз. Мысалы, 6.2 және 6. 3 суреттердегі G2 мен G3 графтары, сәйкесінше изоморфты граф ретінде бірдей болғанмен, A, B, C, D, E төбелерін алфавиттік түрде реттелген деп есептесек, онда олар белгіленген граф ретінде әртүрлі графтар болады. Көп полюсті желі деп –төбелері белгіленіп көрсетілген орграфты айтамыз. Екі полюсті желі деп – екі белгіленіп көрсетілген төбелері бар желіні айтамыз. Әлді байланысты орграф (әлді орграф) деп кез-келген екі төбелерінен бір-біріне бағыт бойымен (қабырға бойымен) жетуге болса. Біржақты байланысты орграф (Біржақты орграф) бұл – кез-келген төбелер жұбы біржақты байланысты болатын, яғни кез-келген төбеден қалған төбелерге қабырға бағытымен, ал кері жол болмауы да мүмкін. Әлсіз байламды орграф (әлсіз орграф) деп доғасының бағдарын өзгерткен соң байланысты болып қалатын орграфты айтамыз. k-байланысқан граф (k-төбелі байланысқан граф) деп кез-келген k-1 төбесін жойған соң, байланысты болып қалатын графты айтамыз. k-қабырғалы- байланысқан граф деп кез-келген k-1 қабырғасын жойған соң, байланысты болып қалатын графты айтамыз. Біртекті (реттелетін k-реттелуші) граф деп барлық төбелерінің дәрежелері бірдей k-ға тең болатын графты айтамыз. (n, m)-граф деп – нақты n төбесі бар, m қабырғасы бар графты айтамыз. Қосымша граф ~G графы – G графында қанша төбелер жиыны болса, сонша төбелер жиыны бар граф және ~G-дың екі төбесі сыбайлас болады, сонда және тек қана сонда егер осы төбелер G-да сыбайлас болмаса.3 2 ТӘЖІРИБЕЛІК БӨЛІМ 2.1 Дейкстра алгоритмі Ең қысқа жолды табудың мысалын қарастырайық. Қала аймақтарын байланыстыратын автомобиль жолдарының желісі берілген. Кейбір жолдар бір бағытта жүреді. Қала орталығынан ауданның әр қаласына ең қысқа жолдарды табыңыз. Бұл мәселені шешу үшін Дайкстра алгоритмін - 1959 жылы голландиялық ғалым Э.Дейкстра ойлап тапқан графиктер бойынша алгоритмді қолдануға болады. Графтың бір төбесінен басқаларына дейін ең қысқа қашықтықты табады. Теріс салмақ жиектері жоқ графиктер үшін ғана жұмыс істейді. 1 шыңнан басқаларына дейін ең қысқа қашықтықты табу талап етілсін. тұтқалар шыңдарды, сызықтар олардың арасындағы жолдарды (графиктің шеттері) көрсетеді. Шеңберлер төбелердің сандарын көрсетеді, шеттерінен жоғары олардың салмағы - жолдың ұзындығы көрсетілген. Әр шыңның жанында қызыл затбелгі бар - бұл шыңға 1 шыңнан ең қысқа жолдың ұзындығы. Инициализация 1 төбеның жапсырмасының өзі 0-ге тең, қалған шыңдарының белгілері - қол жетпейтін сан (идеал бойынша, шексіздік). Бұл 1 төбеден басқа төбелерге дейінгі арақашықтықтардың әлі белгісіз екендігін көрсетеді. Графиктің барлық төбелері шақырылмаған деп белгіленеді. Алғашқы қадам 1 төбеде минималды затбелгі бар, оның көршілері - 2, 3 және 6 төбелері. Біз төбеның көршілерін кезекпен айналып өтеміз. 1 төбеның бірінші көршісі - 2 төбе, өйткені оған жол ұзындығы минималды. 1 төбе арқылы өтетін жолдың ұзындығы 1 төбеге дейінгі ең қысқа қашықтықтың қосындысына (оның белгісінің мәні) және 1-ден 2-ге дейінгі жиектің ұзындығына тең, яғни 0 + 7 = 7. Бұл 2-төбеның қазіргі таңбасынан аз (10000), сондықтан 2-төбеның жаңа белгісі 7-ге тең. Сол сияқты, біз барлық басқа көршілер үшін жолдың ұзындығын табамыз (3 және 6 төбелері). 1 төбеның барлық көршілері тексеріледі. 1 төбеге дейінгі ең аз қашықтық соңғы болып саналады және қайта қарауға жатпайды. 1 төбе барған ретінде белгіленеді. Екінші қадам Алгоритмнің 1-қадамы қайталанады. Қаралмаған шыңдардың қайсысын «ең жақын» деп табыңыз. Бұл 7 деп белгіленген 2 төбе Біз қайтадан таңдалған төбеның көршілерінің жапсырмаларын азайтуға тырысамыз, оларға екінші төбеден өтуге тырысамыз. 2 төбеның көршілері - 1, 3 және 4 төбелер. Vertex 1-ге бұрыннан барған 2 төбеның келесі көршісі - 3 төбе, өйткені онда төбелердың минималды белгісі барылмаған деп белгіленеді. Егер сіз оған 2 арқылы барсаңыз, онда мұндай жолдың ұзындығы 17-ге тең болады (7 + 10 = 17). Бірақ үшінші төбеның қазіргі таңбасы 9, ал 9 <17, сондықтан белгі өзгермейді. 2 төбеның тағы бір көршісі - 4 төбе. Егер оған 2-ші арқылы баратын болсаңыз, онда мұндай жолдың ұзындығы 22-ге тең болады (7 + 15 = 22). 22 <10000 болғандықтан, төбе белгісін 4-тен 22-ге дейін қойыңыз. 2 төбеның барлық көршілері қаралды, біз оны барған деп белгілейміз. Үшінші қадам Алгоритмнің қадамын 3 шегін таңдау арқылы қайталаймыз, оны «өңдегеннен» кейін келесі нәтижелерге қол жеткіземіз. Төртінші қадам Бесінші қадам Алтыншы қадам Осылайша, 1 төбеден 5 төбеге дейінгі ең қысқа жол 1 - 3 - 6 - 5 шыңдары арқылы өтетін жол болады, өйткені осылайша біз 20-ға тең минималды салмақ аламыз. Ең қысқа жолдың шығуын қарастырайық. Біз әр шыңның жол ұзындығын білеміз, енді төбелерді соңынан қарастырамыз. Соңғы төбені қарастырайық (бұл жағдайда 5 шың), және ол байланысқан барлық төбелер үшін сәйкес шеттің салмағын соңғы төбенің жол ұзындығынан шығару арқылы жол ұзындығын табамыз. Сонымен, 5 төбеның ұзындығы 20-ға тең, ол 6 және 4 төбелерімен байланысқан. 6 төбе үшін біз 20 - 9 = 11 салмағын аламыз (сәйкес келеді). 4 төбе үшін біз 20 - 6 = 14 салмағын аламыз (сәйкес келмеді). Егер нәтижесінде біз қарастырылып отырған төбеның жол ұзындығымен сәйкес келетін мән алсақ (бұл жағдайда 6 төбе), онда дәл осы жерден соңғы төбеге көшу жүзеге асырылды. Бұл төбені біз қалаған жолмен белгілейміз. Әрі қарай, біз 6-төбеге жеткен шекті анықтаймыз. Сонымен, біз басымызға жеткенше. Егер осындай траверстің нәтижесінде қандай да бір қадамда бізде бірнеше төбелер үшін бірдей мәндер болса, онда олардың кез-келгенін алуға болады - бірнеше жолдың ұзындығы бірдей болады. Дейкстра алгоритмін жүзеге асыру Квадрат матрица графиктің салмағын сақтау үшін қолданылады. Жолдар мен бағандардың тақырыптарында графиктің шыңдары бар. Ал графикалық доғалардың салмақтары кестенің ішкі ұяшықтарына орналастырылған. Графикте циклдар жоқ, сондықтан матрицаның негізгі диагоналінде нөлдік мәндер бар4.
#define _CRT_SECURE_NO_WARNINGS #include #include #include #define SIZE 6 using namespace std; int main() { int a[SIZE][SIZE]; int d[SIZE]; int v[SIZE]; int temp, minindex, min; int begin_index = 0; system("chcp 1251"); system("cls"); for (int i = 0; i a[i][i] = 0; for (int j=i + 1; j cout<<"kashiqtikti engizingiz "< a[i][j] = temp; a[j][i] = temp; } } for (int i = 0; i for (int j = 0; j } for (int i = 0; i d[i] = 10000; v[i] = 1; } d[begin_index] = 0; do { minindex = 10000; min = 10000; for (int i = 0; i if ((v[i] == 1) && (d[i] min = d[i]; minindex = i; } } if (minindex != 10000) { for (int i = 0; i if (a[minindex][i] > 0) { temp = min + a[minindex][i]; if (temp < d[i]) { d[i] = temp; } } } v[minindex] = 0; } } while (minindex < 10000); cout< int end = 4; ver[0] = end + 1; int k = 1; int weight = d[end]; while (end != begin_index) { for (int i = 0; i { int temp = weight - a[i][end]; if (temp == d[i]) { weight = temp; end = i; ver[k] = i + 1; k++; } } } cout< cout< return 0;} Пайдаланылған әдебиеттер: Х.Дейтелб, П.Дейтел Как программировать на С++: Пер. С англ. – М.: ЗАО «Издательство БИНОМ», 2000г. К. Паппас, У.Мюрреи Программирование на С и С++: - К.: Издательская группа BHV, 2000г. Т.А.Павловская С/С++ программирование на языке высокого уровня СПБ.: Питер, 2001г. Универ Р. Язык Turbo C Москва: Изнательский дом «МИР», 1991г. Download 408.68 Kb. Do'stlaringiz bilan baham: 
|