Книга: Линейные неравенства и комбинаторика

Скачать

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

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

Первым примером будут совершенные графы. Граф называется совершённым, если минимальное число цветов для правильной раскраски любого его подграфа совпадает с максимальным числом попарно соседних вершин. (Подробнее смотри ниже.) Есть много других способов охарактеризовать совершенные графы. Одно из таких утверждений имеет прямое отношение к линейному программированию: с каждым графом можно связать систему линейных неравенств. Оказывается, что множество решений этой системы в случае совершенного графа устроено просто, чем в общем случае. Используя такую характеристику совершённых графов, можно и доказать знаменитую теорему (в слабом варианте), которая утверждает, что дополнение совершенного графа тоже совершенный граф.

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

Изложение сопровождается задачами. Сначала идут рекомендации, которые читателю рекомендуется обязательно выполнить для проверки понимания прочитанного. Остальные — довольно трудные задачи, лежащие несколько в стороне от основного сюжета. Такие задачи отмечены звёздочками. В заключительном разделе приводятся решения некоторых задач.