Kreuzpolytop

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

Als Kreuzpolytop bezeichnet man in der Geometrie ein n-dimensionales, beschränktes Polyeder (also ein Polytop), welches kombinatorisch äquivalent zum Einheits-Kreuzpolytop ist. Kreuzpolytope finden rege Anwendung sowohl in der (speziell linearen) Optimierung sowie in der Kristallographie.

[Bearbeiten] Das Einheits-Kreuzpolytop

Das Einheits-Kreuzpolytop lässt sich folgendermaßen als konvexe Hülle seiner Ecken darstellen:

$P= conv({e_1, e_2, \ldots e_n, -e_1, -e_2, \ldots -e_n}) \subseteq \mathbb{R}^n$ .

Dabei bezeichnet $e_i= (0, 0,\ldots, 1, 0, \dots 0)^T$ den i-ten Einheitsvektor des Vektorraums $\mathbb{R}^n$ . Das Einheits-Kreutpolytop ist konvex, abgeschlossen und zusammenhängend (bezüglich der euklidischen Metrik) und hat folgende Spezielle Eigenschaften:

Es ist Punktsymmetrisch um 0, d.h. $\forall v \in \mathbb{R}^n: v \in P \Rightarrow -v \in P$ .
Es ist symmetrisch bezüglich Spiegelungen an den Koordinatenebenen, d.h.

$\forall (v_1,\ldots v_n)^T \in \mathbb{R}^n, \forall i \in \{1 \ldots n \}: (v_1, \ldots v_i \ldots v_n)^T \in P \Rightarrow (v_1, \ldots -v_i \ldots v_n)^T \in P$ .

Es hat 2n Ecken, eben die (positiven und negativen) Einheitsvektoren
es hat 2n(n-1) Kanten, denn jede Ecke $v n$ ist außer mit der gegenüberliegenden Ecke $- v n$ mit jeder anderen über eine Kante verbunden.
P wird äquivalent zur obigen Darstellung als Lösungsmenge der Ungleichung

$|v_1|+|v_2|+ \ldots + |v_n| \le 1$ definiert.

dieses Ungeleichungssystem lässt sich auch in ein System von $2 n$ linearen Ungleichungen umschreiben. Man erkennt dadurch, dass P genau $2 n$ Facetten (also n-1-dimensionale begrenzende Hyperebenen besitzt.

Das (n-dimensionale) Volumen des Einheits-Kreuzpolytops beträgt $\frac{2^n}{n!}$ . Es wird also für hohe Dimensionen beliebig klein.

Das Standard-Kreuzpolytop ist die Einheitssphäre des $\mathbb{R}^n$ bezüglich der 1-Norm, d. h. $P= \{ v \in \mathbb{R}^n: ||v||_1 \le 1 \}$ . Hierin liegt auch die Bedeutung des Kreuzpolytops in der Kristallographie: Auf molekularer Ebene haben manche Stoffe das Bestreben, sich bezüglich des durch die 1-Norm induzierten Abstandsbegriffes möglichst "dicht" anzuordnen; das Ergebnis sind Kristalle in Form von Kreuzpolytopen.
Das dreidimensionale Kreuzpolytop heißt auch Oktaeder und ist einer der platonischen Körper.
Die n Koordinatenebenen zerteilen das Einheits-Kreuzpolytop in $2 n$ Einheitssimplices des $\mathbb{R}^n$ .
Die Facetten des Kreuzpolytops sind Simplices des $\mathbb{R}^{n-1}$ .
Das Kreuzpolytop gilt als Prototyp eines Polyeders, der (in Relation zur Dimension) sehr wenige Ecken, aber sehr viele Facetten besitzt. Diese Eigenschaft ist in der linearen Optimierung besonders wichtig, da der Simplex-Algorithmus, das Standardverfahren zur Lösung linearer Optimierungsprobleme, gezielt Ecken auf ihre Optimalität prüft. Das Gegenstück hierzu ist der Würfel, dessen Eckenzahl exponentiell, die Facettenzahl aber nur linear in n anwächst.

[Bearbeiten] Allgemeine Kreuzpolytope

Der Kantengraph eines vierdimensionalen Kreuzpolytops

Alternativ nennt man auch jeden Polyeder Kreuzpolytop, der zum Standard-Kreuzpolytop kombinatorisch äquivalent sind. Präzise formuliert bedeutet das:

Ein Polyeder $Q \subseteq \mathbb{R}^n$ heißt genau dann Kreuzpolytop, wenn es eine Bijektion f von der Menge der Ecken von Q auf die Menge der Ecken $\{ e_1,\ldots e_n, -e_1, \ldots -e_n \}$ von P gibt, sodass zwei Ecken v,w von Q stets genau dann durch eine Kante verbunden sind, wenn f(v) und f(w) dies in P sind.

Somit hat ein allgemeines Kreuzpolytop die selbe Anzahl von Ecken, Kanten und Facetten wie das Standard-Kreuzpolytop, doch die Symmetrien gehen dabei verloren.

Eine strengere (und eher geometrisch motivierte) Definition des Kreuzpolytops lautet wie folgt:

Ein Polyeder $Q \subseteq \mathbb{R}^n$ heißt genau dann Kreuzpolytop, wenn es eine orthogonale Matrix $A \in \mathbb{R}^{n \times n}$ , eine reelle Zahl

λ > 0

und einen Vektor $b \in \mathbb{R}^n$ gibt, sodass

Q = λ A P + b

gilt.

Jedes Kreuzpolytop nach der zweiten Definition erfüllt auch die erste, jedoch nicht umgekehrt. Kreuzpolytope gemäß der zweiten Definition sehen "optisch" aus wie das Standard-Kreuzpolytop, und auch die Symmetrieeigenschaften (das Symmetriezentrum und die Spiegelebenen werden entsprechent mittransformiert) und die Volumenformel (bis auf den zusätzlichen Faktor $λ n$ ) bleiben erhalten.

Die mathematische Fakultät der Technischen Universität München führt ein dreidimensionales Kreuzpolytop in ihrem Logo.

Von „http://de.wikipedia.org../../../k/r/e/Kreuzpolytop.html“

Kategorie: Geometrie

Kreuzpolytop

aus Wikipedia, der freien Enzyklopädie

[Bearbeiten] Das Einheits-Kreuzpolytop

[Bearbeiten] Allgemeine Kreuzpolytope

Views

Navigation

Mitmachen

Suche