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}}\)
Jedynki w macierzy
- mol_ksiazkowy
- Użytkownik
- Posty: 11406
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: Jedynki w macierzy
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):
... /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}\)
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):
... /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}\)