Mathematik: To classify the Uncats - Mehr über Matroide
Released by matroid on Sa. 07. Oktober 2006 19:49:27 [Statistics]
Written by jannna - 3553 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

To classify the Uncats - Mehr über Matroide

Was ist ein Matroid? fragte Matroid einmal und hat dies auch beantwortet. Warum also noch ein Artikel über Matroide? Zum einen würde ich Matroide gern etwas ausführlicher, und zum anderen auch etwas anders vorstellen. Die meisten kennen Matroide sicherlich aus der kombinatorischen Optimierung in Verbindung mit dem Greedy-Algorithmus. Ich möchte eher das theoretische Konzept - als Verallgemeinerung des Abhängigkeitsbegriffs aus der LA - behandeln. Dabei braucht es zum Verständnis aber kein spezielles Vorwissen. Lineare Algebra und Graphentheorie, vielleicht noch etwas Algebra, reichen, denke ich. Zum Einstieg ein nettes Tutte-Zitat:

A TOAST TO MATROIDS - W. T. Tutte

I am asked sometimes what a matroid is. I often revert to our sacred writings and recall the encounter of Alice with the grinning Cheshire cat. At one stage the cat vanishes away, beginning with the tip of its tail and ending with the grin, which persists long after the remainder of the cat. "I expect you saw a lot of loose grins wandering around" said Humpty Dumpty. "Yes, indeed" said Alice. "But with some of them you could see they belonged to cats. I kept trying to imagine what the cats behind them were like." "What an Auslandish thing to do" said Humpty Dumpty. "Oh it's very interesting" said Alice. "I look at the grin and I see the eyes and whiskers and the ears and the warm furry body and the long sinuous tail." "You put it very graphically" said Humpty Dumpty. "But I can't do it with all the grins" said Alice. "Some of them have the most uncatly shapes. Whatever can be behind them?" "That's what makes it interesting" said Humpty Dumpty. "You have to classify the Uncats. It now will be right to describe Each particular batch Distinguishing those that are Fanos and bite From K. Kuratowskis that scratch." "I've heard something like that before" said Alice crossly. "The creatures here all recite far too much poetry." And she stalked angrily away. von hier.

Einführung

