В книге систематизирование излагаются основы теории графов. Подробно освещаются ее классические вопросы и проблемы: уникурсалъность и гамшътоновостъ графов, планарность графов и теория раскраски, теория замощений и др. Адресуя книгу, в первую очередь, учителям и школьникам, авторы пытались сочетать математическую строгость с доступностью изложения и наглядностью. Все определяемые понятия и доказываемые теоремы сопровождаются большим количеством примеров, задач, упражнений и графических иллюстраций.
Библиограф. 24 назв.
От авторов
В настоящее время теория графов стала очень популярной среди учителей, школьников и студентов. Это связано с тем, что при помощи этой теории можно довольно просто решать большой круг самых разнообразных математических задач. На языке графов условия задач приобретают завидную наглядность, что упрощает их анализ. Сами решения, как правило, являются простыми, и в отличие от решений другими методами не содержат утомительных вычислений. Это является очевидным достоинством графов, так как изобилие выкладок, как известно, не свидетельствует о содержательности теории. Теория графов притягательна как раз тем, что при всей своей наглядности и простоте помогает решать серьезные математические и прикладные проблемы. Однако, как это ни странно, теория графов не входит в учебные планы математических специальностей университетов и в программы математических школ. В лучшем случае она изучается студентами и школьниками лишь на факультативах и спецкурсах. Исключение составляют технические и экономические вузы, где студенты вынуждены бегло познакомиться с графами при рассмотрении некоторых приложений.
Знакомство с отдельными разделами теории графов становится возможным уже в начальной школе при решении всевозможных логических задач и головоломок. Дальнейшее знакомство с графами в основной школе поможет при изучении многих математических разделов и будет служить хорошим подспорьем при решении сложных олимпиадных задач.
В предлагаемой книге систематизирование излагаются основы теории графов, все определяемые понятия сопровождаются большим количеством примеров, задач, упражнений и графических иллюстраций. Подробно освещаются классические проблемы и вопросы теории.
Адресуя книгу, в первую очередь, учителям и школьникам, авторы пытались сочетать доступность и наглядность изложения с математической строгостью. Подробно
Содержание
ОТ АВТОРОВ.....................................................................................3
ВВЕДЕНИЕ. ПРОИСХОЖДЕНИЕ ТЕОРИИ ГРАФОВ.............................5
ГЛАВА 1. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ.........................8
1.1. АБСТРАКТНОЕ ОПРЕДЕЛЕНИЕ ГРАФА........................................8
1.2. ОПРЕДЕЛЕНИЕ ГЕОМЕТРИЧЕСКОГО ГРАФА.............................10
1.3. ИНЦИДЕНТНОСТЬ И СМЕЖНОСТЬ ЭЛЕМЕНТОВ ГРАФА............12
Определение инцидентности..................................................12
Определение смежности........................................................12
1.4. СТЕПЕНИ ВЕРШИН ГРАФА.......................................................13
Задачи и упражнения..............................................................75
Ответы и пояснения...............................................................16
1.5. ИЗОМОРФИЗМ ГРАФОВ............................................................16
Упражнения.............................................................................19
Ответы и пояснения...............................................................21
1.6. ГЕОМЕТРИЧЕСКИЕ РЕАЛИЗАЦИИ АБСТРАКТНЫХ ГРАФОВ......21
1.7. НЕКОТОРЫЕ КЛАССЫ КОНЕЧНЫХ ГРАФОВ.............................26
Элементарные графы..............................................................26
Элементарные графы с петлями...........................................26
Мультиграфы и псевдографы.................................................27
Однородные графы..................................................................27
Двудольные и k-дольные графы..............................................28
1.8. ЧАСТИ ГРАФА..........................................................................29
Упражнения.............................................................................31
Ответы и пояснения...............................................................32
1.9. ПОПОЛНЕНИЯ ЭЛЕМЕНТАРНЫХ ГРАФОВ................................34
1.10. НЕПРЕРЫВНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ РЕБЕР ГРАФА.........37
Маршруты................................................................................37
Цепи и циклы......................................,.....................................38
Простые цепи и циклы............................................................39
Упражнения.............................................................................39
Ответы и пояснения...............................................................39
1.11. СВЯЗНОСТЬ ГРАФОВ..............................................................41
Определение связных и несвязных графов.............................41
Компоненты связности...........................................................42
k-связные графы.......................................................................43
Задачи и упражнения........................................................i......45
Ответы, указания и решения.................................................. 47
1.12. МНОЖЕСТВА СОЧЛЕНЕНИЯ И РАЗДЕЛЯЮЩИЕ МНОЖЕСТВА. 51
-, , Множества сочленения...........................................................51
t \ Разделяющие множества и разрезы,.....................................52
v Упражнения............................................,.................................54
Ответы и пояснения................................................................55
1.13. ДРЕВОВИДНЫЕ ГРАФЫ..........................................................59
Различные определения деревьев............................................59
Определение леса......................................................................61
Покрывающее дерево связного графа.....................................62
Задачи и упражнения...............................................................63
Ответы, указания и решения................................................64
ГЛАВА 2. КЛАССИЧЕСКИЕ ВОПРОСЫ ТЕОРИИ
ГРАФОВ....................................................................... 68
2.1.УНИКУРСАЛЬНЫЕГРАФЫ........................................................68
Задача Эйлера о кенигсбергских мостах............................... 68
... Определение уникурсальных графов. Примеры.....................69
Признаки уникурсальных графов............................................77,
Количество росчерков.....................................•..........•..............74
Алгоритм нахождения эйлерова цикла..................................75
Задачи и упражнения...............................................................77
Ответы, указания и решения..........i......,.............................. 79
2.2. ГАМИЛЬТОНОВЫ ГРАФЫ.......................„..,„..........,................82
Гамильтоновы цепи и циклы...................................................82
Некоторые свойства гамиаьтоновых графов...................... 84
Задачи и упражнения...—.........>.>,......—,.............................. 87
Ответы, указания и решения—........................................... 89
2.3. ПРОБЛЕМА плАНАРности ГРАФОВ........................................93
Грани плоского графа..............................................................94
Теорема Эйлера о плоском графе...........................................98
Двойственность плоских графов...............,..........................700
Самодвойственные графы....................................................702
Графы из многоугольников.....................................................705
Реберные пересечения в полных графах...............................709
Графы Понтрягина-Куратовского......................................775
Прямолинейные графы..........................................................778
Задачи и упражнения............................................................ 779
Ответы, указания и решения............................................... 727
2.4. РАСКРАСКА ГРАФОВ.............................................................130
Раскраска граней плоского графа............................:...........730
Раскраска вершин графа...................................................... 745
Раскраска ребер графа.,....................................................... 747
Монохроматические треугольники........................i............. 749
Задачи и упражнения............................................................752
Ответы, указания и решения...............................................753
2.5. ТЕОРИЯ ЗАМОЩЕНИЙ............................................................157
Правильные замощения плоскости...................................... 767
Полуправильные замощения плоскости...............................765
Правильные замощения сферы.............................................7SO
Полуправильные плоские графы...........................................782
ГЛАВА 3. ОРИЕНТИРОВАННЫЕ ГРАФЫ.......______197
3.1. ОСНОВНЫЕ ПОНЯТИЯ И СВОЙСТВА......................................197
Орграф и его элементы.........................................................797
Симметризация орграфа......................................................799
Инцидентность и смежность элементов орграфа...........200
Полустепени вершин орграфа..............................................207
Изоморфизм орграфов.......................................................... 203
Элементарные орграфы........................................................204
3.2. СВЯЗНЫЕ ОРГРАФЫ............................................................... 206
Ориентированные маршруты-..............................:............. 206
Упражнения.„...........................:...............................;............ 208
Связность и сильная связность орграфов..................:...:.... 208
Эйлеровость, согласованная с ориентацией...........:........... 210
Гамилыпоновость, согласованная с ориентацией.............. 275
Ориентируемые графы..............__.....:..........................!.... 277
3.3. ГРАФЫ БИНАРНЫХ ОТНОШЕНИЙ.......................................... 219
Бинарные отношения и их графы........................................279
Графы бинарных отношений со свойствами......................223
Граф отношения эквивалентности....................................225
3.4. ОРИЕНТИРОВАННЫЕ ГРАФЫ в ЗАДАЧАХ.............................. 227
Задачи на ориентируемость графов*................................:. 227
Задачи на изменения состояний системы........................... 228
Задачи о выигрышных стратегиях......................................230
Задачи и упражнения............................................................237
Ответы, указания и решения...............................................233
Цена: 150руб.
