Macierze - wstęp

Definicje

Na początku zdefiniujmy sobie dwa pojęcia, którymi będziemy się w dalszej części posługiwać:
Wektor: Uporządkowany zbiór n liczb. Do wektora znanego nam z fizyki ma się to bardzo prosto - po prostu na fizyce mówiliśmy o wektorach rozmiaru 2 (w 2-wymiarowej przestrzeni). Teraz niestraszne nam są inne wymiary, stąd wektor może mieć n współrzędnych.
Macierz: Tablica rozmiaru $m \times n$ wypełniona liczbami, gdzie m jest liczbą wierszy, a n - liczbą kolumn. A oto i przykładowa macierz:

(1)
\begin{align} A = \begin{bmatrix} 0\ 1\ 2\ 0 \\ 3\ 4\ 6\ 1 \\ 0\ 5\ 7\ 2 \end{bmatrix} \end{align}

Macierz ta jest rozmiaru $3 \times 4$.
Jak łatwo zauważyć, wektor to macierz rozmiaru $n \times 1$.

Sprawa porządkowa: tutaj, jak i w algorytmice w ogóle, rozważać będziemy macierze liczb całkowitych nieujemnych. Oczywiście, w macierze można wpisywać liczby jakiekolwiek, z zespolonymi włącznie, ale po co sobie utrudniać życie?

W kwestii oznaczeń: o ile dla nas, informatyków, liczba w i-tym wierszu i j-tej kolumnie macierzy A to po prostu A[i][j], tak w matematyce będzie to aij. Same macierze oznaczamy dużymi literami.

Z trzymaniem macierzy sprawa jest prosta - przedstawiam mój sposób:

struct macierz
{
int t[10000][10000];
int ilosc_wierszy;
int ilosc_kolumn;
};

Oczywiście stałe w linii 3 są dobrane przykładowo, literka t nic tam nie znaczy, ładniej wygląda niż skrót "mać" :D. Elementy będziemy, dla wygody, indeksować od jedynki.

Działania na macierzach

Wprowadźmy sobie jeszcze jedno pojęcie, a mianowicie iloczyn skalarny dwóch wektorów. Weźmy sobie dwa wektory tego samego rozmiaru:

(2)
\begin{align} A = \begin{bmatrix} a_{1} \\ a_{2} \\ \vdots \\ a_{n} \\ \end{bmatrix} \qquad oraz \qquad B = \begin{bmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{n} \\ \end{bmatrix} \end{align}

Ich iloczynem skalarnym nazywamy sumę iloczynów elementów o jednakowych indeksach, czyli:

(3)
\begin{align} A\ \circ\ B \ = \ \sum_{i=1}^{n}a_{i}b_{i} \ =\ a_{1}b_{1} \ +\ a_{2}b_{2} \ +\ \cdots \ +\ a_{n}b_{n} \end{align}

Wzór ten poniekąd znamy już z zeszłorocznych lekcji matematyki.
Oczywiście nie da się mnożyć skalarnie wektorów o różnych rozmiarach

Jakkolwiek idiotycznie by to nie brzmiało, macierze tworzą ciało, to znaczy, że zdefiniowane są na nich podstawowe działania: mnożenie i dodawanie. Żeby nie było tak prosto, działania te nie zawsze są wykonywalne i nie zawsze są podobne do tych, które czynimy na liczbach rzeczywistych.

Dodawanie macierzy:

Wynikiem dodawania dwóch macierzy $m \times n$ jest macierz $m \times n$, której elementy są sumami odpowiadających sobie elementów w danych macierzach, czyli:

(4)
\begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{bmatrix} \ + \ \begin{bmatrix} b_{11} & \cdots & b_{1n} \\ \vdots & \ddots & \vdots \\ b_{m1} & \cdots & b_{mn} \end{bmatrix} \ = \ \begin{bmatrix} a_{11}+b_{11} & \cdots & a_{1n}+b_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1}+b_{m1} & \cdots & a_{mn}+b_{mn} \end{bmatrix}

Wnioski nasuwające się z tej definicji:

  1. Dodawanie macierzy jest przemienne i łączne
  2. Dodawać można tylko macierze jednakowych rozmiarów

Przykład:

