Graphpartitionierung - Versionsgeschichte

JoKa1979: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-05-16T19:49:23Z

Linkvorschlag-Funktion: 2 Links hinzugefügt.

← Nächstältere Version		Version vom 16. Mai 2025, 21:49 Uhr
Zeile 44:		Zeile 44:
	Dieses Verfahren kann in allen der im Folgenden erwähnten Algorithmen angewendet werden. Es verfolgt das verbreitete [[Teile-und-herrsche-Verfahren\|Divide-and-conquer]]-Prinzip und besteht darin, dass der Graph nur in 2 Teilmengen zerlegt wird. Die entstehenden Teilgraphen werden dann rekursiv wieder zweigeteilt, bis die gewünschte Anzahl ''k'' von Teilmengen erreicht ist. Diese Zahl muss somit eine Zweierpotenz sein, d. h. <math>k = 2^t</math> für ein <math>t \in \{1,2,3,...\}</math> (= Rekursionstiefe). Das ist in der Praxis in der Tat oft der Fall, z. B. in einem Parallelrechner, der <math>2^t</math> Prozessoren enthält.		Dieses Verfahren kann in allen der im Folgenden erwähnten Algorithmen angewendet werden. Es verfolgt das verbreitete [[Teile-und-herrsche-Verfahren\|Divide-and-conquer]]-Prinzip und besteht darin, dass der Graph nur in 2 Teilmengen zerlegt wird. Die entstehenden Teilgraphen werden dann rekursiv wieder zweigeteilt, bis die gewünschte Anzahl ''k'' von Teilmengen erreicht ist. Diese Zahl muss somit eine Zweierpotenz sein, d. h. <math>k = 2^t</math> für ein <math>t \in \{1,2,3,...\}</math> (= Rekursionstiefe). Das ist in der Praxis in der Tat oft der Fall, z. B. in einem Parallelrechner, der <math>2^t</math> Prozessoren enthält.

	Durch Anwendung von rekursiver Bisektion nimmt man eine suboptimale Lösung in Kauf, um einen großen zeitlichen Gewinn zu erzielen.		Durch Anwendung von rekursiver [[Bisektion]] nimmt man eine suboptimale Lösung in Kauf, um einen großen zeitlichen Gewinn zu erzielen.

	=== Geometrische Algorithmen ===		=== Geometrische Algorithmen ===
Zeile 51:		Zeile 51:
	Beispiele für geometrische Algorithmen:		Beispiele für geometrische Algorithmen:
	* [[Koordinatenbisektion]]: Wähle die Koordinate (z. B. x), in welcher die Knoten am weitesten voneinander entfernt sind, und für diese einen Grenzwert c so, dass für die Hälfte der Knoten (x > c) gilt.		* [[Koordinatenbisektion]]: Wähle die Koordinate (z. B. x), in welcher die Knoten am weitesten voneinander entfernt sind, und für diese einen Grenzwert c so, dass für die Hälfte der Knoten (x > c) gilt.
	* [[Inertialbisektion]]: Berechne die Inertialachse und wähle diese anstelle einer Koordinatenachse.		* [[Inertialbisektion]]: Berechne die Inertialachse und wähle diese anstelle einer [[Koordinatenachse]].

	=== Spektrale Bisektion ===		=== Spektrale Bisektion ===

Graf Alge: /* Rekursive Bisektion */ Links korrigiert

2025-04-06T19:19:36Z

Rekursive Bisektion: Links korrigiert

