Cuthill–McKee-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.

• 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.

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.