| От автора |
| Глава I. | Первое знакомство с графами |
| | § 1. | Задачи, приводящие к графам |
| | § 2. | Некоторые основные понятия теории графов |
| | | 1. | Полный граф. Дополнение графа |
| | | 2. | Степень вершины |
| | | 3. | Путь в графе. Цикл |
| | | 4 | Связность графа |
| | | 5. | Операция удаления ребра. Мост |
| | § 3. | Деревья. Лес. |
| | § 4. | Изображение графа |
| Глава II. | Плоские графы |
| | § 1. | Представление о плоском графе |
| | § 2. | Формула Эйлера |
| | § 3. | Триангулированный граф |
| | § 4. | Изображение ребер плоского графа прямолинейными отрезками |
| | § 5. | Эйлеровы графы |
| | § 6. | Лабиринты |
| | § 7. | Гамильтоновы циклы и пути в графах |
| Глава III. | Графы с цветными ребрами |
| | § 1. | Свойства полных графов с цветными ребрами |
| | § 2. | Графы помогают решать задачи |
| | § 3. | Задача о несцепленных треугольниках с одноцветными сторонами |
| Глава IV. | Ориентированные графы |
| | § 1. | Исходные понятия |
| | § 2. | Полный ориентированный граф |
| | | 1. | Круговые бескомпромиссные турниры |
| | | 2. | Парадоксы <голосования с предпочтением> |
| Глава V. | Отношения |
| | § 1. | Квадрат множества |
| | § 2. | Свойства отношений |
| | | 1. | Рефлексивность |
| | | 2. | Антирефлексивность |
| | | 3. | Симметричность |
| | | 4. | Антисимметричность |
| | | 5. | Транзитивность |
| | | 6. | Антитранзитивность |
| | | 7. | Полное отношение |
| | § 3. | Отношение эквивалентности |
| | § 4. | Отношение порядка |
| | § 5. | Определение графа |
| Глава VI. | Деревья в работе |
| | § 1. | Деревья и подсчет числа изомеров |
| | § 2. | Число деревьев с пронумерованными вершинами |
| | § 3. | Отыскание кратчайшего пути |
| | § 4. | Деревья в комбинаторике |
| | | 1. | Деревья и перестановки из п элементов |
| | | 2. | Маршруты по местности и число сочетаний Сmn |
| | | 3. | Разбиения и композиции натуральных чисел |
| | § 5. | Деревья, вероятность, генетика |
| | § 6. | Крестики и нолики |
| Глава VII. | Сетевое планирование и управление |
| | § 1. | Сетевой график |
| | § 2. | Построение сетевого графика |
| | § 3. | Критический путь |
| | § 4. | О резервах времени |
| | § 5. | Из истории систем сетевого планирования и управления |
| Глава VIII. | Графы и матрицы |
| | § 1. | Матрицы графа |
| | § 2. | Операции над матрицами |
| Что читать дальше |
| Ответы и указания |
Если вы любите решать задачи на смекалку, логические,
олимпиадного типа или головоломки, то, наверное, не раз
составляли таблицы, изображали объекты точками, соединяли их
отрезками или стрелками, подмечали закономерности у полученных
рисунков, выполняли над точками и отрезками операции, не похожие
на арифметические, алгебраические или на преобразования в
геометрии, то есть вам приходилось строить математический
аппарат специально, для решения задачи. А это означает, что вы
заново открывая" для себя начала теории графов.
Исторически сложилось так, что теория графов зародилась именно в
ходе решения головоломок двести с лишним лет назад. Очень долго
она находилась в стороне от главных направлений исследований
ученых, была в царстве математики на положении Золушки, чьи
дарования раскрылись в полной мере лишь тогда, когда она
оказалась в центре общего внимания.
Толчок к развитию теория графов получила на рубеже XIX и XX вв.,
когда резко возросло число работ в области топологии и
комбинаторики, с которыми ее связывают самые тесные узы родства.
Как отдельная математическая дисциплина теория графов была
впервые представлена в работе венгерского математика Кёнига в
30-е гг. XX в.
В последнее время графы и связанные с ними методы исследований
органически пронизывают на разных уровнях едва ля не всю
современную математику. Графы эффективно используются в теории
планирования и управления, теории расписаний, социологии,
математической лингвистике, экономике, биологии, медицине.
Широкое применение находят графы в таких областях прикладной
математики, как программирование, теория конечных автоматов,
электроника, в решении вероятностных и комбинаторных задач.
Теория графов быстро развивается, находит все новые приложения и
ждет молодых исследователей.
Конечно, в небольшой книге невозможно рассказать о всех
направлениях развития теории графов и разработанных приложениях.
Главная цель автора в другом -- помочь школьникам и учителям
овладеть основными понятиями теории графов, новыми для школы
методами решения задач, в популярной форме познакомить с
некоторыми ее приложениями. Материал книги Сорганизован так, что
знакомство с графами происходит в процессе решения самых
разнообразных задач, в формулировках условий которых не
упоминаются графы. Для решения их требуется "увидеть"
возможность перевести условие на язык графов, решить задачу
"внутри теории графов", интерпретировать полученное решение в
исходных терминах. Возможность представить граф с помощью
наглядных рисунков делает все это более доступным. Вначале
приводятся задачи, которые можно решать с помощью
неориентированных графов (с одноцветными вершинами и ребрами),
потом появляются задачи, для решения которых требуется ввести
цветные ребра, и наконец задачи, для решения которых полезны
ориентированные графы. Таким образом, расширение понятия
"граф" происходит как бы по необходимости, с целью решения
очередной задачи. При чтении книги обратите внимание на то, что
сначала граф появляется как рисунок из точек и отрезков,
соединяющих пары точек. Шаг за шагом выявляются закономерности
необычной "геометрии", в которой нет углов, нет расстояния
между точками в привычном понимании этого слова, равноправны
расположения точек на рисунке, безразлично, соединены ли две
точки отрезком прямой или отрезком кривой, и т. д. Постепенно
содержание понятия "граф" уточняется, а объем его расширяется.
Определение графа появляется лишь в пятой главе книги.
Если в начале книги рассматриваются приложения частного
характера, иллюстрирующие теорию графов и ее связь с жизнью, то
вторая половина книги посвящена прикладным разделам теории
графов, имеющим практическое значение в экономике и управлении.
Конечно, при чтении придется потрудиться, поработать с
карандашом и бумагой. Но ведь иначе и быть не может. Это
математическая книга, и она требует такой работы. Многое
сделано, чтобы облегчить чтение, -- материал в каждой главе
излагается последовательно от простого к более сложному, от
легкого к более трудному. После каждого нового материала
приведено большое число упражнений.
Для чтения книги не требуется каких-либо специальных
предварительных знаний. Большинство ее разделов можно
рекомендовать уже девятиклассникам; она содержит много
материала, интересного для обучающихся в X--XI классах.
Книга предназначена для индивидуального чтения любителям
математики, но может быть использована и как элективный учебный
курс по выбору обучающихся старших классов. Книга призвана
направить их познавательные интересы в сферу дискретной
математики, достаточно быстро развивающейся и находящей все
более широкое применение.
Для тех, кто пожелает более основательно познакомиться с теорией
графов и ее приложениями, в конце книги приведен список
литературы.
Главы VI, VII, VIII независимы друг от друга; поэтому их можно
читать в любом порядке.
Все задачи, рисунки, теоремы и упражнения имеют двойную
нумерацию: первое число обозначает номер главы, а второе -- их
порядковый номер в главе.
Автор выражает искреннюю признательность за полезные советы по
структуре и содержанию книги и постоянную поддержку во время
работы над ней В. Н. Березину -- моему мужу и другу по жизни, а
также другу нашей семьи, одному из первых читателей первого
издания нашей книги, тогда еще школьнику, а ныне доктору
физико-математических наук Б. И. Яцало, благодарность редакции
журнала "Квант", в свое время познакомившей широкую школьную
читательскую аудиторию с отдельными материалами книги.
Лариса Юрьевна БЕРЕЗИНА
Ведущий научный сотрудник лаборатории содержания и технологий общего
образования в системе начального и среднего профессионального образования
Центра профессионального образования Федерального института развития
образования (ФИРО), кандидат педагогических наук, доцент.
В 1964 г. закончила математический факультет МГПИ им. В. И. Ленина. Четыре
года работала учителем математики в старших классах московской
общеобразовательной школы N 52 с углубленным изучением математики;
восемнадцать лет -- в лаборатории математического образования НИИ содержания
и методов образования Российской академии образования; двадцать лет работает
в Институте развития профессионального образования (с 2006 г. -- Федеральный
институт развития образования). Опубликовала более 100 работ, в том числе:
"Графы и их применение" (1979), "Геометрия в 8 классе" (1985; в соавторстве),
"Сборник задач для факультативных и внеклассных занятий по математике"
(1985), "Сборник задач и упражнений по математике для средних профтехучилищ
транспортного профиля" (1985; в соавторстве), "Геометрия в 7-9 классах"
(1990; 2008). Автор статей по использованию графов в решении задач в журналах
"Математика в школе" и "Квант".