← Nächstältere Version		Version vom 6. April 2025, 21:19 Uhr
Zeile 42:		Zeile 42:

	=== Rekursive Bisektion ===		=== Rekursive Bisektion ===
	Dieses Verfahren kann in allen der im Folgenden erwähnten Algorithmen angewendet werden. Es verfolgt das verbreitete [[~~Divide and conquer~~\|Divide-and-conquer]]-Prinzip und besteht darin, dass der Graph nur in 2 Teilmengen ~~[[Schnitt (Graphentheorie)\|geschnitten]]~~ wird. Die entstehenden Teilgraphen werden dann rekursiv wieder zweigeteilt, bis die gewünschte Anzahl ''k'' von Teilmengen erreicht ist. Diese Zahl muss somit eine Zweierpotenz sein, d. h. <math>k = 2 ^ t</math> für ein <math>t \in \{1,2,3,...\}</math> (= Rekursionstiefe). Das ist in der Praxis in der Tat oft der Fall, z. B. in einem Parallelrechner, der <math>2 ^t</math> Prozessoren enthält.		Dieses Verfahren kann in allen der im Folgenden erwähnten Algorithmen angewendet werden. Es verfolgt das verbreitete [[Teile-und-herrsche-Verfahren\|Divide-and-conquer]]-Prinzip und besteht darin, dass der Graph nur in 2 Teilmengen zerlegt wird. Die entstehenden Teilgraphen werden dann rekursiv wieder zweigeteilt, bis die gewünschte Anzahl ''k'' von Teilmengen erreicht ist. Diese Zahl muss somit eine Zweierpotenz sein, d. h. <math>k = 2^t</math> für ein <math>t \in \{1,2,3,...\}</math> (= Rekursionstiefe). Das ist in der Praxis in der Tat oft der Fall, z. B. in einem Parallelrechner, der <math>2^t</math> Prozessoren enthält.

	Durch Anwendung von rekursiver Bisektion nimmt man eine suboptimale Lösung in Kauf, um einen großen zeitlichen Gewinn zu erzielen.		Durch Anwendung von rekursiver Bisektion nimmt man eine suboptimale Lösung in Kauf, um einen großen zeitlichen Gewinn zu erzielen.

Graf Alge: /* Formulierung des Problems */ falschen Grundbegriff korrigiert - gleichartige Objekte können adjazent sein, eine Kanten ist inzident zu ihren Endknoten

2025-04-06T19:12:55Z

Formulierung des Problems: falschen Grundbegriff korrigiert - gleichartige Objekte können adjazent sein, eine Kanten ist inzident zu ihren Endknoten

← Nächstältere Version		Version vom 6. April 2025, 21:12 Uhr
Zeile 25:		Zeile 25:
	# Möglichst wenig Kanten Knoten aus zwei verschiedenen Teilmengen verbinden.		# Möglichst wenig Kanten Knoten aus zwei verschiedenen Teilmengen verbinden.

	Kanten, deren ~~[[Adjazenz (Graphentheorie)\|adjazente]]~~ Knoten in unterschiedlichen Teilmengen liegen, werden durch die Partition geschnitten und deshalb als ''Schnittkanten'' bezeichnet.		Kanten, deren inzidente Knoten in unterschiedlichen Teilmengen liegen, werden durch die Partition geschnitten und deshalb als ''Schnittkanten'' bezeichnet.

	==== Gewichtete Graphen ====		==== Gewichtete Graphen ====

Graf Alge: Der Graph wird zwar in 2 Teile geteilt, aber er ist nicht bipartit!

2025-04-06T19:09:23Z

Der Graph wird zwar in 2 Teile geteilt, aber er ist nicht bipartit!

← Nächstältere Version		Version vom 6. April 2025, 21:09 Uhr
Zeile 1:		Zeile 1:
	{{QS-Informatik\|Knacknüsse=Ja\|allgemeinverständlichkeit --[[Benutzer:Verum\|'''V''']] [[Benutzer Diskussion:Verum\|'''¿ ''']] 22:37, 6. Aug. 2013 (CEST)}}		{{QS-Informatik\|Knacknüsse=Ja\|allgemeinverständlichkeit --[[Benutzer:Verum\|'''V''']] [[Benutzer Diskussion:Verum\|'''¿ ''']] 22:37, 6. Aug. 2013 (CEST)}}

	[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph ~~(2-partit)~~]]		[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph]]

	'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 \|ISBN=3-540-21391-0 \|Seiten=18}}</ref>		'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 \|ISBN=3-540-21391-0 \|Seiten=18}}</ref>

Graf Alge: Änderung 254909079 von Quiorm rückgängig gemacht; beide Links sind nicht sinnvoll, Bisektion sogar irreführend

2025-04-06T19:05:28Z

Änderung 254909079 von Quiorm rückgängig gemacht; beide Links sind nicht sinnvoll, Bisektion sogar irreführend

