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

Жазықтықта әртүрлі бес A, B, C, D, E нүктелерін белгілейік. Осы нүктелерді графтың төбелері, ал оларды қосатын сызықтарды (түзу немесе қисық) графтың қабырғалары деп атайды.

Бұл графты A, B, C, D, E нүктелерін қосатын сызықтар осы нүктелерден басқа ешбір нүктелерде қиылыспайтындай етіп те кескіндеуге болады. Қабырғалары тек төбелерінде ғана қиылысатын графты жазық граф деп атайды.

Төбенің дәрежесі.

G бағытталмаған графы берілген, а төбесінің дәрежесі немесе валенттілігі деп а төбесі қабырғаларының ұшы болатын қабырғалардың санын айтамыз (ілмек екі рет есептеледі). а төбесінің дәрежесін deg_Ga немесе dega деп белгілейміз. Дәрежесі 0 тең төбе – оқшауланған (изолированный), 1 тең болса – соңғы немесе аспалы (висячей) д.а.

Қол алысу туралы лемма. Графтың барлық төбелерінің дәрежесінің қосындысы жұп сан болады және қабырғаларының екі еселенген санына тең.

G – бағытталған граф. а төбесінен шығатын жарты дәрежесі deg⁺a а төбесінен шығатын доғаның санына тең. а төбесіне кіретін жарты дәрежесі deg^-a а төбесіне кіретін доғаның санына тең. Сонда dega= deg⁺a+ deg^-a.

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

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

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

1. 
   кез келген а төбені аламыз.
   
2. 
   а төбесіне инцидентті кез келген u қабырғаны алып, оған 1 номер береміз (бұл қабырғаны жүрілген д.а.)
   
3. 
   әрбір жүрілген қабырғаны сызып, 1 ден артық номер беріп отырамыз.
   
4. 
   х төбесінде тұрып а төбесімен қосатын қабырғаны таңдамаймыз, егер басқа мүмкіндік болатын болса.
   
5. 
   х төбесінде тұрып, сызылған қабырғаны таңдамау керек.
   
6. 
   графтың барлық қабырғасы номерленгеннен кейін эйлер циклі пайда болады. Реттелген номер графтың айналу ретін көрсетеді.
   

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

б) если A₁….. А_n - конечные множества, то множества А₁U... U А_n и A₁х ... хА_n конечны.