Witam
Dostałem do wykonanie takie zadanie realizując temat ze skojarzeń w teorii grafów,
Dana jest macierz zero-jedynkowa \(\displaystyle{ n \times m}\) taka, że każdy wiersz i każda kolumna zawiera dokładnie k jedynek \(\displaystyle{ (k \ge 1)}\). Uzasadnij, że można wybrać w tej macierzy n jedynek tak, by każda kolumna i każdy wiersz zawierały tylko jedną z wybranych jedynek.
Nie wiem, w ogóle jak to ugryźć. Próbowałem zinterpretować macierz jako macierz incydencji grafu, lecz nie widzę żadnych zależności, które mogłyby mi pomóc.
Wybranie jedynek z macierzy (skojarzenia grafów)
-
- Użytkownik
- Posty: 318
- Rejestracja: 23 paź 2009, o 20:17
- Płeć: Mężczyzna
- Lokalizacja: Gorzów Wlkp.
- Podziękował: 80 razy
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Wybranie jedynek z macierzy (skojarzenia grafów)
No jak każdy wiersz i każda kolumna zawiera dokładnie \(\displaystyle{ k}\) jedynek, to musi być \(\displaystyle{ n = m}\). Zinterpretuj tą macierz jako graf dwudzielny (wiersz to jeden zbiór, a kolumna drugi). Wtedy każdy wierzchołek tego grafu ma stopień \(\displaystyle{ k}\). No a Ty masz pokazać, że da się wybrać tak jedynki, żeby było po jednej w wierszu i kolumnie, czyli że w tym grafie dwudzielnym istnieje skojarzenie doskonałe.
To jest znany fakt, że graf regularny dwudzielny ma dosk. skojarzenie. Trzeba skorzystać z tw. Halla. Weźmy dowolny zbiór \(\displaystyle{ X}\) wierzchołków z jednej strony. Trzeba pokazać, że zbiór jego sąsiadów ma wielkość przynajmniej taką jak \(\displaystyle{ X}\). Jak zliczymy liczbę krawędzi między tymi zbiorami to to wyjdzie.
To jest znany fakt, że graf regularny dwudzielny ma dosk. skojarzenie. Trzeba skorzystać z tw. Halla. Weźmy dowolny zbiór \(\displaystyle{ X}\) wierzchołków z jednej strony. Trzeba pokazać, że zbiór jego sąsiadów ma wielkość przynajmniej taką jak \(\displaystyle{ X}\). Jak zliczymy liczbę krawędzi między tymi zbiorami to to wyjdzie.