Графтар теориясы
жүктеу/скачать 346.6 Kb.
|
- Бұл бет үшін навигация:
- Эйлер графы
- Қабырғалар тізімі.
- Қолтықтас матрицалар.
Графтар теориясы
Граф деп V төбелерден және соған сәйкес Е қабырғалардан тұратын (V, E), жұбын айтады. Граф дәрежесі төбеден шығатын қабырғалар санын сипаттайды. Графтар теориясы күрделі жүйелерді талдағанда,компьютер және телефон желілерін т.с.с. жобалаған кезде қолданылады. Граф туралы түсінікті Л.Эйлер 1736 жылы Петербург академиясы журналында жариялады. Ол “Кенигсберг көпірлерінің есебі” деп аталынды. Қала Прегель өзенінің екі жағасында және екі аралда орналасқан. Қала аудандары көпірлер арқылы жалғасады. Кенигсберг қаласының орналасуы Кенигсберг қаласының орналасуы Мәселе былай бір ауданнан шығып әрбір көпірмен бір рет жүріп қайтадан сол ауданға келуге бола ма? Мұнда А,В,С,D -аралдарды немесе жағаларды ал a,b,c,d,g,e,f көпірлерді сипаттайды. Маршруты бір төбеден басталып сол төбеде аяқталатын және әрбір қабырғамен тек бір рет жүрілетін графты Эйлер графы деп айтады. Эйлер графы болу үшін оның төбелері жұп дәрежелі болуға тиісті. G графында циклдық маршрут болу үшін граф байланысты және төбелерінің дәрежесі жұп болуы қажетті және жеткілікті. Жай граф Қабырғалары еселенген Тұзақты граф Ноль граф Толық граф Терек тәріздес граф Бағытталған граф қабырғаларынан тұратын V={a,b,c,d,e} төбелерінен тұратын граф және оған сай матрица тұрғызу керек Графтардың матрицалық сипатталуы Графтарды тиімділік есептерін шығаруға қолдануға болады. Ол үшін графтар бір бағытта пайымдалуы тиіс. Графтардың берілуін мынадай тәсілдер арқылы жүзеге асыруға болады.
Графтың барлық қабырғалары(санмен және төбелері(әріппен) нөмірленеді. Жатық жолы қабырғаға ал төбесі бағанаға сай матрица тұрғызылады. Инциденция матрицасы 2. Қабырғалар тізімі. Бұл инциденция матрицасының қысқартылған түрі.Жатық жол граф қабырғаларына тең.Бағаналар саны 2. Қабырғалар тізімі. Қолтықтас матрицалар. Мұнда әрбір жатық жолға және бағанаға графтың төбесі сай болады.Олардың қиылысына таңба қойылады.Мысалы төбелер тек бір қабырғамен байланысса 1 екі қабырғамен байланысса 2 қойылады. Қолтықтас матрицалар. Жазық графтар туралы түсінік «Үш үй және үш құдық туралы есеп» Үш дос бақша учаскелерін алып, үйлер сала бастады. Алдымен үш құдық қазылып, олардың кез-келгеніне қарай жүрді. Үйлер салынғаннан кейін үй қожалары жанжалдасып кетті. Қойылатын талап олар құдыққа бара жатқан кезде бір бірмен кездеспеу керек. Ол мүмкін бе? Жазық графтар туралы түсінік «Үш үй және үш құдық туралы есеп» Үй қожаларының талаптарын қанағаттандырудың барлық әрекеттері сәтсіз аяқталады (сурет). Неліктен? Себебі бұл графты жазықтықта оның қабырғалалары қиылыспайтындай етіп бейнелеу мүмкін емес. Бұл граф жазық емес. Граф жазық па, жоқ па деген сұрақ интегралдық микросхема технологиясы үшін өте маңызды. Өйткені, әрбір микросхема белгілі бір графты білдіреді, онда байланыс алаңдары (төбелер) және байланыстар (қабырғалар) бар. Жазық графтар туралы Жордан теоремасы Граф жазық па, жоқ па және графтың жазық болуы үшін қандай қажетті және жеткілікті шарттар бар деген сұрақ математиктерді көптен бері мазалап келеді. Бұл тақырыптағы алғашқы жұмыстар Жорданға тиесілі. Ол теореманы дәлелдеді, оның мәнісі мынада. Тұйық L сызығы берілсін. Ол жазықтықты ішкі және сыртқы бөлікке бөледі. L сызығының бойынан үш нүкте жұбын(a,b),(c,d),(e,f) анықтауға және оларды бір бірімен қосуға болады. Мысалы а мен b - ны L1 сызығымен с мен d-ны L2 ал e мен f-ты L3 сызығымен қосайық. Жордан теоремасының түсіндірілуі Графтағы қабырғалар санын анықтау P(A)=2, P(B)=3, P(C)= 3 P(D)=2 P(E)=3 P(F)=3 Графтағы қабырғалар санын анықтау Жалпы алғанда графтағы қабырғалар санының формуласы Графтағы қабырға саны Р(А)=2 Р(С)=2 Р(Е)=2 Р(В)=5 Р(D)=6 Графтағы қабырғалар санын анықтау Кез келген тақ дәрежесіндегі графтағы төбелер саны жұп болады. Граф төбелері туралы теорема Терек тәріздес граф Мұндай графтарда ішкі цикл болмайды. Ж»не төбе саны қабырға санынан артық болады. Графтағы цикл деп әр төбеден қабырғалар арқылы тек бір ақ рет өтетін жүріп өтетін жолды айтады. жүктеу/скачать 346.6 Kb. Достарыңызбен бөлісу:
|