Графов теория

раздел конечной математики (См. Конечная математика), особенностью которого является геометрический подход к изучению объектов. Основное понятие теории — граф. Граф задаётся множеством вершин (точек) и множеством рёбер (связей), соединяющих некоторые (а может быть, и все) пары вершин. При этом пары вершин могут соединяться несколькими ребрами. Примеры графов. Множество городов (вершины графа), например Московской области, и соединяющие их дороги (ребра графа). Элементы электрической схемы и провода, соединяющие их. На рис. 1 изображен граф, вершинами которого являются станции городского метрополитена, а ребрами — пути, соединяющие соседние станции (одна из задач. Указать какой-либо маршрут от станции А к станции В).

Граф называется ориентированным, если на ребрах задана ориентация, т. Е. Указан порядок прохождения вершин. Наконец, в Г. Т. Изучаются графы, у которых ребрам приписаны какие-либо веса (или символы), а также графы, в которых выделены особые вершины, называются полюсами. Примеры. Диаграмма состояний автомата, сеть ж.-д. Путей с указанием на дугах их длин или пропускных способностей. На рис. 2 приведена схема автомобильных дорог между Москвой и Таллином. Надо, например, выбрать маршрут минимальной общей длины пути из Москвы в Таллин (эти два города — полюсы сети). Сравнение двух маршрутов Москва — Ленинград — Таллин и Москва — Витебск — Рига — Таллин показывает, что путь через Ленинград короче (1049 км). Одной из первых работ по Г.

Т. Можно считать работу Л. Эйлера (1736), относящуюся к решению головоломок и математических развлекательных задач. Первые глубокие результаты были получены в 1-й половине 20 в. В связи с решением задач построения электрических цепей и подсчёта химических веществ с различными типами молекулярных соединений. Однако широкое развитие Г. Т. Получила лишь с 50-х гг. В связи со становлением кибернетики и развитием вычислительной техники, когда Г. Т. Существенно обогатилась и новым материалом, и новыми подходами и когда началось систематическое изучение графов с разных точек зрения (структурной, информационной и т. Д.). Именно в это время формулировались проблематика и методы Г. Т. Г. Т. Находит применение в теории программирования и при построении вычислительных машин, в изучении физических, химических и технологических процессов, в решении задач планирования, в лингвистических и социологических исследованиях и т.

Д. Г. Т. Имеет тесные связи как с классическими, так и с новыми разделами математики. Это — топология, алгебра, комбинаторный анализ, теория чисел, теория минимизации булевских функций. Г. Т. Включает большое число разнообразных задач. Одни из них группируются в отдельные направления, другие стоят более изолированно. Среди сложившихся разделов Г. Т. Следует отметить задачи, относящиеся к анализу графов, определению различных характеристик их строения, например выяснение связности графа. Можно ли из любой вершины попасть в любую. Подсчёт графов или их частей, обладающих заданными свойствами, например подсчёт количества деревьев с заданным числом рёбер (дерево — неориентированный граф без циклов). Решение транспортных задач, связанных с перевозками грузов по сети.

Решен ряд задач по синтезу графов с заданными свойствами, например построение графа с заданными степенями вершин (степень вершины — число выходящих из неё рёбер). Имеет прикладное и теоретическое значение задача о выяснении возможности расположения графа на плоскости без самопересечений его рёбер (т. Е. Является ли данный граф плоским), задача о разбиении графа на минимальное число плоских графов. Для некоторых задач Г. Т. (выше были приведены далеко не все) были разработаны методы их решения. Среди них. Метод Пойя перечисления и подсчёта графов с заданными свойствами, теорема и алгоритм Форда — Фалкерсона для решения транспортной задачи, «венгерский» алгоритм решения задачи о назначениях и т. Д. Почти все задачи теории конечных графов (практически интересны именно графы с конечным числом вершин) могут быть решены путём перебора большого числа вариантов (т.

Н. Полный перебор), поэтому для них требуется построение эффективных алгоритмов и использование быстродействующих вычислительных машин. Такими задачами являются. Задача о раскраске вершин графа, задача об определении идентичности двух графов, Коммивояжёра задача. Есть задачи, требующие принципиального ответа, например задача о раскраске плоских графов, задача о восстановлении графа по его подграфам. Лит. Берж К., Теория графов и её применения, пер. С франц., М., 1962. Оре О., Графы и их применение, пер. С англ., М., 1965. Зыков А. А., Теория конечных графов. I, Новосибирск, 1969. Рис. 1 к ст. Графов теория. Рис. 2 к ст. Графов теория..