Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану
жүктеу/скачать 1.12 Mb.
|
- Бұл бет үшін навигация:
- Дәріс №7-8. Графтар саны. Графтармен орындалатын операциялар
| Қолданылған әдебиеттер
[1], [2], [3], [5], [16], [18]. Бақылау сұрақтары: 1.Граф дегеніміз не? 2.Инциденттік матрица қалай анықталады? 3.Толық граф дегеніміз қандай граф? Ілмек деген не? 5.Графтың қандай түрлері бар? Дәріс №7-8. Графтар саны. Графтармен орындалатын операциялар Дәріс мақсаты:Графтармен орындалатын операциялармен таныстыру. Кілттік сөздер:граф,цикломатиялық сан,Гамильтон графы,. Цикломатиялық сан. Графтың барлық төбелері арқылы өтетінэлементарлық жол гамильтондық жол деп аталады да, егер оның басы және соңы бірігіп кетсе, онда оны гамильтондық цикл деп атайды. Белгілі коммивояжер жөніндегі есеп былай тұжырымдалады: Қосарланған қашықтағы белгілі n қалалар бар. Коммивояжер барлық қалаларға келгендегі жолдың ұзындығының қосындысы өте аз (минималды) болатынды табу керек. Бұл дегеніміз оң сандар жазылған қырлардың ұзындығы kn толық графтағы гамильтон жолының ең аз ұзындығын табу (есептің варианты үшін – айналып ( , )
төбе n1 басқа төбелермен қосатын) {1,2,…,n} құралған жиынын қарастырамыз. Сонда көрсетілген тізбек Gn графындағы жолына сәйкес келеді 2.8 а - суретте n =3 кескіні көрсетілген кезкелген графтың екі жұп бөліктерінің қосындысыда жұп граф бөлігі болады. Егер S1 және S2H1 және H2 граф бөліктерінің кейбір төбенің дәрежелері болса, ал S12H1H2 қиылысуындағы оның дәрежесі болса, онда H1H2 граф бөлігінің төбесіндегі S( ) дәрежесі H1H2(S1S12) (S2S12)S1S22S12 . 321
312 231
132
123
1-сурет
S1 жәнеS2 жұп болғандықтан ондаS( ) -де жұп. Сондықтан жұп граф бөліктері кеңістіктегі барлық граф бөліктерінің кеңістік бөліктерін құрайды, да ілінген элементарлық циклдердің жиыны кеңістік бөлігімен бірігіп кетеді. Осы кеңістік бөліктерінің V - өлшемін анықтаймыз. P қырлардан және b төбелерден тұратын G байланысты граф берілсін.D–оның кейбір тұлғасы. P b1 – хорда саны. әрбір хорда бір элементарлық тізбегімен бірге элементарлық цикл құрайды, бірақ осы циклдердің векторы (әртүрлі хорда үшін) байланыссыз жүйе құрайды, циклдердің әрбіреуі жүйенің қалған циклдерінің ешбіреуінде жатпайтын қырды ұстайды. Осыдан V P b 1. Басқаша айтқанда, әрбір жұп граф бөлігі, кез келген жай цикл жүйенің циклі арқылы өрнектеледі. Шынында, H жұп граф бөлігіне жүйенің циклдерінің H -қа кіретін граф хордасын қосамыз. Алынған қосынды ешқандай хорданы ұстамайды (әрбір хорда қосындыға екі рет кіреді: H граф бөлігі және жүйенің циклдерінің біреуі ретінде) D ағашының кейбір граф бөлігі ретінде. Осыдан құр граф бөлігі, сол себепті қарсы жағдайда жұп граф бөлігі шығар еді ( H және циклдерінің қосындысы), D ағашында тұратын элементарлық циклдер. Сондықтан V P b1. K компоненттерімен байланысты базис кеңістігіндегі жұп граф бөліктерінің байланыссыз графы үшін оның байланысты компоненттерінің бірігуімен алынады да, ал қырлары мен
цикломатиялық саны деп аталады.V 0 болғандықтан,кез келген граф үшін b p. Ағаштар байланысты графтар, оның цикломатиялық саны V 0 .
цикломатиялық сан V 10 5 1 6 . жүктеу/скачать 1.12 Mb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||