Mathematik online lernen im Mathe-Forum. Nachhilfe online
Startseite » Forum » Zusammenhangsgrad

Zusammenhangsgrad

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

 
Antworten Neue Frage stellen Im Forum suchen
Neue Frage
NFFN1

NFFN1 aktiv_icon

12:54 Uhr, 08.04.2021

Antworten
Guten Tag,

bei folgender Aufgabe tue ich mich schwer:

Zeige, daß ein Graph G(V,E) mit V(G)3 zweifach zusammenhängend ist, wenn es für je zwei Knoten v und w aus V einen Kreis (das ist eine geschlossene Wanderung v0,...,vn in G, wobei vivj für alle ij mit der einzigen Ausnahme v0 = vn) gibt, der v und w enthalt.
(V(G) ist die Menge der Knoten von G)

MfG,
Noah
Online-Nachhilfe in Mathematik
Antwort
michaL

michaL aktiv_icon

15:01 Uhr, 08.04.2021

Antworten
Hallo,

wie ist bei euch "zweifach zusammenhängend" definiert?

Mfg Michael
NFFN1

NFFN1 aktiv_icon

15:04 Uhr, 08.04.2021

Antworten
Ein Graph G heißt d–fach zusammenhängend (für d ∈ N), wenn
V(G)>d
• und für jede Teilmenge TV(G) mit T<d der durch V(G)\T induzierte
Teilgraph zusammenhängend ist.

Antwort
michaL

michaL aktiv_icon

15:08 Uhr, 08.04.2021

Antworten
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

NFFN1 aktiv_icon

15:14 Uhr, 08.04.2021

Antworten
Ich schätze mal die Äquivalenz. Aber genau steht es eben nicht da.
Antwort
michaL

michaL aktiv_icon

15:17 Uhr, 08.04.2021

Antworten
Hallo,

Scan der Originalaufgabenstellung. Max. 500 kB.

Mfg Michael
NFFN1

NFFN1 aktiv_icon

15:21 Uhr, 08.04.2021

Antworten
Das ist die Original-Fragenstellung. Anbei nochmal ein Screenshot.

snip
Antwort
michaL

michaL aktiv_icon

15:36 Uhr, 08.04.2021

Antworten
Hallo,

also nur "Wenn, dann".

Ich glaube, am einfachsten geht es indirekt.
Es gebe also für zwei Knoten v und w einen derartigen Kreis.

Annahme: G ist nicht zweifach zusammenhängend. Das bedeutet, dass es eine Teilmenge TV(G) geben muss mit den Eigenschaften:
* T<2 (d.h. T=1, d.h. T={x} für ein xV(G))
* der durch V(G)\T ist nicht mehr zusammenhängend.

Nun nimmst du zwei beliebige v,wx her und zeigst, dass sie aufgrund der Bedingung immer noch zusammen hängen.
Durch die Wegnahme von x kann in dem Kreis, in dem sich v und w befinden, höchstens eine Seite geöffnet haben. Das bedeutet aber, dass v und w noch zusammenhängen. Das bedeutet aber, dass es nur eine Zusammenhangskomponente gibt, was im Widerspruch zu Annahme steht.

Mfg Michael
Frage beantwortet
NFFN1

NFFN1 aktiv_icon

15:45 Uhr, 08.04.2021

Antworten
Super, habs verstanden. Danke!