графы

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

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

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

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

Основы теории графов, Зыков A.A., 2004

Основы теории графов, Зыков A.A., 2004.

   Систематическое введение в теорию графов, построенное в соответствии с внутренней логикой ее развития. Основные положения доказываются и иногда иллюстрируются примерами прикладного характера. Многие результаты, не являющиеся необходимыми для последовательного развертывания теории, приводятся в виде упражнений и дополнений.
Для студентов и аспирантов по специальностям «Математика» и «Прикладная математика», а также научных работников и инженеров.

Основы теории графов, Зыков A.A., 2004
Скачать и читать Основы теории графов, Зыков A.A., 2004
 

Графы, Гуровиц В.М., Ховрина В.В., 2014

Графы, Гуровиц В.М., Ховрина В.В., 2014.


Вторая брошюра серии ШКОЛЬНЫЕ МАТЕМАТИЧЕСКИЕ КРУЖКИ посвящена графам. В ней приведены четыре занятия по этой теме, в которых подобран материал для начального знакомства с графами, адресованный школьникам 6-8 классов и руководителям кружков. Несмотря на то, что в школьном курсе математики термин «граф» отсутствует, авторам представляется важным познакомить школьников с этими объектами, научить оперировать соответствующими терминами и использовать их при решении задач. В дальнейшем предполагается выпустить еще несколько брошюр, в которых эта тема будет развиваться для старших школьников. Надеемся, что книжка будет интересна также учителям математики, студентам педагогических вузов и всем, кто занимается со школьниками.

Графы, Гуровиц В.М., Ховрина В.В., 2014
Купить бумажную или электронную книгу и скачать и читать Графы, Гуровиц В.М., Ховрина В.В., 2014
 

Тема 8, Гамильтоновы графы

Тема 8, Гамильтоновы графы.

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

Тема 8, Гамильтоновы графы
Скачать и читать Тема 8, Гамильтоновы графы
 

Теория графов, Омельченко А.В., 2018

Теория графов, Омельченко А.В., 2018.

В основу данного учебника легли материалы семестрового курса лекций, читающегося автором в течение нескольких лет студентам первых курсов бакалавриата Санкт-Петербургского Академического университета. В учебник включены все основные разделы современной теории графов — деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы. В конце каждого параграфа приводятся задачи, дополняющие изложенный в учебнике теоретический материал. Все утверждения снабжены подробными доказательствами, изложение иллюстрируется большим количеством рисунков. Учебник рассчитан на студентов младших курсов, изучающих математику и информатику, а также на специалистов из смежных областей, желающих самостоятельно изучить основные разделы теории графов. Большая часть материала не предполагает специальных предварительных знаний и может быть использована школьниками, изучающими программирование и дискретную математику. Наконец, этот учебник может быть полезен преподавателям, ведущим соответствующие курсы.

Теория графов, Омельченко А.В., 2018

Скачать и читать Теория графов, Омельченко А.В., 2018