Обложка Емеличев В.А., Зверович И.Э., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Теория графов в задачах и упражнениях: Более 200 задач с подробными решениями
Id: 274357
699 руб.

Теория графов в задачах и упражнениях:
Более 200 задач с подробными решениями Изд. стереотип.

URSS. 2021. 416 с. ISBN 978-5-9519-2063-8.
Типографская бумага

Аннотация

Настоящий сборник задач представляет собой пособие для практических занятий и самообразования по курсу "Теория графов". Он составлен в соответствии с учебником В.А.Емеличева, О.И.Мельникова, В.И.Сарванова и Р.И.Тышкевич "Лекции по теории графов" (М., URSS), которому была присуждена Государственная премия Республики Беларусь. В него включено свыше 1000 задач различной степени трудности, посвященных основным вопросам этой теории. Ко всем... (Подробнее)


Оглавление
Предисловие
Основные обозначения
Глава 1.Азбука теории графов
 1.1Графы. Первоначальные понятия
 1.2Маршруты, цепи, компоненты
 1.3Подграфы и наследственные свойства графов
 1.4Операции над графами
 1.5Матрицы, ассоциированные с графом
 1.6Группа автоморфизмов графа
Глава 2.Деревья
 2.1Деревья. Базовые понятия
 2.2Остовные деревья
Глава 3.Независимость и покрытия
 3.1Независимые множества вершин и клики
 3.2Покрытия
 3.3Доминирующие множества
 3.4Паросочетания
 3.5Паросочетания в двудольных графах
Глава 4.Связность
 4.1Двусвязные графы и двусвязные компоненты
 4.2k-связность
 4.3Циклы и разрезы
Глава 5.Матроиды
 5.1Системы независимости
 5.2Матроиды
 5.3Бинарные матроиды
Глава 6.Планарность
 6.1Укладки графов. Формула Эйлера
 6.2Плоские триангуляции
 6.3Критерии планарности
 6.4Двойственность и планарность
 6.5Характеристики непланарности
Глава 7.Обходы в графах
 7.1Эйлеровы графы
 7.2Гамильтоновы графы
Глава 8.Степенные последовательности
 8.1Графические последовательности
 8.2P-графические последовательности
 8.3Расщепляемые и пороговые графы
 8.4Степенные множества и частотные разбиения
Глава 9.Раскраски графов
 9.1Вершинные раскраски
 9.2Хроматический полином
 9.3Реберная раскраска
 9.4Раскраски плоских графов
 9.5Совершенные графы
Глава 10.Ориентированные графы
 10.1Ориентированные графы: основные определения
 10.2Достижимость и компоненты
 10.3Матрицы, ассоциированные с орграфом
 10.4Обходы и пути
 10.5Турниры
 10.6База и ядро
Глава 11.Гиперграфы
 11.1Основные понятия
 11.2Реализации гиперграфа
Ответы, указания, решения
 1. Азбука теории графов
 1.1Графы. Первоначальные понятия
 1.2Маршруты, цепи, компоненты
 1.3Подграфы и наследственные свойства графов
 1.4Операции над графами
 1.5Матрицы, ассоциированные с графом
 1.6Группа автоморфизмов графа
 2. Деревья
 2.1Деревья. Базовые понятия
 2.2Остовные деревья
 3. Независимость и покрытия
 3.1Независимые множества вершин и клики
 3.2Покрытия
 3.3Доминирующие множества
 3.4Паросочетания
 3.5Паросочетания в двудольных графах
 4. Связность
 4.1Двусвязные графы и двусвязные компоненты
 4.2k-связность
 4.3Циклы и разрезы
 5. Матроиды
 5.1Системы независимости
 5.2Матроиды
 5.3Бинарные матроиды
 6. Планарность
 6.1Укладки графов. Формула Эйлера
 6.2Плоские триангуляции
 6.3Критерии планарности
 6.4Двойственность и планарность
 6.5Характеристики непланарности
 7. Обходы в графах
 7.1Эйлеровы графы
 7.2Гамильтоновы графы
 8. Степенные последовательности
 8.1Графические последовательности
 8.2P-графические последовательности
 8.3Расщепляемые и пороговые графы
 8.4Степенные множества и частотные разбиения
 9. Раскраски графов
 9.1Вершинные раскраски
 9.2Хроматический полином
 9.3Реберная раскраска
 9.4Раскраски плоских графов
 9.5Совершенные графы
 10. Ориентированные графы
 10.1Ориентированные графы: основные определения
 10.2Достижимость и компоненты
 10.3Матрицы, ассоциированные с орграфом
 10.4Обходы и пути
 10.5Турниры
 10.6База и ядро
 11. Гиперграфы
 11.1Основные понятия
 11.2Реализации гиперграфа
Библиография
Предметный указатель

Предисловие

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

Настоящий сборник задач, являющийся переводом книги O.Melnikov, V.Sarvanov, R.Tyshkevich, V.Yemelichev and I.Zverovich "Exercises in Graph Theory" (Kluwer Academic Publishers, 1998), составлен в соответствии c учебным пособием В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич <<Лекции по теории графов>> (М.: Наука, 1990; 3-е изд. М.: URSS, 2013).

Весь материал задачника разделен на одиннадцать глав и содержит свыше тысячи задач, посвященных основным вопросам теории графов. В каждом параграфе приведены определения и краткие сведения из теории, необходимые для решения задач. Доказательства приведенных теорем можно найти в упомянутом учебном пособии. Большинство задач снабжено ответами, указаниями к их решению, а в ряде случаев и решениями.

Авторы выражают искреннюю признательность рецензентам --коллективу кафедры прикладной математики Гродненского государственного университета, возглавляемой кандидатом физико-математических наук доцентом Ю.Э.Белых, кандидату физико-математических наук, доценту этой кафедры Н.Н.Иванову и главному научному сотруднику Института технической кибернетики Национальной академии наук Беларуси доктору физико-математических наук В.С.Гор-дону. Мы также признательны А.Ю.Бабайцеву, В.И.Волошину,А.Н.Исаченко, А.Г.Левину, Ю.М.Метельскому, В.Г.Найденко и многим другим нашим коллегам за ценные советы и замечания, способствовавшие улучшению книги. Авторы благодарят К.Г.Кузьмина за подготовку рукописи к печати.


Об авторах
Емеличев Владимир Алексеевич
Доктор физико-математических наук, профессор Белорусского государственного университета, лауреат Государственной премии Республики Беларусь. Действительный член Нью-Йоркской академии наук, член редколлегий ряда международных научно-теоретических журналов в России, Украине и Молдове. Научные интересы — дискретная оптимизация, полиэдральная комбинаторика, теория графов, анализ устойчивости многокритериальных дискретных задач. Автор и соавтор нескольких монографий и учебных пособий.
Зверович Игорь Эдмундович
Доктор философии в области исследования операций (Раттгерс, государственный университет штата Нью-Джерси), кандидат физико-математических наук.
Мельников Олег Исидорович
Профессор механико-математического факультета Белорусского государственного университета, доктор педагогических наук, кандидат физико-математических наук. Научные интересы: теория графов, обучение дискретной математике в высшей и средней школе. Лауреат Государственной премии Республики Беларусь.
Сарванов Владимир Иванович
Кандидат физико-математических наук, заведующий отделом Института математики Национальной академии наук Беларуси. Лауреат Государственной премии Республики Беларусь. Научные интересы: теория графов, дискретная оптимизация, комбинаторная вычислительная геометрия. Автор и соавтор нескольких учебных пособий.
Тышкевич Регина Иосифовна
Доктор физико-математических наук, профессор Белорусского государственного университета. Лауреат Государственной премии Республики Беларусь. Заслуженный работник народного образования Беларуси. Основатель белорусской школы теории графов. Научные интересы — теория графов, дискретная оптимизация, комбинаторный анализ. Автор и соавтор нескольких монографий и учебных пособий. Награждена медалью Франциска Скорины.