Линейные неравенства и комбинаторика, Вялый М.Н.

Линейные неравенства и комбинаторика, Вялый М.Н.

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




Графы.
Граф состоит из множества вершин и соединяющих их рёбер. Каждое ребро соединяет ровно две вершины (при этом говорят, что ребро инцидентно этим вершинам). Вершины, связанные ребром, называются смежными. Степенью вершины (иногда говорят валентностью) графа называется количество инцидентных ей рёбер. Связным называется граф, в котором любые две вершины соединены путём, проходящим по рёбрам. Независимым подмножеством графа G называется такое подмножество вершин, между любыми вершинами которого нет ребра. Через а = a(G) будем обозначать максимальное количество вершин в независимом подмножестве графа G.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Линейные неравенства и комбинаторика, Вялый М.Н. - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу


Скачать - djvu - Яндекс.Диск.







Теги: Вялый :: книги по математике :: математика :: комбинаторика :: графы