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:
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 .
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 .
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.
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.
Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License