ағдарламалау тілдері теориясы және орындалуы

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

Қазақстан Республикасының білім жӘне ғылым министрлігі
М.Х. Дулати атындағы Тараз өңірлік университеті

Ақпараттық технологиялар, автомитика және
телнкоммуникациялық____факультетіи нституты

__________Қолданбалы информатика және бағдарламалау________кафедрасы

КУРСТЫҚ Жұмыс

___________Бағдарламалау тілдері теориясы және орындалуы___________________

___________________________________ _______________________________пәні бойынша

Тақырыбы:___Графтарда ең қысқа жолды анықтау - Дейкстра алгоритмі _

Білімгер Исмоилов Бекзод Тобы__6B06114-201__ ______________
аты-жөні қолы
Жетекші____________________________ ________ __________________________
қызметі аты-жөні
Қорғауға жіберілді ____________________20____ж. __ ___________________
қолы

Жұмыс қорғалды __________________20__ж. Бағасы ___________________
жазбаша
Комиссия мүшелері: _________________________ _____ ___________
аты-жөні қолы

______________________________ _____________
аты-жөні қолы

Тараз 2021

Жоспар:

1. C++ тілінің негізгі түсініктер.
2. С++ қарапайым есептер құру
3. Графтар теореясінің анықтамасы
4. Дейкстра алгоритмі

Курстық жұмыстың тақырыбы
Курстык жұмыстың өзектілігі
Зерттеу обьектісі
Сілтеме матрицасын инициализациялау
Сілтемелер матрицасын шығару
Тік және қашықтықтарды инициализациялау
Табылған минималды салмақты қосыңыз
шыңның ағымдағы салмағына дейін
және шыңның қазіргі минималды салмағымен салыстыру
Төбелерге дейін ең қысқа қашықтықты көрсету
Жолды қалпына келтіру
Жол шығу (бастапқы шегі k элементтерінің жиымының соңында болған)
Курстык жұмыстың мақсаты
Міндеттері

С++ т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 жəне олармен байланысқан операцияларды анықтап алу керек.
Си++ т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 Таңдау операторлары Си жəне С++ тiлдерiнде 4 базалық таңдау инструкциялары бар: if , if else, switchcase жəне whileforgoto операторы. Бұлардың əрқайсысына жеке тоқталу алдында, шартты өрнектердi құрудың жалпы принциптерін еске салайық. Таңдау инструкциясы бір немесе бірнеше қатардан құралған программада анықталған блоктарының таңдаулы орындалуы үшін қолданылады.
1.2 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.

1.3 Whileforgoto операторы
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.
2 Массивтер
Массив дегенiмiз - бiр типтi реттелген мəлiметтер жиынын қамтитын айнымалы. Массивтiң əрбiр элементiне оның адресi бойынша қатынас құруға болады. Си жəне С++ тiлдерiнде массив мəлiметтердiң стандартты типi болып саналмайды.Си жəне С++ тiлiнде массивтi құру жəне онымен жұмыс iстеу негiзiнде бiрдей болады.
2.1 Массивтердiң қасиеттерi
Төменде массивтiң қасиетiн анықтайтын төрт негiзгi принциптер келтiрiлген: :: Массивте жеке мəндер сақталынады. Олар элементтер деп аталады.
:: Массивтiң барлық элементтерi бiр типтi болу қажет.
:: Массивтiң барлық элементтерi жадыда тiзбектi түрде сақталынады жəне бiрiншi элемент адрестiң нольдiк жылжуын алады, яғни нөлiншi индекс.
:: Массив аты тұрақты болып саналады және
2.2 Массивті баяндау
Төменде массивт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н емес.
2.3 Массивтерд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не қарай бiр өлшемдi, екi өлшемдi жəне көп өлшемдi болады.

Табиғаттың кез-келген объектісінен алынған төбелер деп аталатын 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-ден аз емес қабырғасы болады.
C
A
B
D
E
F
6.1 сурет
в) байланысты графта кез-келген максималды ұзындықты қарапайым екі тізбесінің тым болмаса бір ортақ төбесі болады. г) N төбесі бар және К байламдық компоненттері бар графтың қабырғалар саны 12(N-K)(N-K+1)-ден артпайды.
Байланысты графтың екі төбесінің ара қашықтағы деп осы төбелерді қосатын ең қысқа тізбенің (жолдың, маршруттың) ұзындығын айтамыз, яғни қысқа жолдағы қабырғалар саны. Мысалы, 6.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.
A2
u2
A1
A3
A4
A5
u1
u3
u4
u5
6.2 сурет

Графтың төбесінің дәрежесі деп осы төбеге тиісті болатын (түйіскен) қабырғалар санын айтамыз. Графтың төбелерінің дәрежелерінің өсу ретімен немесе кемі ретімен берілген тізімі вектор-дәрежесі деп аталады. Мысалы, G1 графында ол (3,3,4,4,4,4) - ге тең, 6.2 - суретте көрсетілген G2 графында ол (1,2,2,2,3). Дәлелдеуі өте қарапайым.
Графтың барлық төбелерінің дәрежелерінің қосындысы қабырғаларының екі еселенген санына тең.
G2 графын 6.2 суреттен басқа етіп, мысалы 6.3 суреттегідей салуға болады. Бұған көз жеткізу үшін G2 графтың А1 төбесіне- 6.3 суреттегі графтың А төбесін сәйкес қоюға болады, А2 төбесіне - D төбесін А3 төбесіне - Е төбесін, А4 төбесіне - В төбесін, А5 төбесіне - С төбесін сәйкес қоюға болады. Нәтижесінде, екі графтың төбелерінде өзара бірмәнді сәйкестік орнады. .

