Cuthill-Mackey Algoritm

Cuthill - McKee - är en algoritm för reduktion av bandbredd för symmetriska matriser Uppkallad efter utvecklarna - Elizabeth Cuthill och James McKee.

Omvänd Cuthill-McKee ( RCM , omvänd Cuthill-McKee ) är samma algoritm med omvänd indexnumrering.

Algoritm

Den ursprungliga symmetriska matrisen behandlas som grafens närliggande matris . Cuthill-McKee-algoritmen numrerar om grafens hörn på ett sådant sätt att, som ett resultat av motsvarande permutation av kolumnerna och raderna i den ursprungliga matrisen, bredden på dess tejp reduceras . $n\ gånger n$ $(V, E)$

Algoritmen bygger en ordnad uppsättning av hörn som representerar den nya vertexuppräkningen. För en ansluten graf ser algoritmen ut så här: $R$

välj en perifer vertex (eller pseudo-perifer vertex ) för tupelns initiala värde ; $v$ $R:=(v)$
för , medan villkoret är uppfyllt , utför steg 3-5: $i=1,2,...$ $|R|<n$
bygga en närliggande uppsättning för , där är den -:e komponenten av , och exkludera hörn som redan finns i , det vill säga: ; $\operatorname {Adj} (R_{i})$ $R_i$ $R_i$ $i$ $R$ $R$ $A_{i}:=\operatörsnamn {Adj} (R_{i})\setminus R$
sortera i stigande ordning av vertexgrader ; $A_{i}$
lägg till resultatet tupel . $A_{i}$ $R$

Algoritmen räknar med andra ord upp hörnen i en bredd-först-sökning , där intilliggande hörn korsas i ökande ordning efter deras styrkor .

För en frånkopplad graf kan algoritmen tillämpas separat på varje ansluten komponent [1] .

Tidsberäkningskomplexiteten för RCM-algoritmen förutsatt att insättningssortering används för att beställa , , där är den maximala graden av en vertex, är antalet grafkanter [2] . $O(m|E|)$ $m$ $|E|$

Val av startpunkt

För att få bra resultat måste du hitta grafens perifera vertex . Denna uppgift är generellt sett ganska svår, därför letar de i stället för det vanligtvis efter ett pseudo-perifert vertex med hjälp av en av modifieringarna av den heuristiska algoritmen av Gibbs et al. $(V, E)$

För att beskriva algoritmen introduceras konceptet med en rotad nivåstruktur . För en given vertex kommer nivåstrukturen som är rotad till att vara en partition av uppsättningen av hörn : $v$ $v$ $\mathcal{L}$ $V$

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

där delmängder definieras enligt följande: $L_{i}(v)$

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

L_{1}(v)=\operatörsnamn {Adj} (L_{0}(v))

och

L_{i}(v)=\operatörsnamn {Adj} (L_{i-1}(v))-L_{i-2}(v),\qquad i=2,3,\dots ,l (v).

Algoritm för att hitta en pseudo-perifer vertex [3] :

välj en godtycklig vertex från ; $r$ $V$
bygga en nivåstruktur för roten : ; $r$ ${\mathcal {L}}(r)=\{L_{0}(r),L_{1}(r),\dots ,L_{l(r)}(r)\}$
välj vertex med minsta grad från ; $v$ $L_{l(r)}(r)$
bygga en nivåstruktur för roten : ; $v$ ${\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\}$
om , tilldela sedan och gå till steg 3; $l(v)>l(r)$ $r:=v$
vertexet är det önskade pseudo-perifera vertexet. $v$

Anteckningar

↑ George, Liu, 1984 , s. 65-66.
↑ George, Liu, 1984 , sid. 68.
↑ George, Liu, 1984 , s. 70-72.

Litteratur

E. Cuthill och J. McKee. Reducering av bandbredden för glesa symmetriska matriser I Proc. 24:e Nat. Konf. ACM , sid 157-172, 1969.
George A., Liu J. Datorlösning av stora glesa positiva bestämda system. — M .: Mir, 1984. — 333 sid.

Länkar

Dokumentation av Cuthill-McKee-algoritmen för Boost C++-biblioteken .
Detaljerad förklaring av Cuthill-McKee-algoritmen .
Detaljerad förklaring av Cuthill-McKee-algoritmen (ryska) (otillgänglig länk) .
Implementering av Cuthill-McKee-algoritmen i Python (inte tillgänglig länk) .