Diskussion:Matroid

Matroide wurden vielleicht aus der Graphentheorie entwickelt, sind aber doch ein allgemeiner Ansatz zur Definition von Unabhängigkeit (auch z.B. linearer Unabh.).

auch nach der englischen Beschreibung braucht dieser Artikel dringend eine Überarbeitung Guidod 08:10, 18. Sep 2004 (CEST)

Bedingung 3

Ich habe zwar noch nie vorher etwas von einem Matroid gehört, aber Bedingung 3 kommt mir komisch vor. "Wenn A eine Teilmenge von E ist und alle endlichen Teilmengen von E in U sind, dann ist A in U" steht da. Anders formuliert: Wenn alle endlichen Teilmengen (von E) in U sind, sind alle Teilmengen von E in U. Kann es sein, dass da eigentlich $A\subseteq E\land \forall B\subset \subset A:B\in U\Rightarrow A\in U$ stehen sollte? -- Paul E. 21:39, 18. Apr 2005 (CEST)

Einleitung

Ich finde, dass der erste Absatz in der Einleitung genügt. Der Rest ist Zusatzinformation für Leute, die das entsprechende Vorwissen haben und gehört m.E. in den Hauptartikel.

Ich habe das mal dahin gehend geändert, und einen Abschnitt Matroide und Greedy-Strategie eingefügt. --87.123.16.155 16:55, 14. Dez 2005 (CET)

Definition

1.) Paul hat natürlich Recht mit seinem Hinweis, Bedingung 3 sollte heissen: wenn alle endlichen Teilmengen einer Menge A in U sind, dann ist es auch die Menge A selbst.

2.) Wieso wurde am 28. / 29. Juli die Definition wieder auf endliche Mengen eingeschränkt? (Eine Begründung, ein Kommentar wäre wünschenswert gewesen.)

Wollte das nicht wieder wortlos ändern: Ist es besser die Definition zu ändern oder geschickter, die für Mengen allgemein als eine "mögliche Verallgemeinerung" zusätzlich zur bestehenden wieder aufzunehmen?

(Wen's interessiert: die allgemeinere Fassung ist in den Versionen von September 2004 eingefügt worden, wenn auch mit dem von Paul angesprochenen Fehler, s. 1.)

3.) Zum Vorschlag bzgl. der Einleitung: den Part nach dem ersten Absatz könnte man evtl. als Abschnitt "Anwendungen" in den Hauptartikel integrieren.

Frank

zu 2.) Ich Stimme dir zu, dass sollte wieder allgemein gemacht werden. Dann muss man Allerdings auch den Artikel zur Austauscheigenschaft anpassen, da nicht unmittelbar klar ist, was die |A\B|-fache Anwendung der Austauscheigenschaft sein soll.

genus

am 28. aug. 2005 hat jemand als grammatikalisches geschlecht neutrum eingefügt, in beispiel 2 steht "graphischer matroid", also maskulinum. welches davon ist richtig? -- Claviceps purpurea 21:27, 21. Jan 2006 (CET)

Nur das Neutrum ist richtig, ich habe versucht bei der Neubearbeitung darauf zu achten. -- 84.19.199.179 17:07, 26. Mär. 2013 (CET)

Dijkstra-Algorithmus als Greedy-Algorithmus?

Im Artikel wird der Dijkstra-Algorithmus als Beispiel für einen Greedy-Algorithmus genannt. Aber wenn ein Graph die Wege A->B (1), A->C (2), B->D (4), C->D (2) enthält, würde ein Greedy-Algorithmus von A nach D doch den Weg über B mit Kosten 1+4=5 nehmen, während der Weg über C mit Kosten 2+2=4 günstiger wäre. --HeikoTheissen 12:33, 2. Sep 2006 (CEST)

Nein, dass Dijkstra ein Greedy-Algorithmus ist stimmt meiner Meinung nach: Es wird immer die Kante als nächstes Aufgenommen, deren Zielknoten den minimalen Abstand vom Startknoten hat, sofern nur Pfade über bereits aufgenommene Knoten besucht werden. Ohne formale Beschreibung des Algorithmus klingt das vielleicht etwas wirr; das wichtige ist: Greedy heißt hier nicht "nimmt die erste Kante, die Du findest", auch nicht "nimm die kürzeste Kante", sondern: "nimm die Kante, die einen Pfad zu einem neuen Knoten herstellt, so dass keine Einfügung einer einzelnen Kante einen kürzeren Pfad zu einem neuen Knoten herstellt". FarSide 07:47, 13. Okt. 2006 (CEST)

Gemäß der Regel "nimm die Kante, … herstellt" würde also im o.g. Beispiel als erstes die Kante A->C genommen und nicht A->B? --HeikoTheissen 08:27, 13. Okt. 2006 (CEST)

