Дәріс 3. Графтар мен ағаштар. Графтар теориясымен байланыс.

Графтар теориясы – дискреттік математиканың өзіндік кең бөлімі. Теорияның пайда болуы  1736 жылды есептеуге болады, өйткені Л. Эйлер графтын арнайы маршруттының критериін табуға әкелген кенигсберг көпірі туралы есепті шешті. “Граф” терминін 1936 жылы венгер математигі Д. Кенигоммен ұсынылды.

Анықтама 1. Кез келген V жиыны мен V жиынының элементтерінің жұптарынан тұратын E бинарлық қатынасын граф деп айтамыз. Белгілеуі: G = (V, E).

Біз көп жағдайда ақырлы графтарды зерттейміз.

Анықтама 2. Егер E жиынының элементтерін реттелмеген жұптар ретінде қарастырсақ, ондай графты бағытталмаған (симметриялы) деп, ал парлар оның қырлары деп аталады. Кері жағдайда граф бағытталған, ал E жиынының элементтері графтың доғалары деп аталады.

 

Сурет 1. Бағытталған граф. Сурет 2. Бағытталмаған граф.

 

Анықтама 3. (a, a) жұп тұзақ делінеді, егер Е жиынтығында (a, b) жұбы бірнеше рет кездессе, оны еселі қыр (доға) деп айтады.

Анықтама 4. Бұдан былай тұзақсыз жəне еселі қырларсыз графты бағытталмаған (немесе жайғана граф), тұзақсыз графты мультиграф, ал тұзақтар кездесетін мультиграфты псевдограф дейміз.

Анықтама 5. Қыр арқылы жалғасқан граф төбелерін іргелес деп айтады.

Анықтама 6. Егер қандай да бір төбе қырға тиісті болса, онда оларды инцидентті деп айтады.

Анықтама 7. Төбенің дəрежесі (deg v) осы төбемен инцидентті қырлар санын айтады. Псевдографтардағы тұзақтар дəрежені есептегенге екі рет кіреді.

Тұжырым 1. Егер p — төбелер саны, ал q — қырлар саны болса, онда кез келген граф (псевдограф) үшін келесі теңдік орындалады .

Дəлелдеуі. Біз берілген төбенің дəрежесін санағанда, одан шыққан қырлардың санын есептейміз. Барлық төбелердің дəрежесін қосқанда, бұл қосындыда əрбір қыр екі рет есептелгенін көреміз (тұзақтар анықтамасы бойынша екі рет есептеледі).

Анықтама 8. Графтың төбелерінің жиыны V = { v 1, v 2, …, v p }. Онда v i жəне v j төбелері іргелес болғанда a ij = 1, кері жағдайда a ij = 0(мультиграф немесе псевдограф үшін 2,3,..) болатындай A = || a ij || матрицасы іргелестік матрицасы деп аталады. Бұл жағдайда a ii шамасының мəні v i төбесіндегі тұзақтар санына тең.

Сурет 3.І ргелестік матрицасы

Анықтама 9. G 1 = (V 1, E 1) жəне G 2 = (V 2, E 2) графтары(немесе псевдографтары) берілсін. Егер φ 1: V 1 → V 2 жəне φ 2: E 1 → E 2 өзара бірмəнді бейнелеулері мен G 1 графының кез келген u жəне v төбелері үшін _(N€_x‹9__ φ 2(u, v) = (φ 1(u), φ 1 (v)) теңдігі орындалса, бұл графтарды изоморфты деп айтамыз.

 

Сурет 4. Аралас матрица

 

Анықтама 10 (тұзақсыз жəне еселі қырларсыз графтардың изоморфтылығы).

G 1 = (V 1, E 1) жəне G 2 = (V 2, E 2) графтары үшін өзара бірмəнді φ 1: VG 1 = (V 1, E 1) жəне G 2 = (V 2, E 2) графтары үшін өзара бірмəнді φ 1: V 1 → V 2 бейнелеуі табылып, (u, v)∈ E 1 ⇔ (φ (u), φ (v)) ∈ E 2 шарты орындалса, онда бұл графтар изоморфты деп аталады.

Анықтама 11. V 1⊆ V жəне E 1⊆ E болса, онда G 1 = (V 1, E 1) графын G = (V, E) графының ішкі графы деп айтады.

Анықтама 12.G = (V,E) графының төбелері мен қырларынан тұратын тізбегін жол деп атаймыз. Осындағы n саны жолдың ұзындығы деп аталады.

Анықтама 13. Қырлары қайталанбайтын жолды тізбек деп атайды.

Анықтама 14. Төбелері қайталанбайтын жол қарапайым тізбек деп аталады.

Тұжырым 2. G =(V,E) графында P - v ₁ төбесінен v ₂(v ₁≠ v ₂) төбесіне апаратын жол болсын. Онда P жолынан v ₁ төбесінен v₂ (v₁ ≠ v₂) төбесіне апаратын, қарапайым тізбек болатын ішкі жолды алуға болады.

Дəлелдеуі. Берілген жол қарапайым тізбек болмасын дейік. Онда оның қандай да бір v төбесі бұл жолда қайталанады. Жолдың осы бөлігі P = v₀C₀vC₁vC₂v_n болсын. Егер одан P ₂= C ₀ v ішкі жолын алып тастаса, бір қайталану азаяды. Осы əрекетті бірнеше рет қайталау арқылы бастапқы жолдың төбелері бір реттен ғана кездесетін жолды аламыз. Ол қарапайым тізбек болады.

Анықтама 15. Жолда v ₀= v_n болса, ол тұйық жол деп аталады.

Анықтама 16. Қырлары қайталанбайтын тұйық жол цикл деп аталады.

Анықтама 17. Төбелері қайталанбайтын тұйық жол қарапайым цикл деп аталады.

Анықтама 18. Кез келген екі төбесінің арасында жол болатын графты байланған деп атайды. Əрбір төбе өзімен жол арқылы жалғанған деп есептеледі. Ол жолдың ұзындығы нөлге тең.

v_i төбесінен v_j төбесіне жол болса, оны v_i → v_j қатынасымен белгілейміз. Бұл қатынас

1) симметриялы, өйткені v_i → v_j ⇒ v_j → v_i,

