Графтар 2. Графтар теориясының негізгі анықтамалары

 

ГРАФТАР  

 

12.1 Графтар теориясының негізгі анықтамалары  

 

Графтар  теориясын  білуді  қажет  ететін  белгілі  бір  есептердің  класы  болады, 

мысалы,  көлік  есептері,  желілерде  ағындарды  тиімдеу  есептері,  иерархиялық 

бұтақтар тәрізді құрылымдарда іздестестіру есептері, т.б. 

Бұтақтар  мен  графтар  бір  біріне  ұқсас  болып  келеді.  Мысалы,  бағдарлама 

саласындағы  белгілі  теорияшыл  Д.Кнут  графтарды  бұтақтар  бөлімінде  түсіндіріп 

кеткен. Паскаль тілін жасаушы Н.Вирт “Алгоритмы и структуры данных” кітабында 

графты мүлдем қарастырмайды, бірақ күрделілігі әртүрлі бұтақтарды қарастырады. 

Ресей  авторлары  күрделі  құрылымдарды  сипаттағанда  біріншіден  графтарды 

қарастырады (12.1-суретті қара). 

Сонымен қатар граф қос (V,E) жиынтық ретінде анықталады.  

мұнда  

V – төбелердің шекті жиыны; 

E – төбелерді байланыстыратын қабырғалардың шекті жиыны. 

S=  жазбасы  мынаны  сипаттайды:  S  қабырғасы  U  және  W  төбелерін 

байланыстырады.  

Бір қабырғамен байланысатын төбелер сыбайлас төбелер деп аталады. 

S  қабырғасы  және  U  төбесі  (және  S  қабырғасы  мен  W  төбесі)  түйісті 

(инцидентті) деп аталады. 

Бір төбеге түйісті (инцидентті) қабырғалар сыбайлас қабырғалар деп аталады. 

Төбенің дәрежесі оған түйісті (инцидентті) қабырғалардың санына тең. 

U және K төбелерін байланыстыратын жол – W

0

,W

1

, . . . , W

n 

(n>0), төбелерінің 

тізбегі,  мұнда  W

0

=U,  W

n

=K,  кез  келген  i  (0



i



n-1)  үшін  W

i

  және  W

i+1

  төбелері 

қабырғалармен байланысқан. 

W

0

, . . . ,W

n 

жолының ұзындығы оның қабырғаларының санына – n тең. 

Егер жолдың барлық төбелері әртүрлі болса, онда ондай жол қарапайым жол 

деп аталады. 

Егер W

0

=W

n 

болса, онда ондай жол тұйық жол деп аталады. 

Барлық қабырғалары әр түрлі тұйық жолды цикл деп атайды. 

Барлық төбелері әр түрлі тұйық жолды контур деп атайды.  

Екі  төбе  арасындағы  қашықтық  –  осы  төбелерді  байланыстыратын  ең  қысқа 

жолдың ұзындығы.  

Егер кез келген төбелер жұбын байланыстыратын жол бар болса, онда ондай 

граф байланысты граф деп аталады. 

Егер  кез  келген  екі  төбелер  қабырғалар  шекті  байланыстырылса,  онда  ондай 

граф толық граф деп аталады. 

Бағытталған  граф  немесе  орграфтың  қарапайым  графтан  айырмашылығы  - 

төбелер,  қабырғалармен  емес,  доғалармен  (доға  дегеніміз  -  бағыты  берілген 

қабырға) байланысуы. 

Орграф  бойымен  орын  ауыстыруды  тек  доға  бағытымен  ғана  орындауға 

болады. 

Графтың  кез  келген  төбесінен  белгілі  төбеге  дейін  жол  бар  болса,  онда  осы 

төбе орграфтың құйылысы деп аталады. 

Бір  төбеден  графтың  кез  келген  төбесіне  дейін  жол  бар  болса,  онда  ондай 

төбені орграфтың көзі деп атайды.  

U төбесінің графтың қалған төбелеріне дейінгі ең үлкен қашықтық U төбесінің 

эксцентриситеті деп аталады. 

Төбелердің  арасындағы  ең  үлкен  эксцентриситетті  графтың  диаметрі  деп 

атайды.  Төбелердің  арасындағы  ең  кіші  эксцентриситетті  графтың  радиусы  деп 

атайды. 

Эксцентриситеті  графтың  радиусына  тең  төбені  графтың  медианасы  немесе 

оның центрлік төбесі деп атайды. 

 

 

 

12.1-суреті – Графтың көрінісі 

 

Егер барлық төбелер (бірақ барлық қабырғалардың кіруі міндетті емес) циклге 

кіретін болса және осы цикл графта бар болатын болса, онда осы граф гамильтонды 

граф деп аталады. 

Егер графтың барлық қабырғалары циклге бір рет қана кіретін болса және осы 

цикл графта бар болатын болса, онда осы граф Эйлер графы деп аталады. 

Графтың  барлық  қабырғаларының  бойымен  тек  бір  рет  қана  жүріп  өтетін 

жолды Эйлер жолы деп атайды. 

Графты сурет түріндегі қабылданған форма бойынша көрсетуге болады, онда 

төбелерге шеңберлер, ал қабырғаларға осы шеңберлерді байланыстыратын сызықтар 

сәйкес келеді.  

12.1-суретінде Гамильт циклі жалпақ сызықпен белгіленген. 

Бұтақтар тәрізді құрылымның көптеген анықтамалары бар. 

Байланысқан граф арқылы бұтақтардың екі анықтамасын келтірейік.  

Бұтақтар  дегеніміз  –  доғаларының  саны  төбелерінің  санынан  бірге  кем 

болатын байланыстырылған граф. 

Бұтақтар дегеніміз – циклі жоқ байланыстырылған граф. 

«Графтық»  есептерді  шығару  барысында  алгоритмнің  күрделі  болуы  оның 

«машиналық» көрсетіміне байланысты, яғни «графтық» есептің типіне байланысты 

ЭЕМ жадысында графты көрсетудің белгілі бір формасы қолданылады.