Mathematik: Was ist ein Matroid?
Released by matroid on Di. 10. Juni 2003 17:52:41 [Statistics]
Written by matroid - 18451 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\) Symbol der Fano-Ebene

Schon vor 2 Jahren hatte ich einen Artikel
'Was ist ein Matroid' geschrieben, der mir
heute aber nicht mehr gefiel.
Hier ist eine überarbeitet und erweiterte Fassung. Ich werde erklären, was ein Matroid ist, warum
man sich damit beschäftigt und der Frage
nachgehen, in welchem Sinne Matroide nützlich sind. define(M, \big\M) define(E, \big\E) define(I, \big\I) Definition__: Ein Matroid \M=(\E\,\I) ist eine mathematische Struktur, in der \E eine endliche Menge ist und \I eine Familie von Teilmengen von \E, so daß gilt: \ll(M1)\0\el\I, und jede Teilmenge einer zu \I gehörenden Menge gehört ebenfalls zu \I. \ll(M2)(Austauschaxiom) Sind I_p und I_(p+1) Mengen aus \I mit p bzw. p\+1 Elementen, dann gibt es ein Element x\el\ I_(p+1)|\\ I_p\., so daß I_p\union\menge(x)\el\I. Die Elemente von \I nennt man unabhängige__ Mengen von \M. Eine Teilmenge von \E, die nicht in \I ist, heißt abhängig__. Eine mengentheoretisch maximale, unabhängige Menge in \I ist eine Basis__. Eine mengentheoretisch minimale, abhängige Menge ist ein Kreis__. \big\Beispiel: graphische Matroide Sei nun \G=(K,E) ein Graph. K die Menge der Ecken (engl. knots) und E die Menge der Kanten (edges). Die Menge der Kanten ist in einem Graphen eine Menge von Paaren von Elementen aus K. Man nennt E die Inzidenzrelation auf K, weil E angibt, welche Ecken aus K (durch eine Kante) zueinander in Beziehung stehen (miteinander verbunden sind = inzident sind). Wenn wir für einen Graphen \G die Menge \I als Menge der Teilmengen von E definieren, die keine Kreise enthalten, dann ist \M(\G)=(\E,\I) ein Matroid. Die Menge \I erfüllt Axiom \ref(M1), denn jede Teilmenge von \I enthält ebenfalls keinen Kreis in \G, gehört also auch zu \I. Insbesondere enthält die leere Kantenmenge keine Kreise.




Das sog. Austauschaxiom besagt, daß man in zwei verschieden mächtigen
Mengen von Kanten, die kreisfrei sind, ein Element "austauschen" kann.
Man kann in der p\+1\-elementigen, kreisfreien Kantenmenge eine Kante
finden und zu der p\-elementigen kreisfreien Menge hinzutun, und das
Ergebnis ist wieder eine kreisfreie Kantenmenge in \G.


Graphen geben ein sehr anschauliches Beispiel für Matroide \- und die
Austauscheigenschaft ist in der Graphentheorie und kombinatorischen
Optimierung eine viel genutzte Eigenschaft.
Die meisten Optimierungsalgorithmen basieren gerade darauf, daß man
mit einer kreisfreien Kantenmenge beginnt (z.B. der leeren Menge) und
diese durch Hinzunahme von anderen Kanten solange erweitert, wie das
ohne die Kreisfreiheit zu verletzen, noch geht.
(Beispiel: Suche nach einem aufspannenden Baum.)

Das Analoge gilt auch für Basen eines endlich dimensionalen Vektorraums.
\Das Axiom \ref(2) ist dort als Basisaustauschsatz bekannt.
\big\Nutzen der Matroid-Theorie

Matroide abstrahieren von konkreten (konkreteren) Strukturen wie Graphen
oder Vektorräumen.
Die Definition des Matroids reduziert einen Graphen oder Vektorraum auf einen abstrakten Kern. Dieser Kern beinhaltet gewisse Regeln, nach denen Graphen und auch Vektorräume 'funktionieren'.

