bélyegkép|Mátrix Cuthill–McKee-rendezése bélyegkép|Ugyanazon mátrix RCM-rendezése 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.E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157–172, 1969. 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. A gyakorlatban ez általában kevesebb kitöltést eredményez, mint a CM rendezés, amikor is Gauss-eliminációt alkalmaznak.J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981
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 szinteket generál -re, amíg az összes csomópont bejárásra nem kerül. Az halmaz az halmazból jön létre, méghozzá az összes -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 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 halmazát állítja elő, ami a csúcsok egy új rendezése.
Először kiválasztunk egy perifériás csúcsot (), ami tulajdonképpen a legalacsonyabb fokú csúcs és beállítjuk .
Majd -vel az alábbi lépéseket megismételjük, amíg .
Készítsük el szomszédsági halmazát ( az i-edik komponense) és zárjuk ki azokat a csúcsokat, amelyek már szerepelnek -ben.
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
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
Kategória:Gráfalgoritmusok Kategória:Lineáris algebra