Der Greedy-Algorithmus - unter diesem Schlagwort als "best-in-greedy" beschrieben - tut auf dem im Text beschriebenen Matroid tut m.E. genau das, was HeikoTheissen gesagt hat, nimmt also die falsche Kante. Im Unterschied zu "greedy-Algorithmen", bei denen zu jedem Zeitpunkt nur ein Lösungskandidat gespeichert und nach und nach verbessert wird, benötigt Dijkstra zusätzliche Informationen über die kürzesten Wege zu anderen Endpunkten. Das Beispiel erscheint mir deshalb irreführend. --FRR 15:06, 13. Okt. 2006 (CEST)

Es würde erst die Kante A->B und dann die Kante A->C genommen werden. Soweit ist das auch richtig, denn der kürzeste Weg nach B (bzw. C) führt eben über diese Kante. Danach sind die Knoten A/0, B/1 und C/2 besucht worden, hinter dem Schrägstrich steht der Abstand von A. Jetzt stehen die Kanten B->D und C->D zur Auswahl. B->D liefert eine Gesamtlänge von (Abstand A bis B) + (Länge von B->D) = 1 + 4 = 5; die Kante C->D liefert eine Gesamtlänge von (Abstand von A bis C) + (Länge von C->D) = 2 + 2 = 4. Deshalb wird die Kante C->D genommen. Dabei wurde nebenbei auch der kürzeste Weg von A nach B berechnet, aber nur als Zwischenergebnis, diese Information wird nachher nicht mehr verwendet. --FarSide 05:51, 15. Okt. 2006 (CEST)

Ich nehme an, daß wir uns über die Funktionsweise von Dijkstra einig sind, sehe aber nicht, wie man einen Optimierungsalgorithmus auf Matroiden so formulieren könnte, daß Dijkstra ein Spezialfall davon wird. --FRR 17:21, 24. Okt. 2006 (CEST)

Im Buch "Algorithmik" von Uwe Schöning (ISBN-10: 3827410924) wird aufgeziegt, dass dem Dijkstra Algorithmus eine Matroid-Struktur zugrunde liegt. (siehe Seite 195)

Man kann eine Matroidstruktur auch damit beweisen, dass man zeigt, dass die zugrundeliegende Struktur (E, U) (E = Grundmenge von Basen, U = Menge von Teilmengen aus E) den Basisaustauschsatz von Steinitz erfüllt. Beim Dijkstra-Algortihmus wählt man als Grundmenge E die Menge aller zyklenfreien Pfade vom Startknoten aus. U ist dann die Menge aller Teilmengen, die nur Pfade enthalten, die auf verschiedene Endknoten führen. Die Teilmengen in U seien außerdem maximal, d.h. für jeden Endknoten befindet sich ein Pfad in der Teilmenge. Pfade lassen sich nun zwischen Teilmengen austauschen und der Austauschsatz ist somit erfüllt. Damit ist die Struktur ein Matroid. Der Satz von Steinitz ist im Artikel bereits angesprochen (siehe Basen).

Alternative Definition

Hallo, mir ist in einem Skript zur Graphentheorie (leider nicht in elektronischer Form verfügbar) eine alternative Definition insbesondere der Austauscheigenschaft begegnet, die ich hier zur Diskussion stellen will. Ich stelle die Definition als Ganze, jedoch in eigenen Worten zusammen:

• E sei endliche Menge.
• J sei Teilmenge der Potenzmenge von E.

Dann heißt M = (E, J) Matroid gdw. folgende Bedingungen erfüllt sind.

• J ist nach unten ⊆-abgeschlossen, d. h. jede Teilmenge einer zu J gehörenden Menge gehört ebenfalls zu J.
• Man betrachtet nun eine Teilmenge A ⊆ E. Sodann holt man sich zwei Teilmengen I, I' aus J, die ⊆-maximal in A sind, d.h. es gibt keine andere Teilmenge I' ', die Teilmenge von A ist und gleichzeitig Obermenge von I oder I'. Dann haben I und I' die gleiche Zahl von Elementen.

Ist diese Definition äquivalent mit der im Artikel gegebenen? --Mkleine 22:33, 18. Sep. 2007 (CEST)

Ja, wenn $J\neq \emptyset$ vorausgesetzt wird. Die zweite Bedingung entspricht der Austauscheigenschaft, ist aber m.E. nicht einfacher, weil neben den Mengen $I,I'$ und $E$ noch die Teilmenge $A\subseteq E$ drin vorkommt. --HeikoTheissen 08:50, 26. Jun. 2008 (CEST)

Alternative und einfachere Beschreibung der Rangfunktion

