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

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

Жоспар

1. Кіріспе.
2. Негізгі бөлім:

а) Графтар,негізгі анықтамалары,түрлері;

б) Ағаштар, олардың қасиеттері;

     3. Қорытынды.

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

Көпбайланысты структураның қасиеттері:

1. Әрбір элементке (түйін,  төбе) саны еркін алынған сілтемелер  болуы мүмкін.

2. Әрбір элемент  кез  келген басқа элементпен кез  келген рет байланысады.

3. Әрбір байланыстырушы  жасаушының  (қабырға, доға)  бағыты  және салмағы болады. Келесі қасиеттері бар графтарды ағаштар дейді:

- Басқа ешбір элемент  сілтемейтін жалғыз элементі (түйін,  төбе) бар болса және ол түбір  деп аталады.

- Түбірден бастап элементтерде  бар белгілі бір көрсеткіштер  тізбегі бойымен структураның  басқа кез келген элементіне  қатынас жасауға болса.

- Түбірден басқа әрбір  элементке тек бір ғана сілтеме  жасалса, яғни әрбір элементтің  жалғыз адресі болса.

2. Граф деп – бейнеленген заттардың екі – екіден жұпталып

келген заттардың бір  – бірімен қатынасының жүйесін  айтады. Графтармен

коммуникация жолдарын қолайлы  бейнелейді, үздіксіз емес көп қадамды

процестерде («бинарлық қатынастардың  жүйелерін, химиялық формулалардың

құрылымында, тағы басқа  әр түрлі схемалардың диаграммаларында»)

қолданылады.

Граф G - жүйе G(V,E,G)×V = {V} жиынының элементі граф төбесінен тұрады

да, E = {e} қыры болып келген бейнелеуді көрсетеді. G : E ®V 2 егер әрбір

элементтің eÎE реттелген санға сәйкес реттелген екі элементті V V ÎV 1 2 , – ның

қырларының соңы сәйкес келеді.

V ÈE (V және E жиындарының бірігуі) – графтың көптеген

элементтерінен тұрады да, ал V ÇE = ø ( E мен V қиылысуы) құр жиынды

көрсетеді. G бейнесі әрбір соңғы қырының инцинденттігін анықтайды.

G = (V,E,G) үшін ең қысқа G = (V,E). Мұнда инцинденттілігі көрсетілмеген. Олар

контекстпен анықталады. Элементтерінің санына байланысты шекті және

шексіз болып бөлінеді. Біз тек ғана шекті графпен танысамыз.

Егер ( ) ( ) 1 2 r e = V ,V – екі – екіден таралып реттелген.

( ) ( ) 1 2 2 1 V ,V ¹ V ,V 1 2 V =V болғанда, онда e бағытталған доғал болады да,

шыққан 1 V - төбесі e доғасының басы, кіретін 2 V төбесі e доғасының соңы деп

аталады.

Егер ( ) ( ) 1 2 r e = V ,V жұбы ретсіз болса, онда e қыры бағытсыз деп аталады.

Кез – келген G графқа сәйкестендіріліп алынған бағытсыз граф

~G

,V және

E жиындарынан және инцинденттіктерінен тұрады, бірақ барлық парлары

ретсіз болады.

Төбелері бірде – бір қырымен инциндентті болмаса, онда ондай қырды

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

оны аяқталған қыр, не ілінген қыр деп атаймыз. Қырдың басы мен соңы

біріккен болса, оны ілмек деп атаймыз.

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

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

ондай қырды сыбайлас деп атаймыз. Қырға сәйкес қойылған екі төбені еселік,

не параллель төбелер  деп атаймыз.

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

қажет.

Мысалы: жолдар тармағының үзіндісі ретсіз қырмен көрсетіледі де, бір–

бірімен қатынастарының аяқталуын бейнелейді (қоныстанған орындарымен,

қала көшелерімен, көшенің  түйіскен жерімен құралдарындағы бір жақты, не екі

жақты қозғалыстар). Бірнеше доғаларымен бөлектеген әрбір бірнеше

қозғалысты – қырға қосымша жазылған сандар, оның ұзындығын, енін,

епкіштігін және сандар не басқа сипаттамасын көрсетеді.

