Matematyka.pl

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.

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.