|
|
Большая Советская Энциклопедия (цитаты)
|
|
|
|
|
Графов теория | Графов теория (далее Г) раздел конечной математики, особенностью которого является геометрический подход к изучению объектов. Основное понятие теории — граф. Граф задается множеством вершин (точек) и множеством ребер (связей), соединяющих некоторые (а может быть, и все) пары вершин. При этом пары вершин могут соединяться несколькими ребрами. Примеры графов: множество городов (вершины графа), например Московской области, и соединяющие их дороги (ребра графа); элементы электрической схемы и провода, соединяющие их. На рис. 1 изображен граф, вершинами которого являются станции городского метрополитена, а ребрами — пути, соединяющие соседние станции (одна из задач: указать какой-либо маршрут от станции А к станции В). Граф называется ориентированным, если на ребрах задана ориентация, т. е. указан порядок прохождения вершин. Наконец, в Г изучаются графы, у которых ребрам приписаны какие-либо веса (или символы), а также графы, в которых выделены особые вершины, называются полюсами. Примеры: диаграмма состояний автомата, сеть ж.-д. путей с указанием на дугах их длин или пропускных способностей. На рис. 2 приведена схема автомобильных дорог между Москвой и надо, например, выбрать маршрут минимальной общей длины пути из Москвы в (эти два города — полюсы сети); сравнение двух маршрутов Москва — Ленинград — и Москва — Витебск — Рига — показывает, что путь через Ленинград короче (1049 км).
Одной из первых работ по Г можно считать работу Л. Эйлера (1736), относящуюся к решению головоломок и математических развлекательных задач. Первые глубокие результаты были получены в 1-й половине 20 в. в связи с решением задач построения электрических цепей и подсчета веществ с различными типами молекулярных соединений. Однако широкое развитие Г получила лишь с 50-х гг. в связи со становлением кибернетики и развитием вычислительной техники, когда Г существенно обогатилась и новым материалом, и новыми подходами и когда началось систематическое изучение графов с разных точек зрения (структурной, информационной и т. д.). Именно в это время формулировались проблематика и методы Г Г находит применение в теории программирования и при построении вычислительных машин, в изучении физических, и технологических процессов, в решении задач планирования, в лингвистических и социологических исследованиях и т. д. Г имеет тесные связи как с классическими, так и с новыми разделами математики; это — топология, алгебра, комбинаторный анализ, теория чисел, теория минимизации булевских функций. Г включает большое число разнообразных задач. Одни из них группируются в отдельные направления, другие стоят более изолированно. Среди сложившихся разделов Г следует отметить задачи, относящиеся к анализу графов, определению различных характеристик их строения, например выяснение связности графа: можно ли из любой вершины попасть в любую; подсчет графов или их частей, обладающих заданными свойствами, например подсчет количества деревьев с заданным числом ребер (дерево — неориентированный граф без циклов); решение транспортных задач, связанных с перевозками грузов по сети. Решен ряд задач по синтезу графов с заданными свойствами, например построение графа с заданными степенями вершин (степень вершины — число выходящих из нее ребер). Имеет прикладное и теоретическое значение задача о выяснении возможности расположения графа на плоскости без самопересечений его ребер (т. е. является ли данный граф плоским), задача о разбиении графа на минимальное число плоских графов. Для некоторых задач Г (выше были приведены далеко не все) были разработаны методы их решения. Среди них: метод Пойя перечисления и подсчета графов с заданными свойствами, теорема и алгоритм Форда — Фалкерсона для решения транспортной задачи, "венгерский" алгоритм решения задачи о назначениях и т. д. Почти все задачи теории конечных графов (практически интересны именно графы с конечным числом вершин) могут быть решены путем перебора большого числа вариантов (т. н. полный перебор), поэтому для них требуется построение эффективных алгоритмов и использование быстродействующих вычислительных машин. Такими задачами являются: задача о раскраске вершин графа, задача об определении идентичности двух графов, коммивояжера задача. Есть задачи, требующие принципиального ответа, например задача о раскраске плоских графов, задача о восстановлении графа по его подграфам.
Лит.: Берж К., Теория графов и ее применения, пер. с франц., М., 1962; Оре О., Графы и их применение, пер. с англ., М., 1965; Зыков А. А., Теория конечных графов. , Новосибирск, 1969.
|
Для поиска, наберите искомое слово (или его часть) в поле поиска
|
|
 |
 |
 |
|
|
|
Новости 22.12.2024 15:31:35
|
|
|
|
|
|
|
|
|
|
|
