достъпност матрица 1

Матрицата достъпност прост насочено графика - двоичен матрица на преходност на запушалката (матрица близост е дадено от графиката). Така, матрицата се съхранява достъпност информация за съществуването на пътеки между върховете на диграфа.

• 1 Методи за конструиране на достъпност матрица
  • 1.1 умножение на матрици
    • 1.1.1 случай на множество пътеки
    • 1.1.2 Пример
  • 1.2 Uorshella алгоритъм
• 2 Свързани понятия
• 3 Matrix силно свързана
  • 3.1 Изграждане на силна матрица свързаност
    • 3.1.1 Пример
• 4 матрица на графиката

Методи за конструиране на матрицата достъпност

умножение на матрици

При един прост графика. близост матрица, която е. къде. матрица близост дава информация за всички пътища с дължина 1 (т.е., ръбове) в Fargo. За да търсите пътища с обща дължина 2 може да се намери на състав на връзката със себе си:

По дефиниция, съставът има връзка матрица. където - съюзът и - дизюнкцията.

След намиране на матриците за всички състави. Тя ще предоставя информация за всички маршрути от по дължина. Така, матрицата е желания матрица достъпност.

В случай на няколко пътеки

Ако булеви операции дизюнкцията и съюзът замени конвенционален алгебрични събиране и умножение, съответно, чрез намиране на матрицата се намалява на достъпност обичайните етапи умножение на матрици, последвано от добавяне на резултатите от всеки етап. След това, получената матрица ще се състои не само от 0 и 1, и се характеризира не само от присъствието на пътеки между възли, но броят на такива пътища. В този случай, можете да позволите на наличието на множество ръбове в графиката.

Да разгледаме прост свързан насочено графика. Той е матрицата на съседство формата:

Намери булеви правомощията на тази матрица.

Ние се получи матрица достижимост

По този начин, от върха можете да стигнете до всяка друга.

При използване на същите алгебрични операции получат матрица

Това показва броя на пътеки с дължина от 1 до 4 между върховете на диграфа.

Uorshella алгоритъм

Има и друг алгоритъм за намиране достижимост точността на матрица от стъпки - алгоритъм Uorshella.

свързаните с него понятия

силна матрица свързаност

Матрицата силно свързан прост диграфа - двоичен матрица, съдържаща всички върхове в силно свързан диграфа. силна матрица свързаност е симетрична. Силно свързан граф е матрица изпълнен с такива.

Изграждане на силна матрица свързаност

Матрицата силна връзка може да бъде изработена от матрица достъпност. Да - достижимост матрица на диграфа. След това матрицата се състои от силно свързани компоненти.

Помислете за една и съща графика, както преди.

Неговата матрица достижимост:

От него получаваме матрица от силна връзка:

Върховете 3 и 4 са силно свързани един с друг и с тях.

Граф свързаност матрица

За свързан граф е концепцията за свързване матрица. подобен на матрицата на достъпност.