Diese (und noch andere, bisher nicht erwähnte) Strukturen, die so verschieden erscheinen, sind eng verwandt. Man kann eine Vielzahl von Sätzen und Aussagen, die man von Graphen oder Vektorräumen kennt, schon dann beweisen, wenn man nur die Matroid\-Eigenschaften dieser Objekte voraussetzt.

Bekannt ist z.B., daß alle Basen eines Vektorraums gleiche Mächtigkeit haben.
Bekannt ist auch, daß alle aufspannenden Bäume eines Graphen gleich viele Kanten enthalten.

Beide Ergebnisse lassen sich zusammenfassen als:

\light\Satz 1: Alle Basen eines Matroids \M haben gleiche Mächtigkeit.

Beweis__ (Satz 1):
Nach \ref(M2) kann es nicht zwei verschiedene maximal unabhängige Mengen mit verschiedener Elementzahl geben. Wenn dem nämlich so wäre, dann könnte man gemäß \ref(M2) ein Element in der größeren Menge finden, das zur kleineren Menge hinzufügen \- und das Ergebnis wäre unabhängig.
Ein Widerspruch zur Annahme, daß die kleinere Menge bereits maximal unabhängig war.
\stress\qed.

Durch die einheitliche Betrachtung von Strukturen, die Matroide sind, ergibt sich die Chance, bekannte Ergebnisse aus einem konkreten Problemtyp auf ein anderes (bisher nicht so gut erforschtes) Problem zu übertragen.

Wir wissen, wie man in Vektorräumen eine Basis findet.
In Graphen, die als Matroid gesehen werden, und darum \ref(M1) und \ref(M2) erfüllen, kann man daher einen aufspannenden Baum finden, indem man ausgehend von irgendeiner kreisfreien Kantenmenge, solange Kanten hinzunimmt, wie das ohne einen Kreis zu erzeugen noch möglich ist.
Das funktioniert hier genau so, wie es bei Vektorräumen funktioniert \- sogar besser, denn Graphen sind endliche Strukturen \- man kann wirklich alle Kanten durchgehen.

Bei dieser Verfahrensvorschrift, also: 'Starte mit irgendeiner erlaubten Menge, und nimm hinzu, solange es geht', muß man sich überlegen, ob man nicht falsch hätte beginnen können - und schließlich in einer Sackgasse landet, d.h., bei einer Menge, die man nicht mehr vergrößern kann, die aber dennoch keine Basis ist.
Im Bereich der Linearen Algebra hat man das für Vektorräume schon getan.
Auch dort ist das Argument: "Weil alle Basen gleich viele Elemente haben, kann das nicht vorkommen."

\big\Matroide sind konkret überflüssig

Ergebnisse, die man nur mit den Matroid\-Eigenschaften beweisen kann, gelten in allen konkreten Strukturen, die Matroid sind, und die Schlußweise ist immer die gleiche.

Matroide bilden aber eine Brücke zwischen Problemen einer Art zu Problemen einer anderen Art. Egal, wie das Problem ausgestaltet ist, sobald man erkennt, daß dem Problem eine Matroid\-Struktur zugrundeliegt, kann man unmittelbar das ganze vorhandene Wissen übertragen und anwenden.

\big\Nicht\-graphische Matroide

Nicht alle Matroide sind 'graphisch' (d.h. stammen von einem Graphen ab) oder 'matrisch' (d.h. stammen von einem Vektoraum ab).

Beispiel__ eines nicht graphischen Matroids:
Sei E=menge(1\,2\,3\,4). Sei I die Menge aller Teilmengen von E mit höchstens zwei Elementen.
(E\,I) ist ein Matroid, und die zweielementigen Mengen aus I sind Basen.
makro(über,\mixoff\small array(%1;%2))
define(u42,\big\U||über(2,4))
Dieser Matroid ist der sog. 'gleichförmige Matroid' \u42 ('U' für 'uniform').

