+1 Daumen
236 Aufrufe

Es sei \(G\) ein gerichteter Graph mit Kontenmenge \(V(G)\). Betrachte damit folgende Abbildung:

\(\begin{aligned}&f:\ \mathcal{P}(V(G))\to \mathcal{P}(V(G)),\\[10pt] &A\mapsto \{t\in V(G)\setminus A:\ \forall\ w\in A:\ w-t-\text{Weg existiert nicht}\} \end{aligned}\)

Die Menge \(\mathcal{P}(V(G))\) beschreibt hierbei die Menge aller Teilmengen von Knoten der Grundmenge \(V(G)\)

Frage:

Gilt dann für alle Mengen \(X,Y\in \mathcal{P}(V(G))\) die Eigenschaft $$ f(X\cup Y)=f(X)\cap f(Y) $$ ?

Problem/Ansatz:

Für die Gleichheit beider Mengen betrachte ich

\(\begin{aligned} &v\in f(X\cup Y)\\[10pt]&\Leftrightarrow \quad \text{für alle }z\in (X\cup Y): \ z-v-\text{Weg existiert nicht}\\[10pt]&\Leftrightarrow \quad \text{für alle }q\in X: \ q-v-\text{Weg existiert nicht}\ \land \\& \ \ \qquad \text{für alle }p\in Y: \ p-v-\text{Weg existiert nicht}\\[10pt]&\Leftrightarrow \quad v\in f(X) \ \land \ v\in f(Y) \quad \Leftrightarrow \quad v\in (f(X)\cap f(Y))\end{aligned}\)

Wenn ich nun nichts übersehen haben sollte, stimmt dieser Ansatz?

Avatar von 14 k

Hallo,

zur Definition von f(A)  auch, dass \(f(A) \sube V(G) \setminus A\). Das hast Du in Deinem Beweis nicht erwähnt. Soweit ich sehe, ist das aber nur eine kleine Ergänzung.

Gruß

Ja, genau. Es ging mir zunächst um die Essenz. Danke auf jeden Fall! :-)

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community