Množenje matrice susjedstva

Neka je zadan jednostavan graf i promatramo njegovu matricu susjedstva.

Prirodno je zapitati se što ćemo dobiti ako matricu susjedstva množimo s nekom drugom matricom, npr. sa samom sobom?

U matrici na mjestu piše ako možemo doći iz vrha u vrh .

Ako pomnožimo matricu susjedstva sa samom sobom , na mjestu pisat će:

Operator možemo koristiti budući da radimo nad nulama i jedinicama.

Odnosno riječima, u novoj matrici na mjestu , pisat će broj uspješnih prolazaka od vrha do vrha preko nekog trećeg vrha . Prolaz će biti uspješan ako postoji brid između i , te između i .

Primjetite da nova matrica neće sadržavati samo nule i jedinice već može sadržavati i druge prirodne brojeve. Kvadrirana matrica iz našeg primjera je:

Množenje na usmjerenom, netežinskom grafu

Sada možemo zamisliti originalnu matricu susjedstva na novi način, koji će još bolje moći objasniti množenje. Neka u matrici susjedstva na mjestu piše broj puteva od vrha do vrha duljine .

Kvadriranje te matrice sada zapisujemo općenito:

Pogledajmo što prebroji prvi član sume (): . Riječima je to broj putova duljine od vrha do vrha pomnoženo sa brojem putove duljine od vrha do vrha .

Taj umnožak je jednak broju putova duljine koji prolaze preko vrha . Ako zbrojimo ove vrijednosti za svaki , (a ne samo za ), dobivamo broj različitih putova duljine od vrha do vrha . Sigurni smo da nismo neki put brojali dvaput zbog toga što za svaki , vrh preko kojeg prelazimo u sredini puta je drugačiji.

Dakle, u zaključku, kvadriranje matrice susjedstva dati će broj puteva duljine u originalnom grafu.

U našem primjeru, vidljivo je da između vrhova i postoji točno puta duljine , dok između vrhova i postoji takav put, onaj koji prolazi preko vrha .

Dodatno moženje matrice susjedstva

Za sada smo opisali samo kvadriranje matrice susjedstva. Što je s općenitim potenciranjem?

Pretpostavimo da smo na neki način izračunali dvije matrice u kojima nam pišu broj putova duljine između svaka dva vrha te broj putova duljine između svaka dva vrha. Nazovimo te matrice i . Prikažimo množenje tih dviju matrica .

Fiksirajmo neki (slično kao što smo gore fiksirali ). Imamo umnožak . Prvi član predstavlja broj putova duljine od do , dok drugi član predstavlja broj putova duljine od do . Umnoškom ova dva člana dobivamo broj putova duljine od do koji na -tom mjestu imaju vrh . Ovi putovi su svi različiti jer su duljine prvog i drugog segmenta od kojih su spojeni fiksne.

Ako pozbrojimo ovaj umnožak za sve , dobiti ćemo ukupni broj putova duljine od do . Svi ovi putovi u sumaciji su različiti jer na -tom mjestu sadrže drugačije vrhove .

Zaključno, vrijedi da je .

Potenciranje matrice susjedstva

Kako bi izgledala ? To je matrica koja nam kaže broj putova duljine između neka dva vrha. Budući da u koraka možemo doći iz nekog vrha samo u njega samog (ostali smo tamo), ovo je jedinična matrica.

Za imamo originalnu matricu susjedstva.

možemo zapisati kao i indukcijom po dokazujemo da vrijedi .

Budući da je množenje matrica asocijativno, možemo iskoristiti brzo potenciranje.

Pronalazak svih najkraćih putova duljine

Ukoliko maknemo i netežinski uvjet za naš graf, matrica susjedstva pamti težinu brida između dva vrha. Ako brid između neka dva vrha ne postoji, smatramo da je težina brida . Neka je množenje matrica dano s:

Ukoliko implementiramo potenciranje s ovakvim množenjem, uz početnu matricu s nulama na glavnoj dijagonali i na ostalim mjestima, u konačnoj matrici na mjestu možemo očitati najkraći put koji prolazi kroz točno bridova.