Граф теориясы (10 сынып)

ГРАФТАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ
Графтардың түрлері мен берілу тәсілдері. Көптеген қолданбалы есептерде әртүрлі объектілер арасындағы байланыс жүйесі қарастырылады. Міне осындай шектеулі математиканың мәселелерін шешуге геометриялық тұрғыдан келу графтар теориясы деп аталады. Ең алғаш рет «граф» терминін венгер математигі Д.Кениг енгізген. Ол нүктелер жиынынан және осы нүктелерді байланыстыратын түзулер кесінділері мен қисықтардан құрылған схемаларды граф деп атады.
Жазықтықта әртүрлі бес A, B, C, D, E нүктелерін белгілейік. Осы нүктелерді графтың төбелері, ал оларды қосатын сызықтарды (түзу немесе қисық) графтың қабырғалары деп атайды.
Бұл графты A, B, C, D, E нүктелерін қосатын сызықтар осы нүктелерден басқа ешбір нүктелерде қиылыспайтындай етіп те кескіндеуге болады. Қабырғалары тек төбелерінде ғана қиылысатын графты жазық граф деп атайды.
Төбенің дәрежесі.
G бағытталмаған графы берілген, а төбесінің дәрежесі немесе валенттілігі деп а төбесі қабырғаларының ұшы болатын қабырғалардың санын айтамыз (ілмек екі рет есептеледі). а төбесінің дәрежесін degGa немесе dega деп белгілейміз. Дәрежесі 0 тең төбе – оқшауланған (изолированный), 1 тең болса – соңғы немесе аспалы (висячей) д.а.
Қол алысу туралы лемма. Графтың барлық төбелерінің дәрежесінің қосындысы жұп сан болады және қабырғаларының екі еселенген санына тең.
G – бағытталған граф. а төбесінен шығатын жарты дәрежесі deg+a а төбесінен шығатын доғаның санына тең. а төбесіне кіретін жарты дәрежесі deg-a а төбесіне кіретін доғаның санына тең. Сонда dega= deg+a+ deg-a.
Математик, механик Л.Эйлер байланысқан бағытталмаған мультиграфта оның барлық қабырғаларынан тұратын цикл болатынын тұжырымдап берді. Мультиграфтың барлық қабырғаларынан тұратын цикл Эйлерлік д.а.
Теорема. Байланысқан бағытталмаған мультиграф Эйлерлік болады сол жағдайда, егер оның әр төбесінің дәрежесі – жұп сан болса.
Эйлерлік мультиграфта эйлер циклін табудың алгоритмі:
кез келген а төбені аламыз.
а төбесіне инцидентті кез келген u қабырғаны алып, оған 1 номер береміз (бұл қабырғаны жүрілген д.а.)
әрбір жүрілген қабырғаны сызып, 1 ден артық номер беріп отырамыз.
х төбесінде тұрып а төбесімен қосатын қабырғаны таңдамаймыз, егер басқа мүмкіндік болатын болса.
х төбесінде тұрып, сызылған қабырғаны таңдамау керек.
графтың барлық қабырғасы номерленгеннен кейін эйлер циклі пайда болады. Реттелген номер графтың айналу ретін көрсетеді.
Байланысқан және байланыссыз графтар. Графтағы ешбір қабырға арқылы 1-ден артық рет өтпейтін сызық шынжыр деп аталады. Егер қозғалысты А нүктесінен бастап, барлық төбелерден әр қабырға бойымен тек бір ғана рет жүре отырып, сол А төбесіне қайта оралу мүмкін болса, мұндай жолды цикл деп атайды. Егер циклдың барлық төбелері әртүрлі болса, мұндай цикл қарапайым цикл, ал қарсы жағдайда – қарапайым емес цикл деп аталады. Кей жағдайда цикл графтың барлық қабырғаларын дәл бір реттен қамтиды. Мұндай циклдарды Эйлер сызықтары деп атайды.
Егер графтың кез келген екі төбелері қандай да бір шынжырмен байланысып тұрса, ондай графты байланысты граф дейді, яғни байланысты граф дегеніміз бірде бір оқшауланған нүктесі болмайтын граф.
Егер графтың ең болмағанда екі төбесін қосатын жол болмаса, оны байланыссыз граф деп атайды, яғни оның қандай да бір төбесінен шығып, басқа төбелеріне қабырғаларының ешқайсысынан бір рет қана өте отырып бару мүмкін болмайды.
Байланысты графтың қасиеттері:
1. кез келген байланысты графтың дәрежелері тең болатын ең болмағанда екі төбесі бар болады.
2. барлық төбелерінің дәрежелері жұп болатын байланысты граф Эйлер сызығы болып табылады.
3. байланысты графта оның барлық қабырғаларын дәл бір реттен қамтитын l(A, B) шынжыры бар болуы үшін А мен В төбелерінен басқа тақ дәрежелі төбелердің болмауы қажетті және жеткілікті.
Барлық қабырғаларының бағыты көрсетілген граф бағдарланған граф деп аталады. Қабырғаларының бағыты көрсетілмеген графты бағдарланбаған граф дейді. Кей қабырғаларының бағыты бар, ал кей қабырғаларының бағыты көрсетілмеген графты аралас граф дейді.
Ұштарындағы нүктелері беттесетін қабырғаны тұзақ деп атайды. Графты кескіндеу барысында тұзақ сол төбеге қайтып келетін және басқа төбелерден өтпейтін тұйық доға түрінде болады.
Граф - Граф (грекше-жазамын) – төбелер деп аталатын шектеулі нүктелерддің жиынтығы;төберлердің кейбіреулері графтың қырлары деп аталатын сызықтарымен байланысқан болады. Төбелердің жиыны (v) және реттелмеген және реттелген төбелердің (қырлар мен доғалар) жиынтығы (e) граф болып табылады: Граф “G” (V,E) болып белгілінеді. Тек қырлары ғана қамтитын граф – бағдарланбаған, ал тек доғаларды қамтитыны бағдарланған граф деп аталады. Кез – келген екі төбені қосатын тізбегі болатын граф – байланысқан граф болып табылады.
Граф — нысандар мен олардың арасындағы байланыстар жиынтығын айтады. Нысандар графтың төбелері деп, ал байланыстар граф қабырғалары деп аталады. Графты қолданылатын саласына байланысты байланыстар саны, қабырғалар бағытымен және төбелеріндегі әртекті қасиеттерімен ажыратады. Көптеген есептерді, нысандарды графтармен сипаттауға болады.
Графнемесе бағытталмаған граф  — бұл  келесі шарттарды қанағаттандыратын ретті жұптар жиынтығы:
 — төбелер немесе түйіндер бос емес жиыны ; — қабырғалар деп аталатын төбелерден құралған жұптар (бағытталмаған графта — ретсіз).
