ГРАФОВ ТЕОРИЯ
раздел конечной
математики, особенностью к-рого является геом. подход к изучению объектов.
Осн. понятие теории - граф. Граф задаётся
множеством вершин (точек) и множеством рёбер (связей), соединяющих
нек-рые (а может быть, и все) пары вершин. При этом пары вершин
могут соединяться неск. рёбрами. Примеры графов: множество городов (вершины
графа), напр. Моск. области, и соединяющие их дороги (рёбра графа);
элементы электрич. схемы и провода, соединяющие их. На рис. 1 изображён
граф, вершинами к-рого являются станции гор. метрополитена, а рёбрами -
пути, соединяющие соседние станции (одна из задач: указать к.-л. маршрут
от станции А к станции В). Граф наз. ориентированным, если
на рёбрах задана ориентация, т. е. указан порядок прохождения вершин. Наконец,
в Г. т. изучаются графы, у к-рых рёбрам приписаны к.-л. веса (или символы),
а также графы, в к-рых выделены особые вершины, наз. полюсами. Примеры:
диаграмма состояний автомата, сеть ж.-д. путей с указанием на дугах их
длин или пропускных способностей. На рис. 2 приведена схема автомоб. дорог
между Москвой и Таллином; надо, напр., выбрать маршрут минимальной общей
длины пути из Москвы в Таллин (эти два города - полюсы сети); сравнение
двух маршрутов Москва - Ленинград - Таллин и Москва - Витебск - Рига -
Таллин показывает, что путь через Ленинград короче (1049 км).
Одной из первых работ по Г. т. можно
считать работу Л. Эйлера (1736), относящуюся к решению головоломок и ма-тематич.
развлекательных задач. Первые глубокие результаты были получены в 1-й пол.
20 в. в связи с решением задач построения электрич. цепей и подсчёта химич.
веществ с различными типами мол. соединений. Однако широкое развитие Г.
т. получила лишь с 50-х гг. в связи со становлением кибернетики и развитием
вычислит. техники, когда Г. т. существенно обогатилась и новым материалом,
и новыми подходами и когда началось систематич. изучение графов с разных
точек зрения (структурной, информационной и т. д.). Именно в это время
формулировались проблематика и методы Г. т. Г. т. находит применение в
теории программирования и при построении вычислит. машин, в изучении физических,
химических и технологических процессов, в решении задач планирования, в
лингвистических и социологических исследованиях и т. д. Г. т. имеет тесные
связи как с классическими, так и с новыми разделами математики; это - топология,
алгебра, комбинаторный анализ, теория чисел, теория минимизации булевских
функций. Г. т. включает большое число разнообразных задач. Одни из них
группируются в отд. направления, другие стоят более изолированно. Среди
сложившихся разделов Г. т. следует отметить задачи, относящиеся к анализу
графов, определению различных характеристик их строения, напр. выяснение
связности графа: можно ли из любой вершины попасть в любую; подсчёт графов
или их частей, обладающих заданными свойствами, напр. подсчёт количества
деревьев с заданным числом рёбер (дерево - неориентированный граф без циклов);
решение трансп. задач, связанных с перевозками грузов по сети. Решён ряд
задач по синтезу графов с заданными свойствами, напр. построение графа
с заданными степенями вершин (степень вершины - число выходящих из неё
рёбер).
Рис. 1.
Рис. 2.
Имеет прикладное и теоретич.
значение задача о выяснении возможности расположения графа на плоскости
без самопересечений его рёбер (т. е. является ли данный граф плоским),
задача о разбиении графа на миним. число плоских графов. Для нек-рых задач
Г. т. (выше были приведены далеко не все) были разработаны методы
их решения. Среди них: метод Пойя перечисления и подсчёта графов с заданными
свойствами, теорема и алгоритм Форда - Фалкерсона для решения трансп. задачи,
"венгерский" алгоритм решения задачи о назначениях и т. д. Почти все задачи
теории конечных графов (практически интересны именно графы с конечным числом
вершин) могут быть решены путём перебора большого числа вариантов
(т. н. полный перебор), поэтому для них требуется построение эффективных
алгоритмов и использование быстродействующих вычислит. машин. Такими задачами
являются: задача о раскраске вершин графа, задача об определении идентичности
двух графов, коммивояжёра задача. Есть задачи, требующие принципиального
ответа, напр. задача о раскраске плоских графов, задача о восстановлении
графа по его подграфам.
Лит.: Берж К., Теория графов
и её применения, пер. с франц., М., 1962; Оре О., Графы и их применение,
пер. с англ., М., 1.965; Зыков А. А., Теория конечных графов. I, Новосибирск,
1969.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я