Beweis: Uniformes Matroid

01.01.2018, 16:53	FelNa1109	Auf diesen Beitrag antworten »
Beweis: Uniformes Matroid Aufgabe: Zeigen Sie: $\begin{eqnarray} (E,F) \end{eqnarray}$ ist genau dann ein uniformes Matroid, wenn es keinen Kreis $\begin{eqnarray} C \end{eqnarray}$ gibt mit $\begin{eqnarray} \|C\|\leq r(E) \end{eqnarray}$ . Meine Ideen: " $\begin{eqnarray} \Rightarrow \end{eqnarray}$ " $\begin{eqnarray} (E,F) \end{eqnarray}$ ist ein uniformes Matroid, d.h. $\begin{eqnarray} E \end{eqnarray}$ endl. Menge, $\begin{eqnarray} k\in \mathbb N_0 \end{eqnarray}$ und $\begin{eqnarray} F =\left\{ X\subseteq E : \| X \|\leq k \right\} \end{eqnarray}$ . Insbesondere sind die Basen durch $\begin{eqnarray} B =\left\{ X\subseteq E : \| X \|=k \right\} \end{eqnarray}$ gegeben. Der Rang von $\begin{eqnarray} E \end{eqnarray}$ ist $\begin{eqnarray} r(E) =max \left\{\| Y \| : \| Y \| \subseteq E, Y\in F \right\} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \end{eqnarray}$ da $\begin{eqnarray} (E,F) \end{eqnarray}$ Matroid ist, haben alle Basen die selbe Kardinalität/Länge. $\begin{eqnarray} \Rightarrow \end{eqnarray}$ Wäre $\begin{eqnarray} \|C\|\leq r(E)=k \end{eqnarray}$ so folgt nach Definition $\begin{eqnarray} C\in F \end{eqnarray}$ , also kann $\begin{eqnarray} C \end{eqnarray}$ kein Kreis sein. " $\begin{eqnarray} \Leftarrow \end{eqnarray}$ " Angenommen es gibt einen Kreis mit $\begin{eqnarray} \|C\|\leq r(E) \end{eqnarray}$ . Dann ist: $\begin{eqnarray} \|C\|\leq r(E) =max \left\{\| Y \| : Y Basis \right\} \end{eqnarray}$ $\begin{eqnarray} \Leftrightarrow \end{eqnarray}$ $\begin{eqnarray} min \left\{\| Y \| : Y Basis \right\} \leq C \leq max \left\{\| Y \| : Y Basis \right\} \end{eqnarray}$ Dann gilt für den Rangquotienten $\begin{eqnarray} q(E,F)\leq 1 \end{eqnarray}$ $\begin{eqnarray} \Rightarrow \end{eqnarray}$ $\begin{eqnarray} (E,F) \end{eqnarray}$ ist kein Matroid. Nachtrag zur Rückrichtung: Angenommen es existiert ein Kreis mit $\begin{eqnarray} \| C \| \leq r(E)=k \end{eqnarray}$ Da $\begin{eqnarray} C \end{eqnarray}$ ein Kreis ist, gilt $\begin{eqnarray} C\notin F = \left\{ X\subseteq E: \| X \| \leq k\right\} \end{eqnarray}$ , obwohl der Kreis diese Eigenschaft erfüllt. Also ist $\begin{eqnarray} (E,F) \end{eqnarray}$ kein uniformer Matroid. Hoffe mir kann jemand helfen, danke. Zwei Beiträge zusammengefasst. Steffen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »