Теория графов. Задача о нефтепроводе максимальной пропускной способности. 20
 Скачать 0.63 Mb.
|
  Содержание Введение………………………………………………………………………..……………………………………3 Выводы и рекомендации……………………………………………………………...………….24 2 2 Введение 3 1 Теоретическая часть 4 1.1 Основные понятия теории графов 4 1.2 Сетевые графики. Порядок и правила построения. 6 1.3 Нахождение максимального потока в сети 13 2 Практическая часть 20 2.1 Задача о нефтепроводе максимальной пропускной способности. 20 Выводы и рекомендации……………………………………………………………...………….24Библиографический список……………………………………………………………….….25 ВведениеСовременное общество отчасти можно рассматривать как систему сетей, предназначенных для транспортирования, передачи и распределения электроэнергии, товаров и информации. Для решения задач оптимального использования этих систем применяется сетевой анализ. В значительной степени он основан на теории графов. Сетевые модели широко применяются в исследовании операций и могут быть использованы на практике, например, при проектировании вычислительных комплексов, транспортных сетей, телетрансляционных сетей, систем космической связи. Ни один проект с использованием крупной сети со сложной топологией в настоящее время не обходится без исчерпывающего моделирования будущей сети. Программы, выполняющие эту задачу, достаточно сложны и дороги. Целью моделирования является определение оптимальной топологии, адекватный выбор сетевого оборудования, определение рабочих характеристик сети и возможных этапов будущего развития. Ведь сеть, слишком точно оптимизированная для решений задач текущего момента, может потребовать серьезных переделок в будущем. Так, в данной курсовой работе будут рассмотрены основные модели теории графов, и методы решения сетевых задач на примере задачи о нефтепроводе. Сетевой моделью (другие названия: сетевой график, сеть) называется экономико-компьютерная модель, отражающая комплекс работ (операций) и событий, связанных с реализацией некоторого проекта (научно-исследовательского, производственного и др.), в их логической и технологической последовательности и связи. Анализ сетевой модели, представленной в графической или табличной (матричной) форме, позволяет более четко выявить взаимосвязи этапов реализации проекта, а также определить наиболее оптимальный порядок выполнения этих этапов в целях, например, сокращения сроков выполнения всего комплекса работ. Таким образом, методы сетевого моделирования относятся к методам принятия оптимальных решений. 1Теоретическая часть1.1 Основные понятия теории графовГрафом называется набор точек, соединенных между собой ребрами (или дугами). Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, называются смежными (или соседними). Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой). Помимо этого, в теории графов рассматриваются также мультиграфы – это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами. Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней. Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер). Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней. Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур. Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром). Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис. 1 изображен связный граф. Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком.  Рисунок 1 – Связный граф Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице. Лемма 1. Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур. Доказательство. Действительно, выйдя из некоторой вершины и войдя в другую, всегда можно выйти из нее по другому ребру , так как степень вершины больше или равна двум. Выйти из вершины по новому ребру невозможно только в том случае, если эта вершина уже встречалась, а это означает, что можно выделить контур из вершин этого графа. |