(5)
\begin{bmatrix} 0\ 1\ 2\ 0 \\ 3\ 4\ 6\ 1 \\ 0\ 5\ 7\ 2 \end{bmatrix} + \begin{bmatrix} 5\ 1\ 2\ 10 \\ 2\ 4\ 9\ 5 \\ 1\ 3\ 0\ 3 \end{bmatrix} = \begin{bmatrix} 0+5\quad 1+1\quad 2+2\quad 0+10 \\ 3+2\quad 4+4\quad 6+9\quad 1+5 \\ 0+1\quad 5+3\quad 7+0\quad 2+3 \end{bmatrix} = \begin{bmatrix} 5\ 2\ 4\ 10 \\ 5\ 8\ 15\ 6 \\ 1\ 8\ 7\ 6 \end{bmatrix}

Mnożenie macierzy

Przez stałą

Aby pomnożyć macierz przez stałą, mnożymy przez tę właśnie stałą każdy jej element. Po prostu. Za proste> Spokojnie, będzie trudniej…

Przez macierz

Weźmy macierz $A$ rozmiaru $m \times k$, oraz macierz $B$ rozmiaru $k \times n$.
Niech wektor $A_{i}$ rozmiaru $k$ będzie i-tym wierszem macierzy $A$, analogicznie niech wektor $B_{i}$ rozmiaru $k$ będzie i-tą kolumną macierzy $B$.
A więc:

(6)
\begin{align} A \ \cdot \ B \ = \ \begin{bmatrix} A_{1} \circ B_{1} \quad A_{1} \circ B_{2} \quad \cdots \quad A_{1} \circ B_{n} \\ A_{2} \circ B_{1} \quad A_{2} \circ B_{2} \quad \cdots \quad A_{2} \circ B_{n} \\ \vdots \quad \vdots \quad \ddots \quad \vdots \\ A_{m} \circ B_{1} \quad A_{m} \circ B_{2} \quad \cdots \quad A_{m} \circ B_{n} \\ \end{bmatrix} \end{align}

Czyli równoważnie, dla każdego $0 \leqslant i \leqslant m, 0 \leqslant j \leqslant n$ zachodzi:

(7)
\begin{align} c_{ij} = \sum_{x=1}^{k}a_{ix}b_{xj} \end{align}

Gdzie$c_{ij}$ to element znajdujący się w i-tym wierszu i j-tej kolumnie wynikowej tablicy.

Brzmi to strasznie. Zapamiętać wystarczy jedno:
Wiersze bierzemy z macierzy po lewej, kolumny po prawej
Tak jak przy zapisywaniu rozmiaru macierzy, tutaj również najpierw idą wiersze, potem kolumny. Bierzemy wiersz z lewej, przelatujemy przez wszystkie k kolumn, bierzemy kolumnę z prawej, przelatujemy przez wszystkie k wierszy, mnożymy pierwsze z pierwszym, drugie z drugim, sumujemy, i wychodzi.

Przykład:

(8)
\begin{bmatrix} {\color{Blue}0} \ {\color{Blue}1}\ {\color{Blue}2}\ {\color{Blue}0} \\ {\color{Brown}3} \ {\color{Brown}4}\ {\color{Brown}6}\ {\color{Brown}1} \\ {\color{Red}0} \ {\color{Red}5}\ {\color{Red}7}\ {\color{Red}2} \end{bmatrix} \ \cdot \ \begin{bmatrix} {\color{RoyalBlue}5}\ {\color{Mahogany}1} \\ {\color{RoyalBlue}2}\ {\color{Mahogany}4} \\ {\color{RoyalBlue}1}\ {\color{Mahogany}3} \\ {\color{RoyalBlue}7}\ {\color{Mahogany}2} \end{bmatrix} \ = \ \begin{bmatrix} {\color{Blue} 0} \cdot{\color{RoyalBlue}5}+{\color{Blue}1}\cdot{\color{RoyalBlue}2}+{\color{Blue}2}\cdot{\color{RoyalBlue}1}+{\color{Blue}0}\cdot{\color{RoyalBlue}7} \quad {\color{Blue}0}\cdot{\color{Mahogany}1}+{\color{Blue}1}\cdot{\color{Mahogany}4}+{\color{Blue}2}\cdot{\color{Mahogany}3}+{\color{Blue}0}\cdot{\color{Mahogany}2} \\ {\color{Brown}3}\cdot{\color{RoyalBlue}5}+{\color{Brown}4}\cdot{\color{RoyalBlue}2}+{\color{Brown}6}\cdot{\color{RoyalBlue}1}+{\color{Brown}1}\cdot{\color{RoyalBlue}7} \quad {\color{Brown}3}\cdot{\color{Mahogany}1}+{\color{Brown}4}\cdot{\color{Mahogany}4}+{\color{Brown}6}\cdot{\color{Mahogany}3}+{\color{Brown}1}\cdot{\color{Mahogany}2} \\ {\color{Red}0}\cdot{\color{RoyalBlue}5}+{\color{Red}5}\cdot{\color{RoyalBlue}2}+{\color{Red}7}\cdot{\color{RoyalBlue}1}+{\color{Red}2}\cdot{\color{RoyalBlue}7} \quad {\color{Red}0}\cdot{\color{Mahogany}1}+{\color{Red}5}\cdot{\color{Mahogany}4}+{\color{Red}7}\cdot{\color{Mahogany}3}+{\color{Red}2}\cdot{\color{Mahogany}2} \\ \end{bmatrix} \ = \ \begin{bmatrix} 4\ 10\\ 36\ 39\\ 31\ 45 \end{bmatrix}