Der Begriff "Matroid" wurde 1935 von Whitney eingeführt ("On the abstract properties of linear dependence", American Journal on Mathematics 57 (1935), pp. 509-533). Durch die Definition einer abstrakten Struktur kann man nun Eigenschaften, die ganz unterschiedlichen Objekten gemein sind, erfassen: Was verbindet linear abhängige Mengen von Vektoren eines Vektorraumes und Kreise eines Graphen? Je nachdem, was man sich für Objekte ansieht, bekommt man unterschiedliche, aber äquivalente, Axiomensysteme. Ich werde einige hier vorstellen, deren Äquivalenz aber nicht zeigen. Wir fangen mit der Charakterisierung über unabhängige Mengen an: \ Sei E eine Menge und \calP(E) die Menge der Teilmengen von E. Das Paar M=\(E, \calF\) mit \calF\subseteq \calP(E) heißt Matroid__ auf E, wenn gilt: \ll(F1)\normal\ \calF !=0 \ll(F2)\normal\ F' \subseteq F \in \calF => F' \el \calF \ll(F3)\normal\ zu F', F \in \calF mit \abs(F')<\abs(F) <\infty gibt es ein x \in F-F' mit F' \union\ menge(x) \in \calF \ll(F4)\normal\ F \subseteq E ist in \calF, g.d.w. jede endl. Teilmenge von F es ist. Die Mengen aus \calF(M):=\calF heißen unabhängige Mengen von M, die aus \calP(E)- \calF sind die abhängigen Mengen. Meine Definition hier scheint die gleiche zu sein wie Matroids, abgesehen vom zusätzlichen Punkt \ref(F4). Der wesetliche Unterschied, der auch die Existenz von \ref(F4) erfordert, ist die nichtnotwendige Endlichkeit der Grundmenge E. Matroid hat die Endlichkeit gefordert, ich tu das nicht. Allerdings werde ich mich auf abzählbare Mengen beschränken. Später werden wir die Grenzen der Unendlichkeit kennenlernen ;\-) bzw. wir kommen zu einem Punkt an dem es nur noch mit endlichen Matroiden weitergeht... Die Eigenschaft \ref(F3) grenzt die Matroide unter den abstrakten Simplizialkomplexen (\ref(F1), \ref(F2)) endlichen Charakters \( \ref(F4)\) ab. \stress\big\ array(Ein fundamentales Beispiel)__: Matroide aus Vektorräumen Sei V ein Vektorraum über dem Körper K und \small\(a_i )_(i\in E) \normal\ eine Familie von Elementen aus V. Dann ist \darkred\M:=M\(\small\(a_i )_(i\in E) \normal\):=(E,\calF) \black\mit \darkred\calF:=menge(J\subseteq E : \small\(a_i \)_(i\in J) \normal\ linear unabhängig) \black\ein Matroid. Hier ist \ref(F3) die einzige nichtoffensichtliche Eigenschaft: \stress\ Beweis__: \normal Seien J, J' \in \calF mit abs(J')= abs(J). \(=> abs(L)>abs(J') und es gibt ein x \in L-J' mit J' \union\ menge(x) \in \calF, da L\in \calF, J' \union\ menge(x) \subseteq\ L und \ref(F2) \) Gäbe es ein j \in J'-L, so währe a_j=sum(\lambda_k a_k , k\in L ,) für gewisse \lambda_k, wobei \lambda_i !=0 für wenigstens ein i \in L-J' wegen J' \in \calF gilt. Währen L-menge(i) \in \calF, kann es (L-menge(i))\union\ menge(j) nach Wahl von L nicht sein. Dann ist aber a_j=sum(\mu_k a_k , k\in L ,) für gewisse \mu_k mit \mu_i=0, so daß 0=a_j-a_j = sum((\lambda_k - \mu_k) a_k , k\in L ,) eine nichttriviale Linearkombination der Null ist => Widerspruch. q.e.d. array(Spezialfall)__: Ist \small\(a_i )_(i\in E) \normal\ die Familie aller Elemente aus V, so ist \darkred\M(V):=(V, menge(X \subseteq\ V : X linear unabhängig))\black\ . \stress\big\ array(Ein weiteres Beispiel)__: Matroide und Matrizen Seien a_1 , ..., a_n die Spalten einer m x n-Matrix A über dem Körper K. Wir fassen\small (a_i )_(i \el \IN_n) \normal\ als Familie von Vektoren des Vektorraums K^m auf. So bestimmt A ein Matroid: \darkred\M(A):=(\IN_n , menge(J\subseteq \IN_n : \small\(a_i \)_(i\in J) \normal\ linear unabhängig)) \stress\big\Bemerkungen__ \ll(*)Der Körper, über dem sich alles abspielt, taucht in der Notation nicht explizit auf. \ll(*)Je nach Charakteristik des Grundkörpers, kann eine menge(0,1)-Matrix unterschiedliche Matroide induzieren (Beispiele später). \ll(*)Invertierbare n x n-Matrizen sind völlig uninteressant, da sie alle das gleiche Matroid, nämlich (\IN_n , \calP(\IN_n)), induzieren. \ll(*)Je verwickelter die Abhängigkeiten der Spalten untereinander sind, umso interessanter wird dabei das Matroid.

Darstellung

\ Zwei Matroide M=(E,\calF), M'=(E',\calF ') heißen isomorph__, falls eine Bijektion \beta : E -> E' existiert, so dass für alle X \subseteq E, X genau dann unabhängig in M ist, wenn \beta(X) unabhängig in M' ist. \stress\ array(Frage:)__ \normal\kann man zu jedem Matroid M auf E einen Körper K, einen K\-Vektorraum und eine Familie \small\ (a_i )_(i \el E) \normal\von Vektoren aus V finden, so dass M isomorph zu M\(\small\(a_i )_(i\in E) \normal\) ist? Ist also die Matroidtheorie eine Kombinatorik in Vektorräumen? Also gibt es immer eine Abbildung \phi : E -> V mit: X \subseteq E ist genau dann unabhängig in M, wenn\small (\phi(x))_(x \el X) \normal\ linear unabhängig in V ist? Ein solches \phi heißt Darstellung__ von M in V über K. Wir werden später ein Matroid sehen, welches keine Darstellung besitzt, egal wie man V und K wählt. Dass man schon bei der Wahl von K vorsichtig sein muss, zeigt: \stress\big\ array(Beispiel)__: r\-uniforme Matroide Für r>=0 ist \calP_(<=r)(E) die Menge der Teilmengen von E mit <= r Elementen. \darkred\U_r,E:=(E,\calP_(<=r)(E))\black\ ist ein bis auf Isomorphie eindeutig durch r und abs(E) bestimmtes Matroid. \darkred\U_r,n:=U_r,\IN_n \black\ heißt array(r\-uniformes Matroid)__ auf n Elementen. Schauen wir uns man an, wie U_2,4 aussieht: E=menge(1,2,3,4) und \calF=menge(\0, menge(1), menge(2), menge(3), menge(4), menge(1,2), menge(1,3), menge(1,4), menge(2,3), menge(2,4), menge(3,4)). Versuchen wir mal eine Darstellung im Vektorraum V über \IZ_2 zu konstruieren: Die \phi(i) sind paarweise linear unabhängig und daher paarw. verschieden und nicht 0. Für i \in menge(3,4) ist \phi(1), \phi(2), \phi(i) linear abhängig. Also lässt sich \phi(i) eindeutig als Linearkombination von \phi(1) und \phi(2) schreiben. Als Koeffizienten können wir 0 und 1 wählen, also gilt: \phi(i)=\phi(1)+\phi(2) und somit \phi(3)=\phi(4) => Widerspruch. Wir kommen später nochmal auf dieses Beispiel zurück. Matroide, die eine Darstellung in einem K\-Vektorraum besitzen, heißen array(K\-linear)__. \IZ_2 \-lineare Matroide heißen auch binär__. Matroide, die über jedem Körper darstellbar sind heißen regulär__. U_2,4 ist also nicht binär, und somit auch nicht regulär. U_2,4 wird später noch eine besondere Rolle spielen.

Basen I

\ Ist M=(E,\calF) so heißt ein maximales Element aus \calF eine Basis__ von M und deren Gesamtheit wird mit \calB(M) bezeichnet. Matroid hat den Satz von der Gleichmächtigkeit zweier Basen für endliche Matroide bewiesen. Er folgt im Wesentlichen aus einer Umformulierung von \ref(F3). Mit \ref(F4) erfüllt die Menge aller unabhängigen Obermengen einer unabhängigen Menge F, geordnet durch \subseteq , die Voraussetzung des Zornschen Lemmas. Somit ist jede unabhängige Menge von M in einer Basis von M enthalten \(eine Verallgemeinerung des Basisergänzungssatzes\). Mittels \ref(F1) folgt, dass M überhaupt eine Basis besitzt und mit \ref(F2) kann man schließen, dass für verschiedene Matroide auf der gleichen Menge die Mengen ihrer Basen verschieden sind. Über Basen ergibt sich eine zweite Möglichkeit der Charakterisierung von Matroiden. Dafür brauchen wir aber den Begriff des Ranges \(der uns noch eine Charakterisierung liefern wird\), dazu später mehr.

Fundamentalkreise

\ Ist B eine Basis von M und x \in E-B, so ist B \union\ menge(x) abhängig. Es enthält eine minimal abhängige Menge, einen sogenannten Fundamentalkreis__ zu B und x. Ein solcher Fundamentalkreis muss x enthalten und nach \ref(F4) endlich sein. Er ist durch x und B sogar eindeutig bestimmt und wird manchmal auch mit C_M(x,B) bezeichnet. Jede minimal abhängige Menge C kann als Fundamentalkreis aufgefasst werden. Ist x \in C, so kann man C-menge(x) zu einer Basis B ergänzen, d.h. eine Basis B wählen, die C-menge(x) enthält. C ist dann der Fundamentalkreis zu B und dem vorgegebenen x. Die minimal abhängigen Mengen eines Matroids werden einfacher seine Kreise__ genannt und mit \calC(M) bezeichnet. Matroide lassen sich über Kreise charakterisieren: \calC \subseteq \calP(E) ist genau dann die Menge der Kreise eines Matroides \darkred\ M:=(E, menge(F\subseteq E : Für alle C \in \calC ist C \nosubset\ F))\black\, wenn gilt: \ll(C1) 0< abs(C)<\infty für jedes C \in \calC \ll(C2) C \nosubset\ C' für C!= C' mit C,C' \in \calC \ll(C3) zu C!=C' \in \calC und x \in C\cut\C' gibt es ein D \in \calC \ll() mit D \subseteq (C\union\C')-menge(x) \ref(C3) bedeutet anschaulich \(man kann sich das durch Venn\-Diagramme veranschaulichen\), dass es zu zwei Kreisen, und einem x aus dem Schnitt, einen dritten Kreis gibt, der in den beiden Kreisen liegt, aber x vermeidet. Aus \ref(C1)-\ref(C3) folgt sogar noch eine stärkere Aussage: \ll(C3') zu C,C' \in \calC, x\in C\cut\C'und y \in C-C' gibt es ein D \in \calC \ll() mit y \in D \subseteq (C\union\C')-menge(x) Es gibt also nicht nur einen Kreis, der in den beiden Kreisen liegt und x vermeidet, man kann auch noch ein y\in C-C' vorgeben, das getroffen wird. \stress\big\ array(Beispiel)__ \normal\ Ist x=sum(\lambda_b b,b\in B,) die eindeutige Linearkombination von x\in V-B durch Elemente der Basis B im VR V, so bilden die b mit \lambda_b !=0 zusammen mit x den Fundamentalkreis von x zu B in M(V). x~y:<=> x=y \or\ x,y \in C für ein C \in \calC(M) definiert eine Äquivalenzrelation auf E. Dabei ist nur die Transitivität nicht einsichtig: Ist x~y und y~z, so wähle Kreise C,C' mit x \in C, z\in C', C\cut\ C' !=\0 so, dass C\union\ C' minimal ist. Ist x \in C' oder z\in C folgt x~z. Andernfalls ist x \in C-C' und z\in C'-C. Wähle nun w \in C\cut\C', nach \ref(C3') gibt es dann ein D \in \calC mit x \in D \subseteq\ C \union\ C' -menge(w). Aus z\in D folgt x~z. Also sei z \notel\ D. Bild \ Wegen D\nosubset\ C \( \ref(C2) \), muss es ein v \in D-C \subseteq\ C' geben, also gibt es wegen \ref(C3') ein D'\in \calC mit z\in D'\subseteq\ C'\union\ D-menge(v). Wegen D' \nosubset\ C', gibt es ein u \in D'-C'\subset\ C. Bild \ Somit gilt: x\in C, z\in D', u\in C\cut\ D' !=\0, aber C\union\ D' \subseteq C\union\ C'-menge(v) => Widerspruch zur Wahl von C und C'. Die Klassen von ~ heißen Blöcke__ des Matroids. Ein Matroid mit höchstens einem Block heißt zusammenhängend__.

Rang

\ Seien X \subseteq\ E und \calD \subseteq\ \calP(E). Dann ist \darkred\ \calD\|X:=\calD\cut\calP(X) \black\ und \darkred\ (E,\calD)\|X:=(X,\calD\|X)\black\ . Das Matroid M=(E,\calF) induziert so neue Matroide, es ist nämlich für X \subseteq E: M\|X=(X,\calF\|X) ein Matroid; die Einschränkung__ von M auf X. Die Einschränkung ist die erste Operation, die es uns nun ermöglicht neue Matroide aus alten zu erzeugen. Sei M=(E,\calF) ein Matroid und B eine Basis von M. Ist B endlich, so setzen wir \darkred\ r(M):=abs(B) \black\ ansonsten \darkred\ r(M):=\infty\black\ . r(M) heißt Rang__ von M und für X \subseteq\ E ist \darkred\ r_M(X):=r(M\|X) \black\ der array(Rang von X in M)__. Die Basen von M\|X, also die maximalen in M unabhängigen Teilmengen von X, heißen array(Basen von X in M)__. r_M(X) ist also die Mächtigkeit einer Basis von X in M, falls diese endlich ist, \infty sonst. Hierdurch wird eine Abbildung, die Rangfunktion__ von M, definiert: r_M : \calP(E)->\IZ_(>=0)\union\menge(\infty) die Eigenschaften von r=r_M sind \ll(R1) r(X)<=r(Y) für alle X \subseteq Y aus \calP(E) \ll(R2) r(X\cut\ Y)+r(X\union\ Y)<=r(X)+r(Y) für alle X,Y \in \calP(E) \ll(R3) r(X)<=abs(X) für alle X \in\calP(E) Ist der Rang von M endlich, gilt außerdem \ll(R4) Zu Y \subseteq\ E existiert ein endliches X \subseteq\ Y mit r(Y)=r(X) Für ein Matroid M endlichen Ranges auf E gilt \calF(M)=menge(X\subseteq\ E : r_M(X)=abs(X)). Es kann also keine zwei Matroide endlichen Ranges auf E mit derselben Rangfunktion geben. Eine Abbildung f: \calP(E)->\IZ_(>=0), die \ref(R1), \ref(R2) und \ref(R4) erfüllt heißt submodulare__ Funktion auf E. Die Rangfunktion eines Matroids endlichen Ranges ist also submodular und erfüllt \ref(R3). Submodulare Funktionen spielen in der Kombinatorik eine wichtige Rolle. Aus jeder submodularen Funktion lässt sich ein Matroid endlichen Ranges gewinnen: Sei also f: \calP(E)->\IZ_(>=0) submodular und \darkred\ \calF(f):=menge(F\subseteq\ E : f(X)>= abs(X) für alle X \subseteq\ F)\black\ . Dann ist \darkred\ M(f):=(E,\calF(f))\black\ ein Matroid endlichen Ranges auf E und seine Rangfunktion ist r_(M(f))(X)= min(,menge(abs(X), f(Z)+abs(X-Z) : Z\subseteq\ X)) für alle X \subseteq\ E Im Fall f(\0)=0 ist r_(M(f))(X) = min(, menge(f(Z)+abs(X-Z) : Z\subseteq\ X)) für alle X \subseteq\ E Der Beweis, dass M(f) ein Matroid und r_(M(f)) die zugehörige Rangfunktion ist, ist sehr lang und schwierig.

Basen II

\ \calB ist genau dann die Menge der Basen eines Matroids M endlichen Ranges auf E, wenn gilt: \ll(B1)\calB != \0 \ll(B2)abs(B)< \infty für alle B\in \calB \ll(B3)Zu B, B' \in\calB und x\in B-B' gibt es ein y\in B'-B mit (B-menge(x))\union\ menge(y) \in \calB \stress\big\ array(SATZ)____ \normal\ Je zwei Basen eines Matroids haben die gleiche Mächtigkeit.

Kanonische Darstellung

\ Ein Matroid endlichen Ranges besitzt genau dann eine Darstellung in irgendeinem Vektorraum über K, wenn es eine Darstellung in dem kanonischen Vektorraum K^r über K besitzt, bzw. genau dann ist ein Matroid M auf einer endlichen Menge E K-linear, wenn es eine r(M) x abs(E)-Matrix A über K gibt, so dass M isomorph zu M(A) ist. Jetzt können wir nochmal zeigen, dass U_2,4 nicht binär ist, andernfalls könnte man nämlich eine 2x4-Matrix über \IZ_2 angeben, deren Spalten paarweise verschieden und ungleich Null sind: (1,0,1,?;0,1,1,?) Das geht natürlich nicht. ( \IZ_2)^2 ist sozusagen zu klein für U_2,4. \stress\big\ array(Beispiele)__: Fano\- und non\-Fano Matroid Das Fano\- und das non\-Fano Matroid sind wichtige Beispiele. Sei (a_1, ... , a_7) die Familie von Vektoren aus \IZ_3^3 die an keiner Stelle eine -1 aufweisen. \ll(Fano-Matroid)\darkred\ F_7 := M(\IZ_2^3 - menge(0)) \black\ \ll(non-Fano-Matroid)\darkred\ F_7^(-) := M((a_1, ..., a_7)) \black\ Sowohl F_7, als auch F_7^(-) lassen sich darstellen durch die Matrix (1,1,0,0,1,0,1;0,1,0,1,0,1,1;0,0,1,0,1,1,1) Wie oben bereits bemerkt, kommt es hier auf die Charakteristik des Grundkörpers an. Diese Matrix repräsentiert beide Matroide. Das Fano\-Matroid, genau dann wenn die Charakteristik des Grundkörpers gleich 2 ist und das non\-Fano\-Matroid, genau dann wenn sie ungleich 2 ist. Man beachte, dass die Spalten 2,5 und 6 über GF(2) linear abhängig sind, sonst aber nicht, dass also menge(2,5,6) \in \calF(F_7^(-)) aber menge(2,5,6) \notin \calF(F_7). Das folgende Bild zeigt eine geometrische Darstellung des Fano\-Matroids, die mir Matroid zur Verfügung gestellt hat: Symbol der Fano-Ebene \ E=menge(M, A, T, R, O, I, D) ist die Grundmenge und die Kreise sind alle Mengen von drei Buchstaben, die auf einer Linie liegen, z.B. also auch menge(A, O, I), die Menge menge(2,5,6). Im non\-Fano\-Matroid ist diese Menge nicht abhängig, also kann man das non\-Fano\-Matroid durch eine ähnliche Zeichnung repräsentieren: einfach ohne die Linie menge(A, O, I). Über geometrische Repräsentationen von Matroiden weiß ich nicht sehr viel, nur soviel, dass die geometrische Repräsentation des Fano\-Matroids der Projektiven Ebene PG(2,2) entspricht.

Das Kreismatroid

\ \stress\big\ array(Etwas Notation)__ Ein Graph__ G=(V,E,\phi) ist ein Tripel bestehend aus: der Eckenmenge V, der Kantenmenge E, wobei E und V disjunkt sind, und einer Abbildung \phi(G) : E-> menge(menge(x,y) : x,y \in V), die jeder Kante zwei Endecken zuordnet (x=y ist auch erlaubt). Durch V und E \subseteq \calP_(<=2)(V)-menge(\0) wird kanonisch der Graph G=(V,E, id_E)=(V,E) definiert. Zwei Graphen G und H heißen isomorph__, wenn es Bijektionen \alpha : V(G)->V(H), \beta : E(G)->E(H) mit \alpha(\phi(G)(e))=\phi(H)(\beta(e)) gibt. Elementare graphentheoretische Begriffe wie Eckengrad, Teilgraph, Kantenzug, Weg, Kreis, Schlinge, Wald, Komponente, ... setze ich voraus. \stress\big\ array(Bemerkung)__: Wir betrachten im Allgemeinen unendliche Graphen, d.h. Graphen mit unendlich vielen Ecken. Ein Graph, in dem jede Ecke endlichen Grad hat heißt array(lokal endlich)__. \darkred\ \calC(G):=menge(E(Z): Z Kreis in G) \black\ ist die (Kanten-)Menge der Kreise von G. \calC(G) erfüllt \ref(C1) (Kreise sind hier per Definition endlich). Für einen Kreis Z hat im Teilgraphen G(Z) jede Ecke Grad 2. Da kein echter Teilgraph von G(Z) diese Eigenschaft hat folgt \ref(C2). Für einen weiteren Kreis Z' mit E(Z)!=E(Z') betrachte wir die Menge D:=(E(Z)\union\ E(Z'))-(E(Z)\cut\ E(Z')). In G(V,D) hat jede Ecke Grad 0, 2 oder 4. D kann man als disjunkte Vereinigung der Kantenmenge gewisser Kreise darstellen => \ref(C3'). Ist also \darkred\ \calF(G):=menge(E(H): H ist Teilwald von G) \black\ so ist \darkred\ M(G):=(E(G),\calF(G))\black\ ein Matroid auf E(G), das von G erzeugte Matroid oder das Kreismatroid__ von G. Die Kreise von M(G) sind genau die Kantenmengen von Kreisen in G. Zu beachten ist hier, dass die Grundmenge von M(G) Kanten eines Graphen sind. Wir werden später auch noch ein Matroid kennenlernen, das die Eckenmenge eines Graphen als Grundmenge hat. Nicht-isomorphe Graphen können übrigens das gleiche Matroid erzeugen. Zum Beispiel ändert das Hinzufügen isolierter Ecken nichts am Kreismatroid. \stress\big\ array(Bemerkung)__: Die Kreise von G sind hier per Definition endlich. Man kann für unendliche Graphen auch unendliche Kreise definieren, das ist allerdings recht aufwendig, man muss den Graphen topologisieren, und man bekommt Gebilde als Kreise, die nicht unbedingt wie Kreise aussehen. Insbesondere stimmen dann die Kantenmengen der Kreise von G und die Kreise von M(G) nicht mehr überein. Das wollen wir alles nicht, deswegen nur endliche Kreise.

Darstellbarkeit graphischer Matroide

\ Ein Matroid heißt graphisch__, falls es zu dem von einem Graphen erzeugten Matroid isomorph ist. Es gibt nichtgraphische Matroide. Matroid hat bereits gezeigt, dass U_2,4 nicht graphisch ist. \stress\big\ array(SATZ)____ \normal\ Jedes graphische Matroid ist regulär.

Transversalmatroide

\ Eine Menge X von Kanten eines Graphen G heißt ein Matching__ von G, wenn abs(V(e))>1 und V(e)\cut\ V(f) =\0 für e!=f aus X. Wenn also jede Kante aus X mindestens zwei Endecken hat (also keine Schlinge ist), und je zwei Kanten aus X keine gemeinsamen Endecken haben. Aus den Matchings eines Graphen können wir ein Matroid auf V(G) \(also auf der Eckenmenge!\) bekommen, wenn wir voraussetzen, dass G keine unendlichen Matchings besitzt. Wir brauchen diese Einschränkung. Ein Gegenbeispiel für den allgemeinen Fall ist ein unendlicher Stern, bei dem jede Kante noch einmal unterteilt ist. Dessen Matchings bilden kein System endlichen Charakters, verletzen also \ref(F4) (danke schoki). Nun aber das Matroid: \darkred\ \calF:=menge(F \subseteq V(G) : F\subseteq V(X) für ein Matching X in G) \black\ sind die unabhängigen Mengen eines Matroides \darkred\ H(G):=(V(G), \calF)\black\ . Sei \small\(A_i )_(i\in I) \normal\ eine Familie von Teilmengen einer Menge E \(E und I sind immer diskunkt\). T\subseteq\ E heißt array(partielle Transversale)__ wenn eine Injektion \phi : T->I mit x \in A_\phi(x) für alle x \in T existiert. Falls sogar eine Bijektion \phi mit dieser Eigenschaft existiert, so heißt T eine Transversale__. Wenn I endlich ist, ist abs(T) die Länge__ der partiellen Transversale und abs(I)-abs(T)>=0 ihr Defekt__. Eine Transversale ist also eine partielle Transversale vom Defekt 0. Die partiellen Transversalen sind genau die Mengen T \subseteq\ E, die von einem Matching des Graphen (E\union\ I, menge(menge(x,i): i\in I, x \in A_i)) überdeckt werden. Also bilden die partiellen Transversalen \calF(\small (A_i )_(i\in I) \normal\ ) die unabhängigen Mengen eines Matroids \darkred\ M:=(E, \small\(A_i )_(i\in I) \normal\ ) \black\ , des Transversalmatroids__ von \small\(A_i )_(i\in I) \normal\ auf E. Es ist M=H(G)\|E. \stress\big\ array(Hall und Rado)__ Der Satz von Hall besagt, dass eine endliche Familie \small\(A_i )_(i\in I) \normal\ genau dann eine partielle Transversale des Defektes höchstens d besitzt, wenn \ll(Hall-Bedingung)abs(union(A_i , i\in J,)) >= abs(J) -d für alle J \subseteq I erfüllt ist. Ein Satz von Rado verallgemeinert dies. Auf E ist zusätzlich ein beliebiges Matroid M gegeben, und statt nach irgendeiner, fragt man nach einer in M unabhängigen Transversale: \stress\big\ array(SATZ)____ \normal\ Sei d \in\IZ_(>=0) und M ein Matroid auf E und \small\(A_i )_(i\in I) \normal\ eine endliche Familie von Teilmengen von E. Genau dann existiert eine in M unabhängige partielle Transversale T \subseteq E von \small\(A_i )_(i\in I) \normal\ des Defektes höchstens d, wenn \ll(Rado-Bedingung)r_M(union(A_i , i\in J,)) >= abs(J) -d für alle J \subseteq I erfüllt ist. Der Satz von Hall ergibt sich aus dem Satz von Rado durch Spezialisierung auf das freie__ Matroid auf E, M=(E,\calP(E)).

Minoren

\ Minoren sind ein wichtiges Konzept der Graphen\- und Matroidtheorie. \stress\big\ array(Kontraktion)__ Sei G=(V,E,\phi) ein Graph. Für e \in E(G) entsteht G\/e aus G durch Identifizieren der Endecken von e in G-e; e wird quasi zusammengezogen. Kantenmengen geschlossener Kantenzüge der Länge min. 2 werden wieder zu Kantenmengen geschlossener Kantenzüge in G\/e. Ist Z sogar ein Kreis \(also ein doppelpunktfreier geschlossener Kantenzug\) so wird daraus wieder ein Kreis, oder ein geschlossener Kantenzug mit genau einem Doppelpunkt. Es gibt dann zwei Kreise Z', Z'' in G\/e mit E(Z') \cut\ E(Z'') =\0 und e \notel E(Z)=E(Z')\union\E(Z''). Es gilt: \calC(G\/e)=min(opimg(\subseteq),(menge(C-menge(e) : C \in \calC(G))-menge(0))) Das lässt sich auch auf den allgemeinen Fall, der Kontraktion einer Kantenmenge X, übertragen. Dann ist \calC(G\/X)=min(opimg(\subseteq),(menge(C-X : C \in \calC(G))-menge(0))). Dies lässt sich auf Matroide verallgemeinern. Ist M ein Matroid auf E und X \subseteq\ E, dann ist \darkred\ \calC:=min(opimg(\subseteq),(menge(C-X : C \in \calC)-menge(0))) \black\ die Menge der Kreise eines Matoids M\/X auf E-X. M\/X entsteht aus M durch Kontraktion von X. Wie sehen die unabhängigen Mengen von M\/X aus? Für jede Basis B von M\|X gilt: \calF(M\/X):=menge(F \subseteq\ E-X : F \union\B \in \calF(M)) Man kann nun für ein Matroid endlichen Ranges die Rangfunktion von M\/X berechnen: Man wählt ein B \in \calB(M\|X) und für Y \subseteq\ E-X ein B' \in \calB_(M\/X)(Y). Dann ist B \union\ B' eine in M unabhängige Teilmenge von X \union\ Y, sogar maximal mit dieser Eigenschaft, also eine Basis von M\|X\union\ Y. Folglich ist r_(M\/X)(Y) = r_M(X \union\ Y) - r_M(X). Mehrmalige Kontaktion eines Matroids M auf E kann zu einer zusammengefasst werden. Für disjunkte X,Y \subseteq\ E gilt: (M\/X)\/Y = M\/(X\union\ Y) \stress\big\ array(Löschung)__ Sei M ein Matroid auf E und Y \subseteq\ E. Das Matroid \darkred\ M-Y:=M\|(E-Y) \black\ entsteht aus M durch Löschung von Y. Auch hier können mehrmalige Löschungen wieder zu einer zusammengefasst werden. Für disjunkte X,Y \subseteq\ E gilt: (M-X)-Y = M-(X \union\ Y). \stress\big\ array(Minoren)__ Die Reihenfolge zweier Löschungen oder Kontraktionen kann vertauscht werden. Für disjunkte X,Y \subseteq\ E gilt: (M-X)-Y = (M-Y)-X und (M\/X)\/Y = (M\/Y)\/X. Aber auch die Reihenfolge von Kontraktion und Löschung ist vertauschbar. Für disjunkte X,Y \subseteq\ E gilt: (M\/X)-Y = (M-Y)\/X Ein Matroid N heißt Minor__ eines Matroids M auf E, wenn es disjunkte X,Y \subseteq\ E mit N=(M\/X)-Y gibt, und array(echter Minor)__ falls N!=M gilt.

Dualität

\ Und nun zu einem weiteren wichtigen Konzept: Sei M=(E,\calF) ein Matroid und sei \darkred\ \calF^\*(M):=menge(F \subseteq\ E : F \cut\ B = \0 für eine Basis B von M)\black\ . \calF^\*(M) enthält die leere Menge und mit jeder Menge auch deren Teilmengen. Im Allgemeinen ist (E, \calF^\*(M)) jedoch kein Matroid, auch dann nicht, wenn M endlichen Rang hat: Ist k>=1 und E unendlich, so enthält \calF^\* \(U_k,E \) nicht E, aber jede endliche Teilmenge von E, verletzt also \ref(F4). Für ein endliches Matroid ist jedoch \darkred\ M^\*:=(E,\calF^\*(M)) \black\ ein Matroid auf E, das zu M duale__ Matroid und r_(M^\*) (X) = abs(X)-r_M(E)+r_M(E-X) array( für jedes X \subseteq\ E. ) Daraus folgt r(M^\*)=r_(M^\*)(E)=abs(E)-r_M(E), und daraus ergibt sich \calB(M^\*)=menge(E-B : B \in \calB(M)). Also haben M und (M^\*)^\* dieselben Basen, und sind daher gleich. X \subseteq\ E heißt coabhängig, counabhängig, Cobasis, Cokreis von M, falls X abhängig, unabhängig, Basis, Kreis in M^\* ist, M heißt cographisch, falls M^\* graphisch ist ... Außerdem schreibt man auch \calB^\*(M) für \calB(M^\*) usw. X \subseteq\ E ist genau dann abhängig in M^\*, wenn es in keiner Basis von M liegt, wenn es also jede Cobasis von M schneidet. Daher gilt: \calC(M) = min(opimg(\subseteq), menge(C \subseteq\ E : C \cut\ B^\* !=\0 für alle B^\* \in \calB^\*(M)) ) und dual \calC^\*(M) = min(opimg(\subseteq), menge(C^\* \subseteq\ E : C^\* \cut\ B !=\0 für alle B \in \calB(M)) ) Besonders interessant ist das Schnittverhalten von Kreisen und Cokreisen in einem Matroid. Zum Beispiel ist ein endliches Matroid genau dann binär, wenn sich ein Cokreis und ein Kreis nie in genau drei Elementen schneiden. \stress\big\ array(Bemerkungen)__ \ll(*)Ein Kreis und ein Cokreis schneiden sich nie in genau einem Element. Das liefert eine Beschreibung der Cokreise durch die Kreise: \calC^\*(M) = min(opimg(\subseteq), menge(X \subseteq\ E : abs(X\cut\ C)!=1 für alle C \in \calC)-menge(0)) \ll(*)Die Eigenschaft zusammenhängend zu sein ist dual invariant; wenn M zusammenhängend ist, ist es M^\* auch. \ll(*)Ein endliches Matroid M ist genau dann über einem Körper K darstellbar, wenn M^\* es ist. \ll(*)Für ein endliches Matroid M auf E und X \subseteq\ E gilt: M^\* \/X=(M-X)^\* \ll(*)Die dazu duale Gleichung lautet: M^\* -X=(M\/X)^\* \ll(*)Die Minorenrelation ist dual invariant; ist N Minor von M, so ist auch N^\* Minor von M^\*. \ll(*)Mit M ist auch jeder Minor K\-linear. Spätestens hier ist es also vorbei mit der Unendlichkeit. Soviel ich weiß wird aber daran gearbeitet, auch für unendliche Matroide ein vernünftiges Konzept der Dualität zu erklären. Näheres weiß ich da aber leider noch nicht.

Weiterführendes

\ \stress\big\ array(Komplexe Vereinigung)__ Sei \small\(M_i )_(i\in I) \normal\ , mit M_i :=(E_i , \calF_i ), eine Familie von Paaren mit \calF_i \subseteq\ \calP(E_i). \darkred\M:=bigop(\vee,M_i,i\in I,) := (union(E_i,i\in I,), menge(union(F_i,i\in I,) : F_i \in \calF_i für jedes i \in I)) \black\ ist die array(komplexe Vereinigung)__ der M_i. Sind die E_i paarw. disjunkt, so schreibt man auch bigop(\oplus) stratt bigop(\vee). Die komplexe Vereinigung endlich vieler Matroide endlichen Ranges ist wieder ein Matroid. Die Bestimmung der Rangfunktion von M, der komplexen Vereinigung, ist eine Anwendung der Ergebnisse über submodulare Funktionen und des Satzes von Rado. Ich möchte den Beweis nicht komplett aufschreiben, aber eine kurze Skizze soll zeigen, daß der Aufwand, den man betreibt um zu beweisen, daß sich aus submodularen Funktionen Matroide gewinnen lassen deren Rangfunktion sogar eine recht einfache Darstellung als ein gewisses Minimum besitzt, lohnt: Man betrachtet die submodulare Funktion f: \calP(E)-> \IZ_(>= 0) mit f(X)=sum(r_(M_i)(X\cut\ E_i),k=1,k) Wenn die E_i paarweise disjunkt sind, gilt r_M =f (warum?). Im Allgemeinen verletzt f aber die Bedingung \ref(R3). Aber f erzeugt ein Matroid M(f) auf E. Mit dem Satz von Rado kann nun gezeigt werden, daß M=M(f) gilt. Für die Rangformel für die komplexe Vereinigung von Matroiden ergibt sich nun also r_(M_1 \vee\ ... \vee\ M_k)(X)=min(, menge(sum(r_(M_i)(Y\cut\ E_i),k=1,k)+abs(X-Y) : Y\subseteq\ X)) für alle X \subseteq\ E(M_1 \vee\ ... \vee\ M_k). Die Darstellung des Ranges, der ja eigentlich ein Maximum ist, als ein Minimum führt auf einige Min-Max-Theoreme, zum Beispiel Packungs- und Überdeckungssätze; Also wieviele disjunkte Basen kann man in ein Matroid höchstens hineinpacken oder wieviele unabhängige Mengen benötigt man mindestens um es zu überdecken? Als weitere Konsequenz ergeben sich außerdem zwei "Klassiker" der Graphentheorie: der Baumpackungssatz und der Waldzerlegungssatz, deren graphentheoretische Beweise nicht ohne sind (zumindest der Baumpackungssatz ist schwierig), die sich in der Matroidtheorie aber sehr einfach beweisen lassen. \stress array(Beispiel)__: Ein über keinem Körper darstellbares Matroid F_7 \oplus\ F_7^\- also die disjunkte komplexe Vereinigung von Fano\- und non\-Fano\-Matroid, ist nicht darstellbar. Das ist relativ leicht einzusehen, da Mit M auch jeder Minor von M K\-linear ist. Und da sowohl F_7 als auch F_7^(-) Minoren von F_7 \oplus\ F_7^(-) sind, kann es keine Darstellung geben. \stress\big\ array(Der Durchschnitt zweier Matroide)__ Sei \small\(M_i )_(i\in I) \normal\ , mit M_i :=(E_i , \calF_i ), eine Familie von Paaren mit \calF_i \subseteq\ \calP(E_i). \darkred\M:=cut(M_i,i\in I,) := (cut(E_i,i\in I,), menge(F : F \in \calF_i für jedes i \in I)) \black\ Erfüllt jedes M_i \ref(F1) bzw. \ref(F2) so auch der Schnitt. Zum Beispiel sind Schnitte abstrakter Simplizialkomplexe wieder solche. Aber der Durchschnitt zweier Matroide ist im Allgemeinen kein Matroid. Trotzdem ist man oft an einer möglichst großen in jedem zweier vorgegebener Matroide unabhängigen Menge interessiert (Edmonds Intersection Theorem). \stress\big\ array(Brückenspiele)__ Auf die Gefahr hin, daß dieser Artikel wahnsinnig lang wird, möchte ich noch kurz eine recht unterhaltsame Anwendung der Matroidtheorie vorstellen: Sei M ein Matroid auf E. T \subseteq\ E sapnnt__ X\subseteq\ E auf, wenn X\subseteq\ h_M(T) gilt. Wobei h_M : \calP(E) -> \calP(E) mit h_M(X)=menge(a\in E : a\in X oder a \in C \subseteq\ X\union\ menge(a) für ein C \in \calC(M)) ein mengentheoretischer Hüllenoperator ist. Sei M ein endliches Matroid und X, A nichtleere Teilmengen von E. Das Brückenspiel__ L(M,X,A) ist ein Spiel für zwei Personen; Spieler 1 und 2 markieren dabei abwechselnd, Spieler 2 fängt an, noch nicht markierte Elemente aus X (vielleicht mit verschiedenen Farben, oder mit 1 und 2). Spieler 1 gewinnt, wenn er die Elemente einer A aufspannenden Menge markiert hat, Spieler 2 gewinnt wenn alle Elemente aus X markiert wurden ohne daß Spieler 1 sein Ziel erreichte. Dieses Spiel erlaubt offensichtlich kein Unentschieden. Gucken wir uns mal einen Spezialfall an, der das etwas klarer macht: Sei G ein Graph und a,b zwei Ecken von G. Im Spiel L\(G ; a , b\) sichert Spieler 1 eine Kante gegen Löschung und gewinnt sobald er die Kanten eines a-b-Weges gesichert hat. Spieler 2 löscht eine ungesicherte Kante und gewinnt sobald jede verbliebene Kante gesichert ist ohne daß es einen a-b-Weg gibt. Wenn man zu G eine neue Kante e von a nach b hinzufügt, so daß im so entstandenen Graphen G^(+) ein Kreis durch e entsteht sobald es einen a-b-Weg in G gibt, kann man dieses Spiel als Brückenspiel L(M(G^+), E(G), menge(e)) auffassen. \stress array(Strategie für Spieler 1)__ Wenn es im Brückenspiel L(M,X,A) zwei disjunkte, einander aufspannende Teilmengen von X gibt, die A aufspannen, gibt es eine Gewinnstrategie für Spieler 1. Für die Graphenvariante bedeutet dies, daß G 2 kantendisjunkte Spannbäume enthalten muß. Nach einem Satz der Graphentheorie ist das genau dann der Fall, wenn G min. 4-kantenzusammenhängend ist. \stress array(Strategie für Spieler 2)__ Die Bedingung für eine Gewinnstrategie für Spieler 2 sieht ganz anders aus: Wenn es beim Brückenspiel L(M,X,A) ein Y \subseteq\ E(M) und eine Zerlegung von X-Y in zwei disjunkte, in M\/Y unabhängige Mengen F_1, F_2 gibt, so daß F_1 die Menge A-Y in M\/Y nicht aufspannt, dann gibt es eine Gewinnstrategie für Spieler 2. Der Beweis dieser Aussage ignoriert interessanterweise völlig ob Spieler 1 inzwischen bereits gewonnen hat \(was sich a posteriori allerdings als unmöglich erweist\).

To classify the Uncats

\ Klassifikationen sind bei Mathematikern ja sehr beliebt, weshalb ich diesen Artikel auch mit einigen Klassifikationen abschließen möchte. Die Klasse der graphischen, cographischen und K\-linearen Matroide ist abgeschlossen unter Minorenbildung. Das heißt, jeder Minor eines graphischen, cographischen, K\-linearen Matroids ist ebenfalls graphisch, cographisch, K\-linear. Solche Klassen von Matroiden beschreiben wir durch die Angabe verbotener Minoren für diese Klasse. Man kennt das bereits aus der Graphentheorie: \stress\big\ array(SATZ von Kuratowski)____ \normal\ Ein Graph G ist genau dann plättbar, wenn er keinen zu K^5 oder K_3,3 isomorphen Minor enthält. Tutte veralgemeinerte diesen Satz zu einer Charakterisierung graphischer (und cographischer) Matroide: \stress\big\ array(SATZ)____ \normal\ Ein Matroid ist genau dann graphisch, wenn es keinen zu U_2,4, M^\*(K^5), M^\* \(K_3,3 \), F_7 und F_7^\* isomorphen Minor hat. Die Charakterisierung cographischer Matroide folgt direkt durch Bildung des Duals: \stress\big\ array(SATZ)____ \normal\ Ein Matroid ist genau dann cographisch, wenn es keinen zu U_2,4, M(K^5), M\(K_3,3 \), F_7 und F_7^\* isomorphen Minor hat. Die Frage, welche Matroide binär, also darstellbar über GF(2), sind, wurde 1958 von Tutte beantwortet: \stress\big\ array(SATZ (Tutte, 1958))____ \normal\ Ein Matroid ist genau dann GF(2)\-linear, wenn es keinen zu U_2,4 isomorphen Minor hat. Weiterhin bekannt sind noch die Charakterisierungen von GF(3)\- und GF(4)\-linearen Matroiden: \stress\big\ array(SATZ (Reid, 1971, Bixby, 1975))____ \normal\ Ein Matroid ist genau dann GF(3)\-linear, wenn es keinen zu U_2,5, U_3,5 = U_2,5^\*, F_7 und F_7^\* isomorphen Minor hat. \stress\big\ array(SATZ (Greelen, Gerards, Kapoor, 2000))____ \normal\ Ein Matroid ist genau dann GF(4)\-linear, wenn es keinen zu U_2,6, U_4,6= U_2,6^\*, F_7^\- und F_7^\-\*, P_6, P_8 und P_8^'' isomorphen Minor hat. Von einer Charakterisierung GF(q)\-linearer Matroide mit q>4 ist man noch weit entfernt. Allerdings existiert folgende Vermutung von Rota: \stress\big\ array(Vermutung (Rota, 1960))____ \normal\ Zur Primzahlpotenz q existiert eine endliche Menge m_q von Matroiden mit der Eigenschaft, dass M GF(q)\-linear ist <=> M hat keinen Minor aus m_q. Dabei sind: U_2,6=M(1,0,1,1,1,1;0,1,1,a,b,c) über K <=> abs(K)>=5 mit a,b,c \in K-menge(0,1) array(paarw. versch.) P_6=M(1,0,0,1,1,1;0,1,0,1,1,a;0,0,1,1,b,c) über K <=> abs(K)>=5 mit a,b,c \in K-menge(0,1), c \notin menge(a,b,ab) außerdem ist P_6^\* = P_6 P_8=M(1,0,0,0,0,1,1,2;0,1,0,0,1,0,1,1;0,0,1,0,1,1,0,1;0,0,0,1,2,1,1,0) über K <=> char K != 2 und außerdem ist P_8^\* = P_8 P_8^''=M(1,0,0,0,1,1,1,1;0,1,0,0,1,1,b^(-1),a;0,0,1,0,1,a,0,a;0,0,0,1,1,b,1,0) über K <=> abs(K) >=5 und a!=b \in K-menge(0,1), a!= b^(-1) außerdem ist P_8^''\* = P_8^''

Literatur

Die beiden Standardwerke über Matroidtheorie sind wohl D. J. A. Welsh, Matroid Theory und J. Oxley, Matroid Theory. Auf deutsch gibt es glaube ich keine Bücher über Matroide. Man findet einiges in Büchern über Transversaltheorie und Kombinatorik. Sehr lesenswert: What is a matroid - James Oxley The contributions of Dominic Welsh to matroid theory - James Oxley Alice's Adventures in Wonderland and Through the Looking Glass von Lewis Carroll (bzw. Alice im Wunderland und Alice hinter den Spiegeln)
\(\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:
: Mathematik :: Graphentheorie :: Reine Mathematik :
To classify the Uncats - Mehr über Matroide [von jannna]  
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 3553
 
Aufrufstatistik des Artikels
Insgesamt 240 externe Seitenaufrufe zwischen 2012.01 und 2022.05 [Anzeigen]
DomainAnzahlProz
https://google.com2711.3%11.3 %
http://google.de14359.6%59.6 %
https://google.de3414.2%14.2 %
http://google.nl135.4%5.4 %
https://www.bing.com41.7%1.7 %
http://google.es41.7%1.7 %
https://www.ecosia.org31.3%1.3 %
https://duckduckgo.com20.8%0.8 %
http://images.google.de20.8%0.8 %
http://google.com20.8%0.8 %
http://google.at10.4%0.4 %
https://metager.de10.4%0.4 %
http://www.bing.com10.4%0.4 %
http://nortonsafe.search.ask.com10.4%0.4 %
https://google.com.hk10.4%0.4 %
http://google.ch10.4%0.4 %

Häufige Aufrufer in früheren Monaten
Insgesamt 195 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (63x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (30x)https://google.de/
2020-2022 (25x)https://google.com/
201305-05 (16x)http://google.de/url?sa=t&rct=j&q=rangfunktion cographisches matroid
201206-06 (14x)http://google.de/url?sa=t&rct=j&q=rangfunktion matroid submodular
201212-12 (8x)http://google.de/url?sa=t&rct=j&q=schnitt zweier matroide "wieder ein matroid...
2012-2013 (8x)http://google.nl/url?sa=t&rct=j&q=
201211-11 (6x)http://google.de/url?sa=t&rct=j&q=matroid unabhängiger hüllenoperator
201301-01 (5x)http://google.nl/url?sa=t&rct=j&q=beispiel nicht isomorphe graphen graphische...
201306-06 (4x)http://google.de/url?sa=t&rct=j&q=matroid nicht darstellbar
201304-04 (4x)http://google.de/url?sa=t&rct=j&q=matroide geometrisch darstellen
201210-10 (4x)http://google.de/url?sa=t&rct=j&q=bedeutung "r über k" in der statistik...
202106-10 (4x)https://google.de
2020-2021 (4x)https://www.bing.com/

[Top of page]

"Mathematik: To classify the Uncats - Mehr über Matroide" | 1 Comment
The authors of the comments are responsible for the content.

Re: To classify the Uncats - Mehr über Matroide
von: jannna am: Do. 16. November 2006 17:01:30
\(\begingroup\)Bemerkung: Den Satz von Hall (auch als Heiratssatz bekannt) kann man auf lokal endliche Graphen erweitern. Damit ist auch die Einschränkung, daß G keine unendlichen Matchings enthalten darf, für die Gewinnung von Matroiden aus den Matchings eines Graphen zu stark. Es reicht G als lokal endlich zu verlangen. Das ist aber auch nötig -> Gegenbeispiel ist sonst der einmal unterteilte unendl. Stern. Grüße Jana\(\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-2022 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]