Алгоритмы на графах и их приложения. Дорофеева В.И. - 5 стр.

    1 Некоторые сведения из теории графов, необходимые для
решения задач оптимизации
     Задачи дискретной математики, конкретные типы которых будут рас-
смотрены далее, часто приводят к проблеме оптимизации. Пусть дан критерий,
позволяющий выделить решения с некоторыми заданными свойствами. Требу-
ется найти множество таких решений, называемых «оптимальными». В боль-
шинстве задач этот критерий имеет числовую природу, а множество всех задач
разбивается на вполне упорядоченные классы. Как правило, рассматривают за-
дачи на максимум и минимум.
     В основе почти всех комбинаторных методов оптимизации лежит сле-
дующий принцип. Множество всех решений разбивается некоторым образом на
два подмножества: подмножество, содержащее все оптимальные решения, и
подмножество, не содержащее их. Если первое из подмножеств не есть опти-
мальное, то стремятся получать подобные разбиения, в которых подмножества,
содержащие все оптимальные решения, имеют все меньшую мощность. Дейст-
вуют так до тех пор, пока не приходят к оптимальному подмножеству. На этом
же принципе основаны также некоторые способы, позволяющие получать, по
крайней мере, одно оптимальное решение.
     Одними из наиболее удобных способов решения подобных задач стали
способы, в основе которых лежит интерпретация задачи в терминах теории
графов. Введем некоторые известные понятия из теории графов, которые будут
использованы в дальнейшем.
     Представим себе на плоскости некоторое конечное множество точек N и
конечный набор A линий, соединяющих некоторые пары точек из N. Указанной
геометрической конфигурацией описывается, например, схема автомобильных
дорог, связывающих города некоторой области.
     Итак, ориентированный граф G=(N,A) (далее граф) состоит из:
     1. Множества узлов (или вершин) N={ni, n2, …, np}.
     2. Множества A упорядоченных пар (ni, nj) элементов N, элементы A на-
зываются дугами.
                                        5