Қандай графтар ажыратылатын және ажыратылмайтын болып бөлінуін

анықтау өте қажет болып  табылады, оны тіпті графтардың изоморфизм

ұғымымен байланыстырады. Өзара сақталып инцинденттік пайда  болған

бірімен – бірінің мәнді сәйкес бейнелеуін екі графтың 1 ( 1 1 1 ) G = V ,E ,G және

( ) 2 2 2 2 G = V ,E ,G изоморфизмі деп атаймыз да, оны былай белгілейміз

1 2 f :V ÛV және 1 2 g : E Û E кез – келген 1 1 e ÎE теңдікке

( ) ( ) 1 1 1 2 r e = V ,V => ( ) ( ) 2 2 1 2 r ge = fV , fV көптеген жағдайларда графтарды изоморфизмге

дейінгі дәлдікпен қарастыруға болады, яғни изоморфты графтастыруы

байқалмау, бірақ қайсібір графтардың төбелерінің немесе қырларының әртүрлі

ерекшеліктері болса, мысалы, номерленген немесе оларға сандық мәндер

сәйкестендірілген (қырының салмағы, қырының ұзындығы және т. б.) болса,

онда екі графты салыстыру  кезінде олардың ерекшеліктерін ескеру заңды.

Графтарды бірнеше жолдармен  беруге болады. Шекті графты оның

қырларының тізімінің  санын көрсетіп санау арқылы, оған қоса жеке тұрған

төбенің тізімін көрсету.

Инциндент графтардың матрицасы b төбелермен p қырлардан тұратын

тіктөртбұрыш матрица ij A = a

b жолдарымен p тік қатардан құралған

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

егер бағытсыз графтар  матрицаның ij a vi төбесімен j e қыры инциндентті

болған жағдайда ij a = î

í

ì aij

0,карсы жагдайда.

1, v тобесiмен е кыры инцидентті болганжагдайда, i j

ij a = ïî

ïí ì

-

1, , догасынын басы болса.

1, , догасынын соны болса,

i j

i j

егерV e

егерV e

Салбыраған элемент 2–ге  тең. Графтың көршілес (сыбайлас) төбелерінің

B төбелермен құралған матрица ij B = b

өлшемі болатын квадраттық матрица

жолдары мен тік қатарлары  төбелеріне сәйкестенеді де, теріс  емес элемент

ij b i v деп шығып, j v - ға кіретін қырлардың санына тең, бірақ бағытсыз графтар

үшін көршілес (сыбайлас) матрицаға симметриялық сақталады.

Егер инцинденттіктен  пайда болған матрица бір мағынада беретін болса,

онда матрицаның көршілес төбелері графтың кез – келген бағытсыз қырын

қарама – қарсы бағытталған  доғалармен сол төбелер сақталып өзгертілуі

көрсетіледі. Бірақ графтың  үлессіз қырлары үшін графтың  берілуі бір мағынада

осы матрицамен анықталады да көршілес матрицаның элементі мұндай

жағдайда 0 не 1 тең болады.

Көрнекілік үшін көрсетуге  болады: төбелерге кеңістікте (жазықтықта)

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

нүктелерден өтпейтін қисық  сызықтың кесінділері сәйкес нүктелерге

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

Графтың төбелері мен қырларының инцинденттілік қатынасына бөлінген

нүктелер мен сызықтары  бар геометрикалық инцинденттілік сәйкес келеді.

Одан басқа ішкі нүктеде қос – қостан қиылыспайды. Графтың мұндай көрінісі

орындау (жүзеге асыру) деп аталады.

Мынаны көрсетуге болады, кез – келген шекті (типті саналатын) саны бар

элементтерден тұратын графтік  үштік кеңістікте орындалуы, мүмкіндік

жағдайда, егер графтың еселік қабырғалары болмаса, онда қырға түзудің

кеңістіктері арқылы орындату қажетті.

Тегіс емес графты жазықтықта бейнелеу өте қолайлы, суретте төбелерді

оның қырларының қиылысуын  ажырата білу керек (мысалы төбелерді

дөңгелектермен бейнелейді) қырлардың бағытын стрелкамен көрсетеді.

