| Предисловие |
| LXVI | Элементы теории чисел |
| | § 1. | Теорема о делении с остатком |
| | § 2. | Наибольший общий делитель. Алгоритм Евклида |
| | § 3. | (ka -- 1, kb -- 1) = k(a,b) -- 1 |
| | § 4. | Простые числа. Основная теорема арифметики |
| | § 5. | Сравнения и их свойства |
| | § 6. | Системы вычетов |
| | § 7. | Теорема Эйлера |
| | § 8. | Линейные диофантовы уравнения |
| | § 9. | Мультипликативные функции |
| | § 10. | Система РША |
| | Упражнения |
| | Ответы |
| LXVII | Начальные понятия общей алгебры |
| | § 1. | Отношения |
| | § 2. | Отношение эквивалентности |
| | § 3. | Отношения порядка |
| | § 4. | Алгебраические структуры. Группа |
| | § 5. | Кольцо и поле |
| | § 6. | Группы самосовмещений многоугольников и многогранников |
| | Упражнения |
| | Ответы |
| LXVIII | Комбинаторика |
| | § 1. | Правило произведения |
| | | 1.1. | Число перестановок |
| | | 1.2. | Число подмножеств конечного множества |
| | § 2. | Выборки. Размещения |
| | § 3. | Сочетания |
| | § 4. | Перестановки с повторениями |
| | § 5. | Полиномиальная формула |
| | § 6. | Комбинаторные тождества |
| | § 7. | Формула включения-исключения |
| | § 8. | Функция Эйлера |
| | § 9. | Задача о беспорядках и встречах |
| | § 10. | Число сюръекций |
| | § 11. | Обобщение формулы включения-исключения |
| | § 12. | Числа Стирлинга II рода |
| | § 13. | Числа Стирлинга I рода |
| | § 14. | Производящие функции |
| | § 15. | Число счастливых билетов |
| | § 16. | Число бинарных деревьев с n вершинами |
| | § 17. | Решение линейных рекуррентных уравнений |
| | Упражнения |
| | Ответы |
| LXIX | Теория Пойа |
| | § 1. | Цикловой индекс группы подстановок |
| | § 2. | Лемма Бернсайда |
| | § 3. | Функции и классы эквивалентности |
| | § 4. | Теорема Пойа |
| | § 5. | Примеры |
| | Упражнения |
| | Ответы |
| LXX | Введение в теорию графов |
| | § 1. | Определения и примеры |
| | § 2. | Связные графы |
| | § 3. | Метрические характеристики графа |
| | § 4. | Гамильтоновы графы |
| | § 5. | Эйлеровы графы |
| | § 6. | Деревья и леса |
| | § 7. | Теорема Кэли о числе помеченных деревьев |
| | § 8. | Стягивающие деревья |
| | § 9. | Фундаментальная система циклов |
| | | 9.1. | Симметрическая разность множеств |
| | | 9.2. | Псевдоциклы |
| | | 9.3. | Фундаментальная система циклов |
| | § 10. | Укладки графов |
| | § 11. | Формула Эйлера |
| | § 12. | Критерий планарности графа |
| | § 13. | Ориентированные графы |
| | § 14. | Нахождение кратчайших путей в орграфе |
| | § 15. | Задача сетевого планирования и управления (PERT) |
| | § 16. | Потоки в сетях |
| | Упражнения |
| | Ответы |
| LXXI | Паросочетания |
| | § 1. | Теорема Холла |
| | § 2. | Венгерская теорема |
| | § 3. | Теорема Дилворта |
| | § 4. | Совершенные паросочетания в регулярных двудольных графах |
| | § 5. | Дважды стохастические матрицы |
| | § 6. | Латинские прямоугольники |
| | § 7. | Реберная раскраска графов |
| | § 8. | Теорема Бёржа |
| | § 9. | Нахождение наибольшего паросочетания |
| | § 10. | Нахождение наименьшего вершинного покрытия |
| | § 11. | Венгерский алгоритм |
| | § 12. | Задача о назначениях на узкое место |
| | Упражнения |
| | Ответы |
| LXXII | Матроиды |
| | § 1. | Определения и примеры |
| | § 2. | Двойственность |
| | § 3. | Представимые матроиды |
| | § 4. | Ранговая функция |
| | § 5. | Жадный алгоритм |
| | § 6. | Одна задача планирования эксперимента |
| | § 7. | Трансверсали |
| | § 8. | Трансверсальный матроид |
| | § 9. | Независимые трансверсали |
| | § 10. | Общие трансверсали |
| | § 11. | Некоторые интересные матроиды |
| | | 11.1. | Матроид Фано |
| | | 11.2. | Матроид Вамоса |
| | Упражнения |
| | Ответы |
| Предметный указатель |
В предыдущих книгах нашего издания развитие основных событий
в большей или меньшей степени было связано с ключевой идеей близости,
математическое осмысление которой привело к ошеломляющему каскаду самых
разнообразных результатов. И хотя эта идея еще весьма далека от исчерпания,
существует широкий пласт математических задач, в которых она не работает.
Значительную по объему долю в этом пласте составляют задачи, в которых
изучаются свойства множеств, состоящих из конечного числа элементов. Число
элементов в таких множествах может быть разным -- от нескольких единиц
до многих степеней десяти -- 1010, 101010, ... .
Истоки некоторых из этих задач и методы их решения отделены от нас сотнями
и даже тысячами лет. Появление других было стимулировано развитием
вычислительных средств, стремительно расширяющиеся возможности которых сами
служат источником все новых и новых задач.
Нарастающий интерес вызвал к жизни новое понятие -- дискретная
математика. Понимаемая в широком смысле дискретная математика включает в себя
теорию чисел, общую алгебру, математическую логику, комбинаторный анализ,
теорию графов, теорию кодирования, целочисленное программирование, теорию
функциональных систем и др.
Дискретность (от латинского discretus -- разделенный, прерывистый)
нередко противопоставляют непрерывности. Однако при решении сложных
практических задач дискретные и непрерывные подходы работают совместно и весьма
эффективно, взаимно обогащая друг друга.
В 1998 году издательство "Мир" выпустило книгу Р.Грэхема, Д.Кнута
и О.Паташника "Конкретная математика" (Concrete mathematics), термин
CONCRETE
в названии которой образован слиянием слов
CONtinious и disCRETE.
Основная задача этого тома -- дать читателю рабочее представление о технике
оперирования с дискретными объектами, аналогичной технике для объектов
непрерывных.
Наша цель скромней: мы лишь хотим познакомить читателя с некоторыми элементами
дискретной математики.
В первых двух главах тома рассматриваются элементы теории чисел и общей
алгебры. Вводимые при этом понятия широко используются в других главах,
в частности при изложении теории Пойа, позволяющей решать задачи пересчета
объектов с точностью до того или иного отношения эквивалентности. В главе,
посвященной комбинаторике, помимо начальных сведений о выборках излагается
принцип включения-исключения, эффективно работающий при решении классических
комбинаторных задач. Здесь также описывается аппарат производящих функций --
мощное средство комбинаторного анализа. В заключительных главах вводятся
основные понятия теории графов
и матроидов, описываются некоторые эффективные алгоритмы.
Краснов Михаил Леонтьевич
Кандидат физико-математических наук, профессор кафедры высшей математики Московского энергетического института (МЭИ). Был членом Редакционного совета МЭИ, работал в Совете по математическому образованию при Министерстве высшего образования СССР.
В область научных интересов М. Л. Краснова входили дифференциальные уравнения. Им были написаны научные статьи, посвященные уравнениям в частных производных и некоторым прикладным задачам. Вместе с А. И. Киселевым и Г. И. Макаренко он придумал и осуществил простую и в то же время гениальную идею — учить будущих инженеров сложным разделам высшей математики на рассмотрении подробных решений тщательно подобранных типовых примеров при минимальном изложении теории. В результате более чем тридцатилетней совместной работы ими были написаны ставшие классическими учебные пособия ("Векторный анализ", "Вариационное исчисление" и другие). Все эти книги многократно выходили в издательстве URSS, а также были переведены и изданы на испанском, португальском, английском, французском, японском, польском и других языках.
Киселев Александр Иванович
Born on August 26th 1917 in Russia. Graduated from Moscow State University (Department of Mechanics and Mathematics) in 1951. 1951-1962: Affiliated to the Institute of Physical Problems of USSR Academy of Sciences. 1962-1996: Associate Professor of Moscow Power Institute. Department of Mathematics. Fields of interest: Theory of Functions.
Макаренко Григорий Иванович
Окончил механико-математический факультет Московского государственного университета имени М. В. Ломоносова в 1951 г. В 1951–1960 гг. работал на кафедре высшей математики Московского энергетического института. В 1960–1978 гг. — старший научный сотрудник Объединенного института ядерных исследований в Дубне. В 1978–1989 гг. — профессор кафедры математики Московского государственного института путей сообщения. Область научных интересов: дифференциальные уравнения.
Шикин Евгений Викторович
Доктор физико-математических наук, профессор Московского государственного университета имени М. В. Ломоносова. Научные интересы: изометрические погружения двумерных римановых многообразий неположительной кривизны в трехмерное евклидово пространство, геометрические свойства решений уравнения Монжа—Ампера гиперболического типа, геометрические и графические подходы к разрешению задач динамического поиска объектов, исследование проблем управления на разных стадиях кризиса.
Заляпин Владимир Ильич
Окончил механико-математический факультет Московского государственного университета имени М. В. Ломоносова в 1969 г., аспирантуру Отделения математики МГУ — в 1972 г. Кандидат физико-математических наук, доцент, профессор кафедры математического анализа Южно-Уральского государственного университета.
Автор 86 научных и более 40 учебных и методических публикаций. Заместитель председателя Челябинского регионального отделения научно-методического Совета по математике Минобрнауки РФ, председатель Совета по математике ЮУрГУ. Награжден нагрудным знаком "Почетный работник высшей школы РФ".
Эвнин Александр Юрьевич
Кандидат педагогических наук, доцент кафедры прикладной математики Южно-Уральского государственного университета. Автор более 80 научных публикаций, в том числе одного учебника, 16 учебных пособий, а также статей в журналах «Квант», «Математическое образование», «Математика в высшем образовании», «Математика в школе».
