Gráfok kódolása szomszédsági mátrixszal és mátrixhatványozás

Alapkérdés: Adott egy egyszerű gráf. Döntsük el összefüggő-e.

Listás adatstruktúra esetén lineáris, azaz O(m+n) lépésszámú (n a gráf csúcsainak száma, m éleinek száma) algoritmus adható. (Lásd adatstruktúra tárgy gráf bejárási, keresési eljárásait.)
Szomszédsági mátrix esetén a mátrix hatványaiból kiolvasható az összefüggőségi probléma megoldása. A mátrixaritmetika egyszerűvé, transzparenssé teszi az algoritmusunkat.

Egy egyszerű gráf A_G szomszédsági mátrixának elemeit másképpen is értelmezhetjük. Egy u csúcs sorának és egy v csúcs oszlopának találkozásánál álló pozícióban az u-ból v-be vezető 1 hosszú séták száma áll. Ez az értelmezés első hallásra furcsa. A későbbiek azonban magyarázatot adnak erre az értelmezésre.

Definiálhatunk egy furcsa P_G mátrixot is. Ennek sorai és oszlopai is gráfunk csúcsaival vannak azonosítva. A P_G(u,v) elem az uv élen való átlépéssel megtett séta által alkotott halmaz, ha u és v szomszédos, illetve az üreshalmaz különben. Azaz P_G elemei halmazok. P_G már nem szimmetrikus mátrix. u és v szomszédossága esetén a P_G(u,v) elem és a P_G(v,u) elem is egy-egy egyelemű halmaz, de a két elem különböző iráyú séta. Az A_G mátrix ezen P_G mátrixot mossa el úgy, hogy a megfelelő elem helyén csak a P_G-ben szereplő halmaz elemszámát tünteti fel. ``A P_G-ben szereplő séták egyénisége eltűnik, egy statisztikában szereplő vonássá válnak.''

Mi lesz A_G², azaz a szomszédsági mátrix négyzetének egy eleme, mondjuk u sorának és v oszlopának talákozásánal álló A_G²(u,v) elem? A mátrix szorzás definíciója alapján (A_G² az A_G és A_G mátrixok szorzata) ez +{A_G(u,w)A_G(w,v): w a G gráf csúcsa}. Az összeg tagjai 0.0, 0.1, 1.0 és 1.1 szorzatok, azaz maguk is 0-k vagy 1-esek. Így összegük megegyezik az 1 tagok számával, ami azon w csúcsok száma, amelyekre A_G(u,w) és A_G(w,v) is 1, azaz u és w, illetve w és v is szomszédos. Az ilyen w-k természetes módon azonosíthatók a 2 hosszú uv séták számával. Azaz ``A_G² elemei a gráfban lévő 2 hosszú sétákat számolják meg''.

A P_G mátrixunkat is szorozhatjuk önamagával, ha jól állunk hozzá. P_G elemei sétahalmazok. Ha egy s és s' olyan, hogy s végpontja egybeesik s' kezdőpontjával, akkor szorzatukat definiálhatjuk mint azt a sétát, amit úgy kapunk, hogy s bejárása után s'-t is bejárjuk (ezt nevezhetjük konkatenációjuknak, habár a szavaknál megszokott fogalomtól eltérünk, a két sorozatot nem egyszerűen egymásután írjuk, az első sorozat utolsó elemét (s végpontját) és a második sorozat első elemét (s' kezdőpontját) azonosítjuk). Két sétahalmaz - S és S' - szorzata alatt egy S-beli és egy S'-beli séta szorzataként előálló séták halmazát értjük (feltéve, hogy a megfelelő sétaszorzatok értelmezettek). Két sétahalmaz S és S' összege alatt uniójukat értjük. Így ha két mátrix szorzatának definíciójára ránézünk, akkor az ott szereplő szorzat és összeg értelmet nyer akkor is, ha sétahalmazok az elemek. Ez alapján P_G.P_G értelmezhető. Elemei a megfelelő két csúcs közötti kettő hosszú séták Az A_G.A_G mátrix ezen P_G.P_G mátrixot mossa el úgy, hogy a megfelelő elem helyén csak a P_G.P_G-ben szereplő halmaz elemszámát tünteti fel. ``A P_G.P_G-ben szereplő séták egyénisége eltűnik, egy statisztikában szereplő vonássá válnak.''