Satz__: \u42 ist nicht graphisch.
Beweis__: In \u42 sind alle dreielementigen Kantenmengen Kreise.
Zeichne zuerst den Kreis aus den Kanten 123 auf (sieht aus wie ein Dreieck).
Aber auch 124 ist ein Kreis, und man ist gezwungen die Kante 4 mit den gleichen Ecken wie die Kante 3 zu verbinden.
Dann ist aber 34 auch ein Kreis. Das darf aber nicht sein, denn in \u42 ist jede zweielementige Menge unabhängig.
\stress\qed.

\Für einen graphischen Matroid (E\,I) kann man im allgemeinen mehrere Graphen finden, deren kreisfreie Kantenmengen gleich I sind.
Beispiel: E=menge(1\,2\,3) und I=menge({}, {1}, {2}, {3}, {1,3}, {2,3})

Demnach müssen die Kanten {1,2} einen Kreis bilden. Zeichne ihn auf's Papier.
Man hat die freie Wahl, wo man die Kante 3 einzeichnen möchte.
An der einen oder der anderen Ecke des Kreises 12 oder sogar unzusammenhängend irgendwo, als isolierte Kante.

Einen Graphen als Matroid zu betrachten ist damit zu vergleichen, den \IR^n als topologischen Raum zu betrachten.
Auch dabei gehen Eigenschaften verloren. In der algebraischen Topologie kennt man noch Gebiete und kann von Konvergenz sprechen, aber die Längen, Flächenmaßzahlen und Winkelgrößen spielen keine Rolle mehr.

\big\Ein nicht graphischer, nicht matrischer Matroid

\small (Dieser Abschnitt wird überarbeitet.)


Matroide? Ein Fazit

Ich habe mir eine Fortsetzung dieses Artikels vorgenommen.

Leider sehe ich im Moment keinen Weg, wie man einerseits schnell auf einen Punkt kommt und andererseits Matroide wirklich benötigt. Mindestens fast alle praktischen algorithmischen Probleme sind in einer Formulierung für Graphen oder Vektorräume weit griffiger und - soweit befriedigend gelöst - auch angemessen dargestellt und gelöst.

Darüber hinaus gibt es sehr wohl Probleme, die zwar mit Matroiden, aber weder durch Graphen noch Vektorräume beschrieben werden können. Allerdings gibt es auch dafür konkretere Theorien. Man kann Zuordnungs- und Partitionierungsprobleme auch jeweils im originären Kontext betrachten und hat das längst getan. Man kann z.B. Tennisturniere oder magische Quadrate mit Hilfe von 'Block-Designs' und 'Galois-Ebenen' beschreiben und deren Lösbarkeit und Lösungsvielfalt bestimmen.
Allerdings sind Galois-Ebenen auch Matroide.

In meiner lange zurückliegenden Diplom-Arbeit habe ich mich mit 'Flußproblemen in Matroiden' beschäftigt. Matroide gestatten eine Beschreibung solcher Probleme und die Charakterisierung der Lösbarkeit.
Zum damaligen Zeitpunkt lieferte die Matroid-Theorie aber keine neuen Verfahren, mit denen praktische Probleme besser als vorher zu behandeln gewesen wären.
Ergebnisse der Theorie waren Charakterisierungssätze wie:

"Ein bestimmtes Flußproblem in einem Matroid ist lösbar, wenn der Matroid keinen zur Fano-Ebene isomorphen Untermatroid ('Minor') enthält.

Die Fano-Ebene hat 7 Punkte und je 3 Punkte auf einer Geraden. Mit der Menge der Kreise definiert als die Punktmengen, die entweder genau alle Punkte einer Geraden enthalten, oder genau das Komplement einer Geraden sind, bildet F7 einen Matroid. Die Abbildung am Anfang zeigt, wie man sich eine Fano-Ebene veranschaulicht.

