Читать онлайн «Дискретная математика: графы, матроиды, алгоритмы»

М. О. Асанов, В. А. Баранский, В. В. Расин дискретная математика: графы, матроиды, алгоритмы Рекомендовано в качестве учебного пособия Научно-методическим советом по математике и механике УМО по классическому университетскому образованию для математических специальностей и направлений Vyetatttcca Москва ♦ Ижевск 2001 УДК 512 Интернет-магазин . О. , Баранский В. А. , Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001, 288 стр. Изложен ряд основных разделов теории графов и матроидов. Рассмотрены алгоритмы дискретной оптимизации на сетях и графах, наиболее часто используемые программистами. Для студентов и аспирантов, специализирующихся в области компьютерных наук, для практикующих программистов, для всех желающих изучить основы современной дискретной компьютерной математики. ISBN 5-93972-076-5 © Асанов М. О. , Баранский В. А. , Расин В. А. М. Горького, обучающихся по специальностям «Математика, прикладная математика», «Математика, компьютерные науки» и «Компьютерная безопасность». В книге излагается ряд разделов теории графов и приводятся алгоритмы дискретной оптимизации на графах и сетях. Материал, посвященный теории графов, содержит достаточно обширное введение в теорию мат- роидов. Матроиды, в частности, составляют теоретическую основу для изучения и анализа алгоритмов, использующих «жадную» стратегию. Понимание же природы и областей применимости жадных алгоритмов безусловно необходимо каждому специалисту по компьютерной математике и ее приложениям. Теория графов за последние десятилетия развилась в весьма обширную ветвь математики, имеющую многочисленные приложения в самых разнообразных сферах человеческой деятельности. В настоящее время практически невозможно в одном учебном пособии отразить все разделы теории графов. Подбор тем, поднятых в книге, во многом определен вкусами авторов. Нам хотелось представить основное, устоявшееся ядро современной теории графов и сопутствующее ему семейство алгоритмов дискретной оптимизации, наиболее часто используемых программистами. Мы стремились привести главные достижения, не останавливаясь на мелочах и не углубляясь в детальный обзор результатов по обсуждаемым темам. Мы стремились также привести самые лаконичные и изящные доказательства из известных нам. Часть доказательств была существенно переработана нами и некоторые из них стали относительно далеки от своих прототипов.