Поиск максимальных потоков в сетях
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
?у ними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).
5. Модели коллективов и групп, используемые в социологии, основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) в виде ребер или дуг. В рамках подобного описания решаются задачи исследования структуры социальных групп, их сравнения, определения агрегированных показателей, отражающих степень напряженности, согласованности взаимодействия, и др.
6. Модели организационных структур, в которых вершинами являются элементы организационной системы, а ребрами или дугами связи (информационные, управляющие, технологические и др.) между ними.
Изучение этих и других подобных им практических задач приводит к теории потоков в сетях. В данной работе рассматривается только одна (но наиболее существенная) задача этой теории, а именно задача нахождения максимального потока.
1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ТЕОРИИ
ГРАФОВ
- Понятие графа
Пусть V непустое множество, V (2) множество всех его двухэлементных подмножеств. Пара (V, E), где Е произвольное подмножество множества V (2), называется графом (неориентированным графом).
Элементы множества V называются вершинами графа, а элементы множества Е рёбрами. Множество вершин и рёбер графа G обозначаются символами VG и EG соответственно. Число |VG| вершин графа G называются его порядком и обозначаются через |G|. Если |G| = n, |EG| = m, то G называют (n,m)-графом.
Две вершины u и v графа смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если e = {u, v} ребро, то вершины u и v называют его концами. Такое ребро обозначают uv.
Два ребра называются смежными, если они имеют общий конец.
Вершина v и ребро e называются инцидентными, если v является концом ребра e (т.е. e = uv), и не инцидентными в противном случае.
Множество всех вершин графа G, смежных с некоторой вершиной v, называется окружением вершины v и обозначается через N(v).
Упорядоченная пара вершин называется ориентированным ребром.
Ориентированный граф (или орграф) это пара (V, A), где V множество вершин, А множество ориентированных рёбер, которые называются дугами, АV2. Если а = (v1, v2) дуга, то вершины v1 и v2 называются её началом и концом соответственно. Если граф ориентированный, его обозначают .
Каждому неориентированному графу можно поставить в соответствие ориентированный граф с тем же самым множеством вершин, в которых каждое ребро заменено двумя ориентированными рёбрами, которые инцидентны тем самым вершинам и имеют обратные направления. Такое соответствие будем называть каноничным.
Если у ребра начало и конец совпадают, то такое ребро называют петлёй.
1.2. Графическое представление графов
Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а соединяющие пары точек линии (прямолинейные либо криволинейные) рёбрам (табл.1).
Таблица 1
Элементы графовГеометрические элементы1. v V вершина1. точка в пространстве.2. {u,v} ребро неориентированного графа2. u?v отрезок.3. (v1,v2) дуги в ориентированном графе3. v1>v2 направленный отрезок.4. {v,v} петля4. замкнутый отрезок.
1.3. Виды графов
Множество рёбер Е может быть пустым (рис. 1.1). Такой граф называется нуль-графом и обозначается .
рис. 1.1. Нуль-граф
Если же множество вершин V пустое, то пустым является также множество Е. Такой граф называется пустым. Линии, которые изображают рёбра графа, могут пересекаться, но точки пересечения не являются вершинами (рис. 1.2, а); разные рёбра могут быть инцидентными одной и той же паре вершин (рис. 1.2, б), такие рёбра называются кратными. Этот случай соответствует наличию нескольких одинаковых пар (vi,vj) E(G). Граф, который содержит кратные рёбра, называется мультиграфом. Ребро может соединять некоторую вершину саму с собою (рис. 1.2, в), такое ребро называется петлёй. Этот случай соответствует наличию в множестве Е пар вида (v,v). Граф с петлями и кратными рёбрами называется псевдографом. Конечный неориентированный граф без петель и кратных рёбер называется обычным.
а б в
Рисунок 1.2. Графы: а) обычный, б) с кратными рёбрами, в) с петлёй
1.4. Элементы графов
Путь это последовательность рёбер e1, e2, …, em, такая, что рёбра ei, ei+1 имеют общую вершину. Число рёбер называется длинной пути. Если ни одна из вершин не появляется больше одного раза, то путь называется простым. Понятно, что в простом пути ни одно ребро не используется дважды.
Путь называется циклом, если его начальная вершина совпадает с конечной; простым циклом, если это не выполняется для других вершин.
Чередующаяся последовательность v1, e1, v2, e2, …, el,vl+1 вершин и рёбер графа, такая, что ei = vivi+1 (i = 1, l), называется маршрутом. Если v1 = vl+1, то маршрут замкнутый, инач?/p>