Содержание:
Введение. 2
1. Основные понятия теории графов. 3
2. Матричные способы задания графов. 4
3. Упорядочение элементов орграфа. 6
4. Постановка задачи о максимальном потоке. Основныеопределения. 8
5. Разрез на сети. 11
6. Алгоритм решения задачи о максимальном потоке. 13
Заключение. 20
Список использованной литературы… 21
Введение
Впоследнее время в различных областях знаний широко применяется теория графов. Спомощью теории графов хорошо описываются задачи экономической ипланово-производственной практики, как, например, календарное и сетевоепланирование и управление, автоматизация управления производством,рационализация схем перевозок и грузопотоков, оптимальное размещениепроизводства т.п.
1. Основные понятия теории графов
Основным объектом этойтеории является граф. Наглядно граф можно представить как некоторое множествоточек плоскости или пространства и множество отрезков кривых или прямых линий,соединяющих все или некоторые из этих точек. Формально граф Gопределяется заданием двух множеств Xи U и обозначается G=(XU).Элементы xB1B,xB2B,…, xBnB множества Xназываются вершинами и изображаются точками. Элементами uB1B,uB2B,…, uBmмножестваU являются пары связанных междусобой элементов множества Xи изображаются отрезками. Взаимное расположение, форма и длины отрезковзначения не имеют. Если в паре вершин xBiBи BBxBjBуказано направлениесвязи, то есть указано, какая вершина является первой, то отрезок UB1Bназываетсядугой, а если ориентация не указана, — ребром.
Еслив графе G все элементы множестваU изображаются дугами, то графназывается ориентированным (орграф), если ребрами, — неориентированным.
Напрактике используются графы, в которых множества Xи U состоят из конечного числаэлементов, то есть конечные графы. На рисунке располагать вершины графа можнопроизвольно. Также произвольно выбирается и форма соединяющих их линий. Поэтомуодин и тот же граф (граф с одной и той же информацией) может быть представлен вразличных видах. Такие графы называются изоморфными.
Смежныминазывают вершины графа, если они различны и существует дуга (ребро), котораясоединяет эти вершины. Если две дуги (ребра) имеют общую концевую вершину, тотакие дуги (ребра) смежные.
Последовательностьдуг, в которой конец каждой предыдущей дуги совпадает с началом следующей,называется путем в орграфе. Путь, проходящий через все вершины и при этомтолько один раз, называется гамильтоновым. Путь, включающий все дуги графа, ипри этом только по одному разу, называется эйлеровым. Полным путем называютлюбую непрерывную последовательность вершин и дуг, идущих от начальной вершинык конечной. Конечный путь, у которого начальная вершина совпадает с конечной,называется контуром.
Графназывается связным, если для любых двух его вершин существует путь, ихсоединяющий; в противном случае граф называется несвязным.
Вэкономике чаще всего используются два вида графов: дерево и сеть.
Деревопредставляет собой связный граф без циклов, имеющий исходную вершину (корень) икрайние вершины; пути от исходной вершины к крайним вершинам называютсяветвями.
Еслиграф, вообще говоря, не связный, не содержит циклов, то каждая связная егочасть будет деревом. Такой граф называется лесом.
Вприложении теории графов к практическим задачам дугам (ребрам) графасопоставляют какие-то числовые характеристики. Например, пропускная способностьтранспортной магистрали, запас какого-либо ресурса, продолжительностьвыполнения какой-либо работы и т.д. Таким образом, дугам графа приписаны определенныевеса и граф G называется взвешенным.2. Матричные способы заданияграфов
Графможет быть представлен как в виде рисунка, так и в виде матрицы. Это бываетнеобходимо при большом числе вершин и дуг (ребер), когда рисунок теряет своюнаглядность. Матричное представление графов используется при исследовании егона ЭВМ.
Пусть имеется граф G,не содержащий петель, имеющий nвершин и m дуг (ребер). Графу Gможно сопоставить матрицу инциденций графа G.Строки m этой матрицы соответствуютвершинам, столбцы n – дугам(ребрам) графа. Если граф ориентированный, то элементы aBijBматрицы инциденцийравны: (-1), если дуга uисходит из i-й вершины; (+1), еслидуга заходит в i-ю вершину. Еслиграф неориентированный, то элементами матрицы будут 1 и 0. На рис. 1.2 показаныорграф и его матрица инциденций, на рис. 1.3. — неориентированный граф иматрица инциденций./>
uB1B
uB2B
uB3B
uB4B
uB5B
uB6B
uB7B
xB1B -1 -1 -1
xB2B 1 -1
xB3B 1 1 -1
xB4B 1 1
xB5BBB -1 1 1 />
Рис.1.2/>
uB1B
uB2B
uB3B
uB4B
uB5B
uB6B
uB7B
xB1B 1 1 1
xB2B 1 1
xB3B 1 1 1
xB4B 1 1
xB5B 1 1 1
/>
Рис.1.3
Для ориентированных инеориентированных графов можно сформировать матрицу смежности вершин. Пустьорграф G содержит nвершин. Его матрица смежности представляет собой квадратную матрицу n-гопорядка. Строки и столбцы этой матрицы соответствуют вершинам орграфа G.Элементы uBijBесть число дуг,выходящих из i-й вершины и входящий вj-ю. В орграфе, не содержащемпараллельных дуг, элементами матрицы будут 1 и 0. На рис. 1.4. представленорграф и его матрица смежности вершин. Как видно из рис. 1.5, унеориентированного графа матрица смежности вершин будет симметрической. Поматрице смежности вершин определяется степень вершины, т.е. число дуг,пересекающихся в этой вершине. Число входящих в i-ювершину дуг равно сумме элементов i-го столбца; число дуг, исходящих из данной вершины, равно сумме элементов i-йстроки.