|
Оглавление
Предисловие
Данное учебное пособие является расширенным вариантом гл.LXXI учебника [5] и посвящено ряду замечательных результатов теории графов, которые были получены в 30–50-х годах прошлого столетия различными математиками, и которые, как выяснилось впоследствие, эквивалентны друг другу: каждая из этих теорем может быть выведена из любой другой. В комбинаторном анализе и теории сложности вычислений (как и вообще в математике) важнейшей является идея сведения одной задачи к другой. Поэтому интересно показать, как внешне различные утверждения переходят друг в друга в результате построения некоторых дополнительных конструкций. Понимание таких переходов и преобразований важно и для программистов: зная, как одна задача сводится к другой, можно алгоритм решения первой задачи преобразовать в алгоритм решения второй задачи. В пособии, помимо формулировок и различных доказательств теорем Холла, Менгера, Дилворта, Форда–Фалкерсона, Кёнига–Эгервари, * рассматривается их обобщение (критерий существования независимой трансверсали теорема); * устанавливается связь данных теорем с теорией двойственности в линейном программировании; * приводятся примеры задач, эффективно решаемых с помощью этих теорем; * обсуждаются некоторые алгоритмы, связанные с двудольными графами (при этом упор делается не на технических деталях, а на принципиальных моментах); * имеются задачи для самостоятельного решения. За рамками пособия остались критерий существования совершенного паросочетания в произвольном (не двудольном) графе (теорема Татта) и алгоритмы поиска наибольшего паросочетания в произвольном графе. Для изучения этих вопросов читатель может обратиться к книгам [11] и [15]. Первое издание вышло в 2004 г. в издательстве ЮУрГУ. Во втором издании более подробно разбирается задача о пополнении латинских квадратов (приведено новое доказательство критерия Райзера), добавлены новые задачи (с решениями), обновлён библиографический список. А.Ю.Эвнин, 1 февраля 2011 г.
Об авторе
 Эвнин Александр Юрьевич Кандидат педагогических наук, доцент кафедры прикладной математики Южно-Уральского государственного университета. Автор более 80 научных публикаций, в том числе одного учебника, 16 учебных пособий, а также статей в журналах «Квант», «Математическое образование», «Математика в высшем образовании», «Математика в школе».
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||