ПОӘК 042-14. 01. 20. 205/03-2013 02. 09. 20013 №1 басылым



бет14/209
Дата15.09.2017
өлшемі14,91 Mb.
#34004
1   ...   10   11   12   13   14   15   16   17   ...   209

Дәріс 13– 15
Дәріс сабақтың мазмұны:
ГРАФТАР ТЕОРИЯСЫНЫҢ ЭЛЕМЕНТТЕРІ

Графтардың түрлері мен берілу тәсілдері. Көптеген қолданбалы есептерде әртүрлі объектілер арасындағы байланыс жүйесі қарастырылады. Міне осындай шектеулі математиканың мәселелерін шешуге геометриялық тұрғыдан келу графтар теориясы деп аталады. Ең алғаш рет «граф» терминін венгер математигі Д.Кениг енгізген. Ол нүктелер жиынынан және осы нүктелерді байланыстыратын түзулер кесінділері мен қисықтардан құрылған схемаларды граф деп атады.

Жазықтықта әртүрлі бес 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.

Математик, механик Л.Эйлер байланысқан бағытталмаған мультиграфта оның барлық қабырғаларынан тұратын цикл болатынын тұжырымдап берді. Мультиграфтың барлық қабырғаларынан тұратын цикл Эйлерлік д.а.

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

Эйлерлік мультиграфта эйлер циклін табудың алгоритмі:


  1. кез келген а төбені аламыз.

  2. а төбесіне инцидентті кез келген u қабырғаны алып, оған 1 номер береміз (бұл қабырғаны жүрілген д.а.)

  3. әрбір жүрілген қабырғаны сызып, 1 ден артық номер беріп отырамыз.

  4. х төбесінде тұрып а төбесімен қосатын қабырғаны таңдамаймыз, егер басқа мүмкіндік болатын болса.

  5. х төбесінде тұрып, сызылған қабырғаны таңдамау керек.

  6. графтың барлық қабырғасы номерленгеннен кейін эйлер циклі пайда болады. Реттелген номер графтың айналу ретін көрсетеді.

Байланысқан және байланыссыз графтар. Графтағы ешбір қабырға арқылы 1-ден артық рет өтпейтін сызық шынжыр деп аталады. Егер қозғалысты А нүктесінен бастап, барлық төбелерден әр қабырға бойымен тек бір ғана рет жүре отырып, сол А төбесіне қайта оралу мүмкін болса, мұндай жолды цикл деп атайды. Егер циклдың барлық төбелері әртүрлі болса, мұндай цикл қарапайым цикл, ал қарсы жағдайда – қарапайым емес цикл деп аталады. Кей жағдайда цикл графтың барлық қабырғаларын дәл бір реттен қамтиды. Мұндай циклдарды Эйлер сызықтары деп атайды.

Егер графтың кез келген екі төбелері қандай да бір шынжырмен байланысып тұрса, ондай графты байланысты граф дейді, яғни байланысты граф дегеніміз бірде бір оқшауланған нүктесі болмайтын граф.

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

Байланысты графтың қасиеттері:

1. кез келген байланысты графтың дәрежелері тең болатын ең болмағанда екі төбесі бар болады.

2. барлық төбелерінің дәрежелері жұп болатын байланысты граф Эйлер сызығы болып табылады.

3. байланысты графта оның барлық қабырғаларын дәл бір реттен қамтитын l(A, B) шынжыры бар болуы үшін А мен В төбелерінен басқа тақ дәрежелі төбелердің болмауы қажетті және жеткілікті.

Барлық қабырғаларының бағыты көрсетілген граф бағдарланған граф деп аталады. Қабырғаларының бағыты көрсетілмеген графты бағдарланбаған граф дейді. Кей қабырғаларының бағыты бар, ал кей қабырғаларының бағыты көрсетілмеген графты аралас граф дейді.

Ұштарындағы нүктелері беттесетін қабырғаны тұзақ деп атайды. Графты кескіндеу барысында тұзақ сол төбеге қайтып келетін және басқа төбелерден өтпейтін тұйық доға түрінде болады.


ПРАКТИКАЛЫҚ САБАҚТАР

Практикалық сабақтардың құрылымы:

Практикалық сабақтар 1 (5)
Практикалық сабақтардың мазмұны:
1. Доказать, что {} .

2. Доказать, что {{0,1}, {0, 2}} {0,1,2}.



3. Доказать, что

4. Построить пример множеств А и В таких, что АхВВхА.



5. Пусть [0,1], [0,2] - отрезки на числовой прямой. Дать геометрическую интерпретацию множеств [0,1]х[0,2], [0,1]2, [0,2]3.

6. Изобразить отношения Р={(а, 1), (а, 2), (b, 2), (b,3), (с, 1), (с. 4)} и Q = {(1,), (2,), (3,а)}. НайтиQ, рQ и Р о Q.

7. Для отношений Р={(х,у) € R2|x =у2} и Q={(х,у)€ R2|ху>0} найти Р о Q, Q о Р, Р о Р и Р-1.

8. Пусть А и В - конечные множества мощности m и n соответственно. Найти:

а) число бинарных отношений между элементами множеств А и В, б) число функций из А в В; в) число инъекций из А в В; г) число биекций из А в В.

9. Доказать следующие эквивалентности:

а) А х В ~ В х А; б) (А х В)с ~ Ас х Вс.

10. Доказать, что:

а) если А - конечное множество, В - подмножество множества А, то множество В конечно;

б) если A1….. Аn - конечные множества, то множества А1U... U Аn и A1х ... хАn конечны.



Достарыңызбен бөлісу:
1   ...   10   11   12   13   14   15   16   17   ...   209




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет