достъпност матрица - е
Методи за конструиране на матрицата достъпност
умножение на матрици
При един прост графика, близост матрица, която е мястото, където. матрица близост дава информация за всички пътища с дължина 1 (т.е., ръбове) в Fargo. За да търсите пътища с обща дължина 2 може да се намери на състав на връзката със себе си:
.
По дефиниция, матрица състав връзка е където - съюзът. и - разделяне.
След намирането на матриците за всички композиции, тя ще предостави информация за всички пътища на дължина. Така, матрицата е желания матрица достъпност.
В случай на няколко пътеки
Ако булеви операции дизюнкцията и съюзът замени конвенционален алгебрични събиране и умножение, съответно, чрез намиране на матрицата се намалява на достъпност обичайните етапи умножение на матрици, последвано от добавяне на резултатите от всеки етап. След това, получената матрица ще се състои не само от 0 и 1, и се характеризира не само от присъствието на пътеки между възли, но броят на такива пътища. В този случай, можете да позволите на наличието на множество ръбове в графиката.
Помислете prostoysvyaznyyorientirovanny графика. Той е матрицата на съседство формата:
Намери булеви правомощията на тази матрица ,:
, , .
Ние се получи матрица достижимост
По този начин, от върха можете да стигнете до всяка друга.
Това показва броя на пътеки с дължина от 1 до 4 между върховете на диграфа.
Uorshella алгоритъм
Има и друг алгоритъм за намиране достижимост точността на матрица от стъпки - алгоритъм Uorshella.
силна матрица свързаност
Matrix svyaznostiprostogo силен диграфът - двоична матрица. съдържащ всички върхове в силно свързан диграфа. силна матрица свързаност е симетрична. Силно свързан граф е матрица изпълнен с такива.
Изграждане на силна матрица свързаност
Матрицата силна връзка може да бъде изработена от матрица достъпност. Да - достижимост матрица на диграфа. След това матрицата се състои от силно свързани компоненти.
Помислете за една и съща графика, както преди.
Неговата матрица достижимост:
От него получаваме матрица от силна връзка:
Върховете 3 и 4 са силно свързани един с друг и с тях.
Граф свързаност матрица
За конвенционална (не-ориентирана), свързан графика е концепцията за свързване матрица. подобен на матрицата на достъпност.
Този раздел не е приключило.
Вижте това, което "достижимост матрица" в други речници:
достъпност матрица - маршрутизиране на маса, които са изброени само тези възлови точки, с които възловата точка комуникира. Той обикновено се използва за контролиране на образованието в цикъла маршрути. [LM Nevdyaev. Телекомуникационни технологии. Английски Български обяснителен ... ... Референтен технически преводач
Binary матрица - (двоично матрица (0, 1) матрица) матрица, чиито елементи са 0 или 1. Примери на двоичен матрица пермутация матрица двоичен матрица във всяка колона и ред от които само един блок, и всички останали ... ... Wikipedia
Речник на теория на графите - съдържа определения на теория на графите. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р ... Wikipedia
Vertex (графика) - съдържа определения на теория графика. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р Т U V ... Wikipedia
Дължината на диграфа - съдържа определения на теория графика. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р Т U V ... Wikipedia
Дъг (графика теория) - съдържа определения на теория графика. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р Т U V ... Wikipedia
Честота - съдържа определения на теория на графите. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р Т U V ... Wikipedia
Мултиграф - съдържа определения на теория графика. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р Т U V ... Wikipedia
Подграф - съдържа определения на теория графика. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р Т U V ... Wikipedia
Лесен начин да диграфът - съдържа определения на теория на графите. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р Т U V ... Wikipedia