МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

КАФЕДРА ТЕОРЕТИЧЕСКОЙ КИБЕРНЕТИКИ

А. В. Косточка

ДИСКРЕТНАЯ МАТЕМАТИКА

Учебное пособие

Часть 2

Новосибирск

2001

ББК: B 183.5 я73-1

УДК: 519

Пособие является второй частью конспекта лекций по курсу "Дискретная математика". Рассматриваются дискретные алгоритмические задачи (включая основы теории матроидов) и задачи теории кодирования. Пособие предназначено для студентов физического факультета НГУ (специальность "информатика").

Переиздание подготовлено при поддержке гранта ФЦП "Интеграция" N 274.

c Новосибирский государственный университет, Предисловие Настоящее учебное пособие является переизданием второй части конспекта лекций по курсу "Дискретная математика". Первая часть конспекта, написанная вместе с Ф. И. Соловьевой, посвящена основам теории булевых функций, комбинаторики (включая некоторые дискретные задачи теории вероятностей) и теории графов. В пособии рассматриваются дискретные алгоритмические задачи (включая основы теории матроидов) и задачи теории кодирования.

При подготовке лекций использована в основном следующая литература:

1. Г. П. Гаврилов, А. А. Сапоженко, Задачи и упражнения по курсу дискретной математики. М.: Наука, 1992.

2. Э. Х. Гимади, Н. И. Глебов, Экстремальные задачи принятия решений. Новосибирск: НГУ, 1982.

3. В. А. Евстигнеев, Применение теории графов в программировании. М.: Наука, 1985.

4. В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич, Лекции по теории графов. М.: Наука, 1990.

5. В. Липский Комбинаторика для программистов. М.: Мир, 1988.

6. Х. Пападимитриу, К. Стайглиц, Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

7. С. В. Яблонский, Введение в дискретную математику. М.: Наука, 1979.

Большую помощь в подготовке пособия оказали Ф. И. Соловьева и О. Г. Заварзина.

1 АЛГОРИТМЫ ИХ СЛОЖНОСТЬ

1.1 Понятие сложности алгоритмов ЭВМ выполняют пока лишь корректно поставленные задачи. В частности, они выполняют алгоритмы точные и однозначно понимаемые последовательности команд, при помощи которых решаются определенные вычислительные задачи. Существует ряд разных определений понятия алгоритм, (рекурсивные функции, машины Тьюринга – Поста (одноленточные и многоленточные), нормальные алгоритмы Маркова, машины с произвольным доступом к памяти). Оказалось, что множество функций, вычислимых с помощью определенных по-разному алгоритмов, почти совпадает. Это означает, что определения были вполне естественны.

Введем несколько понятий. Под массовой задачей (далее – просто задачей) мы понимаем общий вопрос, на который следует дать ответ.

Задача содержит некоторые параметры, значения которых не определены. Нам нужны 1. Общий список параметров;

2. Формулировка свойств, которым должен удовлетворять ответ.

Индивидуальная задача получается из массовой, когда всем параметрам массовой задачи присвоены конкретные значения.

Пример. Массовая задача: 1) параметры a и b;

2) найти a + b.

Индивидуальная задача: найти 2 + 3.

Понятно, что говорить об алгоритмах имеет смысл лишь для массовых задач. Поскольку упомянутые выше определения алгоритмов были строгими, оказалось, что в терминах любого из них существуют неразрешимые задачи, то есть такие, что для них не существует алгоритма, который за конечное время для любых исходных данных давал бы решение. Тьюринг показал, что не существует алгоритма, который по любой программе для так называемой машины Тьюринга может за конечное время указать, будет ли машина работать по этой программе бесконечно.

На практике более актуален другой вопрос. Нас интересует не просто конечное время работы алгоритма, а возможность получить ответ за не слишком большое время.

Пример. Пусть в полном n-вершинном графе каждому ребру сопоставлен вес. Требуется найти каркас (т. е. остовное дерево), сумма весов ребер которого минимальна. Это так называемая задача о кратчайшей связывающей сети. Она может возникнуть, например, при построении самой дешевой сети дорог, связывающей данные n населенных пунктов.

Очевидно, конечный алгоритм решения этой задачи состоит в просмотре всех каркасов и выборе среди них каркаса минимального веса. Но при этом потребуется рассмотреть, как мы знаем, nn2 вариантов, что уже при n 40 больше 1060.

Поэтому естественной мерой качества работы алгоритма является отрезок времени, затрачиваемый ЭВМ для окончательного ответа. Мы будет оценивать время работы алгоритма в терминах числа элементарных шагов (арифметических операций, сравнений и т. д.), необходимых для выполнения работы алгоритма на гипотетической ЭВМ. Для простоты будем считать, что элементарные операции требуют одинакового времени. Понятно, что малые объемы входной информации ЭВМ должна обрабатывать быстрее, чем большие. Мы будем оценивать fA (n) максимальное время работы алгоритма A по всем входам длины не более n.

Как измерять длину входа? Длиной целого числа m естественно считать log m. Если граф (орграф) G задан матрицей смежности, то длина записи есть O(n2 ), где n число вершин G; если списком смежностей то O(m log n+n), где m число ребер G. Если дана целочисленная матрица A = (aij )n, то длина ее записи есть O(mn + i,j log(ai,j + 1)). Но поскольку многие современные ЭВМ отводят разным числам примерно одинаковое место, мы будем считать, что длина записи информации о графе G, заданном списком смежностей, есть O(m + n), где m число ребер, а n число вершин графа G.

Нас будет интересовать порядок роста функции fA (n), а не точные ее значения. Будем говорить, что алгоритм эффективен, если для некоторого фиксированного k Рассмотрим на примере, чем это обусловлено.

Предположим, что fA1 (n) = 2n, fA2 (n) = 106 n2. Во-первых, при достаточно больших n (а именно, при n 30) A2 работает быстрее, чем A1.

Во-вторых, предположим, что некоторая ЭВМ за время t может решать с помощью A1 все задачи с длиной входа не более n1, а с помощью A все задачи с длиной входа не более n2. Пусть, далее, быстродействие нашей ЭВМ увеличилось в 16 раз. Тогда она за время t сможет решать с помощью A2 все задачи с длиной входа не более 4n2, а с помощью A все задачи с длиной входа не более n1 + 4.

1.2 Поиск по графу Существует ряд алгоритмов на графах, основанных на таком систематическом переборе, при котором каждая вершина просматривается ограниченное число раз. Поэтому важно знать хорошие методы поиска вершин в графе.

Пусть граф G = (V, E) задан списком смежности A(v)(v V ) своих вершин. Алгоритм ПОИСК работает следующим образом.

Вход. Граф G; вершина v.

Выход. Тот же граф, в котором вершины, достижимые из v, помечены.

Begin Begin Пусть x Q; удалить x из Q;

End Утверждение 1.1. Алгоритм ПОИСК помечает все вершины графа G, достижимые из v, за время O(|E|).

ДОКАЗАТЕЛЬСТВО. Если на каком-то шаге в Q были лишь вершины, достижимые из v, то и на следующем шаге в Q будут лишь вершины, достижимые из v. И наоборот, индукцией по расстоянию от v легко доказать, что любая достижимая из v вершина рано или поздно окажется в Q.

Для оценки трудоемкости заметим, что работа алгоритма разбивается на три части.

1. Начальный шаг. Требуется время O(1) (для записи v).

2. Работа с множеством Q. Добавление и удаление элементов множества Q производится 2|V1 | раз, где V1 множество достижимых из v вершин. Заметим, что |V1 | |E| + 1. Если организовать Q очередью или стеком, то каждое включение требует не более трех элементарных операций с числами.

3. Поиск по спискам смежностей. При этом любой элемент списков просматривается один раз, а общее число элементов равно 2|E|.

Суммарно получаем оценку O(|E|). (Везде далее в тексте знак читается "окончание доказательства".) Пример. Алгоритм ПОИСК можно непосредственно использовать для проверки графа на связность и для нахождения компонент связности.

Когда Q организована в виде стека, имеем ПОИСК В ГЛУБИНУ (ПГ) (depth-rst search). При ПГ в стеке все время хранится путь от v до рассматриваемой вершины x. Можно выделять дерево поиска, образующееся при ПГ.

Пример. Поиск в глубину.

Если Q организована в виде очереди, то получаем ПОИСК В ШИРИНУ (ПШ) (breadth-rst search).

Пример. Поиск в ширину.

При ПШ просматриваются вершины сначала на расстоянии 1 от v, а затем на расстоянии 2 и т. д. ПШ удобен для нахождения кратчайшего (по числу ребер или дуг, если граф ориентированный) пути из v до заданной вершины. Более того, дерево поиска при ПШ является деревом кратчайших (по числу ребер) расстояний от v до остальных вершин из той же самой компоненты связности.

1.3 Быстрая сортировка Сортировкой называют упорядочение множества объектов по неубыванию или невозрастанию какого-нибудь параметра. Существует много эвристических алгоритмов сортировки. Но многие из них в худших случаях требуют выполнения O(n2 ) операций сравнения параметров, где n число объектов в рассматриваемом множестве. Мы приведем два алгоритма, которые даже в худшем случае требуют выполнения O(n log n) операций сравнения параметров.

Первый из них иногда называют алгоритмом фон Неймана.

На вход подается последовательность чисел a(1),..., a(n). Алгоритм работает log2 n итераций. Перед началом итерации с номером k (k = 1, 2,..., log2 n ) имеется последовательность a(i(1)),..., a(i(n)) тех же чисел, разбитая на группы по 2k1 элементов (последняя группа может быть неполной), и внутри каждой группы элементы упорядочены по неубыванию. Итерация состоит в том, что эти группы разбиваются на пары соседних групп и элементы упорядочиваются внутри этих новых в два раза больших групп. При этом используется то, что внутри исходных групп элементы уже упорядочены. Пусть, например, элементы групп x1,..., xm и y1,..., ym уже упорядочены. Последовательность z1,..., z2m образована из них по следующим правилам.

Полагаем z1 = min{x1, y1 }. Если этот минимум достигается на x1, то x2 сравниваем с y1 и минимум обозначаем через z2, и т. д. После каждого сравнения одно из сравниваемых чисел вносится в список zi, пока не кончатся элементы одной из групп. Тогда далее просто выписываются оставшиеся элементы еще не истощившейся группы.

Упражнения 1. Доказать, что приведенный выше алгоритм упорядочивает числа a(1),..., a(n) по неубыванию.

2. Доказать, что приведенный выше алгоритм использует не более n · log2 n операций сравнения.

Следующий алгоритм более сложен. Будем называть его пирамидальным алгоритмом. Он состоит из двух этапов.

На первом этапе за линейное (от количества элементов) число шагов мы добиваемся, чтобы для каждого i (1 i n) элемент с номером i был не меньше, чем элемент с номером i/2. На втором этапе происходит окончательное упорядочение.

Назовем (i, n)-операцией следующую последовательность действий.

Сравниваем a2i и a2i+1. Пусть x меньшее из этих чисел (если 2i = n или a2i = a2i+1, то x = a2i ). Сравниваем x с ai ; если ai > x, то меняем местами ai и x.

Так называемая (j, n)-процедура состоит в следующем. Выполняем (j, n)-операцию. Если aj переместилось вниз (скажем, стало a2j+1 ), то производим (2j + 1, n)-операцию, и так далее, пока либо в результате очередной операции наше бывшее число aj не перестанет опускаться, либо его новый номер не станет больше n/2.

На первом этапе последовательно для j = n/2, n/2 1,..., выполняем (j, n)-процедуру.

Упражнения 1. Доказать, что после первого этапа ai min{a2i, a2i+1 } для любого 2. Доказать, что если n = 2k 1, то для выполнения первого этапа достаточно выполнить n k (i, n)-операций.

3. Доказать, что описанный первый этап алгоритма использует не более 2n (i, n)-операций.

Перед началом j-й итерации второго этапа (j1) самых малых чисел уже стоят на местах n, n 1,..., n j + 2, а для каждого i (1 i n j + 1) элемент с номером i не меньше, чем с номером i/2. Из-за этого самый малый из первых nj +1 элементов стоит на первом месте.

На j-й итерации первый и (n j + 1)-й элементы меняются местами, а затем выполняется (1, n j)-процедура. После этого упорядочено уже j элементов и выполнены условия для (j + 1)-й итерации. После n-й итерации все числа будут упорядочены по невозрастанию. Поскольку (1, n j)-процедура при любом j и любых наборах чисел требует не более чем log2 n + 1 (i, n j)-операций, общая трудоемкость алгоритма не более O(n log n) элементарных операций.

Замечания 1. Можно запрограммировать работу алгоритма так, что почти не потребуется дополнительной памяти.

2. Если требуется найти только k самых малых элементов, то на втором этапе достаточно k итераций.

1.4 Идея динамического программирования на примере распределительной задачи и обратной к ней Метод динамического программирования (ДП), созданный Р. Беллманом, можно трактовать как алгоритмическую версию рассуждений по индукции. Он применим к процессам, имеющим этапы, где любой отрезок оптимальной последовательности решений сам является оптимальным. Например, если кратчайший путь между x и y проходит через v, то часть этого пути от v до y сама является кратчайшим путем от v до Рассмотрим задачу. Пусть имеется n предприятий и Y единиц некоторого ресурса. Известно количество fk (x) продукции, которое будет произведено на k-м предприятии, если в него будет вложено x единиц ресурса. Считаем, что fk (x) монотонно неубывающая функция при любом k. Требуется максимизировать объем произведенной продукции.

Сформулируем задачу математически.

Идея ДП состоит в разбиении большой задачи на много малых, которые решаются просто. В данном случае пусть sk (y) для 1 k n, 0 y Y есть значение целевой функции задачи (1)–(3), где n заменено на k, Y на y. Наша цель найти sn (Y ) и набор переменных, на котором достигается это значение.

Теорема 1.2. Если функции f1,..., fn монотонно неубывающие, то справедливы следующие рекуррентные соотношения:

ДОКАЗАТЕЛЬСТВО. Соотношение (4) очевидно. По определению Пусть теперь (x,..., x ) такой вектор, что x +... + x y и sk (y) = = f1 (x ) +... + fk (x ). Поскольку Алгоритм ДП для этой задачи вычисляет множества Sk = = {sk (y) | 0 y Y }, k = 1, n с помощью соотношений (4) и (5), где на каждом шаге оптимизируется ровно одна переменная. Процесс вычисления S1,..., Sn называется прямым ходом алгоритма. При обратном ходе алгоритма вычисляются x,..., x с учетом того, что уже известn ны Sk. Так, x определяется из уравнения sn (Y ) = fn (x )+sn1 (Y x ) и так далее.

Это алгоритм с одним прямым и одним обратным ходом.

При релаксационном варианте запоминаются только последние значения Sk и в конце находятся sn (Y ) и x. Затем работа алгоритма наn чинается сначала и продолжается до нахождения sn1 (Y x ) и x. n n Далее аналогично находятся x,..., x.

Оценим трудоемкость алгоритма ДП с одним прямым и одним обратным ходом. Пусть Нам требуется вычислять nY величин sk (y) и для каждого вычисления надо подсчитать и сравнить y +1 выражений вида sk1 (y x)+fk (x).

Так как sk1 (y x) + fk (x) nM, то общее количество затраченных элементарных операций есть O(Y nY log nM ) = O(nY 2 log nM ). На обратном ходе нужно вычислить только Y величин sk (y). Требуемая память O(nY log nM ).

Время работы релаксационного варианта алгоритма составляет O(n2 Y 2 log nM ), зато требуемая память O(Y log nM ).

Обобщим задачу (1) - (3) следующим образом:

Содержательные интерпретации этой задачи понятны.

Если hi (x) целочисленные монотонно неубывающие функции, то вместо (4) – (5) можно использовать следующие рекуррентные соотношения:

В целом задачу можно трактовать как поиск способа получения наибольшего количества продукции при ограниченных ресурсах. Естественной постановкой является также задача поиска наименьших затрат на получение заданного количества продукции:

Задача (6) (8) называется обратной к задаче (1 ) (3 ). Если fk (x) целочисленные монотонно неубывающие функции, то для решения задачи (6) (8) тоже можно использовать динамическое программирование. Обозначим fi1 (d) = min{0 x ai |fi (x) d}. Пусть tk (d) для 1 k n; 0 d D есть решение задачи (6) (8), в которой n заменено на k, а D на d. Наша цель найти tn (D). Справедливы следующие рекуррентные соотношения:

Теорема 1.3. Предположим, что D наибольшее число, для которого оптимальное значение целевой функции задачи (6) (8) не превосходит Y. Тогда оптимальное значение целевой функции задачи (1 ) (3 ) равно D.

ДОКАЗАТЕЛЬСТВО. Пусть D удовлетворяет условию теоремы и (x,..., x ) соответствующее решение задачи (6) (8). Это значит, тельно, D не превосходит оптимального решения D1 задачи (1 ) (3 ).

Если бы D1 было больше, чем D, то решение задачи (6) (8), в которой D заменено на D1, тоже не превышало бы Y, что противоречит максимальности D.

Таким образом, если, например, hi не целочисленны, а fi целочисленны, то задачу (1 ) (3 ) можно решать переходом к обратной задаче.

1.5 Задача о кратчайшем пути Как мы уже видели, алгоритм поиска в ширину позволяет за O(|E|) шагов для любой вершины графа с невзвешенными ребрами найти кратчайшие пути от нее до всех остальных вершин. В настоящем параграфе приведены алгоритмы нахождения кратчайших путей в графах (орграфах), ребра (дуги) которых могут иметь разную длину.

Вход. Орграф G = (V, A) с длинами cuv 0 его дуг; вершина s V.

Выход. Вектор кратчайших расстояний от s до всех v V и вектор p предшественников на кратчайших путях из s в v.

Begin положить W := s, (s) := 0, p(s) := ;

For all y V \{s} do {(y) := csy, p(y) := s};

Begin найти min{(y)|y V \W }; пусть это (x);

end Утверждение 1.4. Алгоритм Дейкстры находит кратчайшие пути из вершины s до каждой из остальных вершин за O(|V |2 ) операций сравнения и сложения.

ДОКАЗАТЕЛЬСТВО. Покажем сначала, что на каждой итерации справедливо:

a) Для любой вершины x V величина (x) равна длине кратчайшего из путей от s до x, все промежуточные б) Для любой вершины w W величина (w) есть длина Поскольку в конце работы алгоритма W = V, то из (11) будет следовать, что на выходе станет вектором кратчайших расстояний от s до остальных вершин. Итак, когда W = {s}, то (11) верно. Предположим, что на некотором шаге (11) верно и (x) = min{(y) | y V \W }.

Допустим, что длина некоторого пути (s, v1, v2,..., vt, x) меньше (x).

Тогда согласно (11а) имеем {v1, v2,..., vt } \ W =. Пусть i наименьший номер, для которого vi W. По выбору, (vi ) длина (s, v1, v2,..., vi ) длина (s, v1, v2,..., vt, x) < (x). Это противоречит минимальности (x). Значит, (x) есть длина кратчайшего пути от s до x и (11б) будет продолжать выполняться после добавления x к W.

После пересчета (y) := min{(y), (x) + cxy } утверждение (11а) тоже будет выполняться. Таким образом, (11) доказано.