A
B
E
C
D
6.3сурет

Мұндай жағдайда бұл суреттердегі графтарды өзара изоморфты деп те айтады. Изоморфты графтардың вектор-дәрежесі бірдей. Кері тұжырым дұрыс емес. Мысалы, 6.4 суреттегі G4 пен G5 изоморфты емес, себебі G4 графында ұзындығы 3-ке тең цикл жоқ, ал G5 графында ол бар, А1А2А3-ке тең. Бірақ, бұл графтарда вектор - дәрежелері тең: (2,2,2,2,3,3).
A5
A1
A2
A3
A6
A4
G5
A5
A1
A2
A3
A6
A4
G4
6.4сурет
A5
A1
A2
A3
A6
A4
G5
A5
A1
A2
A3
A6
A4
G4
6.4сурет
Граф жазық деп аталады, егер жазықтықта оның қабырғалары тек төбелерде ғана қиылысса. Граф планарлы деп аталады, егер оның жазық кескіні болса. 6.3 және 6.4 суреттерде - жазық графтар, 6.2 суретте планарлы граф, себебі оның изоморфты жазық кескіні бар, ол G3 графы. Ал 6.1 суреттегі граф планарлы да болмайды. Оны келесі теоремадан көруге болады.
6.3 теорема. Граф планарлы болмайды,сонда және тек қана сонда егер келесі шарттардың бірі орындалса:
а) (Понтрягин-Куратовский) Графтың толық бес төбелі К5 немесе К3,3 графына (төменде айтылады) гомеоморфты болатын ішкі графы болады;
б) (Харари-Татта) Графты қабырғасын созу арқылы немесе кейбір элементтерін жою арқылы К5 немесе К3,3 графтарына гомеоморфты графқа айналдыруға болады.
К5
К3,3
6.5 сурет

Графтар гомеоморфты болады, егер біреуі екіншісінен қабырғаларын желімдеу немесе бөлу операцияларының көмегімен алынатын болса (6.6 сурет).
АВ қабырғасын бөлу
6.6 сурет
АС мен СВ қабырғаларын желімдеу
А
В
С
А
В

АВ қабырғасын созу, АВ қабырғасы жойылады, А және В төбелері бір төбеге айналады және осы жаңа төбе А және В төбелерімен сыбайлас болған барлық төбелермен жалғасады (6.7 суретті қараңыз).
В
А4
А3
А1
А2
В3
В1
В2
А
А4
А3
А1
А2
В3
В1
В2
А(В)
6.7 сурет

Графтардың матрицалық берілуі

Графтарды сурет түрінде беру үнемі ыңғайлы бола бермейді. Мысалы, ЭЕМ-де оларға операциялар қолдануда. Бұл үшін графтың матрицалық берілу тәсілдері қолайлы. Одай әдістердің бірі сыбайлас матрица әдісі. Егер G графында n төбе болса, онда оның сыбайлас матрицасының M(G) = n жолы және бағанасы болады. Ол үшін i,j орнына яғни, i-жол мен j-бағанаға 1-ді қоямыз, егер G-да i-жолдан j - бағанаға қабырға болса; қарсы жағдайда 0 қоямыз:
μi,j =
1, егер i-жолдан j - ге қабырға болса

0, егер i-жолдан j - ге қабырға болмаса
6.2 және 6.3 суреттердегі графтар үшін матрицалар келесідей болады:
M(G2) = ; M(G3) = ,
Мұнда G3 графында төбелер алфавиттік түрде реттелген деп есептедік, янғи А-бірінші, В-екінші, С-үшінші, т.с.с. G2 пен G3 графтары изоморфты ( белгіленеді) болса да, олардың сыбайлас матрицалары әртүрлі. Бірақ осы графтардың изоморфтығын дәлелдеуде біз G2 графының бірінші төбесіне G3 графының бірінші төбесін сәйкестікке қойдық, екіншіге - төртіншісін, үшінші-бесіншісін, төртіншіге - екіншісін, ал бесіншіге - үшіншісін. M(G2) матрицасында алдымен, жолдарын ауыстырамыз, біріншісін орнында қалдырамыз, екіншісін төртіншісінің орнына, үшіншісін - бесіншісінің, төртіншісін - екіншісінің, ал бесіншісін - үшіншісінің орнына қоямыз. Содан кейін дәл осы түрлендіруді бағандарға жасаймыз. Нәтижесінде, M(G3) матрицасын аламыз:
M(G2)= = M(G3).
Сыбайлас матрицаны қарапайым граф түрінде де беріге болады, бұнда негізгі диагоналі нөлдер болатын, симметриялы матрица және фультиграф түрінде жазуға болады. Соңғы жағдайда (i,j)-дің орнына басы i-төбеде болатын, соңы j-төбеде болатын қабырғалар санын жазамыз. Мұндағы матрица симметриялы емес болуы мүмкін. Кері есеп - сыбайлас матрицасы бойынша графты салу қиын емес. Жазықтықта n нүкте (жолдары мен бағандарының санына байланысты) белгілейміз, нүктелерді шеңбер бойымен орналастырған ыңғайлы. Егер берілген матрица симметриялы болмаса, онда сәйкес нүктелер бағыттармен жалғанады, қарсы жағдайда - граф бағдарсыз, сондықтан нүктелерді тек сызықтармен қоса саламыз. Егер граф жазық болып кескінделетінін көруге болса, онда олай да салуға болады, бұл сурет графтың планарлығын негіздеуге жеткілікті болады. ... жалғасы

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