← Nächstältere Version		Version vom 6. April 2025, 21:05 Uhr
Zeile 44:		Zeile 44:
	Dieses Verfahren kann in allen der im Folgenden erwähnten Algorithmen angewendet werden. Es verfolgt das verbreitete [[Divide and conquer\|Divide-and-conquer]]-Prinzip und besteht darin, dass der Graph nur in 2 Teilmengen [[Schnitt (Graphentheorie)\|geschnitten]] wird. Die entstehenden Teilgraphen werden dann rekursiv wieder zweigeteilt, bis die gewünschte Anzahl ''k'' von Teilmengen erreicht ist. Diese Zahl muss somit eine Zweierpotenz sein, d. h. <math>k = 2 ^ t</math> für ein <math>t \in \{1,2,3,...\}</math> (= Rekursionstiefe). Das ist in der Praxis in der Tat oft der Fall, z. B. in einem Parallelrechner, der <math>2 ^t</math> Prozessoren enthält.		Dieses Verfahren kann in allen der im Folgenden erwähnten Algorithmen angewendet werden. Es verfolgt das verbreitete [[Divide and conquer\|Divide-and-conquer]]-Prinzip und besteht darin, dass der Graph nur in 2 Teilmengen [[Schnitt (Graphentheorie)\|geschnitten]] wird. Die entstehenden Teilgraphen werden dann rekursiv wieder zweigeteilt, bis die gewünschte Anzahl ''k'' von Teilmengen erreicht ist. Diese Zahl muss somit eine Zweierpotenz sein, d. h. <math>k = 2 ^ t</math> für ein <math>t \in \{1,2,3,...\}</math> (= Rekursionstiefe). Das ist in der Praxis in der Tat oft der Fall, z. B. in einem Parallelrechner, der <math>2 ^t</math> Prozessoren enthält.

	Durch Anwendung von rekursiver [[Bisektion]] nimmt man eine suboptimale Lösung in Kauf, um einen großen zeitlichen Gewinn zu erzielen.		Durch Anwendung von rekursiver Bisektion nimmt man eine suboptimale Lösung in Kauf, um einen großen zeitlichen Gewinn zu erzielen.

	=== Geometrische Algorithmen ===		=== Geometrische Algorithmen ===
Zeile 51:		Zeile 51:
	Beispiele für geometrische Algorithmen:		Beispiele für geometrische Algorithmen:
	* [[Koordinatenbisektion]]: Wähle die Koordinate (z. B. x), in welcher die Knoten am weitesten voneinander entfernt sind, und für diese einen Grenzwert c so, dass für die Hälfte der Knoten (x > c) gilt.		* [[Koordinatenbisektion]]: Wähle die Koordinate (z. B. x), in welcher die Knoten am weitesten voneinander entfernt sind, und für diese einen Grenzwert c so, dass für die Hälfte der Knoten (x > c) gilt.
	* [[Inertialbisektion]]: Berechne die Inertialachse und wähle diese anstelle einer [[Koordinatenachse]].		* [[Inertialbisektion]]: Berechne die Inertialachse und wähle diese anstelle einer Koordinatenachse.

	=== Spektrale Bisektion ===		=== Spektrale Bisektion ===

Quiorm: /* growthexperiments-addlink-summary-summary:2|0|0 */

2025-04-06T15:04:51Z

Linkvorschlag-Funktion: 2 Links hinzugefügt.