Skoro mówiliśmy macierz "z prawej", macierz "z lewej", to na pewno mnożenie macierzy nie jest przemienne. Ponieważ używaliśmy iloczynu skalarnego, to musieliśmy mnożyć wektory tego samego rozmiaru. Oznacza to, że lewa macierz (czy lepiej: macierz z lewej strony) musi mieć tyle samo kolumn co prawa - wierszy. W przeciwnym wypadku mnożenie macierzy jest niewykonalne.

Szybkie mnożenie macierzy jest jednym z ważniejszych nierozwiązanych problemów algorytmiki. Póki co, nieznacznie jedynie zbito złożoność brutalnego algorytmu, który będziemy stosować, a który przedstawiam poniżej:

macierz pomnoz(macierz A, macierz B)
{
    macierz wynik;
    for(int i=1;i<=A.ilosc_wierszy;i++)
        for(int j=1;j<=B.ilosc_kolumn;j++)
            for(int x=1;x<=A.ilosc_kolumn;x++)
                wynik.t[i][j]=wynik.t[i][j]+A.t[i][x]*B.t[x][j];
    return wynik;
}

Oczywiście mogłem równie dobrze, zamiast "x<=A.ilosc_kolumn", napisać w linii 6 "x<=B.ilosc_wierszy".

Złożoność tego algorytmu jest oczywista, i wynosi $O(mkn)$, gdzie:
m i k to wymiary macierzy A
k i n to wymiary macierzy B

Element neutralny mnożenia macierzy.

Elementem neutralnym dodawania jest oczywiście macierz wypełniona zerami. Przy mnożeniu sprawa się nieco komplikuje, ale nadal jest prosta. Oznaczmy sobie macierz dowolną jako A, poszukiwaną "jedynkę" jako B. Chcemy, aby dla każdego aij:

(9)
\begin{align} a_{ij} = \sum_{x=1}^{k}a_{ix}b_{xj} \end{align}

Gdzie k - liczba kolumn macierzy A. Oczywiście warunek ten jest spełniony dla każdego elementu aij wtedy, gdy w wyrazie sumy powyżej, jako współczynnik bxj pojawi się 1 dla x=j (bo wtedy przy a pojawią się indeksy i, j) i 0 w przeciwnym wypadku. Oznacza to ni mniej ni więcej, że w szukanej macierzy chcemy mieć same zera - i jedynki na przekątnej (tj. tam, gdzie nr wiersza = nr kolumny).
Macierz taką oznaczamy literą I

Twierdzenie o macierzy odwrotnej

Jeżeli dla danej macierzy A istnieje taka macierz B, że iloczyn AB = I, to wtedy BA = I.
Macierz B nazywamy macierzą odwrotną do A i oznaczamy A-1, oczywiście jeżeli B= A-1, to A= B-1.
Jeżeli macierz posiada macierz do siebie odwrotną, wtedy nazywamy ją osobliwą, w przeciwnym wypadku: nieosobliwą.

Uwaga: mnożenie macierzy jest łączne, a co za tym idzie, możliwe jest…

Potęgowanie macierzy