На каждой итерации не более |V | раз выбирается минимум из двух чисел. Число итераций равно |V | 1.

В алгоритме Дейкстры существенно, что длины всех дуг неотрицательны. Для нахождения самих кратчайших путей служит величина p(y), указывающая последнюю вершину на кратчайшем пути из s в y.

Весьма эффективным и просто программируемым является алгоритм Флойда – Уоршелла.

Определение. Пусть дана матрица (dij ) размеров n n. Операцией треугольника относительно j называется пересчет dik := min{dik, dij + +djk } по всем i, k = 1,..., n таким, что j = i, k.

Эта операция заменяет dik на dij + djk, если dij + djk dik.

Если выполнить над матрицей (dij ) операцию треугольника последовательно для j = 1, 2,..., n, то в полученной матрице каждый элемент dik равен длине кратчайшего пути из i в k.

ДОКАЗАТЕЛЬСТВО. Покажем сначала, что для каждого j после выполнения операции треугольника для вершины j элемент dik для любых i и k равен наименьшей длине среди путей из i в k, все промежуточные вершины которых имеют номера, не большие j.

Для j = 1 это утверждение очевидно. Пусть оно верно для j = t и проведена операция треугольника для вершины t:

Если кратчайший путь из i в k в подграфе орграфа G на вершинах {1, 2,..., t, i, k} не проходит через t, то минимум в (12) достигнется на первом аргументе и утверждение остается верным. Если же этот путь проходит через t, то dit +dtk dik, а по индукционному предположению dit и dtk длины кратчайших путей из i в t и из t в k по вершинам с номерами t 1.

Вход. Набор неотрицательных чисел cij (длин дуг G).

Выход. Матрица (dij ) кратчайших расстояний между вершинами G, матрица (eij ) промежуточных вершин с наибольшим номером на кратчайших путях.

Begin For all i = j do dij = cij ;

Begin z := dik ; dik := min{dik, dij + djk };

end Замечания 1. Требуется n(n 1)2 сравнений.

2. Алгоритм правильно работает и в случае, когда в орграфе есть дуги отрицательной длины, но нет контуров отрицательной длины. Если же в G есть контур отрицательной длины, то на одном из шагов для некоторого i значение dii станет отрицательным.

3. Если вначале положить dii =, то в конце dii будет равно длине кратчайшего контура, проходящего через i.

1.6 Метод ветвей и границ на примере задачи Для ряда важных в практическом и теоретическом отношении задач до сих пор неизвестны эффективные алгоритмы их решения. Более того, есть основания полагать, что таких алгоритмов нет вообще.

Возможными выходами здесь является использование приближенных алгоритмов и построение алгоритмов направленного перебора. Обсуждаемая ниже схема метода ветвей и границ (МВГ) принадлежит ко второму типу. Она позволяет решать задачи как на максимум, так и на минимум.

Опишем идею МВГ для задач на минимум. Нам требуется найти минимум функции f (x) на "большом" множестве D. Например, среди всех nn2 каркасов n-вершинного графа найти каркас минимального веса.

На каждом шаге МВГ имеются:

1. Рекорд x элемент с наименьшим значением f (x) среди уже просмотренных.

2. Просмотренная часть P множества D, о которой уже известно, 3. Разбиение = (d1,..., dm ) остального множества.

4. Функция H : P(D) R, называемая нижней границей, которая обладает свойствами:

Шаг МВГ начинается с выбора (по некоторому правилу) какого-то di (например, dm ). Затем вычисляется H(dm ). Возможны следующие варианты:

1. H(dm ) f (x ). Тогда всё dm добавляем к просмотренной части D и переходим к следующему шагу.

2. H(dm ) < f (x ) и известен xm dm с f (xm ) = H(dm ). Тогда полагаем x := xm, всё dm добавляем к просмотренной части D и переходим к следующему шагу.

3. H(dm ) < f (x ) и б) не имеет места. Тогда по определенному правилу разбиваем dm на dm, dm+1,..., dm+s и переходим к следующему шагу, имея вместо разбиения разбиение Поскольку D конечно, то через конечное время минимум функции f (x) на множестве D будет найден.

Важно следующее:

1. Выбор функции H(d) (с одной стороны, ее вычисление должно быть не слишком трудоемким, с другой желательно, чтобы ее значения были не слишком далеки от min{f (x)|x d});

2. Выбор перспективного множества dm (здесь часто удобнее применять просмотр в глубину);

3. Способ разбиения dm, если его не удалось отбросить;

4. Выбор первого рекорда.

Применим схему МВГ для решения задачи коммивояжера. Пусть дана матрица (cij ) неотрицательных стоимостей переезда из города i в город j размеров n n. Напомним, что задача коммивояжера состоит в нахождении наименьшего по суммарной стоимости пройденных дуг замкнутого обхода всех городов, при котором каждый город посещается ровно один раз.

Пусть матрица dij (k, ) определена так:

Тогда длина каждого обхода в задаче с матрицей dij (k, ) отличается от длины этого же обхода в задаче с матрицей cij ровно на. Следовательно, обход i1, i2,..., in в задаче с матрицей cij будет оптимальным, если и только если он будет оптимальным в задаче с матрицей dij (k, ).

Мы используем это свойство в следующем алгоритме типа ветвей и границ для задачи коммивояжера.

1. Множество D это множество замкнутых обходов всех городов, при которых каждый город посещается ровно один раз, f (x) стоимость обхода x в матрице cij.

2. Выбираем первый рекорд x для МВГ (например, по принципу "иди в ближайший из еще не пройденных городов").

3. Подмножества di, которые используются в алгоритме, будут иметь специальный вид. Пара d = ({l1,..., lk }, {q1,..., qs }), где l1 = 1 и |{l1,..., lk, q1,..., qs }| = k + s, определяет множество тех замкнутых обходов, в которых после l1 посещается l2, затем l3,..., lk, а следующим после lk не является ни один из городов q1,..., qs.

4. По заданным {l1,..., lk }, {q1,..., qs } построим матрицу (dij ), где Пусть 5. Положим 6. Выбор перспективного множества будем осуществлять как вариант просмотра в глубину:

(a) множества dm,..., d1 хранятся в стеке;

(b) если после вычисления H(dm ) множество dm просмотрено, то (c) если после вычисления H(dm ) не просмотрено множество индекс t, на котором достигается минимум по j выражения dlk,j lk j, затем разобьем dm на два подмножества:

и, поместив dm в стек, рассмотрим dm+1 ;

(d) если после вычисления H(dm ) не просмотрено множество вместо dm рассматриваем dm = ({l1,..., lk, t}, ), где (e) если k = n 1, то dm содержит только обход (l1,..., ln1, t), Описанный алгоритм неплохо решает задачу коммивояжера.

2 ПОТОКИ В СЕТЯХ

2.1 Сети и потоки в них Сетью будем называть орграф G, некоторые вершины которого отмечены. Отмеченные вершины назовем полюсами, а остальные вершины внутренними. Мы будем рассматривать классические сети с двумя полюсами: источником s и стоком t.

Функция f : E(G) R называется потоком, если для любой внутренней вершины v в G где E + (v) множество дуг сети G, заходящих в v, E (v) множество дуг сети G, выходящих из v.

Рассмотрим Ввиду (13) эта величина равна divf (s) + divf (t). С другой стороны, для любой дуги e = (v, u) величина f (e) входит в сумму (14) с плюсом в слагаемом divf (v) и с минусом в слагаемом divf (u). Следовательно, Величина M (f ) = divf (s) = divf (t) называется мощностью потока f.

Поток нулевой мощности называется циркуляцией.

Мощность линейный функционал на множестве потоков, т. е. для любых потоков f и g и действительных чисел и µ Поток f с f (e) = 0 для каждого e E(G) назовем нулевым потоком.

Простейшими ненулевыми потоками являются:

1) Поток L вдоль ориентированного пути L, ведущего из s в t или из t в s: значения L ненулевые лишь на дугах L;

2) Поток C вдоль контура C: значения C ненулевые лишь на дугах C.

Нетрудно убедиться (проделайте это в качестве упражнения), что значения потока L (соответственно потока C ) одинаковы на всех дугах L (соответственно на всех дугах C). Описанные потоки вдоль путей и циклов будем называть элементарными. Элементарный поток, при котором значение потока на каждой дуге выбранного пути L (или цикла C) равно, будем обозначать через L () (соответственно через C ()).

Скажем, что поток f в сети G положителен, если Лемма 2.1. Произвольную положительную циркуляцию f в сети G можно представить в виде суммы не более чем |E(G)| 1 положительных потоков вдоль контуров.

ДОКАЗАТЕЛЬСТВО. Допустим, что утверждение леммы неверно, G наименьшая по числу дуг сеть, для которой утверждение леммы неверно, а f некоторая циркуляция в G.

Если f (e0 ) = 0 для некоторого e0 E(G), то рассмотрим G = G0 \e и f0 = f |G0. Ввиду минимальности G поток f0 можно представить в виде суммы не более чем |E(G0 )| 1 положительных потоков вдоль контуров. Но это представление и будет требуемым представлением для f. Поэтому в дальнейшем считаем, что Рассмотрим произвольную дугу e1 E(G), e1 = (v0, v1 ). Поскольку f циркуляция, то существует дуга e2 E(G), выходящая из v1, e2 = (v1, v2 ). Аналогично, существует дуга e3 E(G), выходящая из v2, e3 = (v2, v3 ), и т. д. Предположим,что vk первая из вершин, встретившаяся в последовательности v0, v1, v2,... второй раз (такая вершина найдется, так как сеть конечна). Пусть vk = vm, m < k.

