Alternatywny dowód twierdzenia Halla

[Azamath]

Mam następujące zadanie za pomocą, którego mam udowodnić twierdzenie Halla:

Niech \(\displaystyle{ U=(A_{1},...,A_{n})}\) bedzie rodziną zbiorów mającą własność typu Halla:

\(\displaystyle{ \ \ \forall I \subseteq \{1,...,n\} \ \ | \bigcup_{i\in I}^{}A_{i}| \ge |I|}\)

Niech \(\displaystyle{ V=(B_{1},...,B_{n})}\) będzie rodziną minimalnych podzbiorów zbiorów \(\displaystyle{ A_{1},...,A_{n}}\) mających tę samą własność; tj, \(\displaystyle{ B_{1} \subseteq A_{1},...,B_{n} \subseteq A_{n}}\), oraz

\(\displaystyle{ \ \ \forall I \subseteq \{1,...,n\} \ \ | \bigcup_{i\in I}^{}B_{i}| \ge |I|}\)

ale usunięcie dowolnego elementu z któregokolwiek zbioru \(\displaystyle{ B_{i}}\) pwoduje niezachodzenie własności tupu Halla.

1. Pokazać, że każdy \(\displaystyle{ B_{i}}\) zawiera dokładnie jeden element.
2. Wywnioskować, że rodzina \(\displaystyle{ U}\) ma transwersalę.


Chciałbym zaznaczyć, że znam dowód wersji małżeńskiej twierdzenia Halla ale zależy mi na udowodnieniu go w ten konkretny sposób, a nie bardzo wiem jak się do tego zabrać.

[max]

Nie wiem czy o to chodziło, ale mam pewien dowód:

Dowodzimy 1. indukcyjnie względem \(\displaystyle{ n.}\)

Zauważmy najpierw, że dla \(\displaystyle{ n=1}\) podzbiór \(\displaystyle{ I\subset\{1\}}\) ma co najwyżej jeden element, więc teza zachodzi.

Przyjmijmy teraz, że teza zachodzi dla \(\displaystyle{ n}\) i pokażemy ją dla \(\displaystyle{ n+1.}\)

Jasne jest, że zbiory \(\displaystyle{ B_{1},\ldots, B_{n}}\) spełniają warunek Halla, zatem z założenia indukcyjnego zawierają po jednym elemencie.
Ponieważ \(\displaystyle{ B_{1}, \ldots, B_{n + 1}}\) spełniają warunek Halla, to w szczególności
\(\displaystyle{ n+1 \le \left|\bigcup_{i=1}^{n+1}B_{i}\right| = n + |B_{n+1}| - \left|\left(\bigcup_{i=1}^{n}B_{i}\right)\cap B_{n+1}\right|.}\)
Zatem
\(\displaystyle{ 1 \le |B_{n+1}| - \left|\left(\bigcup_{i=1}^{n}B_{i}\right)\cap B_{n+1}\right| = \left|B_{n+1}\setminus\left(\bigcup_{i=1}^{n}B_{i}\right)\right|}\)
czyli istnieje \(\displaystyle{ b\in B_{n+1}\setminus\left(\bigcup_{i=1}^{n}B_{i}\right).}\)
Jak łatwo teraz sprawdzić \(\displaystyle{ B_{1},\ldots, B_{n}, \{b\}}\) spełnia warunek Halla, więc z minimalności \(\displaystyle{ B_{n+1} = \{b\}.}\)

2. wynika natychmiast z 1. - transwersalą jest suma minimalnych \(\displaystyle{ B_{i}, i=1,\ldots, n.}\)

[Agata*]

hej:) potrzebuje pomocy. Mianowicie mam zrobić dowod twierdzenia Halla w postaci grafowej.
Dowód mniej wiecej rozumię poza jednym zdaniem.
dlaczego ze jezeli wykazemy ze istnieje w sieci S przepływ o wartosci v >|V| to udowodnimy juz twierdzenie???