1. 1Жиын ұғымы. Шекті және шексіз жиындар. Жиындарды анықтау тәсілдері.Ішкі жиындар. Берілген жиынның барлық жиынтығы. К- элемент жиындарының саны туралы n- элемент жиынтығы
жүктеу/скачать 336,61 Kb.
|
| 2:2.1
Графтар теориясы-әрбір қадамда алгоритм бар ағынға кеңейтетін жол ағынын қосады. Егербарлық жиектердің сыйымдылығы бүтін сандарболса, барлық жиектер арқылы өтетін ағындарәрқашан бүтін сандар болатынын индукция арқылыдәлелдеу оңай. Егер шеттердің ең болмағандабіреуінің сыйымдылығы иррационал сан болса, онда алгоритм тіпті дұрыс шешімге міндетті түрдежақындамай-ақ шексіз жұмыс істей алады. Төменде мысал келтірілген.қ тұрғыдан келу тән бюолып табылатын бөлім. Граф теориясыныңнегізгі мазмұны графтарды зерттеу болыптабылады. Граф – «граф» — «жазамын» дегенмағанадағы грек сөзінен алынған. Жазықтықта әртүрлі бес A,B,C,D,E нүктелерінбелгілейік. Осы нүктелерді графтың төбелері, ал оларды қосатын сызықтарды \түзу немесе қисық\ графтың қабырғалары деа атайды.Бұл графтыA,B,C,D,E нүктелерін қосатын сызықтар осы нүктелерден басқа ешбір нүктелерденқиылыспайтындай етіп те кескіндеуге боладыв. Қабырғалары тек төбелерінде ғана қиылысатынграфты жазық граф деп атайды. Графтың мынадай негізгі қасиеттері болады: Оның тақ төбелерінің саны әрқашан жұп болады. Тақ төбелерінің саны тақ сан болатын графтысызып көрсету мүмкін емес. Егер графтың барлық төбелері жұп болса ондаграфты бір сызықтықпен сызып шығуға болады. Тақ төбелерінің саны екіге тең болатын графты бірсызықпен сызып шығуға болады. Мұндақозғалысты тақ тқбелердің кез – келген біреуіненбастап екіншісінен аяқтау қажет. Тақ төбелерінің саны екіден артық болатын графтыбір сызықпен сызып шығу мүмкін емес. Анықтама. Өзара қиылысу нүктелерінде екі ғанарет бола отырып сызып шығуға болатын жазыққисықты бір бағытты қисық деп атайды. Теорема. Қисық бір бағытты (уникурсал) болу үшіноның тақ түйіндерінің саны екіден артықболмауықажетті және жеткілікті. Анықтама. Кез келген төбелер жұбы байланыстыболатын графты байланысты граф деп атайды. Керіжағдайда граф байланыссыз болады. Ал оның максимал байланысты болатын ішкі графтарынграфтың байланыс компоненталарыдепатайды.Теорема. Егер графтың тура екі төбесініңдәрежелері тақ болса, онда олар байланыстыболады. Егер графы байланыссыз болса, онда оның толықтауышы графы байланысты болады, және оның кез келген екі төбесінің ұзындығы екіденаспайтын тізбегімен байланысты.Теорема. төбелікбайланысты графтың қабырғаларының ең кішісаны тең. • Бағдарланбaғaн граф (Неориентированный граф) — төбелерді қосатын доғаларының бағыты болмайтын граф. • Бағдарланған граф (Ориентированный граф; directed graph) - әр түрлі төбелер жұбын жалғастыратын қабырғалармен бірге түйіндердің (немесе төбелердің) құр ақырғы жиыны. Егер е қабырғасы Vl және V2 төбелерін жалғастырса, онда Vl мен И,-ні инцидент деп атайды және бұл төбелер көршілес болып саналады, е — реттелмеген жұп (К, и V2). Әдетте, граф көрнекті формада ұсынылады, сонымен бірге төбелері нүктелермен немесе кейде ұқсастыру мақсатымен ентаңбаланған басқа мүсіндермен, ал қабырғалары сәйкес нүктелерді жалғастыратын сызықтармен кескінделеді. Егер әрбір қабырғаға бағыт көрсетілсе, онда мұндай граф бағдарланған граф деп аталады. Бұл жағдайда қабырға әр түрлі төбелердің реттелген жұбының жиынын үйымдастырады және оларды көбінесе доға деп атайды. Бағдарланған граф көрнекті түрде ұсынылған кезде әрбір доға жебелікпен жабдықталады. Көптеген қолданбалы есептерде айналамыздықоршаған ортаның әртүрлі объектілер арасындағыбайланыстар жүйесі зерттеледі. Объектілер төбелердеп аталып, нүктелер арқылы белгіленеді, ал төбелерарасындағы байланыстар доғалар деп аталып, сәйкеснүктелерді қосатын бағытталған түзулерменбелгіленеді. Қала көшелерін граф арқылы кескіндеугеболады: көше қиылысуларын графтардың төбесі деп, ал көшелерді доғалар деп алуға болады; Блок-схемаларды да граф түрінде кескіндеуге болады: блоктар — граф төбелері, ал операцияның орындалукезегін көрсететін стрелкалар доғалар. Анықтама: G=(M,R) алгебралық жүйе граф депаталады. Мұндағы М—жиынтығы бос емес жиын, оның элементтері графтың төбелері деп аталады, ал бинарлы R қатынасының R M2 элементтері доғалардеп аталады. Сонымен граф төбелері дегеніміз –айналамызды қоршаған ортаның кез келген объектісі. Олардың саны шектеулі болғандықтан,біз олардынатурал сандармен белгілейміз. Ал граф қабырғаларыоның кейбір төбелерін қосады. Граф қабырғаларынәдетте латын әріптерімен белгілейді. G= ‹M,R› графының геометриялық кескіні жазықтықта графтыңәр төбесін нүкте арқылы белгілеп , егер (a,b) R болса а төбесінен b төбесіне доға жүргізу арқылы алынады. Графтар теориясы - бұл математика бөлімшелердің бірі, объектілерін зерттеу геометриялық әдісі болып табылады, оның негізгі ерекшелігі болып табылады. Ол негізін қалаушы болып саналады атақты математик Эйлер. 19 ғасырдың аяғына дейін графтар теориясын қолдану, қызықты мәселелерді шешуге азайды және айтарлықтай қоғам назарын тартылды. графтар теориясы тәуелсіз математикалық пән ретінде қалыптасты кезде 20-шы ғасырдың бастап, ол кеңінен осындай кибернетика, физика, логистика, бағдарламалау, биология, электроника, көлік және байланыс жүйелері сияқты салаларда қолданылады. жүктеу/скачать 336,61 Kb. Достарыңызбен бөлісу:
|