«Математикалық логика және дискретті математика» пәнінен syllabus
жүктеу/скачать 1,4 Mb.
|
МАТ ЛОГ ж не ДИС МАТ
- Бұл бет үшін навигация:
- Төртінші апта №4 дәрістің тақырыбы: Графтар
| Практикалық сабақтың тақырыбы. Бинар қатынастар операциялары
Дәріс тақырыбы бойынша есептер шығару Әдебиет: [4]. 58 бет. №№ 2, 3, 5, 6. СОӨЖ мазмұны: [4]. 61 бет. №№ 7, 8. СӨЖ мазмұны: [4]. 65 бет. №№ 9, 11. Төртінші апта №4 дәрістің тақырыбы: Графтар 1.Графтар теориясының ұғымдары. 2.Бір бағытты фигуралар. 3.Жазық графтар. Жазық графтар туралы Эйлер теоремасы. 4.Байланысты және Байланыссыз графтар. Графтар теориясы-шектеулі математиканың кейбір мәселелерді шешуге геометриялық тұрғыдан келу тән бюолып табылатын бөлім. Граф теориясының негізгі мазмұны графтарды зерттеу болып табылады. Граф – «граф» - «жазамын» деген мағанадағы грек сөзінен алынған. Жазықтықта әртүрлі бес A,B,C,D,E нүктелерін белгілейік. Осы нүктелерді графтың төбелері, ал оларды қосатын сызықтарды \түзу немесе қисық\ графтың қабырғалары деа атайды. Бұл графты A,B,C,D,E нүктелерін қосатын сызықтар осы нүктелерден басқа ешбір нүктелерден қиылыспайтындай етіп те кескіндеуге боладыв. Қабырғалары тек төбелерінде ғана қиылысатын графты жазық граф деп атайды. Графтың мынадай негізгі қасиеттері болады: Оның тақ төбелерінің саны әрқашан жұп болады. Тақ төбелерінің саны тақ сан болатын графты сызып көрсету мүмкін емес. Егер графтың барлық төбелері жұп болса онда графты бір сызықтықпен сызып шығуға болады. Тақ төбелерінің саны екіге тең болатын графты бір сызықпен сызып шығуға болады. Мұнда қозғалысты тақ тқбелердің кез – келген біреуінен бастап екіншісінен аяқтау қажет. Тақ төбелерінің саны екіден артық болатын графты бір сызықпен сызып шығу мүмкін емес. Анықтама. Өзара қиылысу нүктелерінде екі ғана рет бола отырып сызып шығуға болатын жазық қисықты бір бағытты қисық деп атайды. Теорема. Қисық бір бағытты (уникурсал) болу үшін оның тақ түйіндерінің саны екіден артықболмауы қажетті және жеткілікті. Теорема. Кез - келген жазық граф үшін Т – Қ + Ж= 2 теңдігі орындалады. Мұндағы Т – граф төбелерінің саны, Қ – граф қабырғаларының саны, Ж –оның жақтарының саны. Бұл теорема жазық графтар үшін Эйлер теоремасы деп аталады. Жалпы апйтқанда, графтар төбелерден , қабырғалардын және жақтардан тұрады. Берілген граф арқылы жазықтықтың бөлінген бөліктері жақтар деп аталады. жүктеу/скачать 1,4 Mb. Достарыңызбен бөлісу:
|