Графтар мен ағаштар

3.                     байланысты графта біртіндеп барлық циклді қырларды алып тастаймыз. Сонда  графтың байланысты бөлігі сол төбелердің жиынынан тұратын элементарлық циклсіз ағашқа  графтың тұлғасын аламыз. Тұлға бір мағыналы емес таңдалады да, бірақ ациклді қырлары кезкелген тұлғаға кіреді.

 тұлғасына қарағанда граф бөлігінің  барлық қырларын / -ді  хорда дейміз. Әрбір хорда тұлғаның екі төбесін байланыстырады.

                            

2.7-сурет

Кесте2.1

цикл	Шығарылған қыр
[1,9,14] [6,7,10] [5,13,14] [4,12,13] [8,11,12] [2,9,14,4,3] [14,10,11,4] [16,17,18]	1 6 5 13 8 9 14 16

 

 

 

 

Қорытынды

         Графтың барлық төбелері арқылы өтетін

элементарлық жол гамильтондық жол деп аталады да, егер оның басы және

соңы бірігіп кетсе, онда оны гамильтондық цикл деп атайды.

Белгілі коммивояжер жөніндегі  есеп былай тұжырымдалады: Қосарланған

қашықтағы белгілі n қалалар бар. Коммивояжер барлық қалаларға келгендегі

жолдың ұзындығының қосындысы  өте аз (минималды) болатынды табу керек.

Бұл дегеніміз оң сандар жазылған қырлардың ұзындығы n k толық графтағы

гамильтон жолының ең аз ұзындығын табу (есептің варианты үшін – айналып

45

шығу арқылы қайтадан бастапқы жолға келу – минималды гамильтондық

циклді табу).

n G граф төбесінің n ! алмастыруға сәйкестенетін, ал қыры екі төбені

қосатын көрші элементтерінің өзгешелігі транспозициясында болатын (әрбір

төбе (n -1) басқа төбелермен қосатын) {1,2,…,n} құралған жиынын

қарастырамыз.

Сонда көрсетілген тізбек n G графындағы жолына сәйкес келеді 2.8 а -

суретте n =3 кескіні көрсетілген кезкелген графтың екі жұп бөліктерінің

қосындысыда жұп граф бөлігі болады.

Егер 1 S және 2 S 1 H және 2 H граф бөліктерінің кейбір төбенің дәрежелері

болса, ал 12 S 1 2 H ÇH қиылысуындағы оның дәрежесі болса, онда 1 2 H Å H граф

бөлігінің a төбесіндегі S(a )дәрежесі 1 2 1 12 2 12 1 2 12 H Å H = (S - S ) + (S - S ) = S + S - 2S .

231

321

312

132

213

123

1-сурет

1 S және 2 S жұп болғандықтан онда S(a ) -де жұп.

Сондықтан жұп граф бөліктері  кеңістіктегі барлық граф бөліктерінің

кеңістік бөліктерін құрайды, да ілінген элементарлық циклдердің жиыны

кеңістік бөлігімен бірігіп  кетеді.

Осы кеңістік бөліктерінің V - өлшемін анықтаймыз. P қырлардан және

b төбелерден тұратын G байланысты граф берілсін. D– оның кейбір

тұлғасы. (P - b +1)– хорда саны. (a ,b ) әрбір хорда [a ,b ] Í D бір элементарлық

тізбегімен бірге элементарлық цикл құрайды, бірақ осы циклдердің векторы

(әртүрлі хорда үшін) å байланыссыз жүйе құрайды, циклдердің әрбіреуі

жүйенің қалған циклдерінің  ешбіреуінде жатпайтын қырды  ұстайды.

Осыдан V ³ P - b +1.

Басқаша айтқанда, әрбір  жұп граф бөлігі, кез келген жай  цикл å жүйенің

циклі арқылы өрнектеледі.

Шынында, H жұп граф бөлігіне å жүйенің циклдерінің H -қа кіретін граф

хордасын қосамыз. Алынған  қосынды ешқандай хорданы ұстамайды (әрбір

46

хорда қосындыға екі рет  кіреді: H граф бөлігі және å жүйенің циклдерінің

біреуі ретінде) D ағашының кейбір граф бөлігі ретінде. Осыдан құр граф бөлігі,

сол себепті қарсы жағдайда жұп граф бөлігі шығар еді ( H және циклдерінің

қосындысы), D ағашында тұратын элементарлық циклдер.

Сондықтан V ³ P - b +1. K компоненттерімен байланысты базис

кеңістігіндегі жұп граф бөліктерінің байланыссыз графы  үшін оның

байланысты компоненттерінің бірігуімен алынады да, ал қырлары мен

төбелерінің сандары қосылады. Сондықтан, егер i -ші компоненттің қыры

i P

және i b төбесі болса, онда V = p - b + K ,

å=

=

K

i

i P P

1 ,

å=

=

K

i

i b b

1 , V саны графтың

цикломатиялық саны деп аталады. V > 0 болғандықтан, кез келген граф үшін

K ³ b - p .

Ағаштар байланысты графтар, оның цикломатиялық саны V = 0 .

Мысал 1. 5 K толық граф үшін (5 төбе,

10

2!3!

3!4 5

2!3!

2 5!

5 =

×

=

×

C =

қыр

цикломатиялық сан V =10 - 5 +1 = 6 .__

 

 

 

 

 

Әдебиеттер тізімі:

1. Судоплатов С.В., Овчинников  Е.В. Элементы дискретной математики.

Новосибирск.-НГТУ, 2002.

2. Романовский И.В. Дискретный  анализ. СП., 2003.

3. Иванов Б.Н. Дискретная  математика. Алгоритмы и программы.  Москва,

2003.

4. Новиков Ф.А., Дискретная  математика для программистов.  Питер, 2001.

5. Нефедова В.Н., Осипова  В.А. Курс дискретной математики. – М.:из-во

МАИ, 1992.

6. Белоусов А.И., Ткачев  С.Б. Дискретная математика. –  М.:МГТУ

им.Э.Баумана, 2001.

7. Яблонский С.В. Введение  в дискретную математику. – М.: «Высшая

школа», 2001

Қосымша әдебиеттер:

8. Грехэм Р., Кнут Д., Паташник  О., Конкретная математика. М. 1998.

9. Мальцев А.И., Алгоритмы  и рекурсивные функции

10. Гаврилов Г.П. Сборник  задач по дискретной математике. М. 1977.