В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов, страница 70
Описание файла
DJVU-файл из архива "В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов", который расположен в категории "". Всё это находится в предмете "дискретная математика" из 2 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 70 - страница
НАЧАЛЫ1ЫЕ ПОНЯТИЯ, 4 1, Определение графа $2. Подграфы 3. Операции над графами 4 4. Цепи, циклы, компоненты 1 5. Стеяепн вершин графа 6. Матрицы, ассоциированные с графом 7. Регулярные графы 8. Метрические характеристики графа 9. Критерии двудольности графа 1 10, Реберный граф 4 М. Группа автоморфизмов графа 5 12. <Почти зсе» графы Упражнения Глава Ы. ДЕРЕВБЯ 1 13. Определение дерева 4 14. Матричная тоорема Кнрхгофа 1 15.
Остов ыинимального веса Упражнения . Глава 1ТН МАТРОИДЫ И ТРАНСВЕРСАЛИ 1 16. Азбука теории матроидов 5 17. Двойственный матронд 1 18. Примеры матроидов 4 19. Изоморфизм матроидов 4 20. Представление матропда 5 21. Бинарные матроиды $22. Трансверсали 9 23. Жадный алгоритм $24. Объединение и пересечение матроидов Упражнения, Глава 1К НЕЗАНИСИИОСТБ И ПОНРЫТИЯ 5 25. Независимые множества и покрытия 4 26. Клика $27. Проблемы кчикп, изоморфной вложимости морфного подграфа 1 28. Интерпретации независимых множеств 9 29. Паросочетании 9 9 17 19 22 26 27 32 34 36 38 42 47 51 64 64 68 70 73 75 79 87 92 95 100 102 102 111 и изо- 115 117 122 381 124 128 130 132 Глава У, СРЯЗПОСТЬ 1 33.
Воршиппая связность и 1 34. Двусвязные графы 1 35. Теорема Ментора Упражнения . 133 133 137 145 148 реберпая связность Глава У11. ОБХОДИ 4 43. Эйлеровы графы 1 44. Гамильтоновы графы Упражнспия . 191 191 196 207 Глава У!11, СТЕПЕННЬ1Е ПОСЛЕДОВЛТГЛЬНОСТИ, . 208 1 45. Графическая последовательность...., 209 1 46, Критерия графичности последовательности .. 211 4 47. Реализация графнчсской коследовательности с максимальной связностью . . . . . . .
. 217 1 48. Гамильтопова реализация графической последоватсльпостн . . . . . . . . . . . . 220 1 49. !'асщопляемые графы....,... 222 1 50. Пороговые графы........, . 223 1 51. Пороговое разложение графа...... 228 1 52. Стопенпое мпожсство графа....... 232 Упражнения............, 234 235 235 238 245 248 с раскраска- 252 255 260 264 267 272 277 279 279 283 $30. Паросочетания в двудольном графе 1 31. Двудольные графы и семейства подмножеств 1 32. Парогочстапвя и покрытия Упражпопия . Глава У1. ПЛАНЛРНОСТЬ 1 36. Плоские и планарные графы 1 37. Грани плоского графа. Формула Эйлера 1 38.
Плоские триангуляции 1 39. Критерии плапарности 1 40. Двоиственность и планарность 4 41. Алгоритм укладки графа на плоскости 1 42. Характеристики непланарпых графов Упражнения . Глава 1Х. РАСКРЛСЕИ 4 53. Правильная раскраска 1 54. Оценки хроматического числа 1 55. Хроматический полипом 1 56. Раскраска ребер з 57. Связь матропдных разложений графов ми 1 58. Раскраска планарпых графов 1 59. Проблема четырех красок 1 60. Другие подходы к раскраске графов 1 61. Совершенные графы 1 62. Триапгулировапные графы Упраигнения . Глава Х.
ОРИЕНТИРОВАННЫЕ ГРАФЕ! 1 63. Основные определения 4 64. Полустепени исхода и полустепони захода 382 150 150 153 157 159 169 175 183 187 й86 290 293 296 6 65. Обходы 6 66. Пути $ 67. База и ядро Упражнения, пазначениях 375 377 Глава Х1. ГИПЕРГРАФБ1 1 68. Основные определения и свойства $69. Независимые множества з 70. Раскраски 1 71. Реализации гиперграфа Упражнении . Глава ХБЕ АЛГОРИТМБ1 6 72. Предварительные сведения $ 73. Поиск в глубину 1 74. Отыскание двусвяаных компопент з 75. Миниыальпый остов $76. Кратчайшие пути 1 77. Наибольшие паросочетания и задача о 1 78. Труднорешаемые задачи Упралвиения СПИСОК ЛИТЕРАТУРБ1 ПРЕДМЕТНБ1И УКАЗАТЕЛБ 298 298 304 306 310 315 317 317 323 327 334 342 354 364 373 Учебное н, дщппе ЕИЕЛИЧЕВ В.габилир Алексеевич ИЕЛЬНИКСВ Олег И барович САРВАНОВ Влабилир Иванович ТЫВ1КЕВИЧ Рггика ИосиФовна Лекции по теории графов Завсду~ощий редакцией Е.
1С. Хабпк Редактор А. Д. Вабкгитвбн Худоместаешпгй редактор Т.И. Ка.ььчсико Технический редактор С. Я. Шклар Норректоры О. А, Бутисова, И. Я. Криьпталь ИБ М 32506 Сдано в ппбор 10.05.89 Подшпсано к печати 01.!0.90, Формат 85Х108732. Бумага тип. М 2. Гарнитура о«пьпкаазсннак. Печать высокап Уел. печ. л. 20,16. Ъ'ол. «Р.-отт. 20,18.
Уч.-изд. л. 20,99. Тираж 22000 вкз, Заказ М 866. 1[сна 1 р. Издательско-ароизводотвекное и книготорговое объодинение вНаука» Главная редакция $пзпко-математической лнтпапттоы 1!7071 Москва В-71,Ленинский проспект, Гг Чотвертап типогра$ия издательства вНаукав 630077 Повоапбирек, 7'1, Станиславсного, 25 .