Теория линейных неравенств называется линейным программированием. По существу она совпадает с геометрией многогранников в пространстве произвольной конечной размерности.
Здесь мы рассмотрим несколько примеров приложений линейного программирования к доказательству комбинаторных теорем.
Первым примером будут совершенные графы. Граф называется совершенным, если минимальное цветов для правильной раскраски любого его подграфа совпадает с максимальным числом попарно соседних вершин.
Второй сюжет, который обсуждается ниже — очень важная теорема линейного порграммирования, так называемая теорема двойственности. У этой теоремы есть много приложений к комбинаторике, здесь будут рассмотрены несколько характерных примеров.
Изложение сопровождается задачами. Часть из них — упражнения, которые читателю рекомендуется обязательно выполнить для проверки понимания прочитанного. Остальные — довольно трудные задачи, лежащие несколько в стороне от основного сюжета. Такие задачи отмечены звёздочками. В заключительном разделе приводятся решения некоторых задач.
План доказательства слабой гипотезы Бержа.
Будем доказывать равносильное утверждение: граф совершенный, если и только если в каждом его подграфе есть клика, пересекающая все максимальные по размеру независимые множества. Другими словами, это условие существования независимой трансверсали в дополнении графа.
В доказательстве, будет использован довольно странный трюк. Вершинам графа будем приписывать числа. Рассмотрим, например, произвольное подмножество S вершин графа. Каждая вершина графа либо принадлежит этому подмножеству и тогда ей приписано число 1, либо не принадлежит и тогда ей приписан 0. Такой набор чисел будем обозначать 1s. Но мы будем рассматривать и другие наборы чисел, приписанных вершинам. Отчасти полезно представлять себе это так, как будто некоторые вершины лишь частично входят в некое «виртуальное подмножество». Если вершине приписано число 1/3, то она на треть входит в «множество», описываемое данным набором чисел.
Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Линейные неравенства и комбинаторика, Вялый М.Н. - fileskachat.com, быстрое и бесплатное скачивание.
Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги
Скачать - pdf - Яндекс.Диск.
Дата публикации:
Теги: учебник по математике :: математика :: Вялый :: неравенство :: комбинаторика
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
Предыдущие статьи:
