Тема 47. Эйлеровы графы
Впервые графы были рассмотрены Л. Эйлером в связи с известной задачей о кенигсбергских мостах, которая оказалась связанной с возможностью прохождения вершин графа только по одному разу с возвращением в исходную вершину, т.е. одним росчерком пера. В последствии такие графы стали называться эйлеровыми. Цель курсовой работы – изучить некоторые свойства эйлеровых графов. Рекомендуется следующий план изложения материала:
1 Определить понятие графа в виде представления некоторого бинарного отношения и связанные с графом основные понятия, а также привести простейшие примеры (/1/, с. 9 – 24; /2/, с. 6 – 16).
2Дать определение эйлерова и полуэйлерова графа, привести примеры. Установить необходимые и достаточные условия для эйлеровых и полуэйлеровых графов. Описать алгоритм построения эйлеровой цепи в эйлеровом графе (/1/, с. 43 – 48; /2/, с. 37 – 42).
3Рассмотреть примеры эйлеровых и неэйлеровых графов. Решить несколько упражнений из /1/, /2/.
4Исторические сведения о графах: решение Эйлера задачи о семи кенигсбергских мостах (/3/, §43).
Литература, рекомендуемая для изучения темы
1Уилсон Р. Дж. Введение в теорию графов. – М.: 1977.
2Березина Л.Ю. Графы и их применения. – М.: Просвещение, 1979.
3Емеличев В.А. Лекции по теории графов. – М.: Наука, 1990.
4Оре О. Теория графов. – М.: Наука, 1968.
5Саркисян А.А., Колягин Ю.М. Познакомьтесь с топологией. – М.:
1976.
- 1 АЛГЕБРА И ТЕОРИЯ ЧИСЕЛ
- Тема 1. Алгебра бинарных отношений и отображений
- Тема 2. Отображения и фактор-множества
- Тема 10. Основная теорема алгебры
- Тема 18. Замыкания и соответствия Галуа
- Тема 19. Функция Мёбиуса и её свойства
- Тема 28. Греко-китайская теорема об остатках
- Тема 33. Силовские подгруппы
- 2 МАТЕМАТИЧЕСКАЯ ЛОГИКА
- Тема 34. Логическая игра
- Тема 35. Неразрешимость логики первого порядка
- 3 ДИСКРЕТНАЯ МАТЕМАТИКА
- Тема 47. Эйлеровы графы
- Тема 48. Гамильтоновы графы
- Тема 55. Раскраски графов
- Тема 61. Теорема Пойа и перечисление графов
- Тема 62. Графы на двумерных поверхностях
- Тема 68. Логика на словах
- Тема 75. Элементы теории конечных автоматов
- Тема 82. Модулярные и дистрибутивные решетки
- Тема 83. Булевы алгебры
- 4 РАЗЛИЧНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ
- Тема 86. Элементы линейного программирования
- Тема 95. Барицентрическое исчисление
- Приложение А