ВВЕДЕНИЕ. Теория графов представляет собой раздел математики, имеющий широкое практическое применение

Теория графов представляет собой раздел математики, имеющий широкое практическое применение. В её терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, электрических цепей, блок-схем программ, в экономике, статистике, химии, биологии и в других областях. Теория графов становится одной из существенных частей математического аппарата кибернетики, языком дискретной математики.

В отличие от других научных дисциплин, теория графов имеет вполне определенную дату рождения. Первая работа по теории графов, написанная швейцарским математиком Леонардом Эйлером (1707-1783), была опубликована в 1736 году в Трудах Академии наук в Санкт-Петербурге. Исследование Эйлера было проведено в связи с популярной в то время задачей о кенигсбергских мостах. Эта задача имеет следующую формулировку:

Задача 1. Город Кенигсберг, располагавшийся в восточной Пруссии, был построен в месте слияния двух рек на их берегах и на двух островах. В городе было семь мостов, которые соединяли острова между собой и с береговыми частями города (рис.В.1). Необходимо ответить на вопрос: мог ли любой житель Кенигсберга, выйдя из дома, пройти по всем семи мостам города в точности по одному разу и вернуться домой?

Ответ на вопрос, поставленный в данной задаче, должен быть отрицательным. Эйлер дал этот ответ и нашел критерий существования маршрута, удовлетворяющего требованиям задачи.

Однако результат, полученный Эйлером, более ста лет оставался единственным результатом теории графов.

Развитие теории графов в конце XIX и начале XX вв. было связано с распространением представлений о молекулярном строении вещества и становлением теории электрических цепей. К 50-м годам нашего века в теории графов сложились два различных направления: алгебраическое и оптимизационное.

Например, поиск ответа на поставленный в задаче 1 вопрос относится к алгебраическому направлению теории графов. Изменим задачу 1.

Задача 2. Отличие задачи 2 от задачи 1 состоит в том, что требуется найти маршрут, по которому житель, выйдя из дома, пройдет по каждому мосту хотя бы один раз и вернется домой, причем длина маршрута должна быть минимальной.

Задача поиска такого маршрута относится к оптимизационному направлению теории графов. Вопросам решения задачи 1 и задачи 2 будет уделено место в гл.7.

Оптимизационное направление получило широкое развитие благодаря появлению ЭВМ, так как для эффективного использования ЭВМ при решении прикладных задач с использованием теории графов необходимы эффективные алгоритмы решения графовых задач.

Под эффективным алгоритмом понимают такой алгоритм, сложность которого (число шагов или время работы) выражается полиномиальной функцией от размерности (некоторого параметра, характеризующего длину записи условий задачи).

Для тех, кто считает, что неэффективность алгоритма может быть компенсирована увеличением быстродействия ЭВМ, приведены таблицы В.1 и В.2 [1].

Как следует из таблицы В.1, например, при сложности 3 ⁿ даже увеличение быстродействия ЭВМ в 1000 раз по сравнению с имеющимися в настоящее время позволяет увеличить размерность задачи, которая доступна для расчета лишь на 6 или 7 единиц. А из таблицы В.2 видно, что при той же сложности задача размерности 33 единицы будет решаться около трех веков. Вот почему необходимо искать пути уменьшения сложности. То есть применять эффективные алгоритмы для решения задачи. Однако эффективные алгоритмы существуют не для всех задач. Причем среди задач, для которых пока нет эффективных алгоритмов, есть задачи, составляющие особый класс. Если будет найден эффективный алгоритм для решения хотя бы одной задачи из этого класса, то это будет означать, что эффективный алгоритм найден для всех задач этого класса.

Задачи, для которых не найден эффективный алгоритм решения, можно решать, используя эвристические или приближенные алгоритмы, которые дают результат за приемлемое время, но этот результат не является точным, а имеет какую-то погрешность.

Эвристическими называют алгоритмы, основанные на неформальных соображениях. Корректность таких алгоритмов теоретически не обоснована.

Рассмотрению некоторых существующих в настоящее время эффективных графовых алгоритмов посвящено данное пособие.

Таблица В.1. Влияние технического совершенствования ЭВМ на полиномиальные и экспоненциальные алгоритмы

Слож-ность	Размеры наибольшей задачи, разрешимой за 1 час.
		На современных ЭВМ	На ЭВМ в 100 раз более быстрых	На ЭВМ в 1000 раз более быстрых
	N	N 1	100 N 1	1000 N 1
	n 2	N 2	10 N 2	31.6 N 2
	n 3	N 3	4.64 N 3	10 N 3
	n 5	N 4	2.5 N 4	3.98 N 4
	2 n	N 5	6.64+ N 5	9.97+ N 5
	3 n	N 6	4.19+ N 6	6.29+ N 6

Таблица В.2. Максимальная размерность задач, разрешимых за данное время