← Nächstältere Version		Version vom 6. April 2025, 17:04 Uhr
Zeile 44:		Zeile 44:
	Dieses Verfahren kann in allen der im Folgenden erwähnten Algorithmen angewendet werden. Es verfolgt das verbreitete [[Divide and conquer\|Divide-and-conquer]]-Prinzip und besteht darin, dass der Graph nur in 2 Teilmengen [[Schnitt (Graphentheorie)\|geschnitten]] wird. Die entstehenden Teilgraphen werden dann rekursiv wieder zweigeteilt, bis die gewünschte Anzahl ''k'' von Teilmengen erreicht ist. Diese Zahl muss somit eine Zweierpotenz sein, d. h. <math>k = 2 ^ t</math> für ein <math>t \in \{1,2,3,...\}</math> (= Rekursionstiefe). Das ist in der Praxis in der Tat oft der Fall, z. B. in einem Parallelrechner, der <math>2 ^t</math> Prozessoren enthält.		Dieses Verfahren kann in allen der im Folgenden erwähnten Algorithmen angewendet werden. Es verfolgt das verbreitete [[Divide and conquer\|Divide-and-conquer]]-Prinzip und besteht darin, dass der Graph nur in 2 Teilmengen [[Schnitt (Graphentheorie)\|geschnitten]] wird. Die entstehenden Teilgraphen werden dann rekursiv wieder zweigeteilt, bis die gewünschte Anzahl ''k'' von Teilmengen erreicht ist. Diese Zahl muss somit eine Zweierpotenz sein, d. h. <math>k = 2 ^ t</math> für ein <math>t \in \{1,2,3,...\}</math> (= Rekursionstiefe). Das ist in der Praxis in der Tat oft der Fall, z. B. in einem Parallelrechner, der <math>2 ^t</math> Prozessoren enthält.

	Durch Anwendung von rekursiver Bisektion nimmt man eine suboptimale Lösung in Kauf, um einen großen zeitlichen Gewinn zu erzielen.		Durch Anwendung von rekursiver [[Bisektion]] nimmt man eine suboptimale Lösung in Kauf, um einen großen zeitlichen Gewinn zu erzielen.

	=== Geometrische Algorithmen ===		=== Geometrische Algorithmen ===
Zeile 51:		Zeile 51:
	Beispiele für geometrische Algorithmen:		Beispiele für geometrische Algorithmen:
	* [[Koordinatenbisektion]]: Wähle die Koordinate (z. B. x), in welcher die Knoten am weitesten voneinander entfernt sind, und für diese einen Grenzwert c so, dass für die Hälfte der Knoten (x > c) gilt.		* [[Koordinatenbisektion]]: Wähle die Koordinate (z. B. x), in welcher die Knoten am weitesten voneinander entfernt sind, und für diese einen Grenzwert c so, dass für die Hälfte der Knoten (x > c) gilt.
	* [[Inertialbisektion]]: Berechne die Inertialachse und wähle diese anstelle einer Koordinatenachse.		* [[Inertialbisektion]]: Berechne die Inertialachse und wähle diese anstelle einer [[Koordinatenachse]].

	=== Spektrale Bisektion ===		=== Spektrale Bisektion ===

BumbleMath: Link hinzugefügt

2023-12-11T15:12:19Z

Link hinzugefügt

← Nächstältere Version		Version vom 11. Dezember 2023, 17:12 Uhr
Zeile 15:		Zeile 15:

	==== Das Optimierungsproblem als Graphpartitionierungsproblem ====		==== Das Optimierungsproblem als Graphpartitionierungsproblem ====
	Dieses Optimierungsproblem lässt sich als Graph-Partitionierungsproblem formulieren:		Dieses [[Optimierungsproblem]] lässt sich als Graph-Partitionierungsproblem formulieren:
	* Die einzelnen Berechnungsaufgaben im Programm werden als [[Knoten (Graphentheorie)\|Knoten]] eines Graphen modelliert.		* Die einzelnen Berechnungsaufgaben im Programm werden als [[Knoten (Graphentheorie)\|Knoten]] eines Graphen modelliert.
	* Für jede Berechnung, welche vom Resultat einer anderen Berechnung abhängig ist, werden die entsprechenden Knoten mit einer [[Kante (Graphentheorie)\|Kante]] verbunden.		* Für jede Berechnung, welche vom Resultat einer anderen Berechnung abhängig ist, werden die entsprechenden Knoten mit einer [[Kante (Graphentheorie)\|Kante]] verbunden.

Twistios: /* Algorithmen */ nicht NP-vollständig (d.h. NP-äquivalent), da kein Entscheidungsproblem; Heuristiken existieren, sind also nicht "nur" vorgeschlagen

2023-08-06T21:45:15Z

Algorithmen: nicht NP-vollständig (d.h. NP-äquivalent), da kein Entscheidungsproblem; Heuristiken existieren, sind also nicht "nur" vorgeschlagen

