Информатика пә
жүктеу/скачать 1,41 Mb.
|
МК-Лекция
- Бұл бет үшін навигация:
- 3 Графтар жә н е ағаштар
- Ағаштар, бағытталмаған және бағытталған графтар.
| Логика (бульдік) алгебрасының негізгі заңдары
1.Орнын ауыстыру заңы. Коммутативтік (лат.–айырбастау, қайта айырбастау). X1 X2 = X2 X1 X1 X2 = X2 X1 2. Үйлестіру заңы. Ассоциативтік (лат. – біріктіру). X1 (X2 X3) = (X1 X2) X3 X1 (X2 X3) = (X1 X2) X3 3. Тарату заңы. Дистрибутивтік. X1 (X2 X3) = (X1 X2) (X1 X3) X1 (X2 X3) = (X1 X3) (X1 X3) 4. Жұту заңы. X1 (X1 X2) = X1 X1 (X1 X2) = X1 5. Желімдеу заңы. X1X2 X1X2 = X1 (X1 X2)(X1 X2) = X1 6. Де Морган ережесі. 1 X2 X3 = X1 X2 X3; X1X2X3 = X1 X2 X3 3 Графтар және ағаштар Графтар электр желілерінің және молекулалық құрылымдардың схемаларын салуда қолданылады. Қазіргі уақытта графтар теориясы бір жағынан таза математиканың бөлімдерінің бірі болса, екінші жағынан әр түрлі практикалық мақсаттарда сәйкестіктерді орнатуда, транспорттық есептерді шығаруда, мұнай құбырларын тиімді пайдалануда, Тізбектік желілер туралы есептерде, программалауда қолданылады. Графтар теориясы енді ғылымның барлық салаларында қолданылатын болды: физикада, биологияда, химияда, лингвистикада, қоғамдық ғылымдарда, техникада және т.б. Сондай-ақ, теориялық-графтық моделдер коммуникациялық желілерді, ақпараттық жүйелерді, химиялық және генетикалық құрылымдарды зерттеулерде кең танымал. Көптеген қолданбалы есептерде әр түрлі объектілер арасындағы байланыстар жиыны қарастырылады. Объектілер төбелер деп аталып нүктемен белгіленеді, ал төбелер арасындағы байланыс доға деп аталады және сәйкес нүктелер арасындағы стрелкамен белгіленеді. Осындай жүйелер графты құрайды. Ағаштар, бағытталмаған және бағытталған графтар. Граф нүктелер мен сызықтардың жиынтығы. Нұктелер графтың шыңы (төбесі), сызық қабырғасы (қыры) болады. Егер қыр екі төбені байланыстырса, онда оларды инцидентті, ал шың қабырғамен байланысса аралас деп аттайды. Граф G = (V, Е) V және Е жиындары жұбымен беріледі. Бірінші жиын элементтері v1, v2,..., vM графтың шыңы деп аталады ал (графикалық көріністе оларға нүктелер сәйкес). Екінші жиын элементтері el, e2, ..., eN қабырғалар деп аталады. Әр қабырға шыңдар жұбымен анықталады (графикалық көріністе қабырғалар графтың екі шыңын қосады). Егер граф қабырғалары шыңдардың реттелген жұбымен анықталса,онда мұндай граф бағытталған деп аталады (сызбада бағытталған графтарды бейнелеуде әр қабырғаға оның бағытын анықтайтын стрелкалар қойылады). Бес шыңы және жеті қабырғасы бар бағытталған граф 3-суретте кескінделген. Сурет 3 - Бағытталған граф мысалы Егер екі шың екі немесе одан да көп қабырғалармен қосылса, онда мұндай қабырғалар параллельді деп аталады (мысалы, қабырғалар е4 және е5). Егер қабырғаның басы мен аяғы бір жерден шықса, онда мұндай қабырға ілмек (петля) деп аталады (мысалы, қабырға e7). Ілмексіз және параллельді қабырғаларсыз графтар қарапайым деп аталады. Граф деп G = (V, Е) алгебралық жүйесін айтамыз, мұнда R-екі орынды предикаттық символ. Х тасымалдаушының элементтері G графының төбесі деп, ал V⊆Х бинарлық қатынасының элементтері доғасы деп аталады. Сонымен (a,b)∈V төбелер жұбы доға болып табылады. Мұнда сонымен қатар (а,b) доғасы а төбесінен шығушы және в төбесіне енуші деп аталады. Келтірілген түсініктер мен анықтамаларды анализдеу араларында белгілі бір байланыстар, қатынастар бар қандай да бір обьектілер жүйесін қарастырғанда, жүйе құрылымын үйренуде, оның жұмыс істеу мүмкінділігінде графтарды модель ретінде қолдану ыңғайлылығын көрсетеді. Информатикада графтар операциялық жүйелер, алгоритмдеу, деректер құрылымы, ақпараттық модельдеу және т.б. бөлімдерде қолданылады. Графтардың әртүрлі мүмкін әдістерін қарастыра отырып, сәйкес ақпаратты компьютерге енгізу мұқтаждығын есте сақтау қажет. Осы жағдайда ақпаратты сандық түрде енгізу ең қолайлысы, дегенмен қазіргі техникалық құралдар графикалық ақпаратты да (кестелер, мәтіндер, графиктер, суреттер) енгізеді және өңдей алады. жүктеу/скачать 1,41 Mb. Достарыңызбен бөлісу:
|