Тогда в G имеется контур C = (vm, vm+1,..., vk = vm ). Обозначим = min{f (e)| e E(C)}, C () поток вдоль контура C величины, f = f C. Если f 0, то лемма доказана.

Если f не является тождественно нулевой функцией, то 1) поток f положителен и Для орграфа G0 = G\e0, из-за минимальности G, поток f0 = f |G можно представить в виде суммы не более чем |E(G0 )|1 (= |E(G)|2) положительных потоков вдоль контуров. Но тогда утверждение леммы справедливо для орграфа G, что противоречит его выбору.

Теорема 2.1. Произвольный положительный поток f в сети G можно представить в виде суммы не более чем |E(G)| положительных элементарных потоков.

ДОКАЗАТЕЛЬСТВО. Случай 1. M (f ) 0. Добавим к G новую дугу eo, ведущую из t в s, и в получившейся сети Go положим Поток fo будет циркуляцией в Go, и по лемме 2.1 fo можно представить в виде суммы не более чем |E(Go )| 1(= |E(G)|) положительных потоков вдоль контуров. Контурам сети Go, содержащим дугу eo, в G соответствуют пути из s в t. Отсюда получаем требуемое представление для f.

Случай 2. M (f ) < 0. Тогда добавим к G новую дугу e, ведущую из s в t, и в получившейся сети G положим f (e) = M (f ). Далее действуем аналогично случаю 1.

В дальнейшем под сетью будем понимать орграф G с полюсами s и t, на дугах которого заданы неотрицательные числа c(e), называемые пропускными способностями дуг. То есть G = (V, E, s, t, {c(e)|e E}).

Будут строиться такие потоки f, что Если ранее допускались кратные дуги, то ниже будет удобнее каждый набор {e1,..., er } кратных дуг заменить одной дугой e с c(e) = c(e1 ) +... + c(er ).

В дальнейшем для каждой дуги e E(G) через e будем обозначать обратную к e дугу (которая может как принадлежать, так и не принадлежать E(G)), а через E множество E {e|e E}. Будем полагать c(e) = 0 для e E\E.

Пусть G некоторая сеть и g поток в G, удовлетворяющий условию (15). Построим сеть Gg по следующим правилам. Сначала добавим к G все дуги из E\E. Затем для каждой дуги e E положим Наконец, удаляем дуги e с cg (e) = 0. Сеть Gg построена.

следующим образом. Для каждой дуги e E положим Покажем, что функция f g удовлетворяет ограничениям (15) для сети Gg. Другими словами, докажем, что Действительно, согласно (16) Пусть теперь h поток в сети Gg. Определим функцию h g на E следующим образом. Для каждой дуги e E положим Аналогично предыдущему легко доказывается, что h g удовлетворяет ограничениям (15) для сети G.

Теорема 2.2. Для каждой вершины v V ДОКАЗАТЕЛЬСТВО. Согласно (17), для любой дуги e E Следовательно, Аналогично доказывается утверждение b) нашей теоремы.

Следствие 2.1.Функции f g и h g являются потоками.

Следствие 2.2. M (f g) = M (f ) M (g); M (h g) = M (h) + M (g).

2.2 Теорема о максимальном потоке и минимальном Постановка задачи о максимальном потоке. Дана сеть G с полюсами s и t и набором неотрицательных чисел {c(e)|e E}. Среди потоков f в сети G, удовлетворяющих ограничениям (15), требуется найти поток наибольшей мощности M (G).

Покажем, что максимальный поток существует. В евклидовом замкнутом |E|-мерном пространстве функций f : E R+, удовлетворяющих условиям (15), подпространство потоков M образуется наложением ограничений Значит, при конечных c(e) множество потоков M является замкнутым и ограниченным подмножеством конечномерного евклидова пространства. Но тогда линейный функционал M (f ) достигает на M своего максимума.

Из теоремы 2.2 и следствия 2.1 вытекает Лемма 2.2. Если f g максимальный поток в сети Gg, то f максимальный поток в сети G. Обратно, если h g максимальный поток в сети G, то h максимальный поток в сети Gg.

Разрезом R = (X, X) сети G назовем любое такое разбиение множества V на подмножества X и X, что s X, t X. При этом дуги с началом в X и концом в X называются выходящими из X, и множество таких дуг обозначается E (R). Аналогично, дуги с началом в X и концом в X называются входящими в X, и множество таких дуг обозначается E + (R). Пропускной способностью разреза R называется величина Для любого разреза R и любого потока f в G имеем Лемма 2.3. Если f максимальный поток в сети G, то в сети Gf сток t недостижим из источника s.

ДОКАЗАТЕЛЬСТВО. Допустим, что в Gf есть путь L из s в t. Поскольку пропускные способности всех дуг сети Gf положительны, то число = min{cf (e)|e E(L)} положительно. Пусть L элементарный поток вдоль пути L мощности. Тогда, согласно следствию 2.2, что противоречит выбору f.

Теорема 2.3 (О максимальном потоке и минимальном разрезе.) Величина максимального потока в сети G равна минимальной из пропускных способностей всех разрезов в G.

ДОКАЗАТЕЛЬСТВО. Ввиду (18) нам достаточно построить разрез R = (X, X) такой, что c(R) = M (f ), где f максимальный поток в сети G. Обозначим через X множество вершин, достижимых из s в сети Gf, X = V \X. По определению s X. По лемме 2.3 t X. Значит, разбиение R = (X, X) является разрезом.

Если бы в Gf нашлась дуга (v, u) с v X, u X, то u тоже была бы достижима из s в сети Gf, что противоречит определению X.

Следовательно, для каждой дуги e E, ведущей из X в X, Но c(e) f (e) 0. Значит, f (e) = c(e), f (e) = 0. Таким образом, 2.3 Алгоритмы для нахождения максимального потока Лемма 2.4. Пусть поток f не максимален в G. Тогда в сети Gf существует путь из источника s в сток t.

ДОКАЗАТЕЛЬСТВО. Пусть поток f не максимален в G, и g максимальный поток в Gf. По следствию 2.1 M (g) > 0. По теореме 2.1 поток g можно представить в виде суммы положительных элементарных потоков. Хотя бы один из этих потоков должен быть потоком вдоль пути.

Вход. Сеть G = (V, E, s, t, {c(e)|e E}).

Выход. Поток f в сети G наибольшей мощности.

Begin f = (0,..., 0); H = G;

While в H есть путь L из s в t do begin = min{c(e)|e E(L)} ;

End Если все c(e) рациональны, то алгоритм работает конечное время.

Но в общем случае это не так. Хотя для некоторых простых модификаций АФФ достаточно полиномиального от размеров сети количества элементарных операций.

Назовем рангом вершины v в сети G расстояние (по числу дуг) в G от s до v.

сети Gf, g = L f. Тогда ранг rg (v) любой вершины v в сети Gg не меньше ее ранга в сети Gf.

ДОКАЗАТЕЛЬСТВО. Если rg (v) =, то для v утверждение леммы выполнено. Пусть rg (v) = k и Lv = (vo, v1,..., vk ) кратчайший по числу дуг путь из vo = s в vk = v в сети Gg.

Рассмотрим произвольную дугу e = (vi, vi+1 ) пути Lv. Если e E(Gf ), то rf (vi+1 ) rf (vi ) 1. Если e E(Gf ), то e = (vi+1, vi ) E(Gf ) E(L). Поскольку L кратчайший по числу дуг путь из s в t в сети Gf и e E(L), то rf (vi+1 ) + 1 = rf (vi ) и rf (vi+1 ) rf (vi ) = 1.

Следовательно, Назовем t-рангом вершины v в сети G расстояние (по числу дуг) в G от v до t. Аналогично лемме 2.5 доказывается следующий факт.

Лемма 2.5. Пусть f поток в сети G; L кратчайший по числу дуг путь из s в t в сети Gf ; L поток вдоль пути L в сети Gf, g = f L. Тогда t-ранг trg (v) любой вершины v в сети Gg не меньше ее t-ранга в сети Gf.

Алгоритм кратчайших путей (АКП) отличается от алгоритма Форда – Фалкерсона лишь тем, что увеличивающий путь L ищется с помощью поиска в ширину (и тем самым оказывается кратчайшим в Gf по числу дуг).

Оценим трудоемкость АКП. Как отмечалось в гл. 1, поиск в ширину требует O(|E|) элементарных операций (множитель log |V | возникал изза того, что длина номера вершины может быть порядка log |V |). Для вычисления и пересчета f и H достаточно O(|V |) элементарных операций, поскольку пересчет происходит лишь для дуг L и обратных к ним. Значит, каждая итерация требует не более O(|E|) элементарных операций.

Чтобы оценить число итераций, разобьем их на группы. В k-ю группу попадут те итерации, на которых ранг вершины t равен k. По лемме 2.5 все итерации из группы k идут подряд. Предположим, что перед началом итераций k-й группы мы имели сеть Gg.

Лемма 2.6. Все дуги увеличивающих путей k-й группы итераций АКП принадлежат Gg, и для каждой используемой дуги ранг в Gg ее конца на единицу больше ранга ее начала.

ДОКАЗАТЕЛЬСТВО. Обозначим через Vj, j = 0, 1,..., |V | множество вершин ранга j в Gg. Покажем, что любая дуга любого из увеличивающих путей k-й группы итераций ведет из Vj в Vj+1 для некоторого j {0, 1,..., k 1}. По леммам 2.5 и 2.5 для каждой вершины v, лежащей на каком-нибудь увеличивающем пути, имеем r(v) + tr(v) = k.

Пусть L первый из увеличивающих путей k-й группы итераций, в котором есть такая дуга (v, u), v Vi, u Vj, что j = i + 1. Поскольку L первый такой путь, то "новые" (по сравнению с Gg ) дуги могут вести лишь из Vi в Vi1 для некоторого l {1,..., k}. Значит, j i. Но тогда L должен содержать более чем k дуг.

Поскольку на каждой итерации из k-й группы хотя бы одна из "старых" дуг исчезает (поворачивается), то эта группа состоит из менее чем |E| итераций. Отсюда следует оценка O(|E|2 |V |) элементарных операций для АКП.

Заметим еще раз, что на итерациях k-й группы участвовали лишь такие вершины ранга j, j {0, 1,..., k}, в Gg, расстояние от которых до t равно k j. А дуги, использованные на этих итерациях, ведут из Vj в Vj+1 для некоторого j {0, 1,..., k 1}. Построить такую подсеть можно за O(|E|) элементарных операций: сначала поиском в ширину найти множества Vj, j = 0, 1,... k, затем обратным поиском в ширину из t выделить те из них, расстояние от которых до t равно k j, и, наконец, оставить только нужные дуги.

Применим модификацию АКП для построения путей длины k в полученной k-слойной сети.

На каждой итерации последовательно для i = 0, 1,..., k 1 делаем следующее: уже имеется путь (v0, v1,..., vi ) от vo = s до vi, и если E (vi ) =, то удаляем vi из сети вместе со всеми инцидентными ей дугами и начинаем новую итерацию; а если E (vi ) =, то добавляем к пути (vo, v1,..., vi ) первую дугу (vi, vi+1 ) из списка E (vi ). Если мы дошли до t, то понижаем пропускные способности дуг (vi, vi+1 ) для i = 0, 1,..., k 1 на величину = min{c(vi, vi+1 )| i {0, 1,..., k 1}} и удаляем дуги с новыми пропускными способностями, равными нулю.

Получается, что на удаление из нашей подсети одной дуги тратится O(k) элементарных операций, на k-ю группу O(|E||V |), а общая труO(|E||V |2 ) элементарных доемкость модифицированного алгоритма операций.

Существуют и более быстрые алгоритмы для нахождения максимального потока. Их трудоемкости O(|V |2 |E|) и O(|E||V |log|V |).

2.4 Использование сетевых моделей для нахождения связности графов. Теорема Менгера и теорема Уитни Пусть G = (V, E) орграф, B, C V, B C =. Подмножество X дуг (вершин, не принадлежащих B C) в G называется (B, C)разделяющим, если в графе G X все вершины C недостижимы из B.

Утверждение 2.4. Для любого орграфа G = (V, E) и любых B, C V, B C = мощность наименьшего (B, C)-разделяющего множества дуг равна наибольшему количеству попарно непересекающихся по дугам путей, ведущих из B в C.

ДОКАЗАТЕЛЬСТВО. Построим сеть H по следующим правилам.

Добавим к G вершины s и t и дуги (s, b), b B и (c, t), c C. Положим пропускные способности дуг (s, b), b B и (c, t), c C равными |E| + 1, а пропускные способности остальных дуг равными 1. Поскольку число дуг, выходящих из B, не больше |E|, то минимальный разрез R = (X, X) в H не содержит дуг вида (s, b), b B и (c, t), c C. Отметим, что тогда пропускная способность R равна числу дуг, ведущих из X в X, а множество A этих дуг является (B, C)разделяющим. По теореме о максимальном потоке и минимальном разрезе в H существует поток f мощности |A| из s в t.

Так как пропускные способности всех дуг H целочисленны, то, следуя АФФ, можно выбрать f целочисленным. Тогда по теореме 2.1 поток f можно представить в виде суммы целочисленных положительных потоков вдоль путей и циклов. Удалив потоки вдоль циклов, получим поток той же величины, являющийся суммой потоков вдоль путей. По определению пропускных способностей дуг из G поток вдоль каждого из этих путей равен 1 и, следовательно, их число равно |A|. По той же причине эти пути не имеют общих дуг, кроме инцидентных s или t. Тогда части этих путей, полученные после удаления вершин s и t, удовлетворяют требованиям нашего утверждения.

Утверждение 2.5. Для любого орграфа G = (V, E) и любых B, C V, B C = таких, что нет дуг, ведущих из B в C, мощность наименьшего (B, C)-разделяющего множества вершин равна наибольшему количеству попарно непересекающихся по вершинам путей, ведущих из B в C.

ДОКАЗАТЕЛЬСТВО. Построим по следующим правилам вспомогательный орграф G. Пусть V множество копий (дублей) элементов множества V, то есть V = {v |v V }. Положим V (G ) = = V V, E(G ) = {(v, v )|v V } {(v, u)| (v, u) E}. Обозначим B = {v |v B}. По утверждению 2.4 мощность наименьшего (B, C)разделяющего множества дуг равна наибольшему количеству попарно непересекающихся по дугам путей, ведущих из B в C. Заметим, что в G пути длины два и более, не пересекающиеся по дугам, не пересекаются и по вершинам, а каждому пути в G из B в C взаимно однозначно соответствует путь в G из B в C.

X ребер (вершин, не принадлежащих B C) в G называется (B, C)разделяющим, если в графе G X все вершины C недостижимы из B.

V, (v, u) E. Тогда мощность наименьшего ({v}, {u})-разделяющего множества вершин в G равна наибольшему количеству попарно непересекающихся по внутренним вершинам путей, ведущих из v в u.

ДОКАЗАТЕЛЬСТВО. Построим вспомогательный орграф G по следующим правилам:

Применение утверждения 2.5 с B = {v}, C = {u} к орграфу G завершает доказательство.

Аналогично доказывается реберный вариант теоремы Менгера.

Утверждение 2.7. Пусть G = (V, E) граф, v, u V. Тогда мощность наименьшего ({v}, {u})-разделяющего множества ребер в G равна наибольшему количеству попарно непересекающихся по ребрам путей, ведущих из v в u.

Реберной (вершинной) связностью (G)((G)) графа G называется наименьшее число ребер (вершин), после удаления которых граф становится несвязным или одновершинным.

Говорят, что граф G k-связен, если (G) k.

Из теремы Менгера следует теорема Уитни.

Теорема 2.8 (Уитни.) Граф G является k-связным тогда и только тогда, когда любые две его вершины соединяют не менее k не пересекающихся по внутренним вершинам путей.

Отметим также, что алгоритмы нахождения максимального потока позволяют за полиномиальное время находить минимальные вершинные и реберные разделяющие множества. Более того, оценки трудоемкости алгоритмов в случае используемых здесь сетей могут быть еще улучшены.

2.5 Задача о наибольшем паросочетании в двудольном графе как задача о максимальном потоке.

Теоремы Кёнига и Дилворта Пусть G = (V, E) двудольный граф с долями B и C. Построим сеть H по следующим правилам. Ориентируем каждое ребро графа G из B в C. Добавим к G вершины s и t и дуги (s, b), b B, и (c, t), c C.

Положим пропускные способности всех дуг равными 1. Тогда любой целочисленный поток в сети H взаимно однозначно соответствует некоторому паросочетанию в G. Действительно, как и в утверждении 2.4, в H можно выбрать максимальный поток f так, что Поскольку в каждую вершину из B заходит только одна дуга, а из каждой вершины из C выходит только одна дуга, то пути из s в t, на дугах которых поток равен 1, не имеют общих вершин, кроме s и t. Значит, дуги e с f (e) = 1, не инцидентные ни s, ни t, образуют паросочетание.

Следовательно, M (f ) (G). Обратно, каждому паросочетанию мощности k в G легко сопоставить поток величины k в H, протекающий по этим ребрам.

Алгоритмы нахождения максимального потока дают возможность за полиномиальное время находить наибольшее паросочетание в двудольном графе. Кроме того, теорема о максимальном потоке и минимальном разрезе позволяет дать новое доказательство теоремы Кёнига.

Теорема Кёнига. Для любого двудольного мультиграфа G мощность (G) наибольшего паросочетания равна мощности (G) наименьшего множества вершин, покрывающего все ребра.

ДОКАЗАТЕЛЬСТВО. На паросочетания и покрытия наличие кратных ребер не влияет. Поэтому можно считать, что G двудольный граф с долями B и C. Построим сеть H и поток f, как в начале раздела. Имеем M (f ) (G).

Пусть R = (X, X) минимальный разрез в сети H, Y = X B, Z = X C. Можно считать, что среди всех минимальных разрезов в сети H на разрезе R минимизируется |X|. Допустим, что в H есть дуга (b, c), где b B\Y = X B, c C\Z = X C. Тогда, положив X = X\{b}, получим разрез R, не больший, чем у R пропускной способности с |X | = |X| 1. Это противоречит выбору R.

Следовательно, Y Z покрывает все ребра G, и (G) |Y Z|. С другой стороны, по определению откуда |Y Z| |E (R)|. Но |E (R)| = M (f ).

Выведем из теоремы Кёнига теорему Дилворта. Сначала напомним некоторые понятия.

Частично упорядоченным множеством (ЧУМ) называется пара (P, l, ai,j > 0 выбираем лексикографически минимальную строку k и делаем ak,j ведущим элементом. После этого число элементов базиса увеличивается. Повторяем эту процедуру, пока не построим базис.

3 МАТРОИДЫ Матроидом будем называть произвольную пару M := [E, I], где E конечное множество, а I непустое подсемейство подмножеств множества E, удовлетворяющее условиям:

(M1) из (A I, B A) следует, что B I;

(M2) A, B I таких, что |A| < |B|, e B\A : A {e} I.

Множества семейства I назовем независимыми множествами, а все другие подмножества E зависимыми множествами матроида M.

Из (M 1) и непустоты I следует, что I в любом матроиде [E, I].

База матроида это любое максимальное по включению независимое множество. Из аксиомы (M2) следует, что все базы матроида имеют одну и ту же мощность.

Цикл матроида это любое минимальное по включению зависимое множество.

Примеры 1. Матричный матроид. Элементами множества E являются столбцы некоторой матрицы A, и подмножество столбцов считается независимым, если оно линейно независимо (в обычном смысле).

2. Графический матроид. Элементами множества E являются ребра некоторого графа G, и подмножество множества ребер G считается независимым, если оно не содержит цикла графа G.

3. Матроид разбиений. Элементами множества E являются дуги некоторого орграфа G, и подмножество множества дуг G считается независимым, если никакие две дуги из этого подмножества не заходят в одну и ту же вершину.

проективной плоскости порядка 2 (так называемой плоскости Фано). В плоскости Фано прямыми являются множества {e1, e2, e3 }, Подмножество A множества E считается независимым, если |A| 2 или |A| = 3 и A не является прямой в плоскости Фано.

5. k-матроид. Здесь E произвольное конечное множество, и подмножество A множества E считается независимым, если и только Упражнение. Доказать, что каждый из перечисленных примеров является матроидом. Описать базы и циклы этих матроидов.

6. Матроид трансверсалей. Пусть G = (V, W ; R) двудольный граф с долями V и W. Подмножество A множества V назовем (частичной) трансверсалью, если в G существует паросочетание, покрывающее все вершины множества A. По теореме Кенига – Оре множество A является трансверсалью, если и только если где N (C) = {w W : (v, w) R}.

Теорема 3.1 (Эдмондс и Фалкерсон.) Пусть G = (V, W ; R) двудольный граф с долями V и W. Тогда пара M = [V, I], где I = {A V | A трансверсаль в G}, является матроидом.

ДОКАЗАТЕЛЬСТВО. Выполнение (M1) очевидно. Пусть A, B I и |A| < |B|. Выберем содержащее |A| ребер паросочетание A, покрывающее A, и содержащее |B| ребер паросочетание B, покрывающее B так, чтобы они имели максимально возможное число общих ребер.

Для каждого x A B обозначим через A (x) (соответственно через B (x)) вершину, соединенную с x ребром, принадлежащим A (x) (соответственно B (x)). Для C A B определим A (C) = {A (x) | x C} и B (C) = {B (x) | x C}). Если B (b ) A (A) хотя бы для одного b B\A, то A {b } I. Теорема доказана.

Пусть B ({B\A}) A (A). Поскольку |B| > |A|, найдется b B с B (b) A (A). Согласно доказанному выше b A B. Пусть c = A (b).

Тогда паросочетание A = (A \{(b, c)}) {(b, B (b))} имеет больше общих ребер с B, чем A, что противоречит выбору A.

Замечание. Изложенное здесь доказательство принадлежит В. Ню.

Теорема 3.2. Пусть E конечное множество, а I непустое подсемейство подмножеств множества E, удовлетворяющее условию (M1). При этих предположениях M = [E, I] является матроидом, если и только если выполняется условие:

(M3) для каждого C E любые два максимальных (по включению) независимых подмножества множества C имеют одну и ту же мощность.

ДОКАЗАТЕЛЬСТВО. Допустим сначала, что не выполняется (M3).

Это значит, что для некоторого C E найдутся максимальные (по включению) независимые A, B E с |A| < |B|. Согласно (M2) e B\A : A {e} I. Это противоречит максимальности A.

Допустим теперь, что не выполняется (M2). Тогда найдутся такие A, B I с |A| < |B|, что A {e} I для любого e B\A. Значит, для C := A B не выполняется (M3): A максимальное по включению независимое подмножество множества C, но |A| < |B|.

Следствие. В любом матроиде все базы имеют одну и ту же мощность.

Ввиду теоремы 3.2 на подмножествах множества E матроида M определена ранговая функция, сопоставляющая каждому C E мощность максимальных (по включению) независимых подмножеств C.

Теорема 3.3. Пусть M = [E, I] является матроидом, а ранговая функция на 2E. Тогда (R1) 0 (A) |A|;

(R2) A B (A) (B);

(R3) (A B) + (A B) (A) + (B);

(R4) () = 0;

(R5) (A) (A {e}) (A) + 1;

(R6) если (A {e}) = (A {f }) = (A), то (A {e, f }) = (A).

ДОКАЗАТЕЛЬСТВО. Выполнение (R1), (R2), (R4) и (R5) очевидно.

Допустим, что (A {e}) = (A {f }) = (A), но (A {e, f }) = = (A). Пусть I A, I I, |I| = (A). По теореме 3.2 существует F A {e, f }, F I такое, что |F | > |I|, F I. Но это противоречит допущению (A {e}) = (A {f }) = (A). Значит, (R6) верно.

Докажем (R3). Пусть I A B, I I, |I| = (A B). По теореме 3.2 существуют F A\B и H B\A такие, что F I I, F I H Теорема 3.4. Функция : 2E Z является ранговой функцией некоторого матроида на E тогда и только тогда, когда она удовлетворяет (R4), (R5) и (R6).

ДОКАЗАТЕЛЬСТВО. Ввиду теоремы 3.3 достаточно доказать импликацию "только тогда". Положим I = {A E : (A) = |A|}. Из-за (R4) имеем I =. Допустим, что A B, (A) < |A|, B\A = {x1,..., xk }.

Согласно (R5) (B) 1 + (B\{x1 }) 2 + (B\{x1, x2 })... k+ +(B\{x1,..., xk }) = k+(A) < |B|. Полученное неравенство (B) < < |B| доказывает (M1).

Допустим теперь, что (M2) неверно. Тогда для некоторых A, B I, (A {bi }) = (A) при любом 1 i p. Из (R6) получаем (A {b1, bi }) = (A {b1 }) = (A) при любом 2 i p. Снова, по (R6), (A {b1, b2, bi }) = (A) при любом 3 i p и т. д. Через p шагов получаем (A B) = (A {b1, b2,..., bp }) = (A). Противоречие.

Теорема 3.5. Функция : 2E Z является ранговой функцией некоторого матроида на E тогда и только тогда, когда она удовлетворяет (R1), (R2) и (R3).

ДОКАЗАТЕЛЬСТВО. Ввиду теорем 3.3 и 3.4 достаточно доказать, что выполнение (R1), (R2) и (R3) влечет выполнение (R4), (R5) и (R6).

Очевидно, (R4) следует из (R1), а левое неравенство в (R5) следует из (R2). Правое неравенство в (R5) и свойство (R6) следуют из (R3).

Замечание. Ввиду (M2) для множества B баз произвольного матроида M = [E, I] верно (B1) Для любых B1 = B2 и любого x B1 \B2 найдется такой y B2 \B1, что Теорема 3.6. Пусть E конечное множество, B непустое подсемейство подмножеств множества E, удовлетворяющее условию (B1).

Тогда множество I = {A E | B B : A B} удовлетворяет аксиомам (M1) и (M2).

ДОКАЗАТЕЛЬСТВО. Выполнение (M1) очевидно.

Покажем, что все члены B равномощны. Допустим, что это не так.

Выберем множества B1, B2 B разной мощности так, чтобы максимизировать мощность пересечения. Можно считать, что |B1 | > |B2 |.

Выберем произвольно x B1 \B2. Согласно (B1), найдется такой y B2 \B1, что B := (B1 \{x}) {y} B. Но |B B2 | > |B2 B1 |, |B| = |B1 |. Это противоречит выбору B1 и B2.

Итак, предположим, что (M2) неверно. Это значит, что для некоторых A1, A2 I с |A1 | < |A2 |, Выберем B1, B2 B, B1 A1, B2 A2 так, чтобы максимизировать |B2 B1 |. В силу (1) Если B1 \A1 B2, то в силу (23) имеем |B2 | |B1 \A1 |+|A2 | > |B1 \A1 |+ +|A1 | = |B1 |. Значит, найдется x B1 \(A1 B2 ). Согласно (B1) найдется такой y B2 \B1, что B := (B1 \{x}) {y} B. Но |B B2 | > |B2 B1 |, B A1. Это противоречит выбору B1 и B2.

Из теоремы 3.6 следует, что для задания матроида достаточно задать набор баз, удовлетворяющий аксиоме (B1).

Теорема 3.7. Пусть M = [E, I] матроид. Тогда для любых членов C и D семейства C циклов в M выполняются условия:

(C1) если C D, то C = D;

(C2) если C = D и e C D, то найдется цикл F (C D)\{e}.

И наоборот, если для любых множеств C и D из некоторого семейства C подмножеств E выполнены условия (C1) и (C2), то C является семейством циклов некоторого матроида на E.

ДОКАЗАТЕЛЬСТВО. Выполнение (C1) очевидно. Докажем выполнение (С2). Пусть C = D и e C D. Обозначим A = C D. По условию A I. Допустим, что (C D)\{e} независимо. Тогда по теореме 3.2 найдется независимое множество B C D с |B| = |C D| такое, что B A. Но в этом случае B C или B D.

Пусть для любых множеств C и D из некоторого семейства C подмножеств E выполнены условия (C1) и (C2). Обозначим I = = {A E : C\A = C C}. Выполнение (M1) очевидно. Предположим, что условие (M2) не выполняется. Выберем пару (A, B) множеств из I, противоречащих (M2), с максимальной мощностью пересечения, а среди них пару с минимальной мощностью A. Пусть A {bi } I при любом 1 i p. Это означает, что По выбору (A, B), для пары (A\{a1 }, B) найдется b1 с F = (A\{a1 }) {b1 } I. Снова по выбору (A, B) существует b2 с D = F {b2 } I.

Но по (C2) найдется C C, C (C1 C2 )\{a1 } = D\{a1 }.

Укажем на связь матроидов со структурами, на которых хорошо работают "жадные" алгоритмы.

Пусть E конечное множество, I подсемейство подмножеств множества E и w : E R+ функция, сопоставляющая каждому e E его "вес" w(e). Требуется найти и множество S, на котором максимум достигается.

Begin Упорядочить E так, чтобы w(e1 ) w(e2 )... w(en );

end Теорема Радо – Эдмондса. Если M = [E, I] матроид, то множество S, найденное "жадным" алгоритмом, является решением задачи (24). Напротив, если M = [E, I] не матроид, то найдется функция w : E R+, для которой это S не будет оптимальным.

ДОКАЗАТЕЛЬСТВО. Пусть M = [E, I] матроид, S = {s1,..., sk } множество, найденное "жадным" алгоритмом; причем w(s1 ) M, поскольку отбрасывались лишь элементы, зависимые от S. Пусть T = {t1,..., tk } другая база M и w(t1 ) w(t2 )... w(tk ). Предположим, что w(ti ) > w(si ) для некоторого i. Рассмотрим независимые множества A := {s1,..., si1 } и B := {t1,..., ti }. Согласно (M2) найдется такое j, 1 j i, что A {tj } I. Но w(tj ) w(ti ) > w(si ).

Значит, w(ti ) w(si ) для каждого i, и S решение (24).

Предположим теперь, что M = [E, I] не является матроидом.

Случай 1. Аксиома (M1) не выполняется для I. Тогда найдутся B I и A I такие, что A B. Положим Понятно, что искомым множеством в задаче (24) является B и w(e) = = |B| + |A|. Но при работе "жадного" алгоритма кандидатами в S вначале будут рассматриваться элементы множества A и хотя бы один из них не будет включен в S.

Случай 2. Аксиома (M1) выполняется для I, но (М2) не выполняется. Тогда найдутся B I и A I такие, что |A| < |B| и A {e} I для любого e B \ A. Обозначим m = |B|. Положим Тогда "жадный" алгоритм сначала включит в S все элементы множества A, а затем к S не добавится ни один элемент множества B \ A.

Следовательно, суммарный вес элементов множества S будет равен Но оптимальное решение задачи (24) не меньше, чем |B| = m.

4 КОДИРОВАНИЕ

4.1 Задачи и понятия теории кодирования За основу этой главы взята часть III книги С. В. Яблонского "Введение в дискретную математику".

Кодирование в широком смысле один из самых распространенных видов человеческой деятельности: мы кодируем наши мысли, намерения и чувства словами (разных языков), кодируем нашу речь буквами, иероглифами и рисунками, тексты кодируются для записи в ЭВМ, и т. д. Много вопросов о кодировании возникает при передаче сообщений.

Они могут быть проиллюстрированы приводимой здесь схемой.

В этой схеме источник сообщений хочет передать по каналу связи некоторый набор слов т. е. конечных последовательностей символов из заданного конечного алфавита A = {a1,..., ar }. Для передачи ему нужно (или он хочет) закодировать это сообщение переписать его словами во вспомогательном алфавите B = {b1,..., bq }. После получения сообщения (возможно, искаженного помехами) его нужно снова записать словами в алфавите A (возможно, исправив возникшие ошибки).

Выбор кодов связан с различными обстоятельствами, а именно:

• с удобством передачи кодов, • со стремлением увеличить пропускную способность канала, • с удобством обработки кодов, • с обеспечением помехоустойчивости, • с удобством декодирования, • с необходимостью однозначного декодирования, • с другими возможными требованиями к кодам.

Ниже рассматриваются два вида кодирования:

(а) Алфавитное кодирование. Каждой букве ai из A = {a1,..., ar } ставится в соответствие некоторое слово Bi из алфавита B = {b1,..., bq }.

Схема кодирования, сопоставляющая эти слова, будет обозначаться буквой.

(б) Равномерное кодирование. Некоторое слово Bi из алфавита B ставится в соответствие не букве, а какому-то слову Ai фиксированной длины в алфавите A.

Конечно, одно из первых требований к используемому коду требование однозначности восстановления сообщения по его коду.

4.2 Проверка однозначности декодирования Рассмотрим алфавитные коды. Каждое из слов Bi, i = 1,..., r называется элементарным кодом. Слово в алфавите B назовем кодовым, если его можно расшифровать, т. е. разбить на элементарные коды.

Одна из трудностей проверки однозначности декодирования состоит в том, что формально надо проверять бесконечное число кодовых слов.

Оказывается, этой бесконечности можно избежать. Введем несколько обозначений.

Пусть дана схема кодирования, li длина слова Bi, L = l1 +...+lr.

Назовем нетривиальным разложением слова Bi его представление в виде Bi = Bj1... Bjw, где Bj1 = Bi, является началом какогонибудь элементарного кода, а является концом какого-нибудь элементарного кода (хотя сами не являются элементарными кодами). Слова и могут быть пустыми.

Очевидно, что для каждого i число нетривиальных разложений слова Bi конечно. Обозначим через W максимум чисел w, взятый по всем нетривиальным разложениям всех слов Bi, i = 1,..., r.

Теорема 4.1 (Маркова) Для любой схемы кодирования найдется такое N = N (), что для проверки однозначности декодирования в достаточно проверить коды слов из A длины не более N и ДОКАЗАТЕЛЬСТВО. Допустим, что код неразделим. Выберем самое короткое слово B в алфавите B, допускающее две различные расшифровки A1 и A2. С ними связаны два разбиения слова B на элементарные коды T1 и T2, что представлено на рисунке:

Обозначим через T произведение разбиений T1 и T2, т. е. разбиение, полученное после "разрезания" B там, где его "разрезало" хотя бы одно из разбиений T1 и T2. Части разбиения T разделим на два класса: к первому отнесем части, являющиеся элементарными кодами, ко второму все остальные. Заметим, что каждая часть, принадлежащая второму классу, является концом одного из элементарных кодов и началом другого. Причем, если оканчивает некоторое элементарное кодовое слово в T1, то оно начинает какое-то элементарное кодовое слово в T2, и наоборот (см. рис.). Точнее, если B = B B, то либо B и B являются кодовыми словами в T1, а B и B являются кодовыми словами в T2, либо наоборот.

Покажем, что все части из второго класса различны. Допустим, что B = B B B. Тогда слово B B имеет две расшифровки в противоречие с выбором B. Чтобы убедиться в этом, заметим, что согласно вышесказанному, слова B, B, B и B являются кодовыми.

Число частей из второго класса не превосходит числа непустых начал элементарных кодов, т. е. (l1 1) +... + (lr 1) = L r. Каждый из кусков, на которые разбивается B после выбрасывания всех частей из второго класса, является кодовым словом, входящим в одно из разбиений Ti, и частью некоторого элементарного кода, входящего в T3i.

Причем соседние куски являются частями элементарных кодов, входящих в различные Ti.

Таким образом, имеем не более Lr +1 кусков, и в каждом из Ti как минимум (L r + 1)/2 кусков вместе с соседними частями из второго класса образуют элементарный код в расшифровке Ai. Следовательно, длина каждого из Ai не превосходит Итак, проблема верификации однозначности декодирования заданной схемы является конечной. Но если, например, r = 6, W = 3, L = 20, то (W + 1)(L r + 2)/2 = 4 · 16/2 = 32 и требуется проверить слов. Это очень много. К счастью, из доказательства теоремы можно извлечь существенно более эффективный алгоритм.

Пусть дана схема кодирования. Для каждого элементарного кода Bi рассмотрим все его нетривиальные разложения Обозначим через V = V () множество, содержащее пустое слово и слова, встречающиеся в разложениях вида (25) как в виде начал, так и в виде окончаний. Построим далее помеченный ориентированный граф = () по следующим правилам. Множеством вершин графа является V = V (). Проводим дугу из вершины V в вершину V, если и только если в некотором разложении вида (25) является началом, а концом. При этом дуга (, ) помечается словом Bj1... Bjw.

Теорема 4.2 Схема кодирования не обладает свойством однозначности декодирования тогда и только тогда, когда граф () содержит контур, проходящий через вершину.

ДОКАЗАТЕЛЬСТВО. Допустим, что не обладает свойством однозначности декодирования. Тогда, как следует из доказательства теоремы 4.1, кратчайшее слово, имеющее две расшифровки в схеме, имеет вид B = Bi1,1... Bi1,k(1) 1 Bi2,1... Bi2,k(2) 2... s1 Bis,1... Bis,k(s), где все i различны и слова Bi1,1... Bi1,k(1) 1, 1 Bi2,1... Bi2,k(2) 2,..., s1 Bis,1... Bis,k(s) являются элементарными кодами. Это значит, что в () есть контур, проходящий через вершины, 1,..., s1.

Обратно, пусть в () существует контур, проходящий через вершины 0, 1,..., s1, где 0 = и дуга (j, j+1 ), j = 0, 1,..., s ((s 1) + 1 = 0), помечена словом Bij+1,1... Bij+1,k(j+1). Тогда слово B = Bi1,1... Bi1,k(1) 1 Bi2,1... Bi2,k(2) 2... s1 Bis,1... Bis,k(s) имеет две различные расшифровки.

4.3 Префиксные коды Важным классом однозначно декодируемых кодов являются префиксные коды такие алфавитные коды, где ни один элементарный код не является префиксом (т. е. началом) другого элементарного кода.

Упражнение. Доказать, что любой префиксный код является однозначно декодируемым.

Нам потребуется следующий факт.

Теорема 4.3 (Неравенство Макмиллана.) Если схема кодирования обладает свойством однозначности декодирования, то ДОКАЗАТЕЛЬСТВО. Выберем произвольное n. Рассмотрим коды всех rn слов длины n в алфавите A, полученные с помощью. Поскольку обладает свойством однозначности декодирования, все rn кодовых слов различны. Обозначим через l(B) длину слова B и рассмотрим величину q l(B), где суммирование ведется по всем кодам B слов длины n в алфавите A, полученных с помощью. Пусть l = max{li | 1 i r} и (n, t) каждого из наших кодовых слов не превосходит nl. Следовательно, С другой стороны, поскольку каждое кодовое слово состоит из n элементарных кодов, где суммирование ведется по всем rn наборам длины n чисел из диапазона {1,..., r}. Но последняя сумма равна (q l1 +...+q lr )n. Сравнивая с (27), получаем Это неравенство справедливо для любого n, а его правая часть стремится к 1 при n. Поскольку его левая часть не зависит от n, необходимо, чтобы Следующий факт характеризует префиксные коды с положительной стороны.

Теорема 4.4 Если схема кодирования обладает свойством однозначности декодирования, то существует такая префиксная схема кодирования, что для каждого i, i = 1,..., s длина li элементарного кода Bi в равна длине li элементарного кода Bi в.

ДОКАЗАТЕЛЬСТВО. Можно считать, что элементарные коды Bi занумерованы в порядке неубывания их длин. Пусть длинами элементарных кодов в являются числа 1,..., s, 1 < 2... < s и число элементарных кодов длины i, i = 1,..., s равно i. Тогда неравенство Макмиллана можно переписать в виде В частности, 1 /q 1 1, откуда 1 q 1. Выберем среди q 1 слов длины 1 в алфавите B произвольные 1 слов в качестве элементарных кодов B1,..., B1.

Перейдем к словам длины 2. Из (28) получаем Рассмотрим множество слов длины 2 в алфавите B, не начинающихся c B1,..., B1. В силу (29) из этого множества можно выбрать 2 какихнибудь слов в качестве элементарных кодов B1 +1,..., B1 +2.

Далее из (28) получаем и строим 3 слов длины 3, не начинающихся c B1,..., B1 +2, и т. д.

Через конечное число шагов построим нужное количество слов нужной длины. По построению новый код будет префиксным.

4.4 Коды с минимальной избыточностью При выборе схемы кодирования естественно учитывать экономичность, т. е. средние затраты времени на передачу и прием сообщений.

Предположим, что задан алфавит A = {a1,..., ar }, r 2, и набор вероятностей (p1,..., pr ), p1 +... + pr = 1 появлений букв a1,..., ar.

Тогда cтоимостью кодирования схемы называется величина т. е. математическое ожидание длины элементарного кода.

Понятно, что чем меньше lср, тем экономнее в среднем схема.

Пусть l = l (a1,..., ar, p1,..., pr ) = inf lср, где инфимум взят по всем однозначно декодируемым схемам.

Пусть k = logq r. Тогда все ai можно закодировать разными словами длины k в алфавите B. Очевидно, такое кодирование будет префиксным (а следовательно, и взаимно однозначным). Отсюда l k. Таким образом, при поиске схем с lср < k достаточно рассматривать для i с pi > 0 элементарные коды Bi только длины, меньшей k/pi. Поскольку длины элементарных кодов Bi для i с pi = 0 не влияют на lср, достаточно рассмотреть конечное число вариантов. Это значит, что значение l достигается на некоторой схеме.

Коды, определяемые схемами с lср = l, называются кодами с минимальной избыточностью. Согласно теореме 4.4 существуют префиксные коды с минимальной избыточностью. Изучим структуру префиксных кодов с минимальной избыточностью.

Каждому префиксному коду (со схемой ) поставим в соответствие кодовое дерево ориентированное корневое дерево T = T () по следующим правилам. Множество вершин V (T ) дерева T состоит из элементарных кодов и всех их префиксов, включая пустое слово. Дуга в T ведет из C в D, если C является префиксом D и короче D ровно на одну букву (см. рис. на стр.51).

Элементарные коды соответствуют висячим вершинам в T.

Итак, пусть T кодовое дерево префиксного кода с минимальной избыточностью (со схемой ). Можно считать, что p1... pr. Тогда можно преобразовать таким образом, чтобы б) порядки ветвления всех его вершин, за исключением быть может одной, лежащей в предпоследнем ярусе, равны или 0, или q;

в) порядок ветвления q0 исключительной вершины (если она есть) не равен 1.

Доказательство этих свойств оставляется в качестве упражнения.

Если порядки ветвления всех вершин T равны или 0, или q, то положим q0 = q. Ввиду б), по индукции, легко видеть, что для некоторого целого t имеем r = t(q 1) + q0. Следовательно, если h остаток от деления r на q 1, то Нетрудно видеть, что можно выбрать такой префиксный код с минимальной избыточностью, кодовое дерево которого кроме а)–в) обладает свойством г) для некоторой вершины v, лежащей в предпоследнем ярусе, порядок ветвления вершины v равен q0, а потомками v являются ar, ar1,..., arq0 +1.

Теорема 4.5 Пусть схема кодирования задает код с минимальной избыточностью для алфавита A = {a1,..., ar } и набора вероятностей (p1,..., pr ), а ее кодовое дерево T удовлетворяет свойствам (а)-(г). Обозначим prq0 +1 = pr + pr1 +... + prq0 +1, а через T кодовое дерево, полученное из T удалением вершин ar, ar1,..., arq0 +1 и сопоставлением образовавшейся висячей вершине v буквы arq0 +1. Тогда T является кодовым деревом кода с минимальной избыточностью для алфавита A = {a1, a2,..., arq0, arq0 +1 } и набора вероятностей (p1, p2,..., prq0, prq0 +1 ).

ДОКАЗАТЕЛЬСТВО. Обозначим схему, которой соответствует T, через, номер уровня вершины v через m. Тогда lср ( ) = lср () (m + 1)(pr + pr1 +... + prq0 +1 ) + mprq0 +1 = lср () prq0 +1.

Если бы для алфавита A = {a1,..., arq0, arq0 +1 } и набора вероятностей (p1,..., prq0, prq0 +1 ) нашлась схема префиксного кодирования с меньшей избыточностью, чем lср () prq0 +1, то, подвесив в кодовом дереве для к вершине v вершины ar, ar1,..., arq0 +1, мы получили бы схему префиксного кодирования для алфавита A = = {a1,..., ar } с lср () = lср () + prq0 +1 < lср (). Противоречие с выбором завершает доказательство теоремы.

Данная теорема в сочетании с предыдущими рассуждениями дает следующий алгоритм построения кодов с минимальной избыточностью.

Прямой ход 1. Если r = 1, то переходим к обратному ходу.

2. Упорядочим вероятности так, чтобы p1... pr.

3. Выберем q0 по правилу (30), удалим из списка вероятностей pr, Положим r = r q0 + 1, уберем штрих с pr и перейдем к шагу 1.

Обратный ход Кодовым деревом для одной буквы является одна вершина. В порядке, обратном к тому, в котором склеивались вероятности, расклеиваем вершины кодового дерева.

4.5 Самокорректирующиеся коды Рассмотрим одну из простейших ситуаций, когда сообщение может искажаться в канале связи. Пусть A = {0, 1} алфавит, содержащий два символа. Предположим, что в канале связи действует источник помех, который в слове длины l искажает не более p символов. Возникает вопрос: для какого m можно все m-буквенные слова в алфавите A закодировать l-буквенными словами так, чтобы по коду на выходе закодированные слова однозначно восстанавливались? И как это сделать?

Если l > 2p, то m l/(2p + 1). Действительно, каждую букву можно писать 2p + 1 раз подряд. Но такое кодирование не является самым экономным. Ниже будет построен код Хэмминга для p = 1.

1. Кодирование При передаче слова 1 2... l и не более чем одном искажении на выходе может оказаться одно из l + 1 различных слов. Поскольку для разных кодовых слов эти группы по l + 1 слов не должны пересекаться, необходимо, чтобы Выберем наибольшее m, удовлетворяющее (31). Обозначим k = lm.

Слову 1 2... m ставится в соответствие слово 1 2... l по следующим правилам.

Буквы i слова 1 2... l, у которых индекс i принадлежит {1, 2, 22,..., 2k1 }, будут контрольными символами. Остальные m символов будут информационными: просто поставим символы 1, 2,..., m на эти места. Затем переходим к определению контрольных символов.

Пусть Vi множество таких натуральных чисел от 1 до l, в двоичной записи которых на i-м месте стоит 1. Для i = 1,..., k положим Тогда для i = 1,..., k имеем 2. Обнаружение и исправление ошибок Допустим, что мы передали закодированное так слово 1 2... l и получили слово 1 2... l = 1 2... s... l. Пусть xk... x1 двоичная запись числа s. Рассмотрим, чему будут равны jVi j для i = 1,..., k в зависимости от s.

Случай 1. xi = 0. Тогда Случай 2. xi = 1. Тогда Это значит, что, выписав подряд справа налево значения jVi j для i = 1,..., k, мы получим последовательность xk... x1, т. е. двоичную запись числа s номера символа, который передан с ошибкой.

Заменяем неправильный символ на правильный. Если ошибок не было, то все суммы jVi j равны нулю.

3. Декодирование Удаляем проверочные символы и оставляем информационные.

Содержание

1 АЛГОРИТМЫ ИХ СЛОЖНОСТЬ

1.1 Понятие сложности алгоритмов................ 1.4 Идея динамического программирования на примере распределительной задачи и обратной к ней.......... 1.6 Метод ветвей и границ на примере задачи коммивояжера 2.4 Использование сетевых моделей для нахождения связности графов. Теорема Менгера и теорема Уитни....... 2.5 Задача о наибольшем паросочетании в двудольном графе как задача о максимальном потоке. Теоремы Кёнига и Редакционно-издательский отдел Новосибирского государственного университета; участок оперативной полиграфии НГУ; 630090, Новосибирск 90, ул. Пирогова, 2.