← Nächstältere Version		Version vom 6. August 2023, 23:45 Uhr
Zeile 37:		Zeile 37:

	== Algorithmen ==		== Algorithmen ==
	Die optimale Partition für einen Graphen zu berechnen, ist ein [[NP-~~vollständig~~]]es Problem. Deshalb existiert eine Reihe von ~~vorgeschlagenen~~ [[Heuristik]]en, um in kurzer Zeit wenigstens annähernd optimale Partitionen zu finden.		Die optimale Partition für einen Graphen zu berechnen, ist ein [[NP-Äquivalenz\|NP-äquivalentes]] Problem. Deshalb existiert eine Reihe von [[Heuristik]]en, um in kurzer Zeit wenigstens annähernd optimale Partitionen zu finden.

	Diese lassen sich in etwa gliedern nach den Ansätzen, die sie verfolgen:		Diese lassen sich in etwa gliedern nach den Ansätzen, die sie verfolgen:

Crazy1880: Vorlagen-fix

2019-11-03T10:22:20Z

Vorlagen-fix

79.213.172.168: 2-partit als Erklärung zum Bild

2018-12-02T09:05:07Z

2-partit als Erklärung zum Bild

← Nächstältere Version		Version vom 2. Dezember 2018, 11:05 Uhr
Zeile 1:		Zeile 1:
	{{QS-Informatik\|Knacknüsse=Ja\|allgemeinverständlichkeit --[[Benutzer:Verum\|'''V''']] [[Benutzer Diskussion:Verum\|'''¿ ''']] 22:37, 6. Aug. 2013 (CEST)}}		{{QS-Informatik\|Knacknüsse=Ja\|allgemeinverständlichkeit --[[Benutzer:Verum\|'''V''']] [[Benutzer Diskussion:Verum\|'''¿ ''']] 22:37, 6. Aug. 2013 (CEST)}}

	[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph]]		[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph (2-partit)]]

	'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 \|Seiten=18 \|ISBN=3540213910 \|OCLC= }}</ref>		'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 \|Seiten=18 \|ISBN=3540213910 \|OCLC= }}</ref>

← Nächstältere Version		Version vom 6. April 2025, 21:09 Uhr
Zeile 1:		Zeile 1:
	{{QS-Informatik\|Knacknüsse=Ja\|allgemeinverständlichkeit --[[Benutzer:Verum\|'''V''']] [[Benutzer Diskussion:Verum\|'''¿ ''']] 22:37, 6. Aug. 2013 (CEST)}}		{{QS-Informatik\|Knacknüsse=Ja\|allgemeinverständlichkeit --[[Benutzer:Verum\|'''V''']] [[Benutzer Diskussion:Verum\|'''¿ ''']] 22:37, 6. Aug. 2013 (CEST)}}

	[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph ~~(2-partit)~~]]		[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph]]

	'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 \|ISBN=3-540-21391-0 \|Seiten=18}}</ref>		'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 \|ISBN=3-540-21391-0 \|Seiten=18}}</ref>

← Nächstältere Version		Version vom 2. Dezember 2018, 11:05 Uhr
Zeile 1:		Zeile 1:
	{{QS-Informatik\|Knacknüsse=Ja\|allgemeinverständlichkeit --[[Benutzer:Verum\|'''V''']] [[Benutzer Diskussion:Verum\|'''¿ ''']] 22:37, 6. Aug. 2013 (CEST)}}		{{QS-Informatik\|Knacknüsse=Ja\|allgemeinverständlichkeit --[[Benutzer:Verum\|'''V''']] [[Benutzer Diskussion:Verum\|'''¿ ''']] 22:37, 6. Aug. 2013 (CEST)}}

	[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph]]		[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph (2-partit)]]

	'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 \|Seiten=18 \|ISBN=3540213910 \|OCLC= }}</ref>		'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 \|Seiten=18 \|ISBN=3540213910 \|OCLC= }}</ref>