Егер графпен көшенің  жолдарының тармақтарын көрсетсе, мұнда  көршілес

төбелерді байланыстыратын  жолдарын кесіндімен бейнелеу көрсетіледі.

Алаң және көшенің түйіскен жері – тарап кішкентай ел мекендеген

жерлерге графтың тегіс  болуы мүмкін, бірақта қала үшін жол өтпелерде,

көшелерде транспортардың шешімінде  әр деңгейде тегіс граф қолданылады.

1 – суретте граф 8 төбелері  және 11 қабырғалары бар граф бейнеленген.

Сурет арқылы кейбір ұғымдар кіргізілген 1 l , 3 l , 6 l , 7 l , 8 l , 10 l доғалар болады, 6 l -

бөлектенген (жекеленген) төбе; 4 l және 5 l параллель қырлар; 6 l , 7 l , 8 l , 9 l -

параллель қырлар; 11 l - ілмек (тұзақ); 2 l және 3 l , 2 l және 4 l қос – қостан

алынған көршілес төбелер; 3 l және 4 l екі сыбайлас қырлар.

v1

V2

V3

V4

V5

L1

L2

L3

L4 L5

L6

L7

L8

L9

V6

V7

V8

L10

L11

1-сурет

Инцидентілік матрица A және көршілес B төбелер құралған B матрица

мынау:

А =

÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷

ø

ö

ç ç ç ç ç ç ç ç ç ç ç

è

æ

-

-

- -

-

-

000000000 12

000000000 10

00000000000

00000 1 11100

00111111 100

01011000000

11 100000000

10000000000

В =

÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷ ÷

ø

ö

ç ç ç ç ç ç ç ç ç ç ç ç ç

è

æ

00000002

00000001

00000000

00000000

00020000

01203000

01020000

10100000

00000000

Еселік қырлары бар  графтарды толық граф деп атайды (кейде ілмексіз).

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

(бағытты, не бағытсыз) B төбесі бар толық графты b K деп белгілейміз. Граф

b K - тің

2

â C = 2

b(b -1)

қыры болады. Бағытты толық  граф кейде турнир деп

атайды, себебі ол дөңгелек жүйесі бойынша жарысқа түскенде оның нәтижесі

бір дөңгелекпен бейнеленеді.

а б в г

2-сурет

Толық граф бинарлық R қатынасын көрсетеді, егер R рефлексивті болса,

онда граф ілмекті, егер R симетриялық болса, онда граф бағытсыз, егер

R симетрияға қарсы қатынаста болса, онда граф бағытты.

2 а, б, в суреттерге

3 K

, 4 K , 5 K графтары бейнеленеді. 2 г суретте

5 K графты қырларының қиылысу санымен бейнеленуі көрсетілген, оны толық

жоюға болмайды.

а б в

3-сурет

Екі үлесті граф дегеніміз  төбелері екі қиылыспайтын сынықтарға бөлінген:

1 2 V =V ÈV , ал қырлары әртүрлі кластарда болатын төбелерді қосады. Мұнда

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

1 V сынығындағы әрбір төбелердің 2 V сыныбындағы әрбір төбелермен қыр

арқылы байланыста болса, онда мұндай графты толық екі үлестік граф деп

атаймыз. Оны m n K , белгілейміз, мұнда ; . 1 2 m =V n =V

m n K , графында m + n төбелері және m× n қырлары бар 3 а суреті – екі үлесті

граф, 3 б, 3 в – суреттерде 3,2 K және 3,3 K толық екі үлесті графтар көрсетілген.

n өлшемді бірлік кубы дегеніміз En граф төбелерінде барлық алынған

ұзындығы n нольдер мен бірлер, ал қырлары өзгешелігі бір компонент болатын

төбелерді қосады. 4- суретте n = 3 көрініс көрсетілген.

101

111

110

100

011

001

000

010

4 - сурет

Граф H = (V’, E’) G = (V, E) графының ішкі графы деп аталады да,

мынадай белгімен көрсетіледі H Í G, егер V’ Í V, E’ Í E және V’, E’ жиындары

үшін G графтың ицинденттігін  сақтайды.

Жұп графтар

Граф төбелерін ұстайтын байланыссыз граф бөлігін қарастырамыз.