Төбелері мен қабырғаларын кейде граф элементтері деп те атайды, граф төбелер санын  — граф дәрежесі, қабырғалар санын  — графөлшемі деп атайды.
 және  төбелері  қабырғасының шеткі төбелері (немесе шеттері) деп аталады. Бір қабырғаның екі шеткі төбелері көршілес деп атады.
Ортақ шеткі төбелері бар екі қабырға түйіндес деп аталды.Шеткі төбелер жиыны бірдей болатын екі қабырға еселі деп аталады.Шеткі төбелер беттесетін қабырғаны ілмек аталыды, яғни  болса.
 төбесінің дәрежесі  деп оған тірелетін қабырғалар санын айтады (ілмекті екі рет санайды).Төбе ешқандай қабырғаның шеті болмаса оңашаланған болады; ал егер тек қана бір қабырға шеті болса салбыраулы (немесе жапырақ) болады.
Графтар теориясы ( HYPERLINK "http://kk.wikipedia.org/wiki/%D0%90%D2%93%D1%8B%D0%BB%D1%88%D1%8B%D0%BD_%D1%82%D1%96%D0%BB%D1%96" \o "Ағылшын тілі" ағылш. graphtheory) — түйіндері нүктелер жиыны, ал түйіндердің жалғасуы (қабырға деп аталатын) парлы екі нүкте болып келетін тор түрінде бейнеленеді. Егер түйіндердің жалғасу реті айтарлықтай маңызды болса — бағытталған граф, әйтпесе бағытталмаған граф болады. Графтар HYPERLINK "http://kk.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0" \o "Информатика"информатикада кеңінен қолданылады, айталық,  HYPERLINK "http://kk.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC" \o "Алгоритм" алгоритмдер схемасы немесе HYPERLINK "http://kk.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0" \o "Программа"программалар бағытталған графтарға жатады.
Түрлері
Бағдарланбaғaн граф (Неориентированный граф) — төбелерді қосатын доғаларының бағыты болмайтын граф.
Бағдарланған граф (Ориентированный граф; directed graph) - әр түрлі төбелер жұбын жалғастыратын қабырғалармен бірге түйіндердің (немесе төбелердің) құр ақырғы жиыны. Егер е қабырғасы Vl және V2 төбелерін жалғастырса, онда Vl мен И,-ні инцидент деп атайды және бұл төбелер көршілес болып саналады, е — реттелмеген жұп (К, и V2). Әдетте, граф көрнекті  HYPERLINK "http://kk.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D0%B0" \o "Форма" формада ұсынылады, сонымен бірге төбелері нүктелермен немесе кейде ұқсастыру мақсатымен ентаңбаланған басқа мүсіндермен, ал қабырғалары сәйкес нүктелерді жалғастыратын сызықтармен кескінделеді. Егер әрбір қабырғаға бағыт көрсетілсе, онда мұндай граф бағдарланған граф деп аталады. Бұл жағдайда қабырға әр түрлі төбелердің реттелген жұбының жиынын үйымдастырады және оларды көбінесе доға деп атайды. Бағдарланған граф көрнекті түрде ұсынылған кезде әрбір доға жебелікпен жабдықталады.