Введение в теорию графов, Уилсон Р., 1977

Введение в теорию графов, Уилсон Р., 1977.

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

Введение в теорию графов, Уилсон Р., 1977


ЧТО ТАКОЕ ГРАФ?
Рассмотрим сначала рис. 1.1 и 1.2, на которых изображены соответственно участок электрической цепи и часть карты дорог. Ясно, что оба эти рисунка могут быть представлены одной и той же диаграммой из точек и линий, изображенной на рис. 1.3. Точки Р, Q, R, S и Т называются вершинами, линии называются ребрами, а вся диаграмма называется графом. (Заметим, что точка пересечения линий PS и QT не относится к вершинам графа, так как она не является ни общей точкой двух проводов, ни перекрестком дорог.) Степенью вершины называется число ребер, концом которых является эта вершина; на рис. 1.2 это соответствует числу дорог, сходящихся у перекрестка; так, степень вершины Q равна 4.

Очевидно, что граф, изображенный на рис. 1.3, может описывать и другие ситуации. Например, если обозначить через P, Q, R, S и Т футбольные команды, то наличие ребра между двумя вершинами можно трактовать как состоявшуюся встречу соответствующих двух команд (так, согласно рис. 1.3, команда Р уже сыграла с S, но еще не сыграла с R); в этом случае степенью вершины будет число матчей, сыгранных соответствующей командой.

Оглавление.
Предисловие редактора перевода.
Предисловие.
1. Введение.
§1. Что такое граф?.
2. Определения и примеры.
§2. Определения.
§3. Примеры графов.
§4. Укладки графов.
3. Цели и циклы.
§5. Новые определения.
§6. Эйлеровы графы.
§7. Гамильтоновы графы.
§8. Бесконечные графы.
4. Деревья.
§9. Элементарные свойства деревьев.
§10. Перечисление деревьев.
§11. Некоторые приложения теории графов.
5. Планарность и двойственность.
§12. Планарные графы.
§13. Теорема Эйлера о плоских графах.
§14. Графы на других поверхностях.
§15. Двойственные графы.
§16. Двойственность по Уитни.
6. Раскрашивание графов.
§17. Хроматическое число.
§18. Два доказательства.
§19 Раскрашивание карт.
§20. Реберная раскраска.
§21. Хроматические многочлены.
7. Орграфы.
§22. Определения.
§23. Эйлеровы орграфы и турниры.
§24. Цепи Маркова.
8. Паросочетания, свадьбы и теорема Менгера.
§25. Теорема Холла о свадьбах.
§26 Теория трансверсалей.
§27. Приложения теоремы Холла.
§28. Теорема Менгера.
§29. Потоки в сетях.
9. Теория матроидов.
§30. Введение в теорию матроидов.
§31. Примеры матроидов.
§32. Матроиды и теория графов.
§33. Матроиды и теория трансверсалей.
Послесловие.
Приложение.
Список литературы.
Предметный указатель.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Введение в теорию графов, Уилсон Р., 1977 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.Купить эту книгу



Скачать - pdf - Яндекс.Диск.
Дата публикации:





Хештеги: :: :: ::