Ecken eines Polyeders

08.01.2014, 19:42	10001000Nick1	Auf diesen Beitrag antworten »
Ecken eines Polyeders Meine Frage: Hallo, ich versuche gerade, folgendes zu beweisen: Sei $\begin{eqnarray} X\subseteq\{0,1\}^n. \end{eqnarray}$ Beweisen Sie, dass die Eckenmenge von $\begin{eqnarray} P:=conv(X) \end{eqnarray}$ die Menge $\begin{eqnarray} X \end{eqnarray}$ ist. Meine Ideen: Die Ecken eines Polyeders P sind ja seine minimalen Seiten. Außerdem ist $\begin{eqnarray} u\in P \end{eqnarray}$ genau dann eine Ecke von P, wenn $\begin{eqnarray} v\not\in conv(P\backslash\{u\}) \end{eqnarray}$ ist. Jetzt wollte ich also zeigen, dass für alle $\begin{eqnarray} x\in X \end{eqnarray}$ gilt: $\begin{eqnarray} x\not\in conv(X\backslash\{x\}). \end{eqnarray}$ Mir ist da der Trennsatz eingefallen. Kann man das damit machen? So richtig komme ich damit nicht weiter... Schöne Grüße, Nick
08.01.2014, 21:32	HAL 9000	Auf diesen Beitrag antworten »
Ich sehe da eigentlich keinerlei Probleme bei einem indirekten Beweis: Angenommen, es gibt ein $\begin{eqnarray} x\in X \end{eqnarray}$ mit $\begin{eqnarray} x\in \operatorname{conv}(X\setminus\{x\}) \end{eqnarray}$ , dann existieren $\begin{eqnarray} u_1,\ldots,u_k \in X\setminus\{x\} \end{eqnarray}$ sowie positive Faktoren $\begin{eqnarray} \lambda_1,\ldots,\lambda_k \end{eqnarray}$ (mit Summe 1), so dass $\begin{eqnarray} x = \lambda_1 u_1 + \ldots + \lambda_k u_k \end{eqnarray}$ gilt. Diese Gleichung gilt dann natürlich nun auch komponentenweise i=1 bis n: $\begin{eqnarray} x^{(i)} = \lambda_1 u_1^{(i)} + \ldots + \lambda_k u_k^{(i)} \end{eqnarray}$ . Aus $\begin{eqnarray} x^{(i)} = 0 \end{eqnarray}$ folgt dann sofort $\begin{eqnarray} u_1^{(i)} = \ldots = u_k^{(i)} = 0 \end{eqnarray}$ , genauso folgt aus $\begin{eqnarray} x^{(i)} = 1 \end{eqnarray}$ auch unmittelbar $\begin{eqnarray} u_1^{(i)} = \ldots = u_k^{(i)} = 1 \end{eqnarray}$ , also insgesamt $\begin{eqnarray} u_1 = \ldots u_k = x \end{eqnarray}$ , Widerspruch zu $\begin{eqnarray} u_1,\ldots,u_k \in X\setminus\{x\} \end{eqnarray}$ .
08.01.2014, 22:00	10001000Nick1	Auf diesen Beitrag antworten »
OK, dankeschön. Jetzt muss ich ja auch noch begründen, warum es keine anderen Ecken als die Elemente von $\begin{eqnarray} X \end{eqnarray}$ gibt. Angenommen, es gibt eine Ecke von P $\begin{eqnarray} y\in P\backslash X. \end{eqnarray}$ Dann gilt $\begin{eqnarray} y\not\in\operatorname{conv}(P\backslash\{y\})=\operatorname{conv}(\operatorname{conv}(X)\backslash\{y\})=\operatorname{conv}(\operatorname{conv}(X))=\operatorname{conv}(X)=P\Rightarrow \text{Widerspruch!} \end{eqnarray}$ Ist das so in Ordnung?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »