Умова k + l ВЈ kl виключає випадки матриць з одного рядком або одним стовпцем, в яких взагалі циклу побудувати не можна.
Доказ. Розглянемо мінімальний можливий випадок: k = 2, l = 2 (табл.4).
В
У макеті треба вибрати k + l = 4, тобто всі 4 клітини. Для цього випадку теорема справедлива: вибрані клітини утворюють цикл.
Візьмемо тепер будь-які k > 2, l > 2. Доказ будемо вести методом математичної індукції. p> Припустимо, теорема справедлива для макета, у якого сума рядків і стовпців на одиницю менше взятих нами ( k + l ). Доведемо, що при цьому припущенні теорема буде справедлива для прийнятих ( k + l ). p> Перший випадок. Серед відзначених клітин є одна клітина, єдина в ряді (рядку або стовпці) (табл.5).
В
Відмовимося від цієї клітини, виключимо цей рядок з розгляду. Тоді прийдемо до таблиці, у якої рядків на одиницю менше, а число стовпців збереглося. Число рядків в сумі з числом стовпців буде менше ( K + l ) на одну одиницю, але і число відмічених клітин зменшиться на одну. Для цього випадку можна побудувати цикл за прийнятим допущенню. Цей цикл візьмемо і для нашої таблиці, так як відповідно до застереженням вершини циклу можуть бути і не вo всex відмічених клітинах.
Другий випадок. Немає таких ситуацій, коли клітина одна. У кожному рядку (стовпці) більше ніж одна клітина (або немає ні однієї) (табл.6).
В
Відзначимо одну клітку знаком плюс, підемо від неї по рядку, потрапимо в клітку, яка в іншому стовпці і неєдиним в ньому; по стовпці перейдемо в інший рядок, по цьому рядку в іншій стовпець і т.д. Це можна було б продовжувати до безкінечності, якби не було кінцевим число відмічених клітин. На якомусь етапі прийдемо в рядок (стовпець), в якій вже були, чим буде замкнута ланцюг, тобто отриманий цикл.
Вище було показано, що теорема справедлива для k = 2, l = 2, тобто для k + l = 4. За доведеним вона справедлива для випадків: k + l = 5, тобто k + l > 4; k + l = 6, тобто k + l > 5; k + l > 6 і т.д., т.е . для будь-якого макета.
Допустимий план Х ( x ij ) називається ациклічним (нециклічне), якщо набір клітин з відмінними від нуля компонентами плану x ij > 0 не містить жодного циклу.
Приклад ациклического плану наведено в табл.7,
В
де точки позначають клітини, в яких x ij > 0 ( x ij <0 неприпустимі за змістом задачі). Як покажемо нижче, серед ациклічних планів є оптимальний. p> Якщо в ациклічному плані Х ( X ij ) число позитивних компонентів
N = k + l - 1 (Інші компоненти - нулі), то елементи a ...
