Cuthill-Mackey algoritmus

A Cuthill -McKee algoritmus egy szalagszélesség - csökkentő algoritmus szimmetrikus mátrixokhoz A fejlesztők - Elizabeth Cuthill és James McKee - után nevezték el.

A Reverse Cuthill-McKee ( RCM , fordított Cuthill-McKee ) ugyanaz az algoritmus fordított indexszámozással.

Algoritmus

Az eredeti szimmetrikus mátrixot a gráf szomszédsági mátrixaként kezeljük . A Cuthill-McKee algoritmus átszámozza a gráf csúcsait oly módon, hogy az eredeti mátrix oszlopainak és sorainak megfelelő permutációja következtében a szalag szélessége csökken . $n\szer n$ $(V, E)$

Az algoritmus összeállítja az új csúcsok felsorolását reprezentáló csúcsok rendezett halmazát . Összekapcsolt gráf esetén az algoritmus így néz ki: $R$

válasszon egy perifériás csúcsot (vagy pszeudo-periférikus csúcsot ) a sor kezdeti értékéhez ; $v$ $R:=(v)$
- esetén , amíg a feltétel teljesül , hajtsa végre a 3-5. lépéseket: $i=1,2,...$ $|R|<n$
építsünk szomszédsági halmazt a -hoz , ahol a -edik összetevője , és zárja ki azokat a csúcsokat, amelyek már benne vannak a -ban , azaz: ; $\operatorname {Adj} (R_{i})$ $R_i$ $R_i$ $én$ $R$ $R$ $A_{i}:=\operátornév {Adj} (R_{i})\setminus R$
rendezés a csúcsfokozatok növekvő sorrendjében ; $A_{i}$
add hozzá az eredményhez . $A_{i}$ $R$

Más szavakkal, az algoritmus a csúcsokat egy szélesség-előszöri keresésben sorolja fel, amelyben a szomszédos csúcsokat hatványuk növekvő sorrendjében haladja meg .

Leválasztott gráf esetén az algoritmus minden kapcsolt komponensre külön-külön alkalmazható [1] .

Az RCM algoritmus időszámítási bonyolultsága, feltéve, hogy a rendezéshez beszúrásos rendezést használunk , ahol egy csúcs maximális foka, a gráf éleinek száma [2] . $O(m|E|)$ $m$ $|E|$

A kezdő csúcs kiválasztása

A jó eredmények eléréséhez meg kell találnia a gráf perifériás csúcsát . Ez a feladat általában meglehetősen nehéz, ezért ehelyett általában egy pszeudo-periférikus csúcsot keresnek Gibbs et al. heurisztikus algoritmusának valamelyik módosításával. $(V, E)$

Az algoritmus leírásához bemutatjuk a gyökeres szintű struktúra fogalmát . Egy adott csúcsra a következő helyen gyökerező szintstruktúra a csúcsok halmazának partíciója lesz : $v$ $v$ $\mathcal{L}$ $V$

{\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\},

ahol a részhalmazok meghatározása a következő: $L_{i}(v)$

L_{0}(v)=\{v\},

L_{1}(v)=\operátornév {Adj} (L_{0}(v))

és

L_{i}(v)=\operátornév {Adj} (L_{i-1}(v))-L_{i-2}(v),\qquad i=2,3,\dots ,l (v).

Algoritmus egy pszeudoperiférikus csúcs megtalálására [3] :

válasszon egy tetszőleges csúcsot a közül ; $r$ $V$
szintstruktúrát építsünk a gyökér számára : ; $r$ ${\mathcal {L}}(r)=\{L_{0}(r),L_{1}(r),\dots ,L_{l(r)}(r)\}$
válasszuk ki azt a csúcsot, amelynek minimális foka van -ból ; $v$ $L_{l(r)}(r)$
szintstruktúrát építsünk a gyökér számára : ; $v$ ${\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\}$
ha , akkor rendelje hozzá és folytassa a 3. lépéssel; $l(v)>l(r)$ $r:=v$
a csúcs a kívánt pszeudo-periférikus csúcs. $v$

Jegyzetek

↑ George, Liu, 1984 , pp. 65-66.
↑ George, Liu, 1984 , p. 68.
↑ George, Liu, 1984 , pp. 70-72.

Irodalom

E. Cuthill és J. McKee. Ritka szimmetrikus mátrixok sávszélességének csökkentése In Proc. 24. Nat. Konf. ACM , 157-172. oldal, 1969.
George A., Liu J. Computer Solution of Large Sparse Positive Definite Systems. — M .: Mir, 1984. — 333 p.

Linkek

A Boost C++ könyvtárak Cuthill-McKee algoritmusának dokumentációja .
A Cuthill-McKee algoritmus részletes magyarázata .
A Cuthill-McKee algoritmus részletes magyarázata (orosz) (elérhetetlen link) .
A Cuthill-McKee algoritmus megvalósítása Pythonban (nem elérhető hivatkozás) .