Czyli po prostu mnożenie macierzy przez samą siebie odpowiednią ilość razy. Oczywiście, skoro pierwsza macierz musi mieś tyle samo kolumn co prawa macierz (czyli ona sama), aby potęgowanie było wykonalne, macierz musi mieć tyle samo wierszy co kolumn, czyli mówiąc najprościej, musi być ona kwadratowa.
Do tego niecnego celu użyjemy znanego wszystkim algorytmu szybkiego potęgowania, który przytoczę w wersji ładniejszej, bo rekurencyjnej:

int potega(macierz podstawa,int wykladnik)
{
    if (wykladnik==0) 
        return jedynka;
    kwadrat=pomnoz(podstawa,podstawa);
    if (wykladnik%2==0)
        return potega(kwadrat,wykladnik/2);
    else
        return pomnoz(podstawa,potega(kwadrat,wykladnik/2));    
}

Oczywiście "jedynka" w linii czwartej to element neutralny mnożenia macierzy.

Dlaczego to działa?
Otóż każdą liczbę da się zapisać w systemie dwójkowym. Robimy to w sposób będący rozwiązaniem zadania A z zeszłego roku: jeżeli liczba jest parzysta, piszemy 0, dzielimy ją przez dwa i wywołujemy się rekurencyjnie, jeżeli nieparzysta, piszemy jeden i dalej j.w.
W tym algorytmie "zapisujemy binarnie" wykładnik potęgi. Jeżeli jest on parzysty, to korzystamy z równości $x^{2n}=(x^{n})^{2}$ i jako podstawę traktujemy kwadrat, jeżeli jest nieparzysta, to jako że $x^{2n +1} = x \cdot x^{2n}$, domnażamy sobie brakujący x i dalej jak wyżej. Sądzę, że bardziej elementarnego wytłumaczenia nie potrzeba. A i trudno byłoby wymyśleć, żeby nie zagmatwać.