2) транзитивті, өйткені (v_i → v_j) &(v_j → v_k) ⇒ (v_i → v_k),

3) рефлексивті, өйткені ∀ i (v_i → v_i).

Демек біз анықтаған → қатынасы берілген графтағы эквиваленттік қатынас болады. Сондықтан осықатынасқа сəйкес графтың бөліктеуі анықталады. Ол бөліктерді графтың байланған компоненттері деп айтамыз. Сонымен, кез келген G = (V, E) графы i=1

1) V_i = V: 2) i ≠ j ⇒ V i ∩ V j =∅. шарттары орындалатындай G = (V, E) графының байланған G _i = (V _i, E _i) ішкі графтарға, яғни байланған ішкі компоненттерге жіктеледі.

 

Сурет 5. Байланған тізім              Сурет 6. Қабырғалар тізімі

Тереңдетіп іздеу. Іздеу бір бекітілген  төбесінен басталады. v аралас u төбесі қарастырылады. Ол таңдап алынады. Процесс u төбесінен басталады. Егер келесі қадамда біз q төбесімен  және q мен аралас төбелер жоқ және алдын ала қарастырылмаған болса, онда q төбеден оның алдында болған төбеге қайта келеміз. Сол жағдайда  төбесі болса, онда қарастыру процесінде аяқталады. Бұл әдісті жүзеге асыру үшін мәліметтер құрылымы керек – стек.

Аралас матрицамен бейнеленген графтағы тереңдете іздеу мысалын қарастырамыз. Іздеуді бірінші төбеден бастаймыз. Болсын:

· Келесі төбелерді қараудың матрица сигналы  – FLAG

· Қарастырылған төбелердің нөмірлерін сақтау үшін стек - ST

· Стек төбесінің көрсеткіші - Y

· Келесі төбенің нөмірі – T

Сурет 7. Графтың мысалы және оның аралас матрицасы

Сурет 8. Тереңдете іздеу                     Сурет 9. Граф төбелерінің

трасировкасы берілген                              іздеуде тізбектей

 мысал үшін                                              қарастырылуы

 

Енінен іздеу. Әдістіңмағынасы ағымдағымен байланысты барлық төбелерді қарастыру. Келісі төбені таңдау  принципі келесідегідей – алдында қарастырылып өткен таңдап алынады.  Бұл принципті жүзеге асыру үшін мәліметтер құрылымы керек – кезек.

Аралас матрицасымен сипатталған графтағы тереңдете іздеу мысалын қарастырамыз. Іздеуді бірінші төбеден бастаймыз. Болсын:

· Келесі төбелерді қараудың матрица сигналы  – FLAG

· Төбелерді қарастыру кезегі - ORDER

· Кезек басының көрсеткіші – X

· Кезектің соңынын көрсеткіші – Y

 

Сурет 10. Графтың мысалы және оның аралас матрицасы

Сурет 11. Еніне іздеу                  Сурет 12. Граф төбелерінің

трасировкасы берілген                           енінен іздеуде

мысал үшін                                            тізбектей қарастырылуы

Эйлер циклдері. Эйлер циклі – әрбір қабырғадан тек бір рет өтетін цикл.

Теорема. Байланысқан бағыталмаған граф G эйлер циклін құрайды тек сонда, егер тақ дәрежелі төбелер саны нөлге тең болса. Төбенің дәрежесі – осы төбеге іргелес қабырғалар саны.

Эйлер циклін іздеу. Теорема шартын қанағаттандыратын граф берілген. Эйлер циклін табу керек. Графты тереңінен іздеу графы каөастырылады, бірақ қабырғалары жойылады. Қарау реті (төбе нөмірі) бірінші стекте сақталынады. Қабырғалар шықпайтын төбелер анықталғанда, олар нөмірі екінші стекке жазылады. Процесс бірінші стек бос болғанша дейін жалғаса береді. Екінші стекте граф төбелердің нөмірлері эйлер циклінің тәртібіне байланысты жазылады.

 

 

Сурет 13. Графтың мысалы          Сурет 14. Граф шыңдарының

және оның аралас матрицасы   тізбектей қарастырылуы

                                         еніне іздеуде

Гамильтондық циклдар. Онда графтың әрбір төбесін қамтитын  цикл бар болса, граф гамильтон дық деп аталады. Циклдің өзі де гамильтондық деп аталады. Барлық байланысқан графтар гамильтондық емес.

 

Сурет 15. Гамильтондық емес байланыс графының мысалы

Гамильтондық циклді іздеу. Байланысқан бағытталмаған граф берілген. Барлық гамильтондық циклдарды табу керек, егер олар болса. Шешу тәсілі – қайтаруыменен жинау.

Мысалы, шешімді іздеуді бірінші графтың төбесінен бастайық. Шешімнің бірінші k компонеттерінің шешімі табылды деп болжайық. Соңғы төбеден шығатын қабырғаларды қарастырамыз. Егер алдында қарастырылмаған төбелерде ондайлар болса, онда бұл төбені шешімге енгіземіз және қарастырылған деп белгілейміз. k+1 шешімнің компоненті алынды.

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

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

 

Сурет 16. Байланысқан граф              Сурет 17. Ағаш бөлігі,

         мысалы.                                          берілген механизімнің

                                                                жұмыс істеу тәсілі.