NFFN1
12:54 Uhr, 08.04.2021
|
Guten Tag,
bei folgender Aufgabe tue ich mich schwer:
Zeige, daß ein Graph mit zweifach zusammenhängend ist, wenn es für je zwei Knoten v und w aus V einen Kreis (das ist eine geschlossene Wanderung in G, wobei für alle mit der einzigen Ausnahme v0 = vn) gibt, der v und w enthalt. (V(G) ist die Menge der Knoten von G)
MfG, Noah
|
|
|
Hallo,
wie ist bei euch "zweifach zusammenhängend" definiert?
Mfg Michael
|
NFFN1
15:04 Uhr, 08.04.2021
|
Ein Graph G heißt d–fach zusammenhängend (für d ∈ N), wenn • • und für jede Teilmenge mit der durch induzierte Teilgraph zusammenhängend ist.
|
|
Hallo,
ok, die Entfernung eines Knotens erhöht also nicht die Anzahl der Komponenten.
Noch die Frage zur Exaktheit der Aufgabenstellung: Soll nur "Wenn, dann" gezeigt werden oder Äquivalenz?
Mfg Michael
|
NFFN1
15:14 Uhr, 08.04.2021
|
Ich schätze mal die Äquivalenz. Aber genau steht es eben nicht da.
|
|
Hallo,
Scan der Originalaufgabenstellung. Max. 500 kB.
Mfg Michael
|
NFFN1
15:21 Uhr, 08.04.2021
|
Das ist die Original-Fragenstellung. Anbei nochmal ein Screenshot.
|
|
Hallo,
also nur "Wenn, dann".
Ich glaube, am einfachsten geht es indirekt. Es gebe also für zwei Knoten und einen derartigen Kreis.
Annahme: ist nicht zweifach zusammenhängend. Das bedeutet, dass es eine Teilmenge geben muss mit den Eigenschaften: * (d.h. , d.h. für ein ) * der durch ist nicht mehr zusammenhängend.
Nun nimmst du zwei beliebige her und zeigst, dass sie aufgrund der Bedingung immer noch zusammen hängen. Durch die Wegnahme von kann in dem Kreis, in dem sich und befinden, höchstens eine Seite geöffnet haben. Das bedeutet aber, dass und noch zusammenhängen. Das bedeutet aber, dass es nur eine Zusammenhangskomponente gibt, was im Widerspruch zu Annahme steht.
Mfg Michael
|
NFFN1
15:45 Uhr, 08.04.2021
|
Super, habs verstanden. Danke!
|