accesibilități matrice 1

Matrix accesibilități grafic simplu regia - matrice binară pe tranzitivitatii a elementului de închidere (matricea adiacenta este dată de grafic). Astfel, matricea este stocată informații accesibilități despre existența căilor între vârfurile digraph.

• 1 Metode pentru construirea matricei accesibilități
  • 1.1 Multiplicarea matrici
    • 1.1.1 Cazul de mai multe căi
    • 1.1.2 Exemplu
  • 1.2 Uorshella Algoritmul
• 2 Concepte înrudite
• 3 Matrix conectat puternic
  • 3.1 Construirea unei matrice de conectivitate puternică
    • 3.1.1 Exemplu
• 4 matrice a graficului

Metodele pentru construirea matricei accesibilități

matrice de multiplicare

Având în vedere un grafic simplu. matricea de adiacență, care este. în cazul în care. Matricea de adiacență oferă informații cu privire la toate căile de lungime 1 (adică, margini) în Fargo. Pentru a căuta căi de lungime 2 poate fi găsit o relație de compoziție cu tine:

Prin definiție, compoziția are o matrice de relații. în cazul în care - coroborat și - disjuncției.

După ce a constatat matrici pentru toate compozițiile. Acesta va furniza informații cu privire la toate rutele de la lungime. Astfel, matricea este accesibilități matricea dorită.

Cazul mai multe căi

În cazul în care operațiunile Boolean disjuncției și conjuncției înlocui adăugarea algebric convenționale și multiplicare, respectiv, prin găsirea matricea va fi redusă la accesibilități multiplicarea în trepte obișnuite de matrici, urmată de adăugarea rezultatelor fiecărei etape. Apoi, matricea rezultată ar consta nu numai din 0 și 1, și vor fi caracterizate nu numai prin prezența unor trasee între noduri, dar numărul de astfel de căi. În acest caz, puteți permite prezența mai multor margini în grafic.

Luați în considerare un grafic simplu direcționat conectat. El este matricea de adiacență a formei:

Găsiți puteri Boolean ale acestei matrice.

Obținem o matrice accesibilități

Astfel, din partea de sus poate ajunge la orice alt.

Când se utilizează aceleași operații algebrice se obține o matrice

Acesta arată numărul de căi de lungime între 1 și 4 între vârfurile digraph.

Uorshella algoritm

Există un alt algoritm pentru a găsi acuratețea accesibilități matricea de pași - un algoritm Uorshella.

concepte înrudite

matrice de conectivitate puternică

Matrix conectat puternic digraph simplu - matrice binar care conține toate nodurile din digraph puternic conectate. matrice de conectivitate puternică este simetrică. Noi grafic puternic conectat este o matrice umplut cu cele.

Construirea unei matrice de conectivitate puternică

Conectivitatea puternic Matrix poate fi construit din accesibilități matrice. Să - matricea accesibilități a digraph. Apoi, matricea constă dintr-un componente puternic conectate.

Luați în considerare același grafic ca și înainte.

accesibilități sa matrice:

Din aceasta se obține o matrice de conectivitate puternică:

Nodurile 3 și 4 sunt strâns legate între ele și cu ei înșiși.

Count matrice de conectivitate

Pentru un grafic conectat există conceptul de matrice de conectivitate. similar cu matricea accesibilități.