Macierz przejść

[darek88]

W jaki sposób tworzy się macierz przejść w teorii grafów?

[yorgin]

Jeśli wierzchołki to \(\displaystyle{ w_1,\ldots, w_n}\), a macierz to \(\displaystyle{ P=[p_{ij}]}\), to

\(\displaystyle{ p_{ij}=1 \iff \exists w_i\rightarrow w_j}\)

tzn. \(\displaystyle{ p_{ij}=1}\) gdy istnieje krawędź od wierzchołka \(\displaystyle{ w_i}\) do wierzchołka \(\displaystyle{ w_j}\). Jeśli graf jest nieskierowany, to macierz wyjdzie symetryczna.

Oczywiście jeśli nie ma krawędzi, to wstawiamy zero.

[darek88]

Czy jako pierwsze występują kolumny czy wiersze?

[yorgin]

Standardowo pierwszy indeks to numer wiersza.

Zatem w pierwszym wierszu jest opis przejść od wierzchołka \(\displaystyle{ w_1}\) do pozostałych.

Jeszcze uwaga: zakładam, że graf jest bez krawędzi wielokrotnych. Jeśli jest więcej niż jednak krawędź odpowiadająca parze wierzchołków, to wpisuje liczbę tych krawędzi.

[darek88]

Czym są krawędzie wielokrotne? Czyli rozumiem, że macierz przejść analizuje się poziomo?

[yorgin]

Mówimy, że między wierzchołkami \(\displaystyle{ w_1}\) i \(\displaystyle{ w_2}\) jest krawędź wielokrotna, gdy obrazowo jest więcej niż jedna kreska łącząca te wierzchołki.