Показать ещё...
Данное учебное пособие является расширенным вариантом гл.LXXI учебника [5] и посвящено ряду замечательных результатов теории графов, которые были получены в 30–50-х годах прошлого столетия различными математиками, и которые, как выяснилось впоследствие, эквивалентны друг другу: каждая из этих теорем может быть выведена из любой другой. В комбинаторном анализе и теории сложности вычислений (как и вообще в математике) важнейшей является идея сведения одной задачи к другой. Поэтому интересно показать, как внешне различные утверждения переходят друг в друга в результате построения некоторых дополнительных конструкций. Понимание таких переходов и преобразований важно и для программистов: зная, как одна задача сводится к другой, можно алгоритм решения первой задачи преобразовать в алгоритм решения второй задачи. В пособии, помимо формулировок и различных доказательств теорем Холла, Менгера, Дилворта, Форда–Фалкерсона, Кёнига–Эгервари, * рассматривается их обобщение (критерий существования независимой трансверсали теорема); * устанавливается связь данных теорем с теорией двойственности в линейном программировании; * приводятся примеры задач, эффективно решаемых с помощью этих теорем; * обсуждаются некоторые алгоритмы, связанные с двудольными графами (при этом упор делается не на технических деталях, а на принципиальных моментах); * имеются задачи для самостоятельного решения. За рамками пособия остались критерий существования совершенного паросочетания в произвольном (не двудольном) графе (теорема Татта) и алгоритмы поиска наибольшего паросочетания в произвольном графе. Для изучения этих вопросов читатель может обратиться к книгам [11] и [15]. Первое издание вышло в 2004 г. в издательстве ЮУрГУ. Во втором издании более подробно разбирается задача о пополнении латинских квадратов (приведено новое доказательство критерия Райзера), добавлены новые задачи (с решениями), обновлён библиографический список. А.Ю.Эвнин, 1 февраля 2011 г.
Эвнин Александр Юрьевич Кандидат педагогических наук, доцент кафедры прикладной математики Южно-Уральского государственного университета. Автор более 80 научных публикаций, в том числе одного учебника, 16 учебных пособий, а также статей в журналах «Квант», «Математическое образование», «Математика в высшем образовании», «Математика в школе».
|
2023. 720 с. Твердый переплет. 16.9 EUR
Книга «Зияющие высоты» – первый, главный, социологический роман, созданный интеллектуальной легендой нашего времени – Александром Александровичем Зиновьевым (1922-2006), единственным российским лауреатом Премии Алексиса де Токвиля, членом многочисленных международных академий, автором десятков логических... (Подробнее) URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR
Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее) 2023. 696 с. Твердый переплет в суперобложке. 119.9 EUR
Опираясь на новейшие исследования, историк Кристофер Кларк предлагает свежий взгляд на Первую мировую войну, сосредотачивая внимание не на полях сражений и кровопролитии, а на сложных событиях и отношениях, которые привели группу благонамеренных лидеров к жестокому конфликту. Кларк прослеживает... (Подробнее) URSS. 2024. 704 с. Твердый переплет. 26.9 EUR
В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее) URSS. 2024. 800 с. Мягкая обложка. 37.9 EUR
ВЕРСАЛЬ: ЖЕЛАННЫЙ МИР ИЛИ ПЛАН БУДУЩЕЙ ВОЙНЫ?. 224 стр. (ТВЁРДЫЙ ПЕРЕПЛЁТ) 11 ноября 1918 года в старом вагоне неподалеку от Компьеня было подписано перемирие, которое означало окончание Первой мировой войны. Через полгода, 28 июня 1919 года, был подписан Версальский договор — вердикт, возлагавший... (Подробнее) URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR
Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее) URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR
Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире. Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее) URSS. 2024. 248 с. Мягкая обложка. 14.9 EUR
В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные... (Подробнее) URSS. 2024. 240 с. Твердый переплет. 23.9 EUR
Предлагаемая вниманию читателей книга, написанная крупным биологом и государственным деятелем Н.Н.Воронцовым, посвящена жизни и творчеству выдающегося ученого-математика, обогатившего советскую науку в области теории множеств, кибернетики и программирования — Алексея Андреевича Ляпунова. Книга написана... (Подробнее) 2023. 416 с. Твердый переплет. 19.9 EUR
Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые... (Подробнее) |