Мұнда l ,l ,...,ln 1 2 арқылы номерленген p төбелерден тұратын G графы

болсын. Әрбір графтың H Í G бөлігіне p -өлшемді векторды

( , ,..., ) 1 2 p a a a ноль бірден тұратын î

í

ì

Ï

Í

H

H

i l

l

0,

1, 1

H граф бөлігінің мінездемелік

бөлігін аламыз. Бұл қатынас өзара бір мәнді сәйкестік. 1 H және 2 H граф

бөліктерінің модуль екі бойынша қосындысы 1 2 H Å H олардың

{0,1} коэффициенттер жиынының үстіне графтың барлық бөліктерінің

жиыны сызықтық кеңістікті құрайды: кезкелген граф бөлігін H -ты бірге

көбейткенде H -ты береді, ал H -ты нольге көбейткенде құр граф бөлігін

қырларды ұстамайтын бөлігін береді және G графының бөлектенген

төбелерінен тұрады. G графының бөліктерінің кеңістігі және оның граф

бөліктерінің мінездемелік векторлардың кеңістігі изоморфты және оның

өлшемі P болады. Граф бөліктерінің бір қырлық жиыны базис бола алады.

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

граф дейміз. Кез келген элементарлық тізбек (циклден басқа) жұп графты

тізбекке жатпайтын қырын ұзартсақ, онда тізбектің соңғы дәрежесі бір

және гафта оның дәрежесі екіден кем еместігі шығады. Егер граф шекті

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

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

шығарғаннан кейін жұп граф қалады, себебі барлық дәрежелер жұп санға

өзгереді (екі циклдің төбелері үшін және 0 циклге жатпайтын төбелер

үшін).

2.Эйлер графы

Графта ешбір қыр қалғанша бұл графтың кейбір элементарлық циклге

қайта бөлінуі мүмкін. Сонымен, әрбір шекті жұп циклды екені шығады.

Егер шекті жұп граф байланысты болса, онда (оның элементарлық

циклдерінің саны бойынша  және өзіне қиылысатын қыры бойынша)

графтың барлық қырларын ұстайтын жай цикл болады. Бұл циклді Эйлер

циклі деп атайды, ал оған иелі графты Эйлердің графы деп атайды.

Жай циклдің әрбір төбесінде жұп дәреже болады. Онда төмендегі

теорема дәлелденеді.

Теорема. Егер шекті байланысты граф Эйлердің графы болу үшін

оның жұп болуы қажетті және жеткілікті.

Эйлер графының байланысты барлық компоненті шектелген

байланыспайтын жұп графында болады. Егер төбеге кіретін доғалардың

саны шығатын доғалардың санына тең болса , онда бағытты графтың

төбесін тең дәрежелі деп  аталады.

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

дәрежелі граф деп атайды.

Эйлердің бағытсыз графының Эйлердің циклі бойынша айналып

шығуы графтың әрбір қырын айналып шығуына бағыттайды. Мұндай

бағытауда Эйлердің графы  тең дәрежелі болады. Енді тең дәрежелі граф

берілсін. Бұрынғы пікірді қайталасақ (циклдердің орнына контурлар

жөнінде айтсақ) онда әрбір тең дәрежелі графты қырлары бойынша

қосарланып қилыспайтын  элементарлық нұсқалардың қосындысы  ретінде

көрінуі мүмкін (онымен қоса шекті тең дәрежелі графта графтың барлық

қырларын ұстайтын жай  нұсқа болады). Басқа сөзбен айтқанда Эйлер

теоремасы мынаны танытады: граф төбелерінің барлығының жұп болуы

әрбір қыры бір рет жүретін графты айналып шыққанға қажетті және

жеткілікті шарт болып  табылады.

Эйлер теоремасынан қызықты  салдар шығады.

Кезкелген байланысты G графтағы әрбір қырды ( , ) 1 2 l = V V екі

еселейміз, сол төбелермен оның

l' ,l'' еселік қырлар етеміз. Әрбір төбенің

дәрежесі екіге өседі  де, жұп болады. Алынған жұп G графта Эйлерлік цикл

