Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов

Учебное пособие. — М.: Наука, Главная редакция физико-математической литературы, 1990. — 384 с. — ISBN 5-02-013992-0.В основу настоящего учебного пособия положены курсы лекций, которые читались авторами в Белорусском государственном университете имени В.И. Ленина для студентов-математиков и в Белорусском политехническом институте для студентов, обучающихся по специальности «Прикладная математика». Изложение материала в книге ставит своей целью дать в руки студентов орудие, применимое как к наукам о поведении (кибернетика, теория информации, теория систем, теория игр), так и к теории множеств, теории матриц, теории групп и к другим чисто абстрактным дисциплинам. Основной задачей этого учебного пособия является ознакомление студентов с теоретическими основами теории графов. Вместе с тем большое внимание уделяется вопросам применения теории графов к решению прикладных задач и в связи с этим, — построению эффективных алгоритмов. Книга состоит из двенадцати глав. Отдельная глава посвящена комбинаторным алгоритмам, связанным с поиском структурных и числовых характеристик графов. Каждая глава сопровождается упражнениями. Для студентов специальностей "Математика", "Прикладная математика".Начальные понятия.
Определение графа.
Подграфы.
Операции над графами.
Цепи, циклы, компоненты.
Степени вершин графа.
Матрицы, ассоциированные с графом.
Регулярные графы.
Метрические характеристики графа.
Критерии двудольности графа.
Реберный граф.
Группа автоморфизмов графа.
"Почти все" графы.
Упражнения.
Деревья.
Определение дерева.
Матричная теорема Кирхгофа.
Остов минимального веса.
Упражнения.
Матроиды и трансверсали.
Азбука теории матроидов.
Двойственный матроид.
Примеры матроидов.
Изоморфизм матроидов.
Представление матроида.
Бинарные матроиды.
Трансверсали.
Жадный алгоритм.
Объединение и пересечение матроидов.
Упражнения.
Независимость и покрытия.
Независимые множества и покрытия.
Клика.
Проблемы клики, изоморфной вложимости и изоморфного подграфа.
Интерпретации независимых множеств.
Паросочетания.
Паросочетания в двудольном графе.
Двудольные графы и семейства подмножеств.
Паросочетания и покрытия.
Упражнения.
Связность.
Вершинная связность и реберная связность.
Двусвязные графы.
Теорема Менгера.
Упражнения.
Планарность.
Плоские и планарные графы.
Грани плоского графа. Формула Эйлера.
Плоские триангуляции.
Критерии планарности.
Двоиственность и планарность.
Алгоритм укладки графа на плоскости.
Характеристики непланарпых графов.
Упражнения.
Обходы.
Эйлеровы графы.
Гамильтоновы графы.
Упражнения.
Степенные последовательности.
Графическая последовательность.
Критерии графичности последовательности.
Реализация графической последовательности с максимальной связностью.
Гамильтопова реализация графической последовательности.
Расщепляемые графы.
Пороговые графы.
Пороговое разложение графа.
Степенное множество графа.
Упражнения.
Раскраски.
Правильная раскраска.
Оценки хроматического числа.
Хроматический полином.
Раскраска ребер.
Связь матроидных разложений графов с раскрасками.
Раскраска планарных графов.
Проблема четырех красок.
Другие подходы к раскраске графов.
Совершенные графы.
Триангулированные графы.
Упражнения.
Ориентированные графы.
Основные определения.
Полустепени исхода и полустепени захода.
Обходы.
Пути.
База и ядро.
Упражнения.
Гиперграфы.
Основные определения и свойства.
Независимые множества.
Раскраски.
Реализации гиперграфа.
Упражнении.
Алгоритм.
Предварительные сведения.
Поиск в глубину.
Отыскание двусвяаных компонент.
Минимальный остов.
Кратчайшие пути.
Наибольшие паросочетания и задача о назначениях.
Труднорешаемые задачи.
Упражнения.
Список литературы.
Предметный указатель.