Załóżmy, że \(\displaystyle{ m}\) i \(\displaystyle{ k}\) są takimi dodatnimi liczbami całkowitymi, że \(\displaystyle{ m \ge k+1}\). Definiujemy graf dwudzielny \(\displaystyle{ G=(V_1,V_2,E)}\), którego wierzchołkami są pewne podzbiory zbioru \(\displaystyle{ \left[ 2m\right]}\), w następujący sposób:
\(\displaystyle{ V_1=\left\{ A \subseteq \left[ 2m\right]:\left| A\right|=k \right\}}\)
\(\displaystyle{ V_2=\left\{ B \subseteq \left[ 2m\right]:\left| B\right|=k+1 \right\}}\)
dla \(\displaystyle{ A \in V_1}\) oraz \(\displaystyle{ B \in V_2}\)
\(\displaystyle{ \left\{ A,B\right\} \in E \Leftrightarrow A \subseteq B}\).
Udowodnij, że w grafie \(\displaystyle{ G}\) istnieje skojarzenie pełne z \(\displaystyle{ V_1}\) do \(\displaystyle{ V_2}\).
Jak to zrobić?
Załóżmy, że m i k są liczbami
- VirtualUser
- Użytkownik
- Posty: 443
- Rejestracja: 2 wrz 2017, o 11:13
- Płeć: Mężczyzna
- Podziękował: 113 razy
- Pomógł: 15 razy
Re: Załóżmy, że m i k są liczbami
To zadanie to zastosowanie tw. Halla.
Ustalmy \(\displaystyle{ v_1 \in V_1}\). Jaki jest \(\displaystyle{ \deg(v_1)}\)?
Ustalmy \(\displaystyle{ v_1 \in V_1}\). Jaki jest \(\displaystyle{ \deg(v_1)}\)?
- MrCommando
- Użytkownik
- Posty: 554
- Rejestracja: 5 gru 2016, o 21:55
- Płeć: Mężczyzna
- Lokalizacja: Płock/MiNI PW
- Podziękował: 48 razy
- Pomógł: 107 razy
Re: Załóżmy, że m i k są liczbami
Czego w nim nie rozumiesz konkretnie?
Wierzchołek ze zbioru \(\displaystyle{ V_1}\) jest jakimś podzbiorem \(\displaystyle{ k}\)-elementowym \(\displaystyle{ [2m]}\). Pytanie o stopień równoważne jest pytaniu ile jest \(\displaystyle{ k+1}\)-elementowych podzbiorów \(\displaystyle{ [2m]}\) zawierających nasz poprzedni ustalony \(\displaystyle{ k}\)-elementowy.
Wierzchołek ze zbioru \(\displaystyle{ V_1}\) jest jakimś podzbiorem \(\displaystyle{ k}\)-elementowym \(\displaystyle{ [2m]}\). Pytanie o stopień równoważne jest pytaniu ile jest \(\displaystyle{ k+1}\)-elementowych podzbiorów \(\displaystyle{ [2m]}\) zawierających nasz poprzedni ustalony \(\displaystyle{ k}\)-elementowy.
-
- Użytkownik
- Posty: 3394
- Rejestracja: 26 maja 2016, o 01:25
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 981 razy
- Pomógł: 3 razy
Re: Załóżmy, że m i k są liczbami
Aha, bo krawędź pomiędzy wierzchołkami jest wtedy jak drugi zbiór zawiera pierwszy. No dobra, to coś mi zaczyna świtać chyba. To ten stopień to będzie \(\displaystyle{ 2m-k}\)?