Nun ist der Aufwand einen Matroid auf einen solchen Minor zu testen in der gleichen Größenordnung, wie das ursprüngliche Problem zu lösen.
Zudem enthalten praktische Probleme eher keine Teilprobleme die isomorph zu einer endlichen projektiven Ebene sind.

Mein Fazit: Matroide sind theoretisch hochinteressant, weil sie so vieles vereinen, sie vereinfachen aber nichts.

Ich lasse mich aber gern eines besseren belehren.

Matroid 2003

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Graphentheorie :: Reine Mathematik :
Was ist ein Matroid? [von matroid]  
Schon vor 2 Jahren hatte ich einen Artikel 'Was ist ein Matroid' geschrieben, der mir heute aber nicht mehr gefiel.Hier ist eine überarbeitet und erweiterte Fassung. Ich werde erklären, was ein Matroid ist, warum man sich damit beschäftigt und der Frage nachgehen, in welchem Sinne Matroide nützlich sind.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 18451
 
Aufrufstatistik des Artikels
Insgesamt 4631 externe Seitenaufrufe zwischen 2012.01 und 2023.01 [Anzeigen]
DomainAnzahlProz
https://google.com260.6%0.6 %
https://google.de273259%59 %
https://google.at10%0 %
https://www.startpage.com691.5%1.5 %
http://google.de120426%26 %
https://google.no2024.4%4.4 %
https://www.bing.com761.6%1.6 %
https://duckduckgo.com721.6%1.6 %
http://google.ru461%1 %
https://www.ecosia.org420.9%0.9 %
http://google.hu410.9%0.9 %
http://google.it451%1 %
http://google.nl200.4%0.4 %
https://www.qwant.com80.2%0.2 %
https://startpage.com80.2%0.2 %
https://www.qoq-de.com50.1%0.1 %
http://google.es30.1%0.1 %
https://html.duckduckgo.com30.1%0.1 %
https://de.search.yahoo.com20%0 %
https://engine.presearch.org10%0 %
http://www.bing.com110.2%0.2 %
http://suche.t-online.de20%0 %
https://tab.gladly.io10%0 %
http://de.yhs4.search.yahoo.com10%0 %
http://search.conduit.com10%0 %
https://search.becovi.com10%0 %
http://int.search.myway.com10%0 %
https://swisscows.com10%0 %
https://lite.qwant.com10%0 %
https://bing.com10%0 %
https://cse.google.de10%0 %
http://r.duckduckgo.com10%0 %
https://suche.t-online.de10%0 %
http://sm.de10%0 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 26 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2023.01.02-2023.01.27 (26x)https://google.com/

