Algoritmul Cuthill-Mackey

Algoritmul Cuthill- McKee este un algoritm de reducere a lățimii benzii matrici simetrice Numit după dezvoltatori - Elizabeth Cuthill și James McKee.

Reverse Cuthill-McKee ( RCM , reverse Cuthill-McKee ) este același algoritm cu numerotare inversă a indexului.

Algoritm

Matricea simetrică originală este tratată ca matricea de adiacență a graficului . Algoritmul Cuthill-McKee renumerotează vârfurile graficului în așa fel încât, ca urmare a permutării corespunzătoare a coloanelor și rândurilor matricei originale, lățimea benzii sale este redusă . $n\ ori n$ $(V,E)$

Algoritmul construiește un set ordonat de vârfuri reprezentând noua enumerare a vârfurilor. Pentru un graf conectat , algoritmul arată astfel: $R$

selectați un vârf periferic (sau un vârf pseudo-periferic ) pentru valoarea inițială a tuplului ; $v$ $R:=(v)$
pentru , cât timp condiția este îndeplinită , efectuați pașii 3-5: $i=1,2,...$ $|R|<n$
construiți un set de adiacență pentru , unde este a --a componentă a lui și excludeți vârfurile care sunt deja conținute în , adică: ; $\operatorname {Adj} (R_{i})$ $R_i$ $R_i$ $i$ $R$ $R$ $A_{i}:=\operatorname {Adj} (R_{i})\setminus R$
sortați în ordine crescătoare a gradelor de vârf ; $A_{i}$
adăugați la rezultat tuplu . $A_{i}$ $R$

Cu alte cuvinte, algoritmul enumeră nodurile într-o căutare pe lățimea întâi , în care vârfurile adiacente sunt parcurse în ordinea crescătoare a puterilor lor .

Pentru un graf deconectat, algoritmul poate fi aplicat separat fiecărei componente conectate [1] .

Complexitatea de calcul în timp a algoritmului RCM cu condiția ca sortarea prin inserție să fie utilizată pentru ordonare , , unde este gradul maxim al unui vârf, este numărul de muchii ale graficului [2] . $O(m|E|)$ $m$ $|E|$

Alegerea vârfului de pornire

Pentru a obține rezultate bune, trebuie să găsiți vârful periferic al graficului . Această sarcină este în general destul de dificilă, prin urmare, în loc de ea, de obicei caută un vârf pseudo-periferic folosind una dintre modificările algoritmului euristic al lui Gibbs și colab. $(V,E)$

Pentru a descrie algoritmul, este introdus conceptul unei structuri de nivel înrădăcinat . Pentru un punct dat , structura de nivel înrădăcinată la va fi o partiție a setului de vârfuri : $v$ $v$ $\mathcal{L}$ $V$

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

unde subseturile sunt definite după cum urmează: $L_{i}(v)$

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

L_{1}(v)=\operatorname {Adj} (L_{0}(v))

și

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

Algoritm pentru găsirea unui vârf pseudo-periferic [3] :

selectați un vârf arbitrar din ; $r$ $V$
construiți o structură de nivel pentru rădăcină : ; $r$ ${\mathcal {L}}(r)=\{L_{0}(r),L_{1}(r),\dots,L_{l(r)}(r)\}$
selectați vârful cu gradul minim din ; $v$ $L_{l(r)}(r)$
construiți o structură de nivel pentru rădăcină : ; $v$ ${\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots,L_{l(v)}(v)\}$
dacă , atunci atribuiți și treceți la pasul 3; $l(v)>l(r)$ $r:=v$
vârful este vârful pseudo-periferic dorit. $v$

Note

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

Literatură

E. Cuthill și J. McKee. Reducerea lățimii de bandă a matricelor simetrice rare În Proc. 24 Nat. Conf. ACM , paginile 157-172, 1969.
George A., Liu J. Computer Solution of Large Sparse Positive Definite Systems. — M .: Mir, 1984. — 333 p.

Link -uri

Documentarea algoritmului Cuthill-McKee pentru bibliotecile Boost C++ .
Explicație detaliată a algoritmului Cuthill-McKee .
Explicație detaliată a algoritmului Cuthill-McKee (rusă) (link inaccesibil) .
Implementarea algoritmului Cuthill-McKee în Python (link indisponibil) .