← Nächstältere Version		Version vom 3. November 2019, 12:22 Uhr
Zeile 3:		Zeile 3:
	[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph (2-partit)]]		[[Datei:Graphpart simple.svg\|gerahmt\|rechts\|Partitionierter Graph (2-partit)]]

	'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 ~~\|Seiten=18~~ \|ISBN=~~3540213910~~ \|~~OCLC~~= }}</ref>		'''Graphpartitionierung''' bezeichnet die Anwendung geeigneter [[Algorithmus\|Algorithmen]] zur Berechnung von Graphpartitionen (vgl. [[Schnitt (Graphentheorie)]]) mit gewünschten Eigenschaften. Ein Graph heißt r-partit, wenn eine Partition (Teilung) seiner Knoten in r Teile existiert, so dass die Endecken jeder Kante des Graphen in verschiedenen Partitionsklassen liegen.<ref>{{Literatur \|Autor=Diestel, Reinhard. \|Titel=Graphentheorie \|Auflage=3., neu bearb. und erw. Aufl. \|Verlag=Springer \|Ort=Berlin \|Datum=2006 \|ISBN=3-540-21391-0 \|Seiten=18}}</ref>

	== Graphpartitionierung in der parallelen Programmierung ==		== Graphpartitionierung in der parallelen Programmierung ==
Zeile 73:		Zeile 73:
	* Greedy		* Greedy

	Ein besonderer Ansatz wird durch den ADWISE<ref>{{Internetquelle \|autor=Christian Mayer, Ruben Mayer, Muhammad Adnan Tariq, Heiko Geppert, Larissa Laich, Lukas Rieger, Kurt Rothermel \|url=https://arxiv.org/pdf/1712.08367&sa=U&ved=0ahUKEwis1KGrjMDcAhWLZ1AKHaBKD_IQFggOMAE&usg=AOvVaw0-afIuCzSrMEzuoSde2k1b \|titel=ADWISE: Adaptive Window-based Streaming Edge Partitioning for High-Speed Graph Processing \|hrsg=Universität Stuttgart \|~~zugriff~~=2018-07-27 \|sprache=en}}</ref>-Algorithmus verfolgt. Er ist ein Streaming-Algorithmus, verwendet aber gleichzeitig einen Kanten-Buffer. Dadurch kann der Algorithmus im Rahmen der Buffergröße seine Kantenzuweisungen optimieren. Über die Buffergröße lässt sich außerdem die Laufzeit des Algorithmus beeinflussen. Je größer der Buffer, desto besser ist die berechnete Partitionierung, allerdings führt dies dann auch zu mehr Latenz.		Ein besonderer Ansatz wird durch den ADWISE<ref>{{Internetquelle \|autor=Christian Mayer, Ruben Mayer, Muhammad Adnan Tariq, Heiko Geppert, Larissa Laich, Lukas Rieger, Kurt Rothermel \|url=https://arxiv.org/pdf/1712.08367&sa=U&ved=0ahUKEwis1KGrjMDcAhWLZ1AKHaBKD_IQFggOMAE&usg=AOvVaw0-afIuCzSrMEzuoSde2k1b \|titel=ADWISE: Adaptive Window-based Streaming Edge Partitioning for High-Speed Graph Processing \|hrsg=Universität Stuttgart \|abruf=2018-07-27 \|format=PDF \|sprache=en}}</ref> -Algorithmus verfolgt. Er ist ein Streaming-Algorithmus, verwendet aber gleichzeitig einen Kanten-Buffer. Dadurch kann der Algorithmus im Rahmen der Buffergröße seine Kantenzuweisungen optimieren. Über die Buffergröße lässt sich außerdem die Laufzeit des Algorithmus beeinflussen. Je größer der Buffer, desto besser ist die berechnete Partitionierung, allerdings führt dies dann auch zu mehr Latenz.

	=== Open Source Graphpartitionierungspakete ===		=== Open Source Graphpartitionierungspakete ===
	* KaHIP<ref>Christian Schulz: ''High Quality Graph Partitioning.'' Dissertation. Karlsruhe Institute of Technology, 2013.</ref><ref>Peter Sanders, Christian Schulz: ''Engineering Multilevel Graph Partitioning Algorithms.'' In: ''Proceedings of the 19th European Symposium on Algorithms (ESA’11).'' volume 6942 of LNCS, pages 469--480. Springer, 2011.</ref><ref>Peter Sanders, Christian Schulz: ''Distributed Evolutionary Graph Partitioning.'' In: ''Proceedings of the 12th Workshop on Algorithm Engineering and Experimentation (ALENEX’12).'' S. 16–19, 2012.</ref><ref>Peter Sanders, Christian Schulz: ''High Quality Graph Partitioning.'' In: ''Proceedings of the 10th DIMACS Implementation Challenge Workshop: Graph Partitioning and Graph Clustering.'' S. 1–17, AMS, 2013.</ref>(Karlsruhe High Quality Partitioning).<ref>http://algo2.iti.kit.edu/documents/kahip/index.html</ref>		* KaHIP<ref>Christian Schulz: ''High Quality Graph Partitioning.'' Dissertation. Karlsruhe Institute of Technology, 2013.</ref><ref>Peter Sanders, Christian Schulz: ''Engineering Multilevel Graph Partitioning Algorithms.'' In: ''Proceedings of the 19th European Symposium on Algorithms (ESA’11).'' volume 6942 of LNCS, pages 469--480. Springer, 2011.</ref><ref>Peter Sanders, Christian Schulz: ''Distributed Evolutionary Graph Partitioning.'' In: ''Proceedings of the 12th Workshop on Algorithm Engineering and Experimentation (ALENEX’12).'' S. 16–19, 2012.</ref><ref>Peter Sanders, Christian Schulz: ''High Quality Graph Partitioning.'' In: ''Proceedings of the 10th DIMACS Implementation Challenge Workshop: Graph Partitioning and Graph Clustering.'' S. 1–17, AMS, 2013.</ref> (Karlsruhe High Quality Partitioning).<ref>http://algo2.iti.kit.edu/documents/kahip/index.html</ref>
	* kMetis.<ref>G. Karypis, V. Kumar: ''A fast and high quality multilevel scheme for partitioning irregular graphs.'' SIAM Journal on Scientific Computing 20 (1): S. 359. (1999)</ref><ref>http://glaros.dtc.umn.edu/gkhome/metis/metis/overview</ref>		* kMetis.<ref>G. Karypis, V. Kumar: ''A fast and high quality multilevel scheme for partitioning irregular graphs.'' SIAM Journal on Scientific Computing 20 (1): S. 359. (1999)</ref><ref>http://glaros.dtc.umn.edu/gkhome/metis/metis/overview</ref>
	* Scotch.<ref>http://www.labri.fr/perso/pelegrin/scotch/</ref>		* Scotch.<ref>http://www.labri.fr/perso/pelegrin/scotch/</ref>

	== Literatur ==		== Literatur ==
	* {{Literatur \|Autor=Aydin Buluc, Ilya Safro, Henning Meyerhenke, Peter Sanders, Christian Schulz \|Titel=Recent Advances in Graph Partitioning \|Datum=2013 \|~~arxiv~~=1311.3144}}		* {{Literatur \|Autor=Aydin Buluc, Ilya Safro, Henning Meyerhenke, Peter Sanders, Christian Schulz \|Titel=Recent Advances in Graph Partitioning \|Datum=2013 \|arXiv=1311.3144}}
	* {{Literatur \|Autor=Christian Schulz \|Titel=High Quality Graph Partitioning \|Verlag=epubli GmbH \|Ort=Berlin \|Datum=2013 \|ISBN=978-3-8442-6462-3 \|Kommentar=Dissertation, Karlsruhe Institute of Technology \|Online=[http://algo2.iti.kit.edu/schulz/dissertation_christian_schulz.pdf ~~PDF~~]}}		* {{Literatur \|Autor=Christian Schulz \|Titel=High Quality Graph Partitioning \|Verlag=epubli GmbH \|Ort=Berlin \|Datum=2013 \|ISBN=978-3-8442-6462-3 \|Kommentar=Dissertation, Karlsruhe Institute of Technology \|Online=[http://algo2.iti.kit.edu/schulz/dissertation_christian_schulz.pdf Online] \|Format=PDF \|KBytes=}}
	* {{Literatur \|Autor=U. Elsner \|Titel=Graph partitioning – a survey \|Datum=1997 \|Sprache=en}}		* {{Literatur \|Autor=U. Elsner \|Titel=Graph partitioning – a survey \|Datum=1997 \|Sprache=en}}