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.