Tovább is léphetünk. Mi lesz A_G³, azaz a szomszédsági mátrix köbének egy eleme, mondjuk u sorának és v oszlopának talákozásánal álló A_G³(u,v) elem? A mátrix szorzás definíciója alapján (A_G³ az A_G és A_G² mátrixok szorzata) ez +{A_G(u,w)A_G² (w,v): w a G gráf csúcsa}. Vegyük az u-ból v-be vezető három hosszú sétákat. Ezeket csoportosíthatjuk a séta második csúcsa szerint. Ha ez a csúcs w, akkor éppen A_G(u,w)A_G² darab sétánk van. Így A_G³ elemei az adott végpontú három hosszú séták számait adja meg.

P_G³ elemei az adott végpontú három hosszú sétahalmazok lesznek. A_G³ elemei ezeket a halmazokat mossák el csupán elemszámuk nyilvántartásával.

Általában P_G^k elemei az adott végpontú k hosszú sétahalmazok lesznek. A_G^k elemei ezeket a halmazokat mossák el csupán elemszámuk nyilvántartásával.

A fenti megjegyzés mellett egy gráfelméleti észrevételre lesz szükségünk az algoritmusunk tervezéséhez.

u és v egy gráf két különböző csúcsa. A következők ekvivalensek

u és v csúcs között van séta,
u és v csúcs között van út,
u és v csúcs között van legfeljebb |V|-1 hosszú út,
u és v csúcs között van legfeljebb |V|-1 hosszú séta,
u és v csúcs között van |V|-2 vagy |V|-1 hosszú séta.

Bizonyítás: Az egyetlen problémás lépéshez azt kell észrevennünk, hogy egy séta hossza a séta utolsó lépésének oda-vissza ismételgetésével tetszőleges páros számmal növelhető.

Az alapproblémára (Adott A_G. Döntsuk el G tetszőleges két különböző csúcs között van-e séta) a következő algoritmust adhatjuk:

Számoljuk ki A_G^|V|-2-t és A_G^|V|-1-t.
Adjuk össze A_G^|V|-2-t és A_G^|V|-1-t, azaz számoljuk ki E=A_G^|V|-2+A_G^|V|-1-t.
Ha E összes főátlón kívüli eleme pozitív/nem-nulla akkor G bármely két különböző csúcsa között van séta. Ha E főátlón kívüli elemei kööztt van 0, akkor az ezen pozíciónak megfelleő két csúcs között nincs séta.

A fenti magas szintű leírás nem ad egy programot. Egy konkrét program megírásához (implementációhoz) esetleg komoly ötletekre van szükség. Az első lépés is problémás. Hogyan számolható ki A_G^|V|-2 és A_G^|V|-1, azaz általában adott N-re A_G^N.

A helyes implementáció:

Adott A_G, számoljuk ki a A_G²,A_G⁴, A_G⁸, A_G¹⁶,A_G³²,..., azaz a kettőhatvány kitevős hatványokat. Mindegyik hatványhoz egyetlen négyzetreemelés (szorzás) szükséges, azaz sorozatunk N-nél nem nagyobb kitevős elemeit ~log₂2 N mátrixszorzással kiszámolhatjuk.
Írjuk fel N-et kettes számrendszerben, azaz írjuk fel N-et mint különböző kettőhatványok összege. Ennek a felírásnak megfelelően A_G^N-et felírhatjuk, mint bizonyos A_G^{2^K} mátrixok szorzata.
Az előbb felírt mátrixszorzatot számoljuk ki. Ismét maximum ~log₂2 N mátrixszorzást kell elvégeznünk.

Mi lett volna a naív implementáció? Hány szorzást használ az az algoritmus?

Egy további ötlet a gyakorlati programozónak. A_G^N séták számát tárolja. Ez nem kell nekünk. Mi csak a séta létezésére vagyunk kiváncsiak.

Vezessünk be egy B_G mátrixot, aminek elemei az A_G mátrixból kapjuk az 1-esek helyett `true ', a 0-k helyett `false ' Boole-értéket véve. Tehát a B_G mátrix a P_G mátrix elemeit ``mossa tovább'', csupán azt a minimumot hagyja meg, ami algoritmusunk számára szükséges. Ha ezek után Boole-aritmetikával (+ <- `vagy', .<- `és') számolunk, akkor éppen a szükséges információt kapjuk meg.

A Boole-aritmetikában való számolás gyorsabb mint a nagy egészekkel való számolás, a Boole-értékek jóval kisebb helyet foglalnak el a memóriában mint a nagy egészek.