URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов
Id: 21254
 
599 руб.

Лекции по теории графов

1990. 384 с. Твердый переплетISBN 5-02-013992-0. Букинист. Состояние: 4+. .

 Аннотация

Излагаются основы теории графов, обсуждаются некоторые известные проблемы. Приводятся примеры сведения прикладных задач к задачам теории графов и использования аппарата этой теории. Отдельная глава посвящена комбинаторным алгоритмам, связанным с поиском структурных и числовых характеристик графов. Каждая глава сопровождается упражнениями.

Для студентов вузов, обучающихся по специальностям «Мате?-матика» и «Прикладная математика».


 Оглавление

Предисловие..............

Введение...............

Глава 1. НАЧАЛЬНЫЕ ПОНЯТИЯ........

§ 1. Определение графа.........

§ 2. Подграфы............

§ 3. Операции над графами........

§ 4. Цепи, циклы, компоненты.......

§ 5. Степени вершин графа........

§ 6. Матрицы, ассоциированные с графом....

§ 7. Регулярные графы.........

§ 8. Метрические характеристики графа....

§ 9. Критерий двудольности графа......

§ 10. Реберный граф..........

§ 11. Группа автоморфизмов графа......

§ 12. «Почти все» графы......

Упражнения.............

Глава П. ДЕРЕВЬЯ............

§ 13. Определение дерева.........

§ 14. Матричная теорема Кирхгофа......

§ 15. Остов минимального веса.......

Упражнения.............

Глава III. МАТРОИДЫ И ТРАНСВЕРСАЛИ.....

§ 16. Азбука теории матроидов.......

§ 17. Двойственный матроид........

§ 18. Примеры матроидов........

§ 19. Изоморфизм матроидов........

§ 20. Представление матроида.......

§ 21. Бинарные матроиды.........

§ 22. Трансверсали...........

§ 23. Жадный алгоритм.........

§ 24. Объединение и пересечение матроидов Упражнения.,...........

Глава IV. НЕЗАВИСИМОСТЬ И ПОКРЫТИЯ.... § 25. Независимые множества и покрытия.

§ 26. Клика.............

§ 27. Проблемы клики, изоморфной вложимости и изоморфного подграфа.........

§ 28. Интерпретации независимых множеств

§ 29. Паросочетания........

§ 30. Паросочетания в двудольном графе.... 124

§ 31. Двудольные графы и семейства подмножеств. 128

§ 32. Паросочетания и покрытия....... 130

Упражнения............. 132

Глава V. СВЯЗНОСТЬ........... 133

§ 33. Вершинная связность и реберная связность.. 133

§ 34. Двусвязные графы......... 137

§ 35. Теорема Менгера.......... 145

Упражнения............. 148

Глава VI. ПЛАНАРНОСТЬ......... 150

§ 36. Плоские и пленарные графы...... 150

§ 37. Грани плоского графа. Формула Эйлера... 153

§ 38. Плоские триангуляции........ 157

§ 39. Критерии планарности........ 159

§ 40. Двойственность и планарность...... 169

§ 41. Алгоритм укладки графа на плоскости... 175

§ 42. Характеристики непланарных графов.... 183

Упражнения............. 187

Глава VII. ОБХОДЫ........... 191

§ 43. Эйлеровы графы.......... 191

§ 44. Гамильтоиовы графы........ 196

Упражнения............. 207

Глава VIII. СТЕПЕННЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ.. 208

§ 45. Графическая последовательность..... 209

§ 46. Критерии графпчпости последовательности.. 211 § 47. Реализация графической последовательности с максимальной связностью........ 217

§ 48. Гамильтонова реализация графической последовательности............ 220

§ 49. Расщепляемые графы........ 222

§ 50. Пороговые графы.......... 223

§ 51. Пороговое разложение графа...... 228

§ 52. Степенное множество графа....... 232

Упражнения............. 234

Глава IX. РАСКРАСКИ.......... 235

§ 53. Правильная раскраска........ 235

§ 54. Оценки хроматического числа...... 238

§ 55. Хроматический полином........ 245

§ 56. Раскраска ребер.......... 248

§ 57. Связь матроидных разложений графов с раскрасками.............. 252

§ 58. Раскраска планарных графов...... 255

§ 59. Проблема четырех красок....... 260

§ 60. Другие подходы к раскраске графов.... 264

§ 61. Совершенные графы......... 267

§ 62. Триангулированные графы....... 272

Упражнения............. 277

Глава X. ОРИЕНТИРОВАННЫЕ ГРАФЫ..... 279

§ 63. Основные определения........ 279

§ 64. Полустепени исхода и полустепени захода.. 283

§ 65. Обходы............. 286

§ 66. Пути............. 290

§ 67. База и ядро...........293

Упражнения............. 296

Глава XI. ГИПЕРГРАФЫ.......... 298

§ 68. Основные определения и свойства..... 298

§ 69. Независимые множества........ 304

§ 70. Раскраски............ 306

§ 71. Реализации гиперграфа........ 310

Упражнения............. 315

Глава XII. АЛГОРИТМЫ.......... 317

§ 72. Предварительные сведения....... 317

§ 73. Поиск в глубину.......... 323

§ 74. Отыскание двусвязных компонент..... 327

§ 75. Минимальный остов......... 334

§ 76. Кратчайшие пути......... 342

§ 77. Наибольшие паросочетания и задача о назначениях 354

§ 78. Труднорешаемые задачи....... 364

Упражнения............. 373

СПИСОК ЛИТЕРАТУРЫ.......... 375

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ.........377


 Об авторах

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

Информация о Продавце