Графтар теориясының негіздері Бағытталған графтар
1. Негізгі түсініктер. Орграфтар және бинарлық қатынастар
2. Орграфтың матрицасы
1. Негізгі түсінік
Бағытталған графтармен біз бинарлық қатынастарды оқыған кезде кездескенбіз.
Анықтама.
Бағытталған граф (орграф) деп
реттелген жұбын айтады, мұндағы X
– кез келген жиын, ал
.
X жиынының
элементтері төбе деп, Г жиынының
элементі
орграфының доғасы деп аталады. Көбінесе
орграфтың төбелері жазықтықтың нүктесі,
ал әрбір
доғасы х
төбесінен y төбесіне
бағыт арқылы бейнеленеді.
(x
–доғаның басы, y
– соңы).
Орграфтың екі төбесі сыбайлас
деп аталады, егер олар доғамен біріксе.
Екі доға сыбайлас болады, егер олардың
ортақ төбесі бар болса. x
төбесі және g
доғасы инцидентті деп аталады, егер x
төбесі g
доғасының не басы немесе соңы болса.
доғасы тұзақ деп аталады, егер
болса.
Белгілеу енгізейік
;
;
;
.
төбесінің жету жиыны деп X төбелер жиынын айтады :
төбесінің контр жету жиыны деп X төбелер жиынын айтады :
Орграфтар және бинарлық қатынастар
Біз әрбір төбелер жұбы ең болмағанда екі доғамен бірігетін орграфтарды қарастырамыз; сонымен қатар егер доға екеу болса, онда олар қарама – қарсы бағытта жүреді. Бұл – бинарлық қатынастарды көрсететін – Бержа графтары. Бинарлық қатынастардың қасиетттері жазықтықтағы орграфтың бейнесімен қалай байланысатындығын анықтайық (1.2.4 қараңыз).
Рефлексивті
бинарлық қатынастар, әрбір төбесінде
тұзақ құратын,
орграфымен беріледі, себебі анықтама
бойынша
(3.1, а
сурет).
Антирефлексивті R қатынасына бірде бір тұзағы жоқ орграф сәйкес келеді (3.1, б сурет)
R қатынасының симметриялық қасиеті кез келген екі төбе қарама – қарсы бағытталған доғамен біріккенін көрсетеді (3.1, в сурет). Симметриялық емес қатынастарды көрсететін орграфтардың тұзақтары жоқ, және кез келген төбелер жұбы тек бір ғана доғамен біріге алады (3.1, г сурет). Антисимметриялы дегеніміз бұл орграфтың кез келген төбелер жұбы тек бір ғана доғамен бірігуі мүмкін дегенді білдіреді, алайда оның тұзағы болуы мүмкін (3.1, д сурет). Транзитивтіліктің анықтамасына сәйкес біріншінің соңы екіншісінің басымен сәйкес келетін кез келген доғалар жұбы үшін біріншімен ортақ басы, ал екіншімен ортақ соңы болатын үшінші бір доға бар болады. Бұл шарттарға сәйкес келетін орграфтар 3.1, б, г суреттерде бейнеленген.
2.Орграфтардың матрицасы
ЭЕМ-дарда орграфтармен
байланысты есептерді шығарған кезде
орграфтарды матрица түрінде елестеткен
ыңғайлы.
орграфы үшін матрицаның анықтамасын
берейік, мұндағы
,
.
орграфының сыбайластық
матрицасы деп n
жолдан және n
бағаннан тұратын А
матрицасын айтады, оның i-
ші жолы мен j-
ші бағанының қиылысында тұрған элемент
мынаған тең
Сыбайластық матрицасы орграфтың доғаларының нумерациясы жайлы ақпаратты сақтамайды.
орграфының инциденттілік матрицасы деп n жолдан және m бағаннан тұратын В матрицасын айтады, ал оның i- ші жолы мен j- ші бағанының қиылысында тұрған элемент мынаған тең
Ұсынылған әдебиеттер:
1. Нұрсұлтанов Қ.Н., Дискретті математика және математикалық логика. – Семей 2002.
2. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики. –М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.
3. Смыслова З.А.. Дискретная математика (Учебное пособие), Томск, 2000.
4. Қ.Жетпісов., Математикалық логика және дискретті математика. Алматы, 2011.
5. Шапорев С.Д. Математическая логика. Курс лекций и практических заниятий.- СПБ.: БХВ-Петербург 2005. - 416стр.
6. Тишин В.В. Дискретная математика в задачах и примерах. БХВ-Петербург 2008.
Дәріс 12
Дәріс сабақтың құрылымы:
Бағытталмаған графтар
1. Негізгі терминдер.
2. Графтың матрицасы