Matice
Zadání
Matici K(N,c,d) definujeme jako celočíselnou čtvercovou matici velikosti NxN, která má na hlavní i vedlejší diagonále pouze nuly. V oblasti nad hlavní a nad vedlejší diagonálou a v oblasti pod hlavni a pod vedlejší diagonálou obsahuje matice K(N,c,d) pouze hodnoty c. Všude jinde obsahuje hodnoty d.
Příklad: K(7, 4, 1):
0 4 4 4 4 4 0 1 0 4 4 4 0 1 1 1 0 4 0 1 1 1 1 1 0 1 1 1 1 1 0 4 0 1 1 1 0 4 4 4 0 1 0 4 4 4 4 4 0
Pro daná celá čísla N, a1 ≤ a2, b1 ≤ b2 defnujeme množinu matic M(N, a1, a2, b1, b2) takto:
M(N, a1, a2, b1, b2) = \{K(N, c, d) | a1 ≤ c ≤ a2, b1 ≤ d ≤ b2 }.
Dvě matice A a B z množiny M(N, a1, a2, b1, b2) prohlásíme za spřízněné, pokud součet jejich norem nepřevýší danou celočíselnou hodnotu D. Normu libovolné matice Z definujeme jako horní celou část odmocniny ze součtu druhých mocnin všech prvků Z.
Připomínáme, že libovolný neorientovaný graf je souvislý právě tehdy, když mezi dvěma jeho libovolnými uzly u a v vede cesta. Graf je také souvislý právě tehdy, když při prohledávání do šířky nebo do hloubky, které zahájíme v libovolném uzlu grafu, navštívíme postupně všechny uzly grafu.
Každou matici množiny M(N, a1, a2, b1, b2) prohlásíme za uzel neorientovaného grafu G. Hrana mezi dvěma různými uzly u a v grafu G existuje právě tehdy, pokud matice odpovídající uzlům u a v jsou navzájem spřízněné.
Máme určit minimální možnou hodnotu D, pro níž graf G zkonstruovaný nad množinou M bude souvislý.