болады (егер

l' ,l'' қыралары қарсы бағытталса, онда әрбір төбе тең

дәрежелі Эйлерлік цикл болады). Егер оны 1 G графтың жолы ретінде

қарасақ,

l' ,l'' қырларын бір қыр етіп желімдесек, онда бірінші G графта

бұл траектория (жай емес) әрбір қыры арқылы екі рет жүретін цикл

болады (қарама-қарсы бағыт арқылы).Сонымен, әрбір байланысты графтың әрбір қыры екі рет ұстайтын

цикл болады, шытырмадағы  айналып шығуды бастапқы айналуға қайта

келумен түсіндіруге болады.

Жазық графтар

G графы деп  V(G) шектеулі төбелер жиыны мен R(G) шектеулі қабырғалар

жиыны аталады және әрбір қабырғасының ұштары әртүрлі екі төбе болады.

Егер граф төбелері жазықтық нүктелері болса, ал қабырғалары  осы жазықтықта

сынық сызықтар (кесінділерден  құралған) болса, онда граф жазық деп аталады.

Және жазық граф қабырғаларының ұштары өзара қиылыспайтын, басқа

төбелерді енгізбейтін ұштармен шектеледі. Жазық графта ілгектер (басы мен

ұшы бір төбе болатын қабырғалар) болмауы керек.

Жазық граф жазықтықты D(G) қамтылмайтын көпбұрышты облыстар

жиынына бөліктейді, облыстардың шектеулі болуы міндет емес.

Егер қолданылған түстерді 1, 2, ..., n деп нөмірлесек, картаға сәйкес жазық

графта осы сандармен  төбелер (астаналар) нөмірленеді.

Графтарды бояу есебі

G жазық графының  дұрыс n-түсті боялуы деп : V(G) {1,2,...,n}

бейнесі аталады және егер оның шекарасы v1 мен v2 болатындай r R(G)

қабырғасы бар болса, (v1) (v2 ) өрнегі орындалады. Сонымен, төрт бояу

проблемасын келесі тұжырым  түрінде қорытындылаймыз.

1-теорема. Кез келген жазық граф дұрыс 4 түсті бояуды ұйғарады.

Осы проблеманы шешу мәселесіне жүз жылдан астам уақыт жұмсалды.

Бірақ бір қарағанда әлсіз болып көрінетін дұрыс 5 түсті бояу туралы тұжырым

оңай дәлелденеді. Дәлелдеуге төбелер, қабырғалар және облыстар санын

байланыстыратын Эйлер формуласы  керек болады. M шектеулі жиыны

элементтерінің санын  білдірсін.

Эйлер теоремасы. Кез келген жазық граф үшін |V(G) |+| D(G)|= 2 + |R(G)| .

2- теорема. Кез  келген жазық граф 5 түсті бояуды ұйғарады.

Дәлелдеуі. Алдымен графты ықшамдаймыз. Егер небір төбелер жұбын

біріктіретін бірнеше қабырғалар бар болса (бұндай жағдай екі елдің бірнеше

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

Ресей мен Қытай сияқты), онда тек бір қабырға қалтырамыз: осындай

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

болуына кепілдік береді. Граф төбелері санымен индукция жүргіземіз. Үш

төбесі бар граф үшін теорема  тұжырымы орындалатыны айқын. Бұл тұжырым n

-1 төбелі барлық графтар  үшін әділ.

D1,D2,...,Dm –түгел m =D(G) граф облыстарының толық жиынтығы

болсын, ал N(Di ) – графтың i - інші облысының шекарасын құратын

қабырғалар саны. Сонымен  қатар кез келген i үшін N(D) >3. Кез келген қабырға

екі облыс шекарасына енеді, сондықтан N(D1) + N(D2 ) +...+ N(Dm) = 2R(G) .

N(Di ) 3 теңсіздігінен 2R(G) = N(D1) + N(D2 ) +...+ N(Dm) 3m = 3D(G)

аламыз, осыдан 2R(G) 3D(G) .

Эйлер формуласынан |V (G)|-2 + |D(G) |=|R(G)|, осыдан 3| R(G)| =3|V(G)|-

6+3 |D(G)| 3|V(G)|-6+2|R(G)| және

