Hedetniemen matriisisumma

Kaikkihan tietätävät että graafin solmujen välillä olevien $q$ -kävelyjen lukumäärät saadaan korottamalla graafin vierekkäisyysmatriisi potenssiin $q$ . Mutta entä jos matriisissa käytetään kaarien painotuksia ja matriisitulossa rivin ja sarakkeen pistetulon paikalla alkioiden summien minimiä? Tämä on Hedetniemen matriisisumma.

Määritelmä

Matriisien $A$ (kokoa $m\times n$ ) ja $B$ (kokoa $n\times p$ ) Hedetniemen summa $A \ddagger B$ on $m \times p$ -matriisi $C$ , jonka $(i, j)$ -alkio on

$\begin{aligned} c_{ij} = \min_{ k \in \{1, \dots, n\} } a_{ik}+b_{kj} \end{aligned}$

Huom. Sallimme matriisin alkioksi myös plus äärettömän $\infty$ . Määrittelemme $\infty + x = x + \infty = \infty$ ja $\min(\infty, x) = x$ kaikille luvuille $x$ ja myös tapauksessa $x = \infty$ .

Esimerkki

Hedetniemen summan alkion $(3, 4)$ muodostuminen korostettuna. Matriisi $A$ on alla esiintyvän graafin kaarien painomatriisi.

Hedetniemen summan alkion $(3, 4)$ muodostuminen korostettuna. Matriisi $A$ on alla esiintyvän graafin kaarien painomatriisi.

Mihin tätä summaa sitten käytetään? Sen avulla voidaan selvittää lyhyimmät reitit kaikkien solmuparien välillä graafissa, jonka kaarille on annettu ei-negatiiviset painokertoimet (etäisyydet). Muodostetaan graafille $G=(\{v_1, v_2 \dots, v_n\}, E)$ kaarien painomatriisi $A$ , jossa alkio $a_{ij}$ , $i \neq j$ on $v_i$ :n ja $v_j$ :n välisen kaaren paino tai $\infty$ , jos solmujen välillä ei ole kaarta. Diagonaalialkiot $a_{ii}$ asetetaan nollaksi, sillä solmusta itseensä on nollan askeleen reitti, jonka pituus (=sen käyttämien kaarien painojen summa) on nolla. Oletamme että graafi on yksinkertainen eli sillä ei ole kaaria solmusta itseensä eikä useampia kaaria kahden solmun välillä. Tämä on luonnollinen oletus kun haluamme selvittää lyhyimpiä reittejä, sillä luuppia solmusta itseensä ei kannata reitissä ikinä käyttää ja useammasta kaaresta solmujen välillä kannattaa aina valita se, jolla on pienin paino.

Kaaret ajatellaan suunnaatuiksi, mutta suuntaamattomassa tapauksessa ajatellaan, että kaari on kumpaankin suuntaan olemassa (samalla painolla). Suuntaamattomassa tapauksessa matriisi $A$ on siis symmetrinen.

Suuntaamaton graafi ja sen kaarien painomatriisi $A$ . Ensimmäinen rivi ja sarake ovat indeksejä.

Lasketaan matriisin $A$ iteroituja Hedetniemen summia $A, A^2, A^3, \dots$ . Merkitsemme siis $A^2 = A \ddagger A$ (tämä ei sotkeutune tavalliseen matriisituloon, jota ei tässä postauksessa esiinny). Iteraation $A^{t}$ alkio $a_{ij}^t$ kertoo lyhyimmän $t-1$ :n askeleen reitin pituuden solmusta $v_i$ solmuun $v_j$ . Koska graafi on äärellinen, käy jostakin $t$ :n arvosta $t_1$ lähtien niin, että $A^{t_1} = A^{t_1+1} = A^{t_1+2} = \dots$ eli jono stabiloituu. Ylläolevalle esimerkille

Hedetniemen matriisisumma-iteraatiot edellä olleen graafin kaarien painomatriisille. Jono stabiloituu arvosta $t_1 = 7$ lähtien. Kuten voidaan todeta, eniten askelia vievä lyhyin reitti (solmujen $2$ ja $5$ välillä) on 6 askelta: 2-0-1-3-4-6-5 ja sen pituus on $9 (=2+1+2+1+2+1)$ . Se käykin kaikki graafin solmut läpi, joten tämä on maksimitapaus.

Hedetniemen matriisisumma-iteraatiot edellä olleen graafin kaarien painomatriisille. Jono stabiloituu arvosta $t_1 = 7$ lähtien. Kuten voidaan todeta, eniten askelia vievä lyhyin reitti (solmujen $2$ ja $5$ välillä) on 6 askelta: 2-0-1-3-4-6-5 ja sen pituus on $9 (=2+1+2+1+2+1)$ . Se käykin kaikki graafin solmut läpi, joten tämä on maksimitapaus.

