Basen von Matroiden < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:20 Mi 21.01.2009 | | Autor: | adi87 |
| Aufgabe | | Zeigen Sie: Fügt man zu einer Basis eines Matroides eine Kante hinzu so entsteht genau 1 Kreis. |
Hallo ihr Lieben,
ich bereite mich gerade auf meine Opti DHP vor, und hänge grad an einer Hausübung, die wir hatten mit genau dieser Fragestellung.
Mir ist voll und ganz klar, dass es so sein muss, weil angenommen ich erhalte zwei Kreise, dann muss die Kante genau aus der Schnittmenge der beiden Kreise sein, und ich erhalte dann dadurch einen "größeren Kreis" (wäre die Kante nicht aus der Schnittmenge gewesen, dann hätte ich e schon einen Widerspruch, denn dann wären die beiden Kreise disjunkt und ich hätte schon davor einen Kreis gehabt.)
So, soweit so gut wie ich es mir erkläre, jedoch: wie schreibe ich das mathematisch sauber auf??? Könnt ihr mir mal ein bisschen weiterhelfen?
DANKE!!!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:26 Mi 21.01.2009 | | Autor: | zetamy |
Hallo,
deine Lösung hört sich schonmal gut an. Zur mathematischen Formulierung:
Sei M der Matroid und $C(M)$ die Menge der Kreise von M. Es gilt: [mm] $X,Y\in [/mm] C(M), [mm] X\neq [/mm] Y, [mm] e\in X\cap [/mm] Y [mm] \Rightarrow \exists Z\subset (X\cup Y)\backslash [/mm] e$ mit [mm] $Z\in [/mm] C(M)$ (*).
Sei X ist eine Basis von M. Dann ist für jedes [mm] $e\not\in [/mm] X$ [mm] $X\cup [/mm] e$ eine abhängige Menge, dh es existiert mindestens ein Kreis.
Seien $C,C'$ Kreise in [mm] $X\cup [/mm] e$. Dann ist [mm] $e\in C\cap [/mm] C'$. Nach Aussage (*) existiert also ein Kreis [mm] $Z\subset(C\cup C')\backslash e\subset [/mm] X$. Das ist ein Widerspruch zu X ist Basis.
Folglich entsteht genau ein Kreis.
Gruß zetamy
|
|
|
|
