А. Мырзахметов атында

Амантай Ж. - «Ақпараттық жүйелер және информатика» кафедрасының оқытушысы

Абай Мырзахметов атындағы Көкшетау университеті
Аңдатпа

Бұл мақалада графтар теориясы, оның түрлері және есептер қарастырылады.
Аннотация

В данной статье рассмотрена теория графов, ее виды и задачи.
Annotation

This article describes the theory of graphs, its types and tasks.
Гамильтондық графтар дискрет математиканың бірнеше маңызды есептерінде қолданылады.

Ілгектері және еселі қабырғалары болмайтын бағытталмаған байланысты графтар қарапайым графтар деп аталады. Одан әрі біз граф деп қарапайым графтарды атаймыз.

Графтағы жол деп кез келген екі көршілес қабырғаның ортақ төбесі болатын қабарғалардың тізбегі аталады: (a₁, a₂), (a₂, a₃),…, (a_k–1, a_k). Бұл жағдайда a₁ төбесі жолдың жолдың басы, ал a_k төбесі жолдың соңы деп аталады. Егер жолдың басы мен соңы тең болса, онда жол тұйық деп аталады.

Егер жолдың қабырғалары қайталанбаса, онда жол тізбекше деп аталады. Егер тізбекше тұйықталса, онда ол цикл деп аталады. Егер тізбекшеде төбелері қайталанбаса, онда ол қарапайым тізбекше деп аталады. Егер циклде төбелері қайталанбаса, онда ол қарапайым цикл деп аталады. Графтың барлық төбелерінен өтетін қарапайым цикл гамильтондық цикл деп аталады. Егер графта гамильтондық цикл табылса, онда ол гамильтондық граф деп аталады. Мысалы, әрбір толық граф – гамильтондық, себебі мұнда барлық қабырғалар жүргізілген, барлық төбелерден өтетін.

Берілген графтың гамильтондық болуының шарты әлі толық шарты табылмаған. Графтың гамильтондық болуының бірнеше жеткілікті шарттары табылған: Дирак (1952), Оре (1960), Поша (1962), Бонди (1969), Хватал (1972).

Бірақ бүгінгі күнге дейін графтың гамильтондық болуының тиімді қажетті және жеткілікті шарты табылмаған. Сондықтан графтың гамильтондық болуының тиімді алгоритімін табу дискреттік математиканың өзекті мәселесі болып табылады.

Осы жұмыстың мақсаты: Графтың гамильтондық болуының қажетті және жеткілікті шарттарын табу.

Осы жұмыстың міндеті:

Әдебиеттерді зерттеп, бүгінгі күнге дейін табылған керекті мәліметтерді табу.

Графтың гамильтондық болу белгісін сыбайлас матрицалар, атап айтқанда оның перманенттері арқылы тұжырымдау.

Барынша графтың гамильтондық болу шарттарын немесе алгоритмдерін табу [3].

Анықтама. Граф деп – бейнеленген заттардың екі – екіден жұпталып келген заттардың бір – бірімен қатынасының жүйесін айтады. Графтармен коммуникация жолдарын қолайлы бейнелейді, үздіксіз емес көп қадамды процестерде («бинарлық қатынастардың жүйелерін, химиялық формулалардың құрылымында, тағы басқа әр түрлі сұлбалардың диаграммаларында») қолданылады.
Бірде – бір қырымен инциндент болмаса, онда ондай қырды бөлектенген қыр деп атаймыз, ал төбесі бір қырымен инциндент болса, онда оны аяқталған қыр, не ілінген қыр деп атаймыз. Қырдың басы мен соңы біріккен болса, оны ілмек деп атаймыз.

Егер екі төбе бір қырға инциндент болса, ондай төбелерді көршілес, не сыбайлас төбелер деп атайды. Егер екі қыр бір төбеге инциндент болса, онда ондай қырды сыбайлас деп атаймыз. Қырға сәйкес қойылған екі төбені еселік, не параллель төбелер деп атаймыз [1, 2].

Әртүрлі есептер үшін бір тек сол затқа графтың әртүрлі салыстыруы қажет.

Мысалы: жолдар тармағының үзіндісі ретсіз қырмен көрсетіледі де, бір-бірімен қатынастарының аяқталуын бейнелейді (қоныстанған орындарымен, қала көшелерімен, көшенің түйіскен жерімен құралдарындағы бір жақты, не екі жақты қозғалыстар). Бірнеше доғаларымен бөлектеген әрбір бірнеше қозғалысты – қырға қосымша жазылған сандар, оның ұзындығын, енін, епкіштігін және сандар не басқа сипаттамасын көрсетеді. Қандай графтар ажыратылатын және ажыратылмайтын болып бөлінуін анықтау өте қажет болып табылады, оны тіпті графтардың изоморфизм ұғымымен байланыстырады.

Кез – келген екі төбесі қыры арқылы қосылған еселік қырлары бар графты

Сурет 1.