Введение

1.  Графы, орграфы, деревья

2.  Операции над графами

3.  Хранение графов в ЭВМ

4.  Задача о максимальном потоке

5.  Построение максимального потока. Примеры разбираемых задач

Литература

Введение

В коммерческой деятельности большинство возникающих задач удобно представлять для восприятия и анализа в виде сетей, которые позволяют ответить на два главных вопроса: до какого места необходимо дойти (цель) и какой путь следует избрать (как). Коммерческую деятельность можно рассматривать как совокупность задач, предназначенных для передвижения, складирования и распределения товаров, денег, документов, информации о поставках и покупателях воды, нефти, газа, электроэнергии, теле- и радиосистем. Наглядность и логическая обоснованность методов сетевого анализа позволяет выбрать довольно естественный подход к решению задач коммерческой деятельности. Сетевые модели для людей, не занимающихся научной работой, являются более понятными, чем другие модели, поскольку для них все же лучше один раз увидеть, чем сто раз услышать. В значительной степени методы сетевого анализа основаны на теории графов – области математики, началом развития которой явилась задача о кенигсбергских мостах, сформулированная швейцарским ученым Л. Эйлером в 1736 г. Через реку Прегель, на которой стоял город Кенигсберг, построено семь мостов (рис. 1), которые связывали с берегами и друг с другом два острова. Задача заключалась в том, чтобы пройти по всем мостам только один раз и вернуться обратно к началу маршрута. Эйлер доказал неразрешимость этой задачи.

Позже Д.К. Максвелл и Г.Р. Кирхгоф на основе исследования электрических цепей сформулировали некоторые принципы сетевого анализа. Были разработаны методы расчета наибольшей пропускной способности телефонных линий. В 40-х годах в результате развития теории исследования операций был разработан ряд математических методов, необходимых для анализа больших систем. В 50–60-х годах проводились работы по построению новых сетевых моделей и разработке алгоритмов их решения на основе элементов теории графов.

Графы, орграфы, деревья

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

Основы теории графов разработал Л. Эйлер, решавший задачу о разработке замкнутого маршрута движения по мостам в г. Кенигсберге. При решении задачи он обозначил каждую часть суши точкой, а каждый мост – линией, их соединяющей. В результате был получен граф (рис. 1).

Эйлер доказал, что такая задача решения не имеет.

Эйлер Леонард (1707–1783) швейцарский математик, механик, физик, астроном. Автор более 800 работ по различным разделам математики и другим наукам.

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

Пусть на плоскости задано некоторое множество вершин X и множество U соединяющих их дуг. Графом называют бинарное отношение множества X и множеств U: G = = (X; U), или, иначе ƒ: X → К Здесь ƒ – отображение инциденций.

Граф называется ориентированным, если указано направление дуг и неориентированным, если такое направление не указано. ............