Ile ten algorytm wykona mnożeń?
Każde wywołanie rekurencyjne wykona jedno mnożenie w linii 5. i ewentualnie drugie w linii 9, w jednym wypadku (kiedy wykładnik będzie zerowy), nie wykona ich w ogóle, w każdym razie wykona ich zawsze $O(1)$. Rekurencyjnie wywołujemy się zawsze z wykładnikiem zmniejszonym dwukrotnie. A wszyscy wiemy, że dwukrotnie liczbę zmniejszać możemy co najwyżej tyle razy, ile wynosi z niej logarytm (to wynika z definicji logarytmu dwójkowego). Ponadto, złożoność funkcji "pomnoz" to $O(n^{3}$ (uzasadnienie: patrz wyżej), gdzie n - liczba wierszy potęgowanej macierzy. Stąd, jeżeli wykładnik oznaczymy jako k, otrzymamy złożoność:

(10)
\begin{align} O(1) \ \cdot \ O(\log k) \ \cdot \ O(n^{3})\ = \ O(n^{3}\log k) \end{align}

Trochę dziwna złożoność, ale bywają dziwniejsze.

Macierz przekształcenia liniowego

Przechodzimy do pierwszego z zastosowań macierzy. Weźmy na przykład ciąg Fibbonacciego, określony wzorem:

(11)
\begin{align} f_{0}=0,\ f_{1}=1,\quad f_{n}=f_{n-1}+f_{n-2}\ dla\ n>1 \end{align}

Naiwny algorytm:

f(n)
{
    if(n<=2) return 1;
    return f(n-1)+f(n-2);
}

Ma złożoność pamięciową $O(n)$, czyli zdecydowanie za dużo jak na takie małe… coś. Powstaje pytanie, czy rzeczywiście musimy pamiętać wszystkie wartości tego ciągu aż do jedynek, skoro potrzebujemy za każdym razem tylko dwóch ostatnich. I tu właśnie w sukurs przychodzą macierze, a konkretniej macierz:

(12)
\begin{align} M = \begin{bmatrix} 1\ 1\\ 1\ 0\\ \end{bmatrix} \end{align}

Popatrzmy, co stanie się, jeżeli pomnożymy ją przez wektor zawierający dwa pierwsze wyrazy ciągu Fibbonacciego:

(13)
\begin{align} M' = \begin{bmatrix} 1\ 1\\ 1\ 0\\ \end{bmatrix} \ \cdot \ \begin{bmatrix} 1\\ 0\\ \end{bmatrix} = \begin{bmatrix} 1\\ 1\\ \end{bmatrix} \end{align}

Otrzymaliśmy wyraz drugi i pierwszy w miejsce pierwszego i zerowego. Istotnie:

(14)
\begin{align} M'' = \begin{bmatrix} 1\ 1\\ 1\ 0\\ \end{bmatrix} \ \cdot \ \begin{bmatrix} f_{n}\\ f_{n-1}\\ \end{bmatrix} = \begin{bmatrix} f_{n}+f_{n-1}\\ f_{n}\\ \end{bmatrix} = \begin{bmatrix} f_{n+1}\\ f_{n}\\ \end{bmatrix} \end{align}

Teraz więc, nasza rekurencja przedstawiać się będzie następująco:

(15)
\begin{align} \begin{bmatrix} f_{n+1}\\ f_{n}\\ \end{bmatrix} = \underbrace{ \begin{bmatrix} 1\ 1\\ 1\ 0\\ \end{bmatrix} \bigg( \begin{bmatrix} 1\ 1\\ 1\ 0\\ \end{bmatrix} \bigg( \dots \bigg( \begin{bmatrix} 1\ 1\\ 1\ 0\\ \end{bmatrix}}_{n} \cdot \begin{bmatrix} f_{1}\\ f_{0}\\ \end{bmatrix} \bigg) \dots \bigg) \bigg) \end{align}

Ale przecież mnożenie macierzy jest łączne, więc:

(16)
\begin{bmatrix} f_{n+1}\\ f_{n}\\ \end{bmatrix} = \begin{bmatrix} 1\ 1\\ 1\ 0\\ \end{bmatrix}^{n} \cdot \begin{bmatrix} f_{1}\\ f_{0}\\ \end{bmatrix}

Wystarczy więc podnieść macierz $2 \times 2$ do potęgi n-tej, co daje złożoność pamięciową $O(\log n)$, bo tyle będzie wywołań rekurencyjnych w algorytmie szybkiego potęgowania, zaś pisząc wersję nierekurencyjną zbilibyśmy ją do stałej (!).

Nie to jednak powinno nam umysły teraz zaprzątać, jako że każdy porządny matematyk zastanowi się, jak wygenerować jakikolwiek ciąg, nie tylko Fibbonacciego. Na razie rozpatrzmy ciągi, których wyrazy potrzebują tylko dwóch poprzednich, aby zostały wygenerowane. Dlatego też chcemy przy generowaniu n-tego wyrazu zapamiętywać (n-1)-szy, podobnie jak przed chwilą.
Jak każdy z nas podejrzewa, sekret tkwi w zmianie współczynników macierzy M. Wstawmy więc tam ogólne wartości:

(17)
\begin{bmatrix} m_{11}\ m_{12}\\ m_{21}\ m_{22}\\ \end{bmatrix} \ \cdot \ \begin{bmatrix} a_{1}\\ a_{0}\\ \end{bmatrix} = \begin{bmatrix} m_{11}a_{1}+m_{12}a_{0}\\ m_{21}a_{1}+m_{22}a_{0}\\ \end{bmatrix}

Chcemy, podobnie jak wcześniej, w drugim wierszu wektora zapamiętać jedynie wyraz $a_{1}$, stąd $m_{21}=1$ oraz $m_{22}=0$. W pierwszym wierszu wektora chcemy uzyskać wyraz kolejny, a więc w pierwszym wierszu macierzy powinniśmy trzymać współczynniki wzoru rekurencyjnego tegoż ciągu (w przypadku ciągu Fibbonacciego współczynniki te wynosiły oczywiście 1 oraz 1).
Skoro już mniej więcej wiemy jak, przejdźmy do n-wyrazowego wzoru rekurencyjnego. Weźmy ciąg $a_{k}$ zadany wzorem:

(18)
\begin{align} a_{k+1} = \sum_{i=1}^{n}\alpha_{i}a_{i} \end{align}

Gdzie dla każdego $i \in \{ 0,1, \dots , n-1 \}$ $a_{i}$ jest dane, a $\alpha_{i}$ jest jakimś stałym współczynnikiem.

Czyli aby otrzymać kolejny wyraz tego ciągu, dodajemy do siebie n poprzednich wyrazów, każdy pomnożony przez odpowiednią stałą w zależności od kolejności - ten o najmniejszym indeksie mnożony jest przez $\alpha_{1}$, drugi przez $\alpha_{2}$ itd.

W takim wypadku w naszym wektorze wypiszemy po prostu dane wartości ciągu (od dołu do góry, tj. ten o najmniejszym indeksie będzie na dole), a w macierzy: w pierwszym wierszu współczynniki (od prawej do lewej), a w kolejnych wierszach w odpowiednich miejscach zera i jedynki.

(19)
\begin{align} M= \begin{bmatrix} \alpha_{n}\ \alpha_{n-1}\ \cdots \ \alpha_{2}\ \alpha_{1}\\ 1\ 0\ \cdots \ 0 \ 0 \\ 0\ 1\ \cdots \ 0 \ 0 \\ \vdots\ \vdots\ \ddots\ \vdots\ \vdots \\ 0\ 0\ \cdots \ 1 \ 0 \end{bmatrix} \end{align}

Nie ma wiersza z jedynką na końcu, bo ostatni wyraz chcemy właśnie zapomnieć, utrzymując stały rozmiar wektora.

Dlaczego to działa?
Ano działa to dlatego właśnie, że aby otrzymać 1,1-ty element macierzy będącej iloczynem jakichś dwóch, to mnożymy skalarnie pierwszy wiersz pierwszej z pierwszą kolumną drugiej, czyli tutaj współczynniki przez wyrazy w taki właśnie sposób, w jaki każe nam to robić wzór rekurencyjny, który w swojej ogólnej postaci jest właśnie wzorem na taki iloczyn skalarny. Kolejne wyrazy otrzymujemy jeszcze prościej - po prostu nie zeruje się tylko ten wyraz ciągu, który stoi (w wektorze) w wierszu o takim numerze, jaki numer ma kolumna z jedynką. A że jedynki są w n-1 kolumnach, to zapamiętamy n-1 wyrazów w n-1 ostatnich wierszach nowego wektora. Proste?

No chyba tak, zobaczmy:
Istotnie:

(20)
\begin{align} M\ \cdot \ \begin{bmatrix} a_{n} \\ a_{n-1} \\ \vdots \\ a_{1} \\ \end{bmatrix} = \begin{bmatrix} \sum_{i=1}^{n}\alpha_{i}a_{i} \\ a_{n} \\ \vdots \\ a_{2} \\ \end{bmatrix} = \begin{bmatrix} a_{n+1} \\ a_{n} \\ \vdots \\ a_{2} \end{bmatrix} \end{align}

Dalej postąpmy tak, jak z ciągiem Fibbonacciego - po prostu domnażajmy lewostronnie macierz M, powiedzmy, m razy. Następnie, korzystając z łączności mnożenia macierzy wszystkie te mnożenia zamieńmy na potęgowanie. W ten sposób dochodzimy do zawsze prawdziwego twierdzenia, iż:

Dla każdego ciągu określonego wzorem rekurencyjnym:$a_{k+1} = \sum_{i=1}^{n}\alpha_{i}a_{(k+i)-n}$ zachodzi:

(21)
\begin{bmatrix} \alpha_{n}\ \alpha_{n-1}\ \cdots \ \alpha_{2}\ \alpha_{1}\\ 1\ 0\ \cdots \ 0 \ 0 \\ 0\ 1\ \cdots \ 0 \ 0 \\ \vdots\ \vdots\ \ddots\ \vdots\ \vdots \\ 0\ 0\ \cdots \ 1 \ 0 \end{bmatrix}^{m}\ \cdot \ \begin{bmatrix} a_{n} \\ a_{n-1} \\ \vdots \\ a_{1} \end{bmatrix} \ = \ \begin{bmatrix} a_{n+m} \\ a_{n-1+m} \\ \vdots \\ a_{1+m} \end{bmatrix}

Powyższy wzorek jest bardzo przydatny, widzieliśmy jedno z jego rozlicznych zastosowań.

Macierz sąsiedztwa (incydencji) grafu

Czyli to, co misie lubią najbardziej. Przypomnijmy:

Macierzą sąsiedztwa grafu nazywamy taką macierz A, gdzie każdy jej element aij jest liczbą krawędzi z i-tego do j-tego wierzchołka grafu

Mówię "liczba ścieżek", bo rozważać będziemy też multigrafy, czyli takie grafy, w których pomiędzy dwoma wierzchołkami jest więcej niż jedna ścieżka.
Od razu z tej definicji nasuwa się wniosek, że jeżeli na przekątnej tej macierzy wstawimy zera, to idąc ścieżką długości n pokonamy dokładnie n krawędzi. Jeżeli zaś wstawimy jedynki, to idąc taką ścieżką będziemy mogli "krok" poświęcić na "stanie" w wierzchołku (bo dla każdego i istnieć będzie krawędź (i,i)), czyli w efekcie przejdziemy nie więcej niż n krawędzi bo zamiast "stania" czyli "pójścia" "pętlą", mogliśmy iść po prostu dalej, czyniąc tym samym mniej kroków.
Zauważmy jeszcze, że "krawędź" to po prostu ścieżka długości 1.

A teraz wykorzystajmy naszą wiedzę i podnieśmy macierz sąsiedztwa grafu:

(22)
\begin{align} M= \begin{bmatrix} a_{11}\ a_{12}\ \cdots \ a_{1n}\\ a_{21}\ a_{22}\ \cdots \ a_{2n}\\ \vdots\ \vdots\ \ddots\ \vdots \\ a_{n1}\ a_{n2}\ \cdots \ a_{nn}\\ \end{bmatrix} \quad \end{align}

do kwadratu, wedle definicji. Aby otrzymać i,j-ty element wyniku, musimy dodać do siebie:

  • $a_{i1}a_{1j}$ - czyli ilość ścieżek długości 1 z "i" do "1" razy ilość ścieżek długości 1 z "1" do "j", czyli ilość ścieżek długości 2 z "i" do "j" przez "1"
  • $a_{i2}a_{2j}$ - czyli ilość ścieżek długości 1 z "i" do "2" razy ilość ścieżek długości 1 z "2" do "j", czyli ilość ścieżek długości 2 z "i" do "j" przez "2"

$\vdots$

  • $a_{in}a_{nj}$ - czyli ilość ścieżek długości 1 z "i" do "n" razy ilość ścieżek długości 1 z "1" do "j", czyli ilość ścieżek długości 2 z "i" do "j" przez "n"

Czyli w sumie będzie to ilość wszystkich ścieżek długości 2 z "i" do "j", i to dla wszystkich i,j należących do grafu.

A teraz pomnóżmy uzyskaną macierz (niech się jej elementy nazywają bij) jeszcze raz przez macierz sąsiedztwa. I znowu, żeby otrzymać i,j-ty element wyniku, musimy dodać do siebie:

  • $b_{i1}a_{1j}$ - czyli ilość ścieżek długości 2 z "i" do "1" razy ilość ścieżek długości 1 z "1" do "j", czyli ilość ścieżek długości 3 z "i" do "j" przez "1"
  • $b_{i2}a_{2j}$ - czyli ilość ścieżek długości 2 z "i" do "2" razy ilość ścieżek długości 1 z "2" do "j", czyli ilość ścieżek długości 3 z "i" do "j" przez "2"

$\vdots$

  • $b_{in}a_{nj}$ - czyli ilość ścieżek długości 2 z "i" do "n" razy ilość ścieżek długości 1 z "1" do "j", czyli ilość ścieżek długości 3 z "i" do "j" przez "n"

Uzyskaliśmy więc macierz zawierającą ilości ścieżek długości 3. Jak łatwo się spodziewać, możemy tak robić ile dusza zapragnie, a jako że chyba za wiele nie pragnie (bo już zaczyna to być nudne), sformułujmy twierdzenie:

Jeżeli macierz A jest macierzą sąsiedztwa grafu G, to element bij macierzy B=An jest równy ilości ścieżek długości n z wierzchołka i do wierzchołka j w grafie G.

Oczywiście pod nazwą "ilość ścieżek długości n" kryje się:

  • ilość ścieżek długości dokładnie n, jeżeli na przekątnej macierzy A są zera
  • ilość ścieżek długości niewiększej niż n, jeżeli na przekątnej macierzy A są jedynki

Co jest oczywistym wnioskiem z przytoczonego wcześniej wniosku (o fe, pleonazm) z definicji macierzy sąsiedztwa.

I to by było na tyle, bo mam już serdecznie dość tej pisaniny ;) Mam nadzieję, że coś z tego zapamiętacie…

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License