Hallo, ich habe eine alternative Beschreibung der Rangfunktion formuliert. Die formale Notation stammt aus einem Skript, die natürlichsprachliche Erläuterung habe ich selbst notiert. Mit der aktuellen Beschreibung der Rangfunktion im Artikel habe ich so meine Probleme, die folgende Formulierung finde ich viel einfacher:

Die Rangfunktion eines Matroids M = (E, J) liefert für eine beliebige Teilmenge A ⊆ E die Kardinalität der größten Teilmenge aus A, die auch Element von J ist. Formal:

rang A = max{|X|: X ⊆ A UND X ∈ J}

Was meint ihr? --Mkleine 22:44, 18. Sep. 2007 (CEST)

Hab's aufgenommen. --HeikoTheissen 18:42, 25. Jun. 2008 (CEST)

Neubearbeitung

Hallo, ich habe den Artikel einmal komplett überarbeitet. (Wie oft kommt es in solchen Fällen vor, dass exakt soviele Zeichen hinzugefügt wie gelöscht werden?^^) Die ursprüngliche Motivation war eine präzisiere Formulierungen der definierenden Bedingungen der vorkommenden Mengensysteme und Funktionen (unabhängige Mengen, Basen, Kreise, Rangfunktion und Hüllenoperator) mit TeX. Dabei habe ich auch gleich die Gelegenheit genutzt (meiner Meinung nach) missverständlich oder redundant formulierte Passagen zu straffen und generell für eine einheitlichere Notation zu sorgen (bei Quellenangaben etc.).

A propos Quellen: Da bereits sehr viel Literatur für den Artikel angegeben wurde habe ich mich mit neuen Einzelnachweisen sehr zurück gehalten und mich ausschließlich auf die aktuelle Quellenlage gestützt. Dies führte aber zu der möglicherweise unbefriedigenden Situation, dass die Auswahl der drei einzeln nachgewiesener Aussagen aus der Gesamtheit aller aufgestellten Behauptungen sehr willkürlich wirkt. Sollte jemand den Wunsch verspüren die übrigend Zusammenhänge ebenfalls mit Einzelnachweisen auszustatten steht ihm/ihr das natürlich frei.

--84.19.199.179 12:38, 8. Mär. 2013 (CET)

Duale Matroide erwähnt trotz fehlender Definition

Der Abschnitt "Matroide und Hyperebenen" erwähnt duale Matroide, obwohl sie nirgendwo definiert noch verlinkt sind. --Heinrich Puschmann (Diskussion) 23:51, 26. Sep. 2015 (CEST)

Hyperebenenaxiome

Ist die im Artikel gegebene Definition

(H2) $\forall H_{1};H_{2}\in {\mathcal {H}}\colon (H_{1}\neq H_{2})\Rightarrow (H_{1}\subsetneqq H_{2})$

wirklich korrekt?

Darunter steht noch ein Kommentar, den man beachten sollte. Es geht darum, dass zwei verschiedene Hyperebenen selbstverständlich niemals ineinander enthalten sind. Hyperebenen sind ja in einem Matroid genau die maximalen echten Unterräume.

--Schojoha (Diskussion) 20:23, 12. Nov. 2018 (CET)

Nachtrag: Hallo, Sanitiy! Das mathematische Zeichen "\subsetneqq " ist natürlich falsch. Was du vermutlich meintest! Ich habe es korrigiert. Also Danke für den Hinweis.

Noch zwei Bitten:

1. Bitte künftig immer alle Diskussionsbeiträge mit 2-mal "-" und 4-mal "~" abzeichnen! Dann sieht man im Kontext, wer wann was gesagt hat. Sehr wichtig bei längeren Diskussionen!

2. Bitte künftig exakt sagen, was du meinst! So schüchtern vorgetragene Anfragen der obigen Art helfen oft nichts, weil der Angesprochene erst einmal nicht weiß, was los ist. Höfliche Direktheit spart Zeit. Ich habe oben erst beim zweiten Hinsehen gemerkt, worum es dir ging.

--Schojoha (Diskussion) 22:26, 13. Nov. 2018 (CET)

Einführende Beispiele

Müsste das nicht "Beispiel für ein Vektormatroid" heißen (weiter oben steht ja, dass das Wort Matroid ein Neutrum ist...)? Mir gefällt auch nicht, dass in den beiden Bedingungen für nicht unabhängige Mengen die Möglichkeit einer Linearkombination nicht deutlicher erwähnt wird. So entsteht der Eindruck, etwa die Menge {b,c,d} sei nicht abhängig, denn keiner der Vektoren ist ein Vielfaches eines anderen. Drittens sind die inklusionsmaximalen Elemente in I genau die Basen des von E erzeugten Vektorraums - es ist ja nirgends vorausgesetzt, dass E ein Erzeugendensystem von V ist. (nicht signierter Beitrag von KühnSte (Diskussion | Beiträge) 09:20, 21. Okt. 2020 (CEST))