Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Freitag, 24. März 2017 09:07 

Artikel zu dem Thema:

Diskrete Mathematik


Thema durchsuchen:   

Startseite | Thema auswählen ]


Einführung in die Theorie der Matroide (Mathematik)
mehr... (42 mehr Zeichen) Druckoptimierte Version Diesen Artikel an einen Freund senden Kommentare (0) 7211 mal gelesen

Die Theorie der Unabhängigkeitssysteme wurde bereits Anfang der 1930er Jahre von B.L. van der Waerden in seiner legendären zweibändigen Reihe Moderne Algebra behandelt; allerdings von einer rein algebraischen Warte aus. Im September des Jahres 1934 publizierte die American Mathematical Society eine Arbeit von Hassler Whitney mit dem Titel On the Abstract Properties of Linear Dependence. Diese Arbeit markiert die eigentliche Geburtsstunde der Theorie der allgemeinen Unabhängigkeitssysteme. Hassler Whitney schlug damals den Namen „Matroid“ vor, da er allgemeine Unabhängikeitssysteme mit Hilfe von Matrizen (oid [zu griech. -oiedes = ähnlich]) definierte.

Im zweiten Abschnitt Präliminarien werden wir die wichtigsten Definitionen und Sätze aus der linearen Algebra, der Graphentheorie und der Mengenlehre wiederholen. Im darauffolgenden Abschnitt Matroide wird der zentrale Begriff des gesamten Dokuments definiert und veranschaulicht. Dazu behandeln wir die erste wichtige Klasse von Matroiden, die so genannten Vektormatroiden. Ein wesentliches Charakteristikum von Matroiden ist, dass diese auf viele äquivalente Arten definiert werden können (sie sind kryptomorph). Im vierten Abschnitt werden wir die einige davon kennenlernen. Im vorletzten Abschnitt werden wir ein, nicht nur für die Matroidtheorie, wichtiges Prinzip kennenlernen – die Dualität. Schließlich untersuchen wir noch im letzten Abschnitt, wie Verbände und Matroide zusammenhängen.

Im Einzelnen werden behandelt:
  • Lineare Unabhängigkeit: Definition, Herleitung und äquivalente Chrakterisierung, überflüssige Vektoren, Reduzierung, Beweis.
  • Graphentheorie: kartesische (direkte) Produkt, Menge der geordneten Paare von Elementen, erste und zweite Element, ungeordnete Paare, ungerichteter Graph, Knoten, Kanten, Kanteninzidenzabbildung, Knoten v und Kante k heißen inzident, Adjazenz für Knoten und Kanten, Knotengrad, Kantengrad, Knoten- bzw. Kantengradabbildung, Schlinge, parallele Kanten, einfacher Graph, Beispiele, Kantenfolge der Länge n, verbindbar, zusammenhängend oder verbunden, unzusammenhängend, Untergraph oder Teilgraph, erzeugte Untergraph, Kograph, Komponente, Rang, Kantenzug, Kantenweg oder kurz Weg, geschlossene Kantenfolge, geschlossener Kantenzug, Kantenkreis oder kurz Kreis, Baum, maximal kreislos, minimal zusammenhängend.
  • Ordnungen und Verbände: Teilordnung, Halbordnung, partieller Ordnung oder Ordnungsrelation, Reflexivität, Antisymmetrie, Transitivität, halbgeordnete Menge, vergleichbar, unvergleichbar, total geordnet oder linear geordnet, Trichotomie, Beispiele, maximales Element, minimales Element, obere Schranke von M, untere Schranke von M, nach oben beschränkt, nach unten beschränkt, Infinum, Supremum, Nullelement, Einselement der Halbordnung, Lemma von Zorn, (triviales) Intervall , Atom, Coatom, x bedeckt y, total geordnete Teilmenge, Kette der Länge n, Antikette, unterteilbare Kette, maximale Kette, Höhe eines Elements, Jordan-Dedekindsche Kettenbedingung auf einer Halbordnung, Hasse-Diagramm, Beispiele, Vereinigung und Schnitt (meet and join) auf einer Halbordnung, (vollständiger) Verband, atomarer Verband, Potenzmenge mit Inklusion ist Verband, Boolesche Algebra.
  • Matroide: Definition mit Hilfe der Menge aller unabhängigen Mengen, erblich, hereditär, Ergänzungssatz, unabhängig, abhängig, Beispiele, triviale Matroide, Matroide aus Vektorräumen, Vektormatroiden, Isomorphismus zwischen Matroiden, darstellbare bzw. repräsentierbare Matroide, Beweise, Matrizen, Matrix.
  • Axiomatik der Matroide: Axiome des Basissystems, Basis, Gleichmächtigkeit zweier Basen eines Matroids, Basis-Axiome, durch Basissystem eindeutig bestimmter Matroid, uniforme Matroid, freie Matroid, Axiome des Zirkuitsystems, Kreise eines Matroids, minimal abhängig, Kreis oder Zirkuit, Zirkuitsystem, Länge eines Kreises, graphische Matroide, Beispiele, durch Menge aller Kreise bestimmter Matroid, Kreis-Axiome, schwaches Kreiseliminationsaxiom, starkes Kreiseleminationsaxiom, Fundamentalkreise eines Matroids, Fundamentalkreis zur Basis B und
    dem Element x, Kreismatroide aus Graphen, Kreismatroid oder Polygonmatroid, Axiome der Rangfunktion, lineare Hülle, Abschlussoperator oder Hüllenoperator, extensiv, isoton und idempotent, Rangfunktion eines Matroids, Reduktion von, Löschen von, Rang von, Rangfunktion r ist nicht negativ und subkardinal, sie ist monoton und submodular, Abschlussoperator und die Rangfunktion, durch Rangfunktion eindeutig bestimmter Matroid, Axiome des Abschlussoperators, Steinitz-MacLane-Austauscheigenschaft, Rangfunktion bildet Hüllenoperator, Unterräume, abgeschlossenen Mengen, Punkte, Linien, Ebenen, Hyperebenen, Erzeugendensystem von M, Charakterisierung von Erzeugendensystemen, Basen und Hyperebenen durch den Rang, Restriktion/Reduktion eines Matroids, Kreismatroide und der Abschluss.
  • Dualität und Matroide: Definition und Beispiele, Existenz des „dualen“ Matroiden, Dual von M oder den zu M dualen Matroiden M*, Cobasen, Cokreise, Cohyperebenen, Corang, counabhängig, Attribute eines Duals, Zusammenhang zwischen M und dessen Dual M*, Rangformel für duale Matroide, Clutter und Blocker, Clutter (oder Antikette), komplementären Clutter, Eigenschaften eines Blockers, Clutter und Hyperebenen.
  • Unterraumverbände von Matroiden: Unterräume eines Matroids bilden einen (geometrischen) Verband, Beispiel, Fano-Matroid, Fano-Ebene, projektive Ebene, semimodular.
Geschrieben von Alexander am Donnerstag, 14. Februar 2008 mehr...


Umfrage
Ganz klar, das schönste Ressort der Mathematik ist die

Zahlentheorie
(Lineare) Algebra
Topologie, Maßtheorie, Integrationstheorie
Statistik, Wahrscheinlichkeitstheorie, Stochastik
Analysis, Funktionalanalysis
Funktionentheorie
Kombinatorik, Graphentheorie
Diskrete Mathematik
Lineare Optimierung

Ergebnisse
Stimmen: 660
Kommentare: 0
Umfragen

Login
Benutzername:

Passwort:



Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.074 Sekunden, mit 51 Datenbank-Abfragen