Cuthill–McKee-algoritmus

A lineáris algebrában használják a Cuthill–McKee-algoritmust (CM), amely Elizabeth Cuthill és James McKee után kapta a nevét.^[1] Ez az algoritmus egy szimmetrikus mintával rendelkező ritka mátrixot egy kis sávszélességű sávmátrixba permutál. Az Alan George-nak köszönhető fordított Cuthill–McKee-algoritmus (RCM) ugyanez az algoritmus, de eredményül fordítva adja vissza az indexszámokat.^[2] A gyakorlatban ez általában kevesebb kitöltést eredményez, mint a CM rendezés, amikor is Gauss-eliminációt alkalmaznak.^[3]

A Cuthill–McKee-algoritmus a gráfkereső algoritmusok között használt standard szélességi keresés algoritmusának egy változata. Perifériás csomóponttal kezdődik, majd $R_{i}$ szinteket generál $i=1,2,...$ -re, amíg az összes csomópont bejárásra nem kerül. Az $R_{i+1}$ halmaz az $R_{i}$ halmazból jön létre, méghozzá az összes $R_{i}$ $R_{i}$ -beli csomópont szomszédságában lévő csúcsok növekvő sorrendben történő felsorolásával. Ez a részlet az egyetlen különbség a CM és a szélességi keresés algoritmusa között.

Algoritmus

Adott egy szimmetrikus $n\times n$ mátrix, amit a gráf szomszédsági mátrixaként jelenítünk meg. A Cuthill–McKee-algoritmus a gráf csúcsainak újracímkézése a szomszédsági mátrix sávszélességének csökkentése érdekében.

Az algoritmus rendezett n-es csúcsok $R$ halmazát állítja elő, ami a csúcsok egy új rendezése.

Először kiválasztunk egy perifériás csúcsot ( $x$ ), ami tulajdonképpen a legalacsonyabb fokú csúcs és beállítjuk $R:=(\{x\})$ .

Majd $i=1,2,\dots$ -vel az alábbi lépéseket megismételjük, amíg $|R|<n$ .

Készítsük el $Ri$ szomszédsági halmazát ( $Ri$ az $R$ i-edik komponense) és zárjuk ki azokat a csúcsokat, amelyek már szerepelnek $R$ -ben.

A_{i}:=\operatorname {Adj} (R_{i})\setminus R

Rendezzük csúcsait növekvő sorrendbe (csúcsfok).
Majd fűzzük azt az eredményhalmazhoz.

Más szóval, számozzuk a csúcsokat egy konkrét szélességi gráfbejárás szerint, ahol a szomszédos csúcsokat növekvő sorrendben járjuk be.

Jegyzetek

↑ E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.
↑ Ciprian: Ciprian Zavoianu - weblog: Tutorial: Bandwidth reduction - The CutHill-McKee Algorithm. Ciprian Zavoianu - weblog, 2009. január 15. (Hozzáférés: 2020. május 11.)
↑ J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981

Irodalom

Cuthill – McKee dokumentáció a Boost C ++ könyvtárakhoz .
A Cuthill – McKee algoritmus részletes leírása .
symrcm a MATLAB RCM megvalósítása.
reverse_cuthill_mckee RCM rutin SciPyból Cythonban megírva.

Fordítás

Ez a szócikk részben vagy egészben a Cuthill–McKee algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

[cm-1] E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969.

[2] Ciprian: Ciprian Zavoianu - weblog: Tutorial: Bandwidth reduction - The CutHill-McKee Algorithm. Ciprian Zavoianu - weblog, 2009. január 15. (Hozzáférés: 2020. május 11.)

[gl-3] J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981

[1]

[2]

[3]