elérhetőségi mátrix 1

Mátrix elérhetőségi egyszerű irányított gráf - bináris mátrix tranzitivitást a lezárás (a szomszédsági mátrix által adott grafikon). Így a mátrix tároljuk elérhetőségi információk a létezését utak között a csúcsai a digráf.

• 1 megalkotásának eljárásai elérhetőségi mátrix
  • 1.1 Szorzás mátrixok
    • 1.1.1 Ha több útvonal
    • 1.1.2 példa
  • 1.2 Uorshella algoritmus
• 2. Kapcsolódó fogalmak
• 3 Matrix erősen összefüggő
  • 3.1 épület egy erős kapcsolat mátrix
    • 3.1.1 példa
• 4 mátrixa a grafikon

Megalkotásának eljárásai elérhetőségi mátrix

mátrix szorzás

Adott egy egyszerű gráf. szomszédsági mátrix, amely. hol. A szomszédsági mátrix információt nyújt minden olyan út, a hossz 1 (azaz, élek) Fargoban. Kereséséhez utak hossza 2 megtalálható a készítmény kapcsolatot önmagaddal:

A definíció szerint a készítmény egy kapcsolat mátrix. ahol - az és kötőszó - eltérésre.

Miután megtalálta a mátrixok minden kompozíciók. Ez tájékoztatást fog nyújtani minden útvonalakat méretre. Így a mátrix a kívánt mátrix elérhetőségi.

A esetében a többszörös útvonal

Ha a logikai műveletek diszjunkciót és összefüggésben helyettesíti a hagyományos algebrai összeadást és szorzást, megfelelőleg, a megállapítás a mátrix fog csökkenni elérhetőségi szokásos lépésenkénti szaporodását mátrixok majd az eredményeket összeadjuk az egyes lépésben. Ezután, a kapott mátrix állna nemcsak 0 és 1, és lesz jellemző nem csak a jelenléte utak csomópontok közötti, de ez a szám az ilyen utak. Ebben az esetben, akkor lehetővé teszik a többszörös élek a grafikonon.

Tekintsünk egy egyszerű csatlakoztatott irányított gráf. Ő a szomszédsági mátrix a következő formában:

Keresse logikai hatáskörét ez a mátrix.

Kapunk egy mátrixot elérhetőséget

Így a felső akkor kap a többinél.

Amikor ugyanazt az algebrai műveleteket kapjunk mátrixot

Ez azt mutatja, útvonalak számának hossza 1 és 4 közötti a csúcsai a digráf.

Uorshella algoritmus

Van egy másik algoritmust, hogy megtalálják a mátrix elérhetőség pontosságára lépések - egy algoritmus Uorshella.

kapcsolódó fogalmak

erős kapcsolat mátrix

Mátrix erősen összefüggő egyszerű digráf - bináris mátrix tartalmazza az összes csúcs erősen összefüggő digráf. erős kapcsolat mátrix szimmetrikus. Erősen összefüggő gráf egy olyan mátrix, tele is.

Egy erős kapcsolat mátrix

Mátrix erős kapcsolat lehet alakítani mátrix elérhetőséget. Let - elérhetőségének mátrixa digráf. Ezután a mátrix egy olyan, erősen összefüggő komponensek.

Tekintsük ugyanazon a grafikonon, mint korábban.

A mátrix elérhetőség:

Belőle kapunk egy mátrix erős kapcsolat:

A csúcsok a 3. és 4. erősen köti össze egymással és önmagukkal.

Gróf kapcsolat mátrix

Egy gráf van fogalma kapcsolódási mátrix. hasonló a mátrix elérhetőség.