Теориялық мәлімет

 

Графтар теориясы–жас ғылым (айталық, геометриямен салыстырғанда). 1736 жылы Санкт-Петербург ғылым академиясында Леонард Эйлердің еңбегі жарық көрді, онда кенигсберг көпірі туралы есеп қарастырылды ("Барлық қала көпірлерінен тек бір реттен өтіп, бастапқы нүктеге қайта оралу мүмкін бе?"). Бұл болашақ графтар теориясы бойынша бірінші жұмыс еді.

Граф – бұл <V, E> екілігі, мұнда V – бос емес төбелер жиыны, а Е – осы төбелерді қос-қостан байланыстыратын, қабырғалар жиыны. Қабырғасымен байланысқан екі төбе, теңқұқықты, жәнеде сондықтан осындай графтар бағдарланбаған деп аталады: қабырғалардың "басы" және "соңы" арасында ешқандай айырмашылық жоқ.

 

Кесте 3.1. Бағдарланбаған графтар мысалдары
Граф	Төбелер	Қабырғалар
Жан-ұя	Адамдар	Туыстық байланыс
Қала	Қиылыстар	Көшелер
Желі	Компьютерлер	Кабельдер
Домино	Тастар	Мүмкіндік
Үй	Пәтерлер	Көршілер
Лабиринт	Айырымдар және тұйықтар	Өткелдер
Метро	Станциялар	Ауысып отыру
Тор қағаз	Торлар	Ортақ шекара болуы

 

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

Мысалы, 3.1 суретіндегі үш граф бірдей, ал екі граф 3.2 суреттегі- әртүрлі.

 

3.1. сурет. Бір графты бейнелеудің үш тәсілі

 

Жоғарыда келтірілген анықтамалардан шығатыны, графтарда қандайда бір төбені өзін өзімен байланыстыратын, ілмек-қабырға болмайды (3.3 сурет).

Егер v төбесі е қабырғасының шеттерінің бірі болып табылса, е қабырғасы және v төбесі бір біріне инцидентті деп аталады.

 

 

3.2. сурет. Екі түрлі графтар мысалы

 

 

3.3.сурет. Псевдограф

 

Кезкелген қабырғаға теңдей екі төбе инцидентті, ал төбеге қабырғалардың кезкелген саны инцидентті болуы мүмкін. Бөлек төбе оған инцидентті ешқандай қабырғадан тұрмайды (оның дәрежесі 0 тең).

Екі төбе, егер олар бір қабырғаның әртүрлі шеті болып табылса шектес деп аталады (басқаша айтқанда, осы төбелер бір қабырғаға инцидентті). Осыған ұқсас, екі қабырға шектес деп аталады, егер олар бір төбеге инцидентті болса.

Графтағы жол – бұл төбелер тізбегі (қайталанбайтын), ондағы кезкелген екі көршілес төбе шектес. Мысалы, 3.1 суретте бейнеленген графта, а төбесінен с төбесіне дейін екі түрлі жол бар: adbc и abc.

Егер u басталып v аяқталатын жол болса, онда v төбесіне u төбесінен жетуге болады.

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

Байланыс құрауыштары - бұл максимальды байланысқан ішкі граф. Жалпы жағдайда граф байланыс құрауыштарының кезкелген санынан тұруы мүмкін. Кезкелген бөлек төбе байланыстың жеке құрауышы болып табылатынын ескертейік. 3.4 суретте төрт байланыс құрауыштарынан тұратын граф бейнеленген: [abhk], [gd], [c] және [f].

Жол ұзындығы – қабырғалар саны, олардан осы жол тұрады. Мысалы, adbc және abc алдыда айтылған жолдар ұзындығы (3.1 сурет) – сәйкес 3 және 2.

 

 

3.4. сурет. Байланыспаған граф

 

v төбесі u төбесіне қатысты k-шы деңгейге жатады деп айтады, егер ұзындығы дәл k қабырғадан тұратын u-дан v-ға дейін жол болса. Бір және сол төбе әртүрлі деңгейге жатуы мүмкін. Мысалы, 3.1 суретте бейнеленген графта, а төбесіне қатысты 4 деңгей бар:

· 0) a;

· 1) b, d;

· 2) b, d, c (adb, abd, abc жолдары);

· 3) c (adbc жолы).

u және v төбелері арасындағы қашықтық- бұл u-дан v-ға дейінгі ең қысқа жолдың ұзындығы. Осы анықтамадан, 3.1 суреттегі графтың a және c төбелері арасындағы қашықтық 2 тең екендігі көрінеді.

Цикл – бұл тұйық жол. Циклдағы, бірінші және соңғы төбелерден басқалары әртүрлі болуы тиіс. Мысалы, 3.1 суреттегі графтың abda жолы цикл болып табылады.

Эйлер графы - бұл граф, онда графтың барлық қабырғаларынан тұратын цикл бар (төбелер қайталануы мүмкін). Тек осындай графтар сабақ басында айтылған кенигсберг көпірлері туралы есепті дұрыс шешеді. Мысалы, 3.5 суреттегі граф Эйлерлік болып табылады: ондағы ізделіп отырған цикл dbacfbcd болады.

 

3.5. сурет. Эйлер графы

 

Гамильтон графы - бұл граф, онда графтың барлық төбелерінен тұратын цикл бар (қайталанбайтын (3.5 сурет; ізделіп отырған цикл: abdfca).