Jedynki w macierzy

Przestrzenie wektorowe, bazy, liniowa niezależność, macierze.... Formy kwadratowe, twierdzenia o klasyfikacji...
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 5847
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 2393 razy
Pomógł: 643 razy

Jedynki w macierzy

Post autor: mol_ksiazkowy » 4 maja 2019, o 22:05

Dana jest macierz kwadratowa \(\displaystyle{ A}\) wymiaru \(\displaystyle{ n}\) , o elementach \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\), która nie ma podmacierzy \(\displaystyle{ \left[\begin{array}{cc}a_{i,r}&a_{i,s}\\ a_{j,r}&a_{j,s} \end{array}\right]}\) zbudowanej z samych jedynek.
Udowodnić, że ilość jedynek w \(\displaystyle{ A}\) nie jest większa niż \(\displaystyle{ n \sqrt{2n-1}}\)

Mruczek
Użytkownik
Użytkownik
Posty: 1110
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 155 razy

Re: Jedynki w macierzy

Post autor: Mruczek » 5 maja 2019, o 17:34

To jest bardzo znany problem. Robimy z tej macierzy graf dwudzielny, który ma po \(\displaystyle{ n}\) wierzchołków z każdej strony - jeden zbiór wierzchołków odpowiada kolumnom, a drugi wierszom tej macierzy. Łączymy krawędzią tylko te pary wierzchołków, dla których w odpowiadających im polach macierzy (kolumnie i wierszu) stoi jedynka.
Teraz podmacierz z samymi jedynkami odpowiada cyklowi długości \(\displaystyle{ 4}\) w tym grafie, a my szukamy maksymalnej liczby krawędzi (czyli jedynek) w takim grafie tak aby nie miał cyklu długości \(\displaystyle{ 4}\).

Rozwiązanie np. tutaj (rozdział 2.2):
http://www.thi.informatik.uni-frankfurt ... /44-49.pdf

Podane tam szacowanie należy osłabić:
\(\displaystyle{ |E| \le \frac{n}{4}(1 + \sqrt{4n - 3} ) \le n \sqrt{2n - 1}}\)
\(\displaystyle{ 1 + \sqrt{4n - 3} \le 4\sqrt{2n - 1}}\), do kwadratu
\(\displaystyle{ 1 + 4n - 3 +2\sqrt{4n - 3} \le 16(2n - 1)}\)
\(\displaystyle{ 2\sqrt{4n - 3} \le 28n - 14}\)
\(\displaystyle{ \sqrt{4n - 3} \le 14n - 7}\)
\(\displaystyle{ \sqrt{4n - 3} \le 2n \le 7n \le 14n - 7n \le 14n - 7}\)

ODPOWIEDZ