Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану
жүктеу/скачать 1.12 Mb.
|
- Бұл бет үшін навигация:
- Бақылау сұрақтары
- Дәріс №6. Графтар теориясына кіріспе
- Графтың негізгі анықтамалары
| Логикалық амалдар
1-кесте
0 және 1 функциялары сәйкесінше нөлдік және бірлік функция деп аталады. функциясын теңбе - тең фунция деп атайды. функциясын х – ті жоққа шығару немесе терістеу деп атайды, деп белгілейміз. 4. функциясын нің конъюнкциясы немесе логикалық көбейтіндісі деп атайды, оны деп белгілейміз. 5. функциясын ің дезъюнкциясы немесе логикалық қосындысы деп атайды, оны белгілейміз. 6. функциясын нің модуль екі бойынша қосындысы деп атайды, оны деп белгілейміз. функциясын нің эквиваленциясы деп атайды, оны деп белгілейміз. функциясы ің импликациясы деп атайды, оны деп белгілейміз функциясын нің Шеффер штрихы деп атайды, оны деп белгілейміз. Бұл функция антиконъюнкция деп те аталады. 10. функциясын нің Пирс бағыттаушысы деп атайды, оны деп белгілейміз. Бұл функция антидизъюнкция деп те аталады. Бақылау сұрақтары: Бульдік функция деген қанадй функция? Құрама дегеніміз не? Логикалық функцияларға қолданылатын амалдарды атаңыз. Дәріс №6. Графтар теориясына кіріспе Дәріс мақсаты:Графтар теориясының негізгі ұғымдарымен,олардыңтүрлерімен таныстыру. Кілттік сөздер:граф,ілмек,сыбайлас,инциденттік матрицасы,төбе,қыр. Жоспары: Графтың негізгі анықтамалары Графтың инциденттік матрицасы Графтың түрлері Графтың негізгі анықтамалары Анықтама. Граф деп–бейнеленген заттардың екі–екіден жұпталыпкелген заттардың бір – бірімен қатынасының жүйесін айтады. Графтармен 39
коммуникация жолдарын қолайлы бейнелейді, үздіксіз емес көп қадамды процестерде («бинарлық қатынастардың жүйелерін, химиялық формулалардың құрылымында, тағы басқа әр түрлі схемалардың диаграммаларында») қолданылады. Граф G - жүйе G V,E,V V жиынының элементі граф төбесінен тұрады да, E e қыры болып келген бейнелеуді көрсетеді. :E V2 егер әрбір элементтің e E реттелген санға сәйкес реттелген екі элементті V1,V2V – ның қырларының соңы сәйкес келеді.
G V,E, үшін ең қысқа G V,E . Мұнда инцинденттілігі көрсетілмеген. Олар контекстпен анықталады. Элементтерінің санына байланысты шекті және шексіз болып бөлінеді. Біз тек ғана шекті графпен танысамыз. Егер r e V1,V2–екі–екіден таралып реттелген. V1,V2 V2,V1 V1V2болғанда,ондаeбағытталған доғал болады да, шыққан V1 - төбесі e доғасының басы, кіретін V2 төбесі e доғасының соңы деп аталады. Егер r e V1,V2жұбы ретсіз болса,ондаeқыры бағытсыз деп аталады. ~ Кез – келген G графқа сәйкестендіріліп алынған бағытсыз граф G ,V және жиындарынан және инцинденттіктерінен тұрады, бірақ барлық парлары ретсіз болады. Төбелері бірде – бір қырымен инциндентті болмаса, онда ондай қырды бөлектенген қыр деп атаймыз,ал төбесі бір қырымен инциндентті болса,ондаоны аяқталған қыр, не ілінген қыр деп атаймыз. Қырдың басы мен соңы біріккен болса, оны ілмек деп атаймыз. Егер екі төбе бір қырға инциндентті болса, ондай төбелерді көршілес, не сыбайлас төбелер деп атайды.Егер екі қыр бір төбеге инциндентті болса,ондаондай қырды сыбайлас деп атаймыз. Қырға сәйкес қойылған екі төбені еселік, не параллель төбелер деп атаймыз. Әртүрлі есептер үшін бір тек сол затқа графтың әртүрлі салыстыруы қажет. Мысалы: жолдар тармағының үзіндісі ретсіз қырмен көрсетіледі де, бір– бірімен қатынастарының аяқталуын бейнелейді (қоныстанған орындарымен, қала көшелерімен, көшенің түйіскен жерімен құралдарындағы бір жақты, не екі жақты қозғалыстар). Бірнеше доғаларымен бөлектеген әрбір бірнеше қозғалысты – қырға қосымша жазылған сандар, оның ұзындығын, енін, епкіштігін және сандар не басқа сипаттамасын көрсетеді. Қандай графтар ажыратылатын және ажыратылмайтын болып бөлінуін анықтау өте қажет болып табылады, оны тіпті графтардың изоморфизм ұғымымен байланыстырады. Өзара сақталып инцинденттік пайда болған
r1 e1 V1,V2 =>r2 ge2 fV1,fV2 көптеген жағдайларда графтарды изоморфизмгедейінгі дәлдікпен қарастыруға болады, яғни изоморфты графтастыруы байқалмау, бірақ қайсібір графтардың төбелерінің немесе қырларының әртүрлі ерекшеліктері болса, мысалы, номерленген немесе оларға сандық мәндер сәйкестендірілген (қырының салмағы, қырының ұзындығы және т. б.) болса, онда екі графты салыстыру кезінде олардың ерекшеліктерін ескеру заңды. Графтарды бірнеше жолдармен беруге болады. Шекті графты оның қырларының тізімінің санын көрсетіп санау арқылы, оған қоса жеке тұрған төбенің тізімін көрсету.
жүктеу/скачать 1.12 Mb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||