Reitin selvitys

Lyhyimmän reitin pituus on luettavissa matriisin $A^{t_1}$ alkiosta, mutta kuinka saamme tiedon mikä tuo reitti on? Se voidaan selvittää solmu kerrallaan lähtemällä päätepisteestä ja ratkaisemalla mikä sitä täytyy reitillä edeltää. Otetaan esimerkiksi edellä olleen graafin solmut $0$ ja $6$ . Matriisista $A^7$ nähdään, että lyhyimmän reitin pituus on $a_{60}^7 = 6$ . Tutkitaan nyt päätepisteen eli solmun $6$ naapureita ( $k= 4, \text{ ja } 5$ ). Se kummasta kutoseen on tultu, täytyy toteuttaa yhtälö, että lyhyin reitti nollasta siihen on $6 - a_{k6}$ . Koska solmusta $4$ tulee 2:n painoinen kaari ja lyhyin reitti nollasta solmuun $4$ on $A^7$ :n mukaan pituudeltaan 4, niin valitaan solmu $4$ . Jatketaan nyt solmusta $4$ ja etsitään sen edeltäjä. Näin jatketaan kunnes päästään alkupisteeseen ja reitti on selvitetty.

Reitin selvityksen kaksi ensimmäistä askelta. Loput menevät vastaavasti.

Huomioita

Jos matriisin jää äärettömyyksiä jonon stabiloiduttua, tarkoittaa se että graafi on epäyhtenäinen: jostain solmusta ei ole mitään reittiä johonkin toiseen solmuun.
Stabiloituminen vie korkeintaan $|V|-1$ askelta, sillä lyhyin reitti ei vieraile missään solmussa kuin korkeintaan kerran.
Pienempiä (ennen stabiloitumista) iterantteja voi käyttää askelten määrän ollessa rajoitettu, sillä ne tosiaan kertovat sen hetkisen lyhyimmän etäisyyden kun käytetään korkeintaan $t$ askelta. (Jos haluaisi käyttää tasan $t$ askelta sen voisi varmaan toteuttaa asettamalla diagonaalialkiot äärettömiksi, jolloin solmussa ei ole luvallista pysyä. ???)
Algoritmin kehittäjä on Stephen Hedetniemi. Lisätietoa historiasta Seuran artikkelissa. Hedetniemen nimissä on myös graafien tensoritulon väritykseen liittyvä konjektuuri, joka ratkesi aivan tässä viime aikoina kielteisesti eli siihen löytyi vastaesimerkki: Yaroslav Shitov, Counterexamples to Hedetniemi’s conjecture.

Ohjelmakoodit (Python)

INFTY = 2**56 #number larger than any other occuring one

def hedetniemiMatrixSum(a, b):
    m = len(a)
    n = len(b)
    p = len(b[0])
    return [[min(a[i][k] + b[k][j] for k in range(n))
             for j in range(p)]
            for i in range(m)]


def findStableHedetniemiSum(a):
    n = len(a)
    prev = a
    b = a
    counter = 0
    while counter<n:
        b = hedetniemiMatrixSum(b, a)
        if b == prev: break
        prev = b
    return b
    

def findPath(start, end, minDMat, a):
    """
       start: index of the start node
       end: index of the target node
       minDMat: the stabilized matrix
                containing the minimum paths lenghts
       a: the weighted adjacency matrix
    """
    n = len(a)
    path = [end]
    dist = minDMat[start][end]
    if dist>=INFTY: return None #no path exists
    curr = end
    def findPrev():
        for i in range(n):
            if i==curr: continue
            if dist-a[i][curr] == minDMat[start][i]: return i
    counter = 0
    while curr != start and counter<n:
        prev = findPrev()
        dist -= a[prev][curr]
        curr = prev
        path.append(curr)
    return path[::-1]

#the example matrix
a = [
    [0,1,2,INFTY,INFTY,8,INFTY],
    [1,0,4,2,INFTY,INFTY,INFTY],
    [2,4,0,INFTY,7,INFTY,INFTY],
    [INFTY,2,INFTY,0,1,INFTY,INFTY],
    [INFTY,INFTY,7,1,0,INFTY,2],
    [8,INFTY,INFTY,INFTY,INFTY,0,1],
    [INFTY,INFTY,INFTY,INFTY,2,1,0]
]
b = findStableHedetniemiSum(a)
print b
print findPath(0, 6, b, a)

Hedetniemen matriisisumma

Määritelmä

Esimerkki

Reitin selvitys

Huomioita

Ohjelmakoodit (Python)

Julkaissut membolic

Jätä kommentti Peruuta vastaus

Määritelmä

Esimerkki

Reitin selvitys

Huomioita

Ohjelmakoodit (Python)

Jaa:

Aiheeseen liittyy

Julkaissut membolic

Jätä kommentti Peruuta vastaus