Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану

0. 
   0 және 1 функциялары сәйкесінше нөлдік және бірлік функция деп аталады.
   

0. 
   функциясын теңбе - тең фунция деп атайды.
   

0. 
   функциясын х – ті жоққа шығару немесе терістеу деп атайды, деп белгілейміз.
   

0. 
   функциясын нің эквиваленциясы деп атайды, оны деп белгілейміз.
   

0. 
   функциясы ің импликациясы деп атайды, оны деп белгілейміз
   

0. 
   функциясын нің Шеффер штрихы деп атайды, оны деп белгілейміз. Бұл функция антиконъюнкция деп те аталады.
   

1. 
   Бульдік функция деген қанадй функция?
   

2. 
   Құрама дегеніміз не?
   

3. 
   Логикалық функцияларға қолданылатын амалдарды атаңыз.
   

1. 
   Графтың негізгі анықтамалары
   
2. 
   Графтың инциденттік матрицасы
   
3. 
   Графтың түрлері
   

0. 
   Графтың негізгі анықтамалары
   

Граф ^G - жүйе ^{G V,E,V V} жиынының элементі граф төбесінен тұрады да, ^{E e} қыры болып келген бейнелеуді көрсетеді. ^{:E V2} егер әрбір

Егер ^{r e V}1^,V2–екі–екіден таралып реттелген.

Егер ^{r e V}1^,V2жұбы ретсіз болса,ондаeқыры бағытсыз деп аталады.

~

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

0. 
   жиындарынан және инцинденттіктерінен тұрады, бірақ барлық парлары ретсіз болады.
   

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

қажет.
Мысалы: жолдар тармағының үзіндісі ретсіз қырмен көрсетіледі де, бір– бірімен қатынастарының аяқталуын бейнелейді (қоныстанған орындарымен, қала көшелерімен, көшенің түйіскен жерімен құралдарындағы бір жақты, не екі жақты қозғалыстар). Бірнеше доғаларымен бөлектеген әрбір бірнеше қозғалысты – қырға қосымша жазылған сандар, оның ұзындығын, енін, епкіштігін және сандар не басқа сипаттамасын көрсетеді.

бірімен – бірінің мәнді	сәйкес бейнелеуін екі		графтың	G1V1,E1,1және
G2V2,E2,2изоморфизмі деп атаймыз да,оны былай белгілейміз
f:V1V2және	g:E1E2кез	–	келген	e1 E1 теңдікке

^r1 ^e1 ^V1^,V2 =>^r2 ^ge2 ^fV1^,fV2 көптеген жағдайларда графтарды изоморфизмгедейінгі дәлдікпен қарастыруға болады, яғни изоморфты графтастыруы байқалмау, бірақ қайсібір графтардың төбелерінің немесе қырларының әртүрлі ерекшеліктері болса, мысалы, номерленген немесе оларға сандық мәндер сәйкестендірілген (қырының салмағы, қырының ұзындығы және т. б.) болса, онда екі графты салыстыру кезінде олардың ерекшеліктерін ескеру заңды.
Графтарды бірнеше жолдармен беруге болады. Шекті графты оның қырларының тізімінің санын көрсетіп санау арқылы, оған қоса жеке тұрған төбенің тізімін көрсету.

2.Графтың инциденттік матрицасы

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

p қырлардан тұратын

тіктөртбұрыш

матрица

Aaijbжолдарыменpтік

қатардан құралған

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

егер бағытсыз графтар матрицаның aij vi төбесімен

ej қыры инциндентті

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

болған жағдайда

aij

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

=

1,егерV ,e

j

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

i

a

1,егерV ,e

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

ij =

i j

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

0. 
   төбелермен құралған матрица ^{B b}ij өлшемі болатын квадраттық матрица жолдары мен тік қатарлары төбелеріне сәйкестенеді де, теріс емес элемент
   

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

0. 
   Графтың түрлері
   

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

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

Kb -тіңCâ	2 =	b(b 1)
		2 қыры болады. Бағытты толық граф кейде турнир деп

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

а б в г

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

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

2 а, б, в суреттерге ^K3 , ^K4 , ^K5 графтары бейнеленеді. 2 г суретте

а б в 3-сурет

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

атаймыз. Оны ^Km,n белгілейміз, мұнда ^{m V}1^{;n V}2^.

0. 
   өлшемді бірлік кубы дегеніміз Eⁿ граф төбелерінде барлық алынған ұзындығы n нольдер мен бірлер, ал қырлары өзгешелігі бір компонент болатын төбелерді қосады. 4- суретте n = 3 көрініс көрсетілген.
   
1. 
   ₁₁₁
   

001

000 ¹⁰⁰

4 - сурет
Граф H = (V’, E’) G = (V, E) графының ішкі графы деп аталады да, мынадай белгімен көрсетіледі H G, егер V’ V, E’ E және V’, E’ жиындары үшін G графтың ицинденттігін сақтайды.