| |
| Autor |
 Satz von Menger - fehlerhafter Induktionsbeweis |
|
Lupi98
Wenig Aktiv 
Dabei seit: 23.05.2021
Mitteilungen: 24
 |  Themenstart: 2023-05-25
|
Hallo liebe Mathe Freunde,
wir arbeiten in meinem Graphentheorie-Kurs mit dem Diestel Lehrbuch und unser Dozent hat uns mit Hinblick auf die bevorstehende Prüfung geraten, uns auch die Übungsaufgaben aus dem Buch anzuschauen.
Dort fand ich folgenden (falschen) Beweis vom Satz von Menger:
Sei X ein A-B-Trenner von minimaler Mächtigkeit. Bezeichne mit G(A) den Untergraphen von G, der durch X und all die Komponenten von G-X induziert wird, die A treffen; Entsprechend sei G(B) definiert. Da jeder A-B-Weg X trifft, enthält G(A) keinen A-X-Trenner aus weniger als IXI Ecken.
Das sollte bis hierhin stimmen, denke ich. Gerade letzteres macht ja Sinn, da jeder A-X-Trenner auch ein A-B-Trenner ist.
Nun geht es weiter:
Mit Induktion nach IGI enthält G(A) daher IXI disjunkte A-X-Wege und G(B) enthält entsprechende X-B-Wege. Zusammen bilden diese Wege das gesuchte Wegesystem.
Zur Erinnerung: Menger sagt, dass die kleinste Mächtigkeit einer A von B trennenden Eckenmenge (in G) gleich der größten Mächtigkeit disjunkter A-B-Wege (in G) ist.
Ich finde aber partout den Fehler in dem obigen Beweis nicht. Ich hatte überlegt, ob es vielleucht möglich ist, dass G(A)=G oder G(B)=G. In dem Fall würde ja die Induktion nicht hinhauen, oder ?
Vielleicht hat jemand ja einen Hinweis für mich :))
Wir wurden ferner darauf hingewiesen, dass man den Beweis korrigieren kann. Wenn ich nur wüsste, wo der Fehler ist, würde ich bestimmt nicht so auf dem Schlauch stehen :/
Ich freue mich auf eure Antworten!
Liebe Grüße,
Lupi98
|
 Profil
| | Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen. |
StrgAltEntf
Senior 
Dabei seit: 19.01.2013
Mitteilungen: 8384
Wohnort: Milchstraße
 | Beitrag No.1, eingetragen 2023-05-25
