Составители:
Рубрика:
174
Список литература
1. Акимов О.Е. Дискретная математика: логика, груп-
пы, графы. – М.: Лаборатория Базовых Знаний,
2003.
2. Белоусов А.И., Ткачев С.Б. Дискретная математика:
Учеб. для вузов. – М.: Изд-во МГТУ им.
Н.Э.Баумана, 2002.
3. Березина Л.Ю. Графы и их применение: Пособие
для учителей. – М.: Просвещение, 1979.
4. Берж К.
Теория графов и ее применения. – М.: Из-
дательство иностранной литературы, 1962.
5. Гаврилов Г.П., Сапоженко А.А. Сборник задач по
дискретной математике. – М.: Наука, 1997.
6. Гаврилов Г. П., Сапоженко А. А. Задачи и упраж-
нения по курсу дискретной математики: Учебное
пособие для вузов. – М.: Физматлит, 2003.
7. Галушкина Ю.И. Конспект лекций
по дискретной
математике. – М.: Айрис-пресс, 2007.
8. Горбатов В.А. Дискретная математика. – М.: ООО
«Издательство АСТ»: ООО «Издательство Аст-
рель», 2003.
9. Дискретная математика. Методические указания к
практическим занятиям. Новосибирск, НГТУ, 1996.
10. Дискретная математика. Программа курса. Для сту-
дентов 1 курса направления 351400, 2001 (м/п вари-
ант).
11. Кристофидес Н. Теория графов: алгоритмический
подход. – М.: Мир,1978.
12. Кузнецов О.П. Дискретная математика для инжене-
ров.– СПб: Изд. «Лань», 2005.
3
СОДЕРЖАНИЕ
Введение ........................................................................... 5
1. Основные характеристики графов.............................. 9
1.1. Виды и способы задания графов......................... 9
1.2. Матричные способы задания графов.................. 16
1.3. Изоморфизм графов.............................................. 19
1.4. Маршруты, циклы в неориентированном
графе.......................................................................
21
1.5. Пути, контуры в ориентированном графе.......... 23
1.6. Связность графа.................................................... 25
1.7. Пути во взвешенных ориентированных
графах.....................................................................
29
1.8 Алгоритм Форда – Беллмана нахождения
минимального пути...............................................
35
1.9. Алгоритм нахождения максимального
пути.........................................................................
42
1.10. Деревья................................................................. 48
1.11. Минимальные остовные деревья
нагруженных графов...........................................
50
1.12. Раскраски графов................................................. 55
1.13. Расстояния в графах............................................ 58
1.14. Фундаментальные циклы.................................... 60
1.15. Разрезы................................................................. 64
1.16. Операции над графами....................................... 68
1.17. Внутренняя и внешняя устойчивость графа..... 75
2. Основные теоремы теории графов ............................. 79
3. Эйлеровы циклы........................................................... 85
3.1. Основные понятия и определения....................... 85
3.2. Критерий существования эйлерова цикла.......... 86
3.3. Алгоритмы построения эйлерова цикла............. 89
3.4. Некоторые родственные задачи........................... 93
3.5. Задача китайского почтальона............................. 95
Список литература СОДЕРЖАНИЕ
1. Акимов О.Е. Дискретная математика: логика, груп- Введение ........................................................................... 5
пы, графы. – М.: Лаборатория Базовых Знаний, 1. Основные характеристики графов.............................. 9
2003. 1.1. Виды и способы задания графов......................... 9
2. Белоусов А.И., Ткачев С.Б. Дискретная математика: 1.2. Матричные способы задания графов.................. 16
Учеб. для вузов. – М.: Изд-во МГТУ им. 1.3. Изоморфизм графов.............................................. 19
Н.Э.Баумана, 2002. 1.4. Маршруты, циклы в неориентированном
3. Березина Л.Ю. Графы и их применение: Пособие графе....................................................................... 21
1.5. Пути, контуры в ориентированном графе.......... 23
для учителей. – М.: Просвещение, 1979.
1.6. Связность графа.................................................... 25
4. Берж К. Теория графов и ее применения. – М.: Из- 1.7. Пути во взвешенных ориентированных
дательство иностранной литературы, 1962. графах..................................................................... 29
5. Гаврилов Г.П., Сапоженко А.А. Сборник задач по 1.8 Алгоритм Форда – Беллмана нахождения
дискретной математике. – М.: Наука, 1997. минимального пути............................................... 35
6. Гаврилов Г. П., Сапоженко А. А. Задачи и упраж- 1.9. Алгоритм нахождения максимального
нения по курсу дискретной математики: Учебное пути......................................................................... 42
пособие для вузов. – М.: Физматлит, 2003. 1.10. Деревья................................................................. 48
7. Галушкина Ю.И. Конспект лекций по дискретной 1.11. Минимальные остовные деревья
математике. – М.: Айрис-пресс, 2007. нагруженных графов........................................... 50
8. Горбатов В.А. Дискретная математика. – М.: ООО 1.12. Раскраски графов................................................. 55
1.13. Расстояния в графах............................................ 58
«Издательство АСТ»: ООО «Издательство Аст-
1.14. Фундаментальные циклы.................................... 60
рель», 2003.
1.15. Разрезы................................................................. 64
9. Дискретная математика. Методические указания к 1.16. Операции над графами....................................... 68
практическим занятиям. Новосибирск, НГТУ, 1996. 1.17. Внутренняя и внешняя устойчивость графа..... 75
10. Дискретная математика. Программа курса. Для сту- 2. Основные теоремы теории графов ............................. 79
дентов 1 курса направления 351400, 2001 (м/п вари- 3. Эйлеровы циклы........................................................... 85
ант). 3.1. Основные понятия и определения....................... 85
11. Кристофидес Н. Теория графов: алгоритмический 3.2. Критерий существования эйлерова цикла.......... 86
подход. – М.: Мир,1978. 3.3. Алгоритмы построения эйлерова цикла............. 89
12. Кузнецов О.П. Дискретная математика для инжене- 3.4. Некоторые родственные задачи........................... 93
ров.– СПб: Изд. «Лань», 2005. 3.5. Задача китайского почтальона............................. 95
174 3