|R(G)| 3|V (G)|-6 (1)

шығарылады. Екі еселенген  қабырғалар санын басқа да граф

сипаттамасымен теңдестіруге болады. ... , n=V(G) граф төбелерінің

толық жиынтығы болсын, ал M( ) – j нөмірлі төбеге жинақталатын

қабырғалар саны. Бірақ  әр қабырға екі төбемен шектеледі, сондықтан 2R(G)

=M( ) +M( )+ ... +M( ).

Сонымен қатар, (1) теңсіздігінен  шығарылатындай, 2| R(G)| 6|V(G)|-12.

Ендеше,

M( 1) + M( ) +...+ M( ) 6|V (G)|-12 (2)

Соңғы теңсіздіктен бестен артық емес қабырға жинақталатын, ең болмаса,

бір төбе болатыны тұжырымдалады. Шынымен, қарсы тұжырымды

қабылдайық, яғни j M( ) 6 болсын. Онда M( )+M( )+...+M( ) 6n =

6|V(G)|, бұл (2)-ге қайшы болады.

Төбелерді төбесіне бестен артық емес қабырға жинақталатындай

етіп, қайта нөмірлейік.

Егер төбесінде төрттен  артық емес қабырға жинақталса, онда G \

графын қарастырамыз, ол G -дан төбесін және төбеге тірелетін

қабырғалардың бәрін аластаудан алынады. G\ графы индукция болжамымен

дұрыс 5 түсті бояуды ұйғарады. Ал қабырғалар төбені кіші графтың төрт

төбесімен біріктіретіндіктен, - ны дұрыс түстеп бояу үшін, ең болмаса, бір түс

қалады (бесеуден). Енді - ға бес қабырға жинақталсын. Бес төбеден құралған

H G графын қарастырайық, оған - дан шығатын және біріктіретін (G-да)

қабырғалар келеді. H графында міндетті түрде қабырғалармен біріктірілмейтін

екі төбе табылады. Расында  да керісінше болса H бесбұрышында

қабырға болады (оны есептеу қиын емес).

Бірақ (1)-ге сәйкес

|R(H)| 3|V(H)|-6= 3*5-6=9

сөйтіп, қайшылыққа тірелеміз.

мен - H -тың өзара байланыстырылмаған төбелері болсын. Олар G \

графындада біріктірілмеген. G \ графынан өзгертілумен алынған графын

қарастырайық, мен өзгерту  нәтижесінде теңестірілген.

Бұл жағдайда төбелерін теңестіргеннен ілмек пайда болмайтындықтан, G -

жазық граф. Бірақ үшін индукция болжамы әділ болады және оған дұрыс

5 түсті бояу бар. Бұл боялған графта мен төбелерін ажыратайық. Онда

дұрыс 5 түсті бояуды G \ графы да алады, және оған теңдігі

әділ болады. Басқаша айтқанда, мен бірдей түспен боялған, ендеше

төбесімен көршілес H графының бес төбесін түстеп бояуға төрттен артық емес

түс қолданылады. Қалған түсті  төбесін бояуға қолданамыз және G -дің дұрыс

5 түсті бояуын аламыз. Бір қарағанда төрт бояу проблемасы математиканың

басқа тарауларымен және іс жүзіндегі есептермен аз байланысатын тұйық есеп

сияқты болып көрінеді. Шындығында олай емес. Бұл проблеманың алгебра,

статикалық механика және жоспарлау есептерімен байланыстыратын 20-дан

астам тұжырымы бар. Бұл да математикаға тән қасиет: таза қызығушылықпен

зерделенген есеп шешімі нақты және табиғаты бойынша мүлде әртүрлі болатын

объектілер мен процестерді  сипаттауға пайдалы болып шығады.

Төрт бояу теоремасының дәлелдеуі туралы

К. Аппель мен У. Хакен  дәлелдеуін математикалық қауымның

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

Математикамен үстірт таныс оқырманды айтылған сөйлем, әрине,

таңдандырады, себебі математикадағы үшінші тұжырым аластатылған: немесе

әділ, немесе жоқ деген принцип қайда? – деген сұрақ еріксіз туындайды.

