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]

Mátrix Cuthill–McKee-rendezése

Ugyanazon mátrix RCM-rendezése

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 ${\displaystyle R_{i}}$szinteket generál ${\displaystyle i=1,2,...}$-re, amíg az összes csomópont bejárásra nem kerül. Az ${\displaystyle R_{i+1}}$halmaz az ${\displaystyle R_{i}}$ halmazból jön létre, méghozzá az összes ${\displaystyle R_{i}}$${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 (${\displaystyle x}$), ami tulajdonképpen a legalacsonyabb fokú csúcs és beállítjuk ${\displaystyle R:=(\{x\})}$.

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

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

${\displaystyle 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

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.)
3. 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.