Häufige Aufrufer in früheren Monaten
Insgesamt 4556 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2022 (2376x)https://google.de/
2013-2020 (545x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (351x)https://google.de/url?sa=t
202006-06 (202x)https://google.no/
2012-2013 (106x)http://google.de/url?sa=t&rct=j&q=was ist ein matroid
201305-08 (95x)http://google.de/url?sa=t&rct=j&q=matroide graphen
201501-02 (87x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCAQFjAB
2020-2022 (70x)https://www.bing.com/
2020-2022 (68x)https://www.startpage.com/
2020-2022 (65x)https://duckduckgo.com/
201202-02 (46x)http://google.ru/url?sa=t&rct=j&q=alle teilmengen eines matroiden beispiel
201206-06 (42x)http://google.de/url?sa=t&rct=j&q=zeige ist ein matroid
201211-11 (41x)http://google.de/url?sa=t&rct=j&q=was ist ein matroid?
2020-2022 (40x)https://www.ecosia.org/
2014-2016 (38x)http://google.de/url?sa=t&rct=j&q=matroid beispiel
201407-07 (38x)http://google.de/url?sa=t&rct=j&q=uniformes matroid graphisches matroid
201210-10 (37x)http://google.de/url?sa=t&rct=j&q=uniformes matroid basen
201304-04 (27x)http://google.hu/url?sa=i&rct=j&q=
201503-03 (26x)http://google.it/url?sa=t&rct=j&q=matroide
201207-07 (22x)http://google.de/url?sa=t&rct=j&q=was ist matroid
201505-05 (22x)http://google.de/url?sa=t&rct=j&q=uniforme matroid beispiel
201412-12 (22x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCIQFjAB
201506-06 (21x)http://google.de/url?sa=t&source=web&cd=1&ved=0CB0QFjAAahUKEwjw9duQwJbGAhUqnn...
2013-2015 (21x)http://google.de/url?sa=t&rct=j&q=matroide
201311-11 (20x)http://google.nl/url?sa=t&rct=j&q=
201212-12 (19x)http://google.de/url?sa=t&rct=j&q=uniformes matroid
201301-01 (19x)http://google.de/url?sa=t&rct=j&q=was ist ein matroids
201204-04 (19x)http://google.it/url?sa=t&rct=j&q=matroid was ist das
201404-04 (15x)http://google.de/url?sa=t&source=web&cd=1&ved=0CCoQFjAA
201504-04 (14x)http://google.hu/search?source=hp&q=u42 matroid
2021-2022 (8x)https://www.qwant.com/
2020-2022 (8x)https://startpage.com/
201205-05 (8x)http://google.de/url?sa=t&rct=j&q=matroidtheorie
2020-2021 (7x)https://duckduckgo.com
2020-2021 (6x)https://www.bing.com/search?q=matroide
202006-07 (5x)https://www.qoq-de.com/

[Top of page]

"Mathematik: Was ist ein Matroid?" | 10 Comments
The authors of the comments are responsible for the content.

Re: Was ist ein Matroid?
von: Ex_Mitglied_40174 am: So. 08. Juni 2003 22:58:33
\(\begingroup\)Einsame Klasse der Artikel!
Also, ganz toll!
Klatsch, klatsch klatsch.\(\endgroup\)
 

Re: Was ist ein Matroid?
von: Ex_Mitglied_40174 am: Di. 10. Juni 2003 22:03:02
\(\begingroup\)Eine Basis sollte als *mengentheoretisch* maximal unabhaengige Menge definiert werden, nicht als *kardinal* maximal unabhaengige Menge.

Mit der Definition im Artikel ist Satz 1 trivial.\(\endgroup\)
 

Re: Was ist ein Matroid?
von: matroid am: Di. 10. Juni 2003 23:19:06
\(\begingroup\)Ja, wie offensichtlich. Ich ändere das.

Gruß
Matroid\(\endgroup\)
 

Re: Was ist ein Matroid?
von: Martin_Infinite am: So. 01. August 2004 14:40:35
\(\begingroup\)Hi Matroid,

ich habe den Artikel mal wieder überflogen, nachdem ich mich mit Unabhängigkeitsstrukturen im Lüneburg beschäftigt habe, und stelle dazu keinen Unterschied fest. Allerdings kenne ich nur die algebraische Seite dahinter, du hast hier auch eie graphentheoretische beleuchtet.

Du schreibst am Ende

Mein Fazit: Matroide sind theoretisch hochinteressant, weil sie so vieles vereinen, sie vereinfachen aber nichts.

Damit gebe ich dir völlig Recht. Es ist aber auch hochspannend, wenn man sich schon vorher mit Matroiden beschäftigt hat, ohne es zu wissen, und dann in die Theorie eintaucht und Gemeinsamkeiten zwischen den bekannten Objekten hergestellt werden.

Aber dass sie nichts vereinfachen, will ich eigentlich nicht sagen. Das wäre ja fast analog dazu, dass der Begriff des Ringes nichts vereinfacht, weil man da ja auch immer dieselben Eigenschaften hat, und die Objekte mit diesen Eigenschaften Ringe nennt.

Ich will damit sagen, dass es gerade so typisch für die Mathematik ist, ähnliches zusammenzufassen, und der Begriff des Matroids ist nichts als eine weitere Zusammenfassung, mit der man alle Objekte mit den charakteristischen Eigenschaften gleichzeitig untersuchen kann.

Doch Matroide sind besonders: Erst mal, weil sie deinen Namen tragen :D, und dann noch, weil ihre Definition so allgemein ist, dass Beispiele extrem vielfältig sind und aus so vielen Bereichen der Mathematik kommen, wie ich es noch nie vorher gesehen habe, bis eines Tages ZAOS mit seiner hyperallgemeinen Kategorientheorie ankam :D

Gruß
Martin


\(\endgroup\)
 

Re: Was ist ein Matroid?
von: jannna am: Do. 06. April 2006 18:33:29
\(\begingroup\)hallo Matroid Ein interessanter Artikel. Es gibt aber sehr wohl unendliche Graphen 😉 (Es gibt sogar Sätze über Graphen, die sich in der Unendlich-Version viel leichter beweisen lassen.) Grüße Jana\(\endgroup\)
 

Re: Was ist ein Matroid?
von: jannna am: Do. 11. Mai 2006 12:37:40
\(\begingroup\)Hallo nochwas 😉 Der Greedy-Algorithmus wäre vielleicht noch interessant gewesen oder? Grüße Jana\(\endgroup\)
 

Re: Was ist ein Matroid?
von: Martin_Infinite am: Do. 11. Mai 2006 16:43:33
\(\begingroup\)@Jana: Wie wäre es mit einer Fortsetzung von dir? 😄 \(\endgroup\)
 

Re: Was ist ein Matroid?
von: Salserito am: Fr. 16. April 2010 10:35:43
\(\begingroup\)Hallo ein sehr guter Artikel, der alle die Fragen beantwortet hat, die ich mir durch die Axiomatische Definition gestellt habe. Leider wurde das in unserem Buch 'Diskrete Mathematik' nicht annähernd 'diskutiert'. Gruß Salsa 😄 \(\endgroup\)
 

Re: Was ist ein Matroid?
von: Ex_Mitglied_40174 am: Do. 13. Februar 2014 21:55:28
\(\begingroup\)Hey! auch von mir ein herzliches Danke! Mir hat der Artikel sehr weitergeholfen. Die (bei uns) zugehörige Vorlesung war leider nicht annähernd so verständlich und logisch aufgebaut. Gruß Gurs \(\endgroup\)
 

Re: Was ist ein Matroid?
von: Ex_Mitglied_40174 am: Sa. 28. Februar 2015 00:03:30
\(\begingroup\)Hallo, ich habe eben den Artikel gelesen und er hat mir gut gefallen und Verständlich war er auch, jedoch wollte ich zwei Dinge erfragen/vorschlagen: a.) Du sprichst von zwei Knoten als "Inzident" wenn sie durch eine Kante verbunden sind. Nun ist aber laut meinem Uniskript und einem Buch über Diskrete Mathematik was mir vorliegt, die Inzidenz nur für Knoten/Kante definiert und die Nachbarschaft im Graphen heisst Adjazenz. Ist das gewollt,bzw. sind hier andere Definitionen üblich? b.) Das Zweite ist nur, dass es meines Wissens im Englischen üblich ist die Knoten im Graphen "vertices"(bzw "node", daher vielleicht die Verwechselung) zu nennen, weil ein "knot" ein tatsächlicher Knoten im Sinne von Verknotung eines Seils ist und solche Knoten ja durchaus in der Topologie eine Rolle spielen. Ich will nicht klugscheissen ich dachte mir nur ich mach dich vielleicht auf ein mögliches Missverständniss(?) aufmerksam, Danke nochmal für den informativen Artikel, m.\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]