Мәселе оңай емес. Дәлелдеу авторлары былай деп жазады: «Оқырман 50 бет

мәтінді және диаграмманы, 2500 диаграммасы бар 85 бетті, тағы диаграммасы бар 400 бет микрофишаларды, негізгі мәтінде жазылған 24 леммадағы

мыңдаған жеке тұжырым  тексерістерін зерделеуі керек. Сонымен қатар

оқырман кейбір фактілерді тексеруге 1200 сағат компьютерлік уақыттың

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

айтпаса да түсінікті. Мақалалар  стилі мен ұзындығы бойынша адам

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

математиктер өте аз». Турасын айтқанда, дәлелдеудің компьютерлік бөлігін

қолмен тексеру мүмкін емес, ал дәлелдеудің дәстүрлі бөлігі өте ұзақ және

күрделілігі соншалық, оны толығымен ешкім тексермеген. Сонымен, тексеруге

болмайтын дәлелдеу – нонсенс. Осындай дәлелдеумен келісу, авторларға сене

салумен бірдей. Бірақ бұл  арада да бәрі күрделірек.

Ұзақ уақыт Евклид тұжырымдамалары мен дәлелдеулері математикалық

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

белгілі ережелермен орындалған (айқын емес тұжырымдарды айқын

тұжырымдардан алуға мүмкіндік беретін дедукция әдісі). Бұл қаталдық үлгісі

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

замандағы таза математикаға Евклид стандарттары жеткіліксіз. Евклид,

жазықтықты түзу неге екі бөлікке бөлетіні туралы ойланбаған сияқты (және ол

нені білдіреді), «арасында» деген түсінікті анықтамаған, бұл түсінік онсыз да

айқын деп есептеген және т.б. Осындай тұжырымдардың үлкен бөлігі соңғы

жүз жылдықта ғана дәлелденіп, геометрия аксиоматикасына енгізілген. Жаңа

аксиома жүйесінен формалды қорытындылар көне замандағы қорытындыларға

қарағанда өте ұзын орындалған.

Сонымен, төрт бояу теоремасын дәлелдеу мәселесі таза математика

тұрғысынан ашық болып қала береді.

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

Төмендегі төрт шартты қанағаттандыратын  графты ағаш дейміз:

1) Кезкелген қырды алып  тастағанда байланысты граф байланыспайтын

болады.

2) Қырлар саны төбелер  санынан біреуі аз болатын  байланысты граф.

3) Бір элементарлық тізбекте байланыста болатын граф.

4) Екі төбені байланыстыратын  қырларды қосқаннан кейін пайда  болған

циклсіз граф.

Ағаштан кезкелген 0 a төбені аламыз және оны тамыр , не ноль қабаттағы

төбе дейміз. Көрші төбелерді 1-ші қабаттағы төбе, көрші (i -1) қабаттағы төбені

i -ші қабаттағы төбе дейміз, тағы сол сияқты.

Ағаштағы әрбір төбе белгілі бір қабатқа жатады. Қабаттың номері

ағаштағы төбелердің ара  қашықтығы мен тамырына тура келеді. 3-ші қасиет

бойыншы әрбір байланыс i -ші қабаттағы қыр арқылы (i -1)-ші қабаттағы

номермен төбемен байланыста болады да, ешқандай i -ші қабаттағы төбемен

байланысты болмайды. Ағаштың  осындай көрінісі өте қолайлы. Мұндай

көрініс, аяқталған ағашта үнемі соңғы төбе болады. (мысалы ақырғы қабаттағы

төбе, бірақ басқалары болуы мүмкін).

1-сурет

Тамырды D ағашында бөлу оның төбелерінің жиынында жартылай

реттелгенін a < b анықтайдыда, егер a ¹ b және элементарлық тізбек тамырдан

b төбесінде a -ні ұстайды.Әрбір 0 a төбе 2 D ағаштың тамырын анықтайды, осы төбелерге іліну болып

табылады, мұнда a £ b осы әрбір a D ағаштың бөлігінде D = D 0 a .

Тамырды D ағашында бөлу оның төбелерінің жиынында жартылай

реттелгеніне a < b анықтайды да, егер a ¹ b және элементарлық тізбек

