imported>Fan-vom-Wiki: fehlendes Leerzeichen

2025-10-16T08:24:01Z

fehlendes Leerzeichen

Neue Seite

[[Datei:can 73 cm.pdf|miniatur|Cuthill-McKee-Sortierung derselben Matrix]]
[[Datei:can 73 rcm.pdf|miniatur|Umgekehrte Cuthill-McKee-Sortierung derselben Matrix]]

Der '''Cuthill-McKee-Algorithmus''' (benannt nach Elizabeth Cuthill und James<ref name="mckee">{{Webarchiv|url=http://calhoun.nps.edu/bitstream/handle/10945/30131/recommendationsf00fran.pdf |wayback=20210910184613 |text=''Recommendations for ship hull surface representation'' |archiv-bot=2024-11-20 20:18:07 InternetArchiveBot }}, page 6</ref> McKee) ist in der [[Numerische Mathematik|numerischen Mathematik]] ein [[Algorithmus]], der eine [[Symmetrische Matrix|symmetrische]] [[dünnbesetzte Matrix]] in eine [[Bandmatrix]] mit einer geringeren [[Bandmatrix|Bandbreite]] transformiert.<ref name="cm"> E. Cuthill and J. McKee. [http://portal.acm.org/citation.cfm?id=805928 ''Reducing the bandwidth of sparse symmetric matrices''] In Proc. 24th Nat. Conf. [[Association for Computing Machinery|ACM]], pages 157–172, 1969.</ref> Für Bandmatrizen existieren sehr effiziente Berechnungsalgorithmen, beispielsweise für die Lösung von sehr großen [[Lineares Gleichungssystem|linearen Gleichungssystemen]] (siehe [[BLAS]]).

Der '''umgekehrte Cuthill-McKee-Algorithmus''' von Alan George ist derselbe Algorithmus mit umgekehrter Indexreihenfolge. Im Allgemeinen führt der umgekehrte Algorithmus zu einem geringeren Fill-in, wenn eine [[Gaußsches Eliminationsverfahren|Gaußelimination]] durchgeführt wird. Unter „Fill-in“ versteht man das Entstehen von Nichtnull-Elementen an Positionen, die in der ursprünglichen Matrix mit Null besetzt sind.<ref name="gl"> J. A. George and J. W-H. Liu, Computer Solution of Large Sparse Positive Definite Systems, Prentice-Hall, 1981 </ref>

Der Cuthill-McKee-Algorithmus unterscheidet sich von der [[Breitensuche]] für [[Graphen]] durch seine Reihenfolge, die durch Nummerierung adjazenter Knoten anhand ihres Grades ermittelt wird.

== Algorithmus ==
Es sei <math>M\!</math> eine <math>n\times n</math> [[Adjazenzmatrix]], also eine [[symmetrische Matrix]], die als Einträge nur Nullen und Einsen besitzt. Der Cuthill-McKee-Algorithmus ist eine Umnummerierung der Knoten des durch die Adjazenzmatrix repräsentierten Graphen, um die Bandbreite der Adjazenzmatrix zu reduzieren. Der Algorithmus errechnet ein <math>n</math>-Tupel von Knoten, die die neue Reihenfolge darstellen, wie folgt:

*Man wähle einen Startknoten <math>x\!</math> und setze <math>R:=(x)\!</math>.

*Für <math>i=1,2,\dots</math> führe, solange <math>|R|<n</math> ist, folgende Schritte aus:

:* Konstruiere die Menge der adjazenten Knoten <math>A_i</math> von <math>R_i</math>, wobei <math>R_i</math> die <math>i</math>-te Komponente von <math>R</math> ist, und schließe alle Knoten aus, die schon in <math>R</math> enthalten sind: <math>A_i := \operatorname{Adj}(R_i) \setminus R</math>
:* Sortiere <math>A_i</math> nach steigendem [[Knotengrad]].
:* Hänge <math>A_i</math> an das Ergebnis-Tupel <math>R</math> an.

=== Wahl des Startknotens ===
Die Qualität der durch den Algorithmus bestimmten neuen Nummerierung bzw. [[Permutation]] hängt entscheidend von der Wahl des Startknotens ab. Da das Bandbreitenminimierungsproblem [[NP-Schwere|NP-schwer]] ist<ref>{{Literatur |Autor=Uriel Feige |Titel=Coping with the NP-Hardness of the Graph Bandwidth Problem |Sammelwerk=Algorithm Theory - SWAT 2000 |Band=1851 |Verlag=Springer Berlin Heidelberg |Ort=Berlin, Heidelberg |Datum=2000 |ISBN=978-3-540-67690-4 |DOI=10.1007/3-540-44985-x_2 |Seiten=10–19 |Online=http://link.springer.com/10.1007/3-540-44985-X_2 |Abruf=2020-03-23}}</ref>, fällt auch die Wahl eines optimalen Startknotens in diese [[Komplexitätsklasse]]. Stattdessen schlagen Cuthill und McKee vor, immer einen Knoten minimalen Grads zu wählen<ref name="cm" />, dies hat sich aber in der Praxis nicht bewährt. Alternativ ist auch die Wahl eines peripheren Knotens, also eines Knotens im [[Weg (Graphentheorie)#Länge und Abstand|Rand]] des Graphen, als Startknoten naheliegend. Das Bestimmen eines peripheren Knotens ist allerdings nur in quadratischer Laufzeit möglich, was den eigentlichen Algorithmus dominiert. Daher begnügt man sich in der Praxis damit einen '''pseudo-peripheren Knoten''' zu wählen, der auf folgende Weise ermittelt werden kann:

# Man wähle einen beliebigen Knoten <math>x \in X\!</math>.
# Man erzeuge die Schichtung <math>\{L_0(x),...,L_{\varepsilon(x)}(x)\}\!</math> mit der Wurzel <math>x\!</math>.
# Man wähle einen beliebigen Knoten minimalen Grades <math>r \in L_{\varepsilon(x)}(x)\!</math>.
# Man erzeuge die Schichtung <math>\{L_0(r),...,L_{\varepsilon(r)}(r)\}\!</math> mit der Wurzel <math>r\!</math>. Falls <math>\varepsilon(r) > \varepsilon(x)\!</math>, ersetze man <math>x\!</math> durch <math>r\!</math> und gehe nach 3.
# <math>r\!</math> ist ein pseudo-peripherer Knoten.

Als Exzentrizität <math>\varepsilon(x)\!</math> eines Knotens <math>x\!</math> eines zusammenhängenden Graphen bezeichnet man die Größe <math>\varepsilon(x):=\underset{y\in X}{\max} \text{ dist}(x, y) .\!</math>

== Anwendung ==
Der Algorithmus wird angewendet, um die [[Bandmatrix|Bandbreite]] von Matrizen zu reduzieren und damit zum Beispiel den Aufwand der [[Gaußsches Eliminationsverfahren|Gauß-Elimination]] bei der Lösung linearer Gleichungssysteme drastisch zu verringern.

== Weblinks ==
* [http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/cuthill_mckee_ordering.html Dokumentation des Cuthill–McKee-Algorithmus] für die [[Boost (C++-Bibliothek)|Boost C++-Bibliothek]] (englisch)
* [http://ciprian-zavoianu.blogspot.com/2009/01/project-bandwidth-reduction.html Beschreibung des Cuthill–McKee-Algorithmus] (englisch)
*[http://www.scielo.br/scielo.php?pid=S2179-84512019000300497&script=sci_arttext#DavisHu2011 Ein Vergleich der Qualität und Effizienz verschiedener Algorithmen zur Wahl eines pseudo-peripheren Knotens] (englisch)

== Einzelnachweise ==
<references />

[[Kategorie:Numerische Mathematik]]

Cuthill-McKee-Algorithmus - Versionsgeschichte

imported>Fan-vom-Wiki: fehlendes Leerzeichen