ЛИТЕРАТУРА ПО ФУНДАМЕНТАЛЬНЫМ И ПРИКЛАДНЫМ НАУКАМ
для школьников, студентов и научных работников

Каталог

Книги

Вокруг теоремы Холла Эвнин А.Ю. Книжный дом
/Эвнин А.Ю./

Вокруг теоремы Холла

Издательство:Книжный дом "ЛИБРОКОМ"
Год издания:2012
ISBN:978-5-397-02390-0
Кол-во страниц:88
Переплёт:Мягкий
 176 руб.  В корзину

В настоящем пособии рассматривается теорема Ф.Холла о системе различных представителей, решающая задачу о свадьбах, и эквивалентные ей теоремы Менгера, Дилворта, Кёнига---Эгервари, Форда---Фалкерсона. Показано, что эти теоремы являются проявлением принципа двойственности в линейном программировании. Приведен также венгерский алгоритм решения задачи о назначениях.

Книга ориентирована на студентов специальностей "Математика", "Прикладная математика", "Прикладная математика и информатика", "Программная инженерия", изучающих дискретную математику и дискретную оптимизацию.

Оглавление

Предисловие

Минимаксные теоремы

1.1. Теоремы Менгера

1.1.1. Вершинная форма

1.1.2. Рёберная форма

1.1.3. Теоремы Менгера для орграфов

1.2. Теорема Холла

1.3. Венгерская теорема

1.4. Теорема Дилворта

2. Обобщения

2. 1. Трансверсали

2.2. Понятие матроида

2.3. Трансверсальный матроид

2.4. Теорема Радо

2.5. Общие трансверсали

3. Линейное программирование и принцип двойственности

3.1. Общие сведения

3.2. Абсолютно унимодулярные матрицы

3.3. Наибольшие паросочетания

3.4. Максимальный поток

4. Приложения к различным задачам

4.1. Совершенные паросочетания в регулярных двудольных графах

4.2. Латинские прямоугольники

4.3. Критерий Райзера

4.4. Дважды стохастические матрицы

4.5. Рёберная раскраска графов

4.6. Вершинная и рёберная Связность

4.7. Теорема Эрдёша

5. Алгоритмы для задач о двудольных графах

5.1. Теорема Бёржа

5.2. Нахождение наибольшего паросочетания

5.3. Нахождение наименьшего вершинного покрытия

5.4. Венгерский алгоритм

5.5. Задача о назначениях на узкое место

6. Упражнения

Ответы Указания. Решения

Литература

Предисловие

Данное учебное пособие является расширенным вариантом гл.LXXI учебника [5] и посвящено ряду замечательных результатов теории графов, которые были получены в 30--50-х годах прошлого столетия различными математиками, и которые, как выяснилось впоследствие, эквивалентны друг другу: каждая из этих теорем может быть выведена из любой другой.

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

В пособии, помимо формулировок и различных доказательств теорем Холла, Менгера, Дилворта, Форда--Фалкерсона, Кёнига--Эгервари,

* рассматривается их обобщение (критерий существования независимой трансверсали теорема);

* устанавливается связь данных теорем с теорией двойственности в линейном программировании;

* приводятся примеры задач, эффективно решаемых с помощью этих теорем;

* обсуждаются некоторые алгоритмы, связанные с двудольными графами (при этом упор делается не на технических деталях, а на принципиальных моментах);

* имеются задачи для самостоятельного решения.

За рамками пособия остались критерий существования совершенного паросочетания в произвольном (не двудольном) графе (теорема Татта) и алгоритмы поиска наибольшего паросочетания в произвольном графе. Для изучения этих вопросов читатель может обратиться к книгам [11] и [15].

Первое издание вышло в 2004 г. в издательстве ЮУрГУ. Во втором издании более подробно разбирается задача о пополнении латинских

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

Комментарии: (авторизуйтесь, чтобы оставить свой)
В корзине нет товаров
Новости
2017-07-17
Уважаемые заказчики! В связи с сезоном летних отпусков сроки обработки отдельных заказов могут быть несколько увеличены. Приносим вам свои извинения
2017-07-03
Издательство «Физматкнига» с глубоким прискорбием сообщает, что 2 июля на 87-м году жизни скончался наш многолетний автор, профессор, доктор педагогических наук Михаил Иванович Шабунин.
2017-07-01
Магазин «Физтех-книга» в летний период (июль и август) будет работать с 9.00 до 19.00. Выходные — суббота и воскресенье.
2016-11-07
Уважаемые покупатели! У нас изменился номер телефона. Новый городской номер (499) 390-51-38.