Негізгі анықтамалар
Графтардың матрицалық берілуі
жүктеу/скачать 289,71 Kb.
|
13-15АПТАдәрістері
| 6.2 Графтардың матрицалық берілуі
6.2.1 Графтарды сурет түрінде беру үнемі ыңғайлы бола бермейді. Мысалы, ЭЕМ-де оларға операциялар қолдануда. Бұл үшін графтың матрицалық берілу тәсілдері қолайлы. Одай әдістердің бірі сыбайлас матрица әдісі. Егер G графында n төбе болса, онда оның сыбайлас матрицасының M(G) = n жолы және бағанасы болады. Ол үшін i,j орнына яғни, i-жол мен j-бағанаға 1-ді қоямыз, егер G-да i-жолдан j–бағанаға қабырға болса; қарсы жағдайда 0 қоямыз: 6.2 және 6.3 суреттердегі графтар үшін матрицалар келесідей болады: M(G2) = ; M(G3) = , Мұнда G3 графында төбелер алфавиттік түрде реттелген деп есептедік, янғи А-бірінші, В-екінші, С-үшінші, т.с.с. G2 пен G3 графтары изоморфты ( белгіленеді) болса да, олардың сыбайлас матрицалары әртүрлі. Бірақ осы графтардың изоморфтығын дәлелдеуде біз G2 графының бірінші төбесіне G3 графының бірінші төбесін сәйкестікке қойдық, екіншіге – төртіншісін, үшінші-бесіншісін, төртіншіге – екіншісін, ал бесіншіге – үшіншісін. M(G2) матрицасында алдымен, жолдарын ауыстырамыз, біріншісін орнында қалдырамыз, екіншісін төртіншісінің орнына, үшіншісін – бесіншісінің, төртіншісін – екіншісінің, ал бесіншісін – үшіншісінің орнына қоямыз. Содан кейін дәл осы түрлендіруді бағандарға жасаймыз. Нәтижесінде, M(G3) матрицасын аламыз: M(G2)= = M(G3). Сыбайлас матрицаны қарапайым граф түрінде де беріге болады, бұнда негізгі диагоналі нөлдер болатын, симметриялы матрица және фультиграф түрінде жазуға болады. Соңғы жағдайда (i,j)-дің орнына басы i-төбеде болатын, соңы j-төбеде болатын қабырғалар санын жазамыз. Мұндағы матрица симметриялы емес болуы мүмкін. Кері есеп - сыбайлас матрицасы бойынша графты салу қиын емес. Жазықтықта n нүкте (жолдары мен бағандарының санына байланысты) белгілейміз, нүктелерді шеңбер бойымен орналастырған ыңғайлы. Егер берілген матрица симметриялы болмаса, онда сәйкес нүктелер бағыттармен жалғанады, қарсы жағдайда – граф бағдарсыз, сондықтан нүктелерді тек сызықтармен қоса саламыз. Егер граф жазық болып кескінделетінін көруге болса, онда олай да салуға болады, бұл сурет графтың планарлығын негіздеуге жеткілікті болады. 6.2.2 Графтардың көптеген қолдануларында қандай төбелері сыбайлас екенін білу аздық етеді, сонымен қатар қайсыбір төбесі мен қабырғасының салмағын білу де маңызды рөл атқарады. Бұл салмақтар берілу жағдайларына байланысты әртүрлі жағдайды білдіреді: ара қашықтық, шығындар, кіріс, жұмыс істеуге кететін уақыт, жағдайдан шығу ықтималдығы т.с.с. Бізге, ереже ретінді қабырғаларының салмағы ғана қажет болады. Егер қосымша төбелер мен қабырғалар енгізсе, онда 6.8 суретте осы операцияға сипатттама береді. Қабырғаларының салмағы берілген графтарды (өлшенетін графтар) салмақтар матрицасы түрінде беру ыңғайлы. Оның сыбайлас матрицадан айырмашылығы i–жолдың j–орнында i–төбеден j–ге баратын қабырғасының салмағы тұрады. Сонымен қатар, i–төбеден j–бағанаға сәйкес келсе, онда салмақтар матрицасындағы сәйкес орында ереже бойынша 0 емес, берілі жағдайына байланысты сызықша, немесе шексіздік немесе минус шексіздік белгісі тұрады. Мысалы, 6.2 суреттегі G2 графта салмақтар келесідей: u1 = 3, u2 = 4, u3 = 2, u4 = 7, u5 = 0, онда оның салмақтар матрицасы келесідей болады: 6.2.3 Кейбір жағдайларда графты инцидент (түйісу) матрицасы арқылы берген ыңғайлы болады. Бұл матрица тік бұрышты, онда графта қанша төбе болса, сонша жол болады, ал бағандар саны қабырғалар санымен тең. Оны толтырғанда төбелері ғана емес, қабырғалары да нөмірленеді, және i–ші және j–ші жолдарының k–шы бағаналарына бірлер қойылады, егер k нөмірлі қабырға i–ші және j–ші төбелерді біріктірсе. Қалған орындарға нөлдер қойылады. Графта ілгек (бастапқы және соңғы төбелері беттесетін қабырға) болса, оған сәйкес бағанаға тек бір ғана «1» жазылады. Кейде ыңғайлы болу үшін, оның орнына «2» қояды. L(G) матрицасы 6.9 суреттегі G графының инцидент матрицасы болады. жүктеу/скачать 289,71 Kb. Достарыңызбен бөлісу:
|