Ідеальна матриця

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Ідеальна матриця — це m-by-n двійкова матриця, яка не має k x k підматриць K, що задовольняють таким умовам:[1]

  • k > 3
  • Суми елементів рядків та колонок K дорівнюють b, де b ≥ 2
  • Не існує жодного рядка (m − k) x k підматриці, яка утворена з рядків, що не були включені в K, із сумою елементів рядка, що більша за b.

Наступна матриця є прикладом підматриці K, де k = 5 і b = 2:


\begin{bmatrix}
1 & 1 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 1
\end{bmatrix}.

Примітки[ред.ред. код]

  1. D. M. Ryan, B. A. Foster, An Integer Programming Approach to Scheduling, p.274, University of Auckland, 1981.