тамырдан b төбесінде a - ні ұстайды. Әрбір 0 a төбеде Da ағаштың тамырын

анықтайды, осы төбелерге  іліну болып табылады, мұнда a £ b . Осы әрбір

Da ағаштың бөлігінде D = D 0 a . Барлық 0 Da ағаштың бөліктері өзінің

бұтақтарынан a тамырына желімдеу арқылы пайда болады.

3. G байланысты графта біртіндеп барлық циклді қырларды алып

тастаймыз. Сонда G графтың байланысты бөлігі сол төбелердің жиынынан

тұратын элементарлық циклсіз ағашқа G графтың тұлғасын аламыз. Тұлға бір

мағыналы емес таңдалады  да, бірақ ациклді қырлары кезкелген  тұлғаға кіреді.

D тұлғасына қарағанда граф бөлігінің барлық қырларын G / D-ді хорда

дейміз. Әрбір хорда тұлғаның екі төбесін байланыстырады.1.Егер кезкелген   графтың қыры кем дегенде бір элементарлық циклге жататын болса, онда ол графтың қырын циклділік қыр деп атайды, ал қарсы жағдайда ациклділік деп атайды: Ациклділікке мысал ретінде ілінген қырды келтіруге болады. Төменде екі пікір орындалады:

1)Байланысты графтан циклдік  қырды шығарғанда, оның байланыстылығы  сақталады.

2)Ациклдік қырды шығарғанда  байланыспайтын граф болып өзгереді.

Біріншіден кезкелген тізбек үшін циклдік қырды циклдегі қалған қырлардың тізбегімен өзгертуге болады.

Екіншісі қарсы жолмен дәлелденеді, егер байланысты қалпында қалатын болса, онда алынған қырдың соңы элементарлық тізбекпен байланыста болар еді; алынған қырды орнына қойсақ, онда элементарлық цикл шығар еді, бұл мүмкін емес, себебі бұл қыр ациклді.

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

Төмендегі төрт шартты қанағаттандыратын  графты ағаш дейміз:

1) Кезкелген қырды алып  тастағанда байланысты граф байланыспайтын  болады.

2) Қырлар саны төбелер  санынан біреуі аз болатын  байланысты граф.

3) Бір элементарлық тізбекте  байланыста болатын граф.

4) Екі төбені байланыстыратын  қырларды қосқаннан кейін пайда  болған циклсіз граф.

2. Ағаштан кезкелген  төбені аламыз және оны тамыр , не ноль қабаттағы төбе дейміз. Көрші төбелерді 1-ші қабаттағы төбе, көрші  қабаттағы төбені -ші қабаттағы төбе дейміз, тағы сол сияқты.

Ағаштағы әрбір төбе белгілі бір  қабатқа жатады. Қабаттың номері ағаштағы төбелердің ара қашықтығы мен  тамырына тура келеді. 3-ші қасиет бойыншы  әрбір байланыс -ші қабаттағы қыр арқылы -ші қабаттағы номермен төбемен байланыста болады да, ешқандай -ші қабаттағы төбемен байланысты болмайды. Ағаштың осындай көрінісі өте қолайлы. Мұндай көрініс, аяқталған ағашта үнемі соңғы төбе болады. (мысалы ақырғы қабаттағы төбе, бірақ      2.5-сурет                            басқалары болуы мүмкін).  

Тамырды D ағашында бөлу оның төбелерінің  жиынында жартылай реттелгенін   анықтайдыда, егер  және элементарлық тізбек тамырдан  төбесінде -ні ұстайды.

Әрбір  төбе  ағаштың тамырын анықтайды, осы төбелерге іліну болып табылады, мұнда осы әрбір  ағаштың бөлігінде .2.6-сурет

Тамырды  ағашында бөлу оның төбелерінің жиынында жартылай реттелгеніне  анықтайды да, егер  және элементарлық тізбек тамырдан  төбесінде - ні ұстайды. Әрбір  төбеде ағаштың тамырын анықтайды, осы төбелерге іліну болып табылады, мұнда . Осы әрбір  ағаштың бөлігінде . Барлық ағаштың бөліктері өзінің бұтақтарынан  тамырына желімдеу арқылы пайда болады.