|
Hallo Lupi98,
um den Satz von Menger anwenden zu können, darf es doch keine A-B-Kante geben. (Denn andernfalls gibt es keine A-B-trennende Eckenmenge.) Da es aber A-X-Kanten geben kann, lässt sich die IV nicht anwenden.
Edit: Das stimmt wohl doch noch nicht so ganz. Bei der Mengenversion des Satzes von Menger ist es wohl unerheblich, ob A-B-Kanten existieren. A und B müssen noch nicht einmal disjunkt sein. Dafür darf eine A-B-trennende Menge X auch Ecken aus A oder B enthalten. Im Extremfall ist A=B. Dann ist X=A=B A-B-trennend. Wenn dann noch zusätzlich A alle Ecken des Graphen enthält, ist tatsächlich G(A)=G.
|
Profil
|
Kitaktus
Senior 
Dabei seit: 11.09.2008
Mitteilungen: 7234
Wohnort: Niedersachsen
| Beitrag No.2, eingetragen 2023-05-25
|
Vielleicht übersehe ich etwas, aber wenn es |X| disjunkte Wege von A nach X gibt, folgt daraus noch nicht, dass zu jedem Knoten aus X einer dieser Wege führt. Das wäre aber notwendig, um diese Wege mit den B-X-Wegen verbinden zu können.
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8384
Wohnort: Milchstraße
| Beitrag No.3, eingetragen 2023-05-25
|
\quoteon(2023-05-25 16:20 - Kitaktus in Beitrag No. 2)
Vielleicht übersehe ich etwas, aber wenn es |X| disjunkte Wege von A nach X gibt, folgt daraus noch nicht, dass zu jedem Knoten aus X einer dieser Wege führt. Das wäre aber notwendig, um diese Wege mit den B-X-Wegen verbinden zu können.
\quoteoff
Hm, weshalb folgt das noch nicht?
|
Profil
|
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 7234
Wohnort: Niedersachsen
| Beitrag No.4, eingetragen 2023-05-25
|
Weil nach meinem Verständnis „disjunkte Weg“ die Bedeutung hat „alle Knoten - bis auf Anfangs- und Endknoten - sind verschieden“.
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8384
Wohnort: Milchstraße
| Beitrag No.5, eingetragen 2023-05-25
|
Aber doch nicht bei der Mengenversion von Menger?
|
Profil
|
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 7234
Wohnort: Niedersachsen
| Beitrag No.6, eingetragen 2023-05-26
|
Was meinst Du mit "Mengenversion"?
Nochmal etwas ausführlicher:
\quoteon(2023-05-25 10:52 - Lupi98 im Themenstart)
Zur Erinnerung: Menger sagt, dass die kleinste Mächtigkeit einer A von B trennenden Eckenmenge (in G) gleich der größten Mächtigkeit disjunkter A-B-Wege (in G) ist.
\quoteoff
Der Einfachheit halber betrachten wir einen Graphen, bei dem der kleinste Trenner von A und B -- dies sei X -- keine Knoten aus A oder B enthält.
Diesen Satz verwenden wir im Induktionsbeweis und wenden ihn auf die Mengenpaare (A, X) und (X, B) an. Die Mächtigkeit der kleinsten trennenden Eckenmengen kennen wir jeweils (das ist in beiden Fällen |X|) und mit der Induktionsvoraussetzung folgt daraus die Existenz von je |X| disjunkten Wegen von A nach X bzw. von B nach X. Daraus sollen jetzt |X| disjunkte Wege von A nach B "zusammengebastelt" werden.
Damit das aufgeht, muss jeder dieser |X| Weg von A nach B mindestens einen Knoten aus X enthalten und diese $\geq$ |X| Knoten müssen alle verschieden sein. Es gilt also sogar Gleichheit (1)
Andernfalls wären die zusammengesetzten A-B-Wege nicht disjunkt.
Nur woraus folgt (1) denn? Der Satz von Menger auf die Trennung von A und X angewandt liefert das nicht. Da dürften disjunkte Wege den _gleichen_ Endknoten in X haben.
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8384
Wohnort: Milchstraße
| Beitrag No.7, eingetragen 2023-05-26
|
\quoteon(2023-05-26 01:52 - Kitaktus in Beitrag No. 6)
Was meinst Du mit "Mengenversion"?
\quoteoff
@Kitaktus:
Bin gerade verreist und melde mich ausführlich nach Pfingsten.
|
Profil
|
Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 7234
Wohnort: Niedersachsen
| Beitrag No.8, eingetragen 2023-05-27
|
Mich würde auch interessieren, was Lupi98 dazu sagt ...
|
Profil
|
StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 8384
Wohnort: Milchstraße
| Beitrag No.9, eingetragen 2023-05-29
|
So, jetzt etwas mehr.
@Kitaktus (Lupi98 hat es anscheinend die Sprache verschlagen):
Sei G = (V, E) ein endlicher einfacher Graph.
Satz von Menger Eckenversion:
Seien \(s,t\in V\) mit \(\{s,t\}\not\in E\). Dann ist die minimale Anzahl einer s-t-trennenden Eckenmenge gleich der maximalen Anzahl paarweise disjunkter\(^1\) s-t-Wege.
Satz von Menger Mengenversion:
Seien \(A,B\subseteq V\). Dann ist die minimale Anzahl einer A-B-trennenden Eckenmenge gleich der maximalen Anzahl paarweise disjunkter\(^2\) A-B-Wege.
Hierbei bedeutet disjunkt\(^1\), dass die Wege außer s und t keine gemeinsamen Ecken durchlaufen. Disjunkte\(^2\) Wege dürfen hingegen überhaupt keine gemeinsamen Ecken durchlaufen - auch nicht Anfangs- oder Endecke.
Im Fall \(v\in A\cap B\) ist übrigens (v) ein A-B-Weg (der Länge 0). Das ist nicht so interessant. Man könnte also o.B.d.A annehmen, dass \(A\cap B=\emptyset.\)
Im Fall, dass es eine Kante {a,b} mit \(a\in A\) und \(b\in B\) gibt, ist (a, b) ein A-B-Weg der Länge 1. Das ist auch nicht interessant, und man könnte o.B.d.A diesen Fall ausschließen.
Auch nicht so dolle interessant ist der Fall, dass es |A| viele paarweise disjunkte² A-B-Wege gibt. (Mehr können es nicht sein!) Hier ist die Mengenversion trivial, denn A ist eine A-B-trennende Eckenmenge.
Man könnte die Mengenversion also auch wie folgt formulieren:
Seien \(A,B\subseteq V\) disjunkt und es gebe keine A-B-Kante. Weiterhin gelte für eine kleinste A-B-trennende Eckenmenge X, dass \(|X|<\min\{|A|,|B|\}\). Dann gibt es |X| paarweise disjunkte² A-B-Wege.
Und hierauf spielst du hier anscheinend an:
\quoteon
Der Einfachheit halber betrachten wir einen Graphen, bei dem der kleinste Trenner von A und B -- dies sei X -- keine Knoten aus A oder B enthält.
\quoteoff
Das Problem ist aber, dass du die IV nicht auf A und X anwenden kannst, da diese "Einfachheit" dann nicht mehr unbedingt gegeben ist.
Ich glaube nicht, dass der Induktionsbeweis zu retten ist.
|
Profil
|
| Lupi98 wird per Mail über neue Antworten informiert. |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
