Файл: Задача о кратчайшем пути замена оборудования, составление расписания движения транспортных средств, размещение пунктов скорой помощи, размещение телефонных станций.pdf
Добавлен: 07.11.2023
Просмотров: 30
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Тема. ТИПОВЫЕ ЗАДАЧИ ТЕОРИИ ГРАФОВ Основными типовыми задачами, решение которых базируется на теории графов, являются
1. Задача о кратчайшем пути замена оборудования, составление расписания движения транспортных средств, размещение пунктов скорой помощи, размещение телефонных станций.
2. Связность графов и сетей проектирование кратчайшей коммуникационной сети, синтез структурно-надежной сети циркуляционной связи, анализ надежности стохастических сетей связи.
3. Раскраска в графах распределение памяти в компьютере, проектирование сетей телевизионного вещания.
4. Задача о максимальном потоке анализ пропускной способности коммуникационной сети, организация движения в динамической сети, оптимальный подбор интенсивностей выполнения работ, задача о распределении работ.
5. Задача об упаковках и покрытиях оптимизация структуры ПЗУ постоянного запоминающего устройства, размещение диспетчерских пунктов городской транспортной сети.
6. Изоморфизм графов и сетей структурный синтез линейных избирательных цепей, автоматизация контроля при проектировании БИС больших интегральных схем.
Рассмотрим методы решения этих задач более подробно.
8.1. Построение остова минимального веса алгоритмы Прима и Краскала Одной из самых распространенных задач является задача построения оптимального каркаса графа (остовного дерева минимальной длины. Для решения задачи об оптимальном каркасе известно много алгоритмов алгоритм поискав ширину, алгоритм поискав глубину (которые мы уже рассматривали, а также жадные алгоритмы Прима и Краскала. Жадность алгоритма состоит в том, что на каждом шаге из всех подходящих ребер выбирается ребро наименьшего веса. У этих алгоритмов общий подход алгоритм добавляет некоторые ребра графа по одному так, что в любой момент выбранные ребра составляют часть некоторого минимального остовного дерева, то есть всегда можно уже выбранные ребра завершить до минимального остовного дерева. Алгоритм продолжается пока не будет выбрано n−1 ребро, образующее дерево (при этом нужно следить, чтобы выбранные ребра в каждый момент не образовывали циклов. Но принцип выбора очередного ребра в каждом алгоритме отличается. Алгоритм Краскала Весь единый список рёбер упорядочивается по неубыванию весов рёбер. Текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция из всех рёбер, добавление которых к уже
1. Задача о кратчайшем пути замена оборудования, составление расписания движения транспортных средств, размещение пунктов скорой помощи, размещение телефонных станций.
2. Связность графов и сетей проектирование кратчайшей коммуникационной сети, синтез структурно-надежной сети циркуляционной связи, анализ надежности стохастических сетей связи.
3. Раскраска в графах распределение памяти в компьютере, проектирование сетей телевизионного вещания.
4. Задача о максимальном потоке анализ пропускной способности коммуникационной сети, организация движения в динамической сети, оптимальный подбор интенсивностей выполнения работ, задача о распределении работ.
5. Задача об упаковках и покрытиях оптимизация структуры ПЗУ постоянного запоминающего устройства, размещение диспетчерских пунктов городской транспортной сети.
6. Изоморфизм графов и сетей структурный синтез линейных избирательных цепей, автоматизация контроля при проектировании БИС больших интегральных схем.
Рассмотрим методы решения этих задач более подробно.
8.1. Построение остова минимального веса алгоритмы Прима и Краскала Одной из самых распространенных задач является задача построения оптимального каркаса графа (остовного дерева минимальной длины. Для решения задачи об оптимальном каркасе известно много алгоритмов алгоритм поискав ширину, алгоритм поискав глубину (которые мы уже рассматривали, а также жадные алгоритмы Прима и Краскала. Жадность алгоритма состоит в том, что на каждом шаге из всех подходящих ребер выбирается ребро наименьшего веса. У этих алгоритмов общий подход алгоритм добавляет некоторые ребра графа по одному так, что в любой момент выбранные ребра составляют часть некоторого минимального остовного дерева, то есть всегда можно уже выбранные ребра завершить до минимального остовного дерева. Алгоритм продолжается пока не будет выбрано n−1 ребро, образующее дерево (при этом нужно следить, чтобы выбранные ребра в каждый момент не образовывали циклов. Но принцип выбора очередного ребра в каждом алгоритме отличается. Алгоритм Краскала Весь единый список рёбер упорядочивается по неубыванию весов рёбер. Текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция из всех рёбер, добавление которых к уже
имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса. Алгоритм Прима (алгоритм ближайшего соседа) (отличается от алгоритма Краскала только тем, что на каждом шаге строится непросто ациклический графа дерево. Построение дерева начинается с произвольной вершины. Затем к дереву последовательно добавляются ребра и вершины, пока не получится остовное дерево, те. каркас. Для того, чтобы из текущего дерева при добавлении нового ребра опять получилось дерево, это новое ребро должно соединять вершину дерева с вершиной, еще не принадлежащей дереву так, чтобы не образовался цикл. Такие ребра будем называть подходящими относительно рассматриваемого дерева. Это ребро вместе с одной новой вершиной добавляется к дереву. Если обозначить через U и F множества вершин и ребер строящегося дерева, а через
W множество вершин, еще не вошедших в это дерево, то алгоритм Прима можно представить следующим образом
U := {a}, где a – произвольная вершина графа
F:= ∅
W:=V − {a} while W ≠ ∅ do найти ребро наименьшего веса e = (x,y) среди всех таких ребер, у которых x ∈U , y ∈W
F := F ∪ {e}
U := U ∪ {y}
W := W − {y} Пример 8.1. Определим минимальное остовное дерево нагруженного графа на рисунке 8.1. В примере длины дуг (веса) – это числа 1, 2, 3, 4, 5. Рис. 8.1. Рис. 8.2.
W множество вершин, еще не вошедших в это дерево, то алгоритм Прима можно представить следующим образом
U := {a}, где a – произвольная вершина графа
F:= ∅
W:=V − {a} while W ≠ ∅ do найти ребро наименьшего веса e = (x,y) среди всех таких ребер, у которых x ∈U , y ∈W
F := F ∪ {e}
U := U ∪ {y}
W := W − {y} Пример 8.1. Определим минимальное остовное дерево нагруженного графа на рисунке 8.1. В примере длины дуг (веса) – это числа 1, 2, 3, 4, 5. Рис. 8.1. Рис. 8.2.
Для решения этой задачи применяется следующий алгоритм
1) Выберем в графе G ребро минимальной длины. Вместе с инциндентными ему вершинами оно образует подграф G
2
(рис. 8.2.).
2) Строим граф G
3
, добавляя к графу G
2 новое ребро минимальной длины, выбранное среди ребер графа G, каждое из которых инциндентно какой–либо вершине графа G
2
, и одновременно инциндентно какой–либо вершине графа G, не содержащейся в графе G
2 3) Строим графы G
4
, G
5
, …, G
n
, повторяя действия пункта 2 до тех пор, пока не переберем все вершины графа G.
4) На четвертом шаге алгоритма получили дерево G
5
, которое соединяет все вершины исходного графа. Таким образом, дерево G
5
будет минимальным остовным деревом графа G. Пример 8.2. Построим остовное дерево минимального веса для нагруженного графа на рисунке 8.3. Рис. Рис. Решение.
1) Применяем алгоритм Прима (рис. 8.4.). Вводим в дерево ребро минимального веса (v
1
,v
6
) = 1. Вводим вершины и v
6
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
6
}
(v
1
,v
4
) = 3, добавляем конец этого ребра – вершину v
4
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
4
, v
6
} (v
4
,v
5
) =1, добавляем конец этого ребра – вершину v
5
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
4
, v
5
, v
6
} (v
4
,v
2
) = 3, добавляем конец этого ребра – вершину v
2
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
2
, v
4
, v
5
, v
6
} (v
2
,v
7
) =1, добавляем конец этого ребра – вершину v
7
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
2
, v
4
, v
5
, v
6
, v
7
} (v
7
,v
3
) = 2, добавляем конец этого ребра – вершину v
3
. Все вершины вошли в дерево, оно построено. Вес дерева 1+3+1+3+1+2=11.
2) Применяем алгоритм Краскала (рис. 8.5.). Вводим в дерево ребро минимального веса (v
1
,v
6
) = 1. Вводим вершины и v
6
. Вводим в дерево ребро минимального веса (v
4
,v
5
) =1. Вводим вершины v
4
и
1) Выберем в графе G ребро минимальной длины. Вместе с инциндентными ему вершинами оно образует подграф G
2
(рис. 8.2.).
2) Строим граф G
3
, добавляя к графу G
2 новое ребро минимальной длины, выбранное среди ребер графа G, каждое из которых инциндентно какой–либо вершине графа G
2
, и одновременно инциндентно какой–либо вершине графа G, не содержащейся в графе G
2 3) Строим графы G
4
, G
5
, …, G
n
, повторяя действия пункта 2 до тех пор, пока не переберем все вершины графа G.
4) На четвертом шаге алгоритма получили дерево G
5
, которое соединяет все вершины исходного графа. Таким образом, дерево G
5
будет минимальным остовным деревом графа G. Пример 8.2. Построим остовное дерево минимального веса для нагруженного графа на рисунке 8.3. Рис. Рис. Решение.
1) Применяем алгоритм Прима (рис. 8.4.). Вводим в дерево ребро минимального веса (v
1
,v
6
) = 1. Вводим вершины и v
6
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
6
}
(v
1
,v
4
) = 3, добавляем конец этого ребра – вершину v
4
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
4
, v
6
} (v
4
,v
5
) =1, добавляем конец этого ребра – вершину v
5
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
4
, v
5
, v
6
} (v
4
,v
2
) = 3, добавляем конец этого ребра – вершину v
2
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
2
, v
4
, v
5
, v
6
} (v
2
,v
7
) =1, добавляем конец этого ребра – вершину v
7
. Выбираем ребро минимального веса, смежное с вершинами дерева, v
2
, v
4
, v
5
, v
6
, v
7
} (v
7
,v
3
) = 2, добавляем конец этого ребра – вершину v
3
. Все вершины вошли в дерево, оно построено. Вес дерева 1+3+1+3+1+2=11.
2) Применяем алгоритм Краскала (рис. 8.5.). Вводим в дерево ребро минимального веса (v
1
,v
6
) = 1. Вводим вершины и v
6
. Вводим в дерево ребро минимального веса (v
4
,v
5
) =1. Вводим вершины v
4
и
v
5
. Вводим в дерево ребро минимального веса (v
2
,v
7
) =1. Вводим вершины v
2
и v
7
. Ребер веса 1 больше нет. Теперь вводим ребра веса 2 так, чтобы не образовать циклы. Вводим в дерево ребро минимального веса (v
2
,v
3
) = 2. Вводим вершину v
3
. Ребер веса 2, не образующих циклов с существующими, больше нет. Теперь вводим ребра веса 3 так, чтобы не образовать циклы. Вводим в дерево ребро минимального веса (v
1
,v
4
) = 3. Вводим в дерево ребро минимального веса (v
2
,v
4
) = 3. Все вершины вошли в дерево, оно построено. Рис. Вес дерева 1+3+1+3+1+2=11.
8.2. Минимальные пути в нагруженных орграфах алгоритм Дейкстры
G – данный граф, t – начальная вершина, s – конечная вершинах х j
) – вес ребрах х j
), х i
) – метка вершины х i
I. Присваивание начальных значений. Каждой вершине, кроме начальной, сопоставим метку х i
)=∞, назовем эти метки временными. Начальной вершине сопоставим метку l(s) = 0, назовем эту метку постоянной, вершину s назовем текущей и обозначим как p (p=s).
II. Обновление меток. Всем вершинам х i
, связанным с текущей по исходящим дугами имеющим временные метки, изменим их метки по правилу х i
) = х i
), х i
)}.
III. Превращение меток в постоянные. Среди вершин с временной меткой найдем вершину с минимальной меткой и назовем ее текущей, а ее метку постоянной. Если это есть вершина t, то перейдем к пункту IV, иначе к пункту II.
IV. Выделение пути обратным ходом. Определим конечную вершину как текущую p=t; для каждой вершины х, связанной с ней по заходящим дугам, определим разность между меткой текущей вершины и весом дуги х) =
=l(p)−c(p,x). Вершину, метка которой совпадает с этой разностью, назовем текущей, а дугу отнесем к пути. То, что такая вершина всегда найдется, гарантируется способом построения меток вершин. Возможно, что таких вершин будет несколько, что говорит о существовании нескольких решений задачи. Выберем в этом случае любую из них. Повторим эту процедуру до тех пор, пока текущей не станет начальная вершина. В результате множество отнесённых к пути дуг дадут искомое решение – кратчайший путь изв. Пример 8.3. Найдем кратчайшие пути в орграфе (рис. 8.6.) от первой вершины ко всем остальным, используя алгоритм Дейкстры. Построим дерево кратчайших путей.
5
. Вводим в дерево ребро минимального веса (v
2
,v
7
) =1. Вводим вершины v
2
и v
7
. Ребер веса 1 больше нет. Теперь вводим ребра веса 2 так, чтобы не образовать циклы. Вводим в дерево ребро минимального веса (v
2
,v
3
) = 2. Вводим вершину v
3
. Ребер веса 2, не образующих циклов с существующими, больше нет. Теперь вводим ребра веса 3 так, чтобы не образовать циклы. Вводим в дерево ребро минимального веса (v
1
,v
4
) = 3. Вводим в дерево ребро минимального веса (v
2
,v
4
) = 3. Все вершины вошли в дерево, оно построено. Рис. Вес дерева 1+3+1+3+1+2=11.
8.2. Минимальные пути в нагруженных орграфах алгоритм Дейкстры
G – данный граф, t – начальная вершина, s – конечная вершинах х j
) – вес ребрах х j
), х i
) – метка вершины х i
I. Присваивание начальных значений. Каждой вершине, кроме начальной, сопоставим метку х i
)=∞, назовем эти метки временными. Начальной вершине сопоставим метку l(s) = 0, назовем эту метку постоянной, вершину s назовем текущей и обозначим как p (p=s).
II. Обновление меток. Всем вершинам х i
, связанным с текущей по исходящим дугами имеющим временные метки, изменим их метки по правилу х i
) = х i
), х i
)}.
III. Превращение меток в постоянные. Среди вершин с временной меткой найдем вершину с минимальной меткой и назовем ее текущей, а ее метку постоянной. Если это есть вершина t, то перейдем к пункту IV, иначе к пункту II.
IV. Выделение пути обратным ходом. Определим конечную вершину как текущую p=t; для каждой вершины х, связанной с ней по заходящим дугам, определим разность между меткой текущей вершины и весом дуги х) =
=l(p)−c(p,x). Вершину, метка которой совпадает с этой разностью, назовем текущей, а дугу отнесем к пути. То, что такая вершина всегда найдется, гарантируется способом построения меток вершин. Возможно, что таких вершин будет несколько, что говорит о существовании нескольких решений задачи. Выберем в этом случае любую из них. Повторим эту процедуру до тех пор, пока текущей не станет начальная вершина. В результате множество отнесённых к пути дуг дадут искомое решение – кратчайший путь изв. Пример 8.3. Найдем кратчайшие пути в орграфе (рис. 8.6.) от первой вершины ко всем остальным, используя алгоритм Дейкстры. Построим дерево кратчайших путей.
Рис. Рис. Решение представлено в таблице Кратчайшие пути найдены, их длина приведена в последних двух столбцах расчетной таблицы. Построим дерево кратчайших путей (рис. 8.7) (ребра дерева обведены жирным) – ребра (1,2), (2,5), (5,4), (4,3), (5,6), (6,7), (7,8). Все вершины вошли в дерево, вес дерева 32+23+10+18+11+7+12=113.
8.3. Раскраска графов. Проблема четырех красок
Исторически раскрасочная терминология пришла в теорию графов из задачи о раскраске странна карте Сколько цветов требуется для раскраски различных странна карте так, чтобы каждые две смежные страны были окрашены по-разному?». Эта задача, получившая название проблемы гипотезы) четырех красок, была впервые предложена вниманию общественности в выступлении
Кэли на заседании Лондонского математического общества в 1878 г. Р
Теорема (окрасках. Всякий плоский граф можно раскрасить четырьмя красками. Доказать теорему окрасках не могли в течение 125 лет после ее первоначальной формулировки ив течение 99 лет после ее формулировки для научной общественности. Доказана теорема была только в 1977 г. Аппелем и
Хакеном. Вершинной раскраской графа называется такое приписывание цветов натуральных чисел) его вершинам, что никакие две смежные вершины не получают одинаковый цвет. Раскраска графа в р цветов называется р- раскраской. Раскраска графа, в которой используется минимальное число цветов, называется минимальной. Наименьшее возможное число цветов р в раскраске графа G называется хроматическим числом и обозначается χ(G). Если χ(G) = 2, то граф называется бихроматическим. Множество вершин, покрашенных в один цвет, называется цветовым классом. Никакие две вершины в цветовом классе не смежны. Реберной раскраской графа называется такое приписывание цветов натуральных чисел) ребрам графа, что никакие два смежных ребра не получают одинаковый цвет. Наименьшее возможное число цветов m в реберной раскраске графа G называется реберным хроматическим числом или хроматическим индексом и обозначается χ'(G). Очевидно, что для любого графа χ'(G) ≥ ∆(G), где ∆(G) – максимальная степень вершин графа G. Хроматическое число играет важную роль при решении задач наиболее экономичного использования ячеек памяти при программировании. Если вершинам сопоставить вхождение переменной в программу, а ребром обозначить зависимость одной переменной от другой, то идентификатору переменной будет соответствовать краска. Действительно, зависимые переменные должны иметь разные имена. Тогда нахождение минимального числа внутренних переменных сведется к минимальной раскраске вершин графа. В этой трактовке задача рассматривалась А.П. Ершовым, одним из крупнейших теоретиков и практиков программирования, предложившим интересный эвристический алгоритм решения этой задачи. Однако определение хроматического числа, за исключением χ(G) = 2, представляет собой довольно трудную задачу, часто требующую применения ЭВМ. Пример 8.4.
χ(K
p
) = p, χ(????
p
) = 1, χ(K
m,n
) = 2, χ(C
2n
) = 2, χ(C
2n+1
) = 3, χ(T) = 2. Для графа на рис. 8.8 χ= 4 (его раскраска изображена на рисунке 8.9).
Рис.8.8.
Рис.8.9.
Хакеном. Вершинной раскраской графа называется такое приписывание цветов натуральных чисел) его вершинам, что никакие две смежные вершины не получают одинаковый цвет. Раскраска графа в р цветов называется р- раскраской. Раскраска графа, в которой используется минимальное число цветов, называется минимальной. Наименьшее возможное число цветов р в раскраске графа G называется хроматическим числом и обозначается χ(G). Если χ(G) = 2, то граф называется бихроматическим. Множество вершин, покрашенных в один цвет, называется цветовым классом. Никакие две вершины в цветовом классе не смежны. Реберной раскраской графа называется такое приписывание цветов натуральных чисел) ребрам графа, что никакие два смежных ребра не получают одинаковый цвет. Наименьшее возможное число цветов m в реберной раскраске графа G называется реберным хроматическим числом или хроматическим индексом и обозначается χ'(G). Очевидно, что для любого графа χ'(G) ≥ ∆(G), где ∆(G) – максимальная степень вершин графа G. Хроматическое число играет важную роль при решении задач наиболее экономичного использования ячеек памяти при программировании. Если вершинам сопоставить вхождение переменной в программу, а ребром обозначить зависимость одной переменной от другой, то идентификатору переменной будет соответствовать краска. Действительно, зависимые переменные должны иметь разные имена. Тогда нахождение минимального числа внутренних переменных сведется к минимальной раскраске вершин графа. В этой трактовке задача рассматривалась А.П. Ершовым, одним из крупнейших теоретиков и практиков программирования, предложившим интересный эвристический алгоритм решения этой задачи. Однако определение хроматического числа, за исключением χ(G) = 2, представляет собой довольно трудную задачу, часто требующую применения ЭВМ. Пример 8.4.
χ(K
p
) = p, χ(????
p
) = 1, χ(K
m,n
) = 2, χ(C
2n
) = 2, χ(C
2n+1
) = 3, χ(T) = 2. Для графа на рис. 8.8 χ= 4 (его раскраска изображена на рисунке 8.9).
Рис.8.8.
Рис.8.9.
Очевидно, что существует р-раскраска графа G для любого р в диапазоне
χ(G) ≤ р ≤ n. Теорема. Доказательство Пусть граф G имеет хроматическое число k = χ(G). Тогда G содержит, по меньшей мере, одно ребро, инцидентное вершинам из разных цветовых классов, или один и тот же цвет можно использовать для двух различных цветовых классов. Пары вершин из k различных цветовых классов можно выбрать С способами, поэтому m
С = ½k(k-1). Решая это неравенство относительно k, получаем требуемое утверждение. Теорема Книга (1916 г. Для каждого двудольного графа χ'(G) = ∆(G), где ∆(G) – максимальная степень вершин графа G. Теорема Визинга (1964 г. Для каждого графа ∆(G) ≤χ'(G) ≤∆(G) +1. Таким образом, если для χ(G) имеются лишь приблизительные оценки, то родственное ему число χ'(G) может принимать лишь 2 значения. К сожалению, не существует эффективных алгоритмов (те. имеющих полиномиальную сложность) решения задач нахождения минимальной раскраски вершин и ребер графа. Разработаны лишь алгоритмы нахождения минимальной раскраски произвольного графа, основанные на переборе возможных вариантов, и алгоритмы с полиномиальной сложностью, приводящие к раскраске, близкой к минимальной. Рекомендации по нахождению хроматического числа и хроматического индекса состоят в следующем. Вычисление χ(G) целесообразно начинать с выделения в графе максимального полного подграфа – количество вершин в нем будет минимально возможным значением χ(G). Нахождение χ'(G) лучше начинать с определения вершины максимальной степени и раскраски инцидентных ей ребер. Дальнейшую раскраску вершин (или ребер) следует производить, исходя из экономии цветов, те. две несмежные между собой вершины (ребра, но смежные третьей вершине (ребру, нужно раскрашивать одним цветом. Эвристическая процедура раскрашивания графа.
1. Для каждой вершины графа определить ее степень. Расположить вершины в порядке не возрастания их степеней.
2. Первая вершина окрашивается в цвет №1, затем список вершин просматривается сверху вниз ив цвет №1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет.
3. Возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет №2 и, двигаясь по списку, окрашиваем вершины в цвет
№2 также, как окрашивали в цвет №1.
4. Процедура продолжается до тех пор, пока все вершины не будут окрашены. Количество использованных цветов будет приближенным значением хроматического числа.
χ(G) ≤ р ≤ n. Теорема. Доказательство Пусть граф G имеет хроматическое число k = χ(G). Тогда G содержит, по меньшей мере, одно ребро, инцидентное вершинам из разных цветовых классов, или один и тот же цвет можно использовать для двух различных цветовых классов. Пары вершин из k различных цветовых классов можно выбрать С способами, поэтому m
С = ½k(k-1). Решая это неравенство относительно k, получаем требуемое утверждение. Теорема Книга (1916 г. Для каждого двудольного графа χ'(G) = ∆(G), где ∆(G) – максимальная степень вершин графа G. Теорема Визинга (1964 г. Для каждого графа ∆(G) ≤χ'(G) ≤∆(G) +1. Таким образом, если для χ(G) имеются лишь приблизительные оценки, то родственное ему число χ'(G) может принимать лишь 2 значения. К сожалению, не существует эффективных алгоритмов (те. имеющих полиномиальную сложность) решения задач нахождения минимальной раскраски вершин и ребер графа. Разработаны лишь алгоритмы нахождения минимальной раскраски произвольного графа, основанные на переборе возможных вариантов, и алгоритмы с полиномиальной сложностью, приводящие к раскраске, близкой к минимальной. Рекомендации по нахождению хроматического числа и хроматического индекса состоят в следующем. Вычисление χ(G) целесообразно начинать с выделения в графе максимального полного подграфа – количество вершин в нем будет минимально возможным значением χ(G). Нахождение χ'(G) лучше начинать с определения вершины максимальной степени и раскраски инцидентных ей ребер. Дальнейшую раскраску вершин (или ребер) следует производить, исходя из экономии цветов, те. две несмежные между собой вершины (ребра, но смежные третьей вершине (ребру, нужно раскрашивать одним цветом. Эвристическая процедура раскрашивания графа.
1. Для каждой вершины графа определить ее степень. Расположить вершины в порядке не возрастания их степеней.
2. Первая вершина окрашивается в цвет №1, затем список вершин просматривается сверху вниз ив цвет №1 окрашивается всякая вершина, которая не смежна с другой, уже окрашенной в этот цвет.
3. Возвращаемся к первой в списке неокрашенной вершине, окрашиваем ее в цвет №2 и, двигаясь по списку, окрашиваем вершины в цвет
№2 также, как окрашивали в цвет №1.
4. Процедура продолжается до тех пор, пока все вершины не будут окрашены. Количество использованных цветов будет приближенным значением хроматического числа.
Данный алгоритм может дать различные варианты окраски для одного итого же графа. На рисунке 8.10 представлены различные раскраски графа, в первом случае хроматическое число равно 4, а во втором – 3. Рис. Сети. Потоки в сетях.
Сеть – конечный взвешенный связный орграф без контуров и петель, ориентированный водном общем направлении от вершины I (исток, вход) к вершине S (сток, выход. Максимальное количество r ij вещества, которое может пропустить за единицу времени ребро (i, j), называется его пропускной способностью. В общем случае r ij
≠ r ji
. Если вершины не соединены, то r ij
= 0. Так как нет петель, то r ii
=0. Пропускную способность можно задать квадратной матрицей. Количество х ij вещества, проходящего по ребру (i, j) в единицу времени, называется потоком по ребру (i, j). Предполагается, что если из х i
в х направляется поток х ij
, то изв направляется поток (х ij
): x ij
= -x ji
(1) Поток по каждому ребру не превышает его пропускную способность Количество вещества, притекающее в вершину, равно количеству вещества, вытекающего из неё Совокупность Х = {x ij
} потоков по всем рёбрам сети называют потоком посети. Общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, те. Функцию F называют мощностью потока. Если на сети задан поток Х = {x ij
}, то ребро (i,j) называется насыщенным, если поток x ij по нему совпадает сего пропускной способностью r ij
(x ij
= r ij
), и ненасыщенным, если x ij
< r Замечание. Не всякие n
2
чисел могут задавать поток посети. Только такие n
2
чисел x ij задают поток, которые удовлетворяют условиям (1) – (3).
Сеть – конечный взвешенный связный орграф без контуров и петель, ориентированный водном общем направлении от вершины I (исток, вход) к вершине S (сток, выход. Максимальное количество r ij вещества, которое может пропустить за единицу времени ребро (i, j), называется его пропускной способностью. В общем случае r ij
≠ r ji
. Если вершины не соединены, то r ij
= 0. Так как нет петель, то r ii
=0. Пропускную способность можно задать квадратной матрицей. Количество х ij вещества, проходящего по ребру (i, j) в единицу времени, называется потоком по ребру (i, j). Предполагается, что если из х i
в х направляется поток х ij
, то изв направляется поток (х ij
): x ij
= -x ji
(1) Поток по каждому ребру не превышает его пропускную способность Количество вещества, притекающее в вершину, равно количеству вещества, вытекающего из неё Совокупность Х = {x ij
} потоков по всем рёбрам сети называют потоком посети. Общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, те. Функцию F называют мощностью потока. Если на сети задан поток Х = {x ij
}, то ребро (i,j) называется насыщенным, если поток x ij по нему совпадает сего пропускной способностью r ij
(x ij
= r ij
), и ненасыщенным, если x ij
< r Замечание. Не всякие n
2
чисел могут задавать поток посети. Только такие n
2
чисел x ij задают поток, которые удовлетворяют условиям (1) – (3).
Задачу о максимальном потоке можно сформулировать следующим образом найти совокупность Х = {x*
ij
} потоков x*
ij по всем рёбрам сети, которая удовлетворяет условиями максимизирует линейную функцию
(4). Это типичная задача линейного программирования. В задаче о максимальном потоке единственным параметром является пропускная способность дуги. Задача состоит в том, чтобы найти максимальный поток, протекающий по дугам сети из заданного узла источника в заданный узел-сток. Пример задачи о максимальном потоке представлен на рис. 8.11, где узел
1 является источником, а узел 6 – стоком, (x ij
, r ij
). На рис. 8.11 изображен один из возможных оптимальных вариантов распределения потоков по дугам сети. Рис. 8.11. Пример задачи о максимальном потоке.
Разрезом называется набор дуг, удаление которых из сети приводит к тому, что источники сток оказываются несвязанными, те. между ними нельзя передать поток. В задаче о минимальном разрезе требуется построить разрез с минимальной суммарной пропускной способностью дуг. Для примера на рисунке 8.11 минимальный разрез состоит из дуги. Заметим, что суммарная пропускная способность этих дуг составляет 9 ед. потока, те. совпадает со значением максимального потока. Разность сумм весов исходящих и входящих дуг для вершины v называется дивергенцией функции весов в этой вершине. Пример 8.5. Для сети на рисунке 8.12. найдем дивергенции вершин. Рис. 8.12. Дивергенция вершины а равна 3+1=4, дивергенция вершины b равна
(4+6)–3=7, дивергенция вершины с равна 12 – (4 + 5) = 3, дивергенция вершины d равна (5+1)–(6+1)= –1, дивергенция вершины e равна 23–1= –22, дивергенция вершины f равна 0 – (12 + 23) = –35.
ij
} потоков x*
ij по всем рёбрам сети, которая удовлетворяет условиями максимизирует линейную функцию
(4). Это типичная задача линейного программирования. В задаче о максимальном потоке единственным параметром является пропускная способность дуги. Задача состоит в том, чтобы найти максимальный поток, протекающий по дугам сети из заданного узла источника в заданный узел-сток. Пример задачи о максимальном потоке представлен на рис. 8.11, где узел
1 является источником, а узел 6 – стоком, (x ij
, r ij
). На рис. 8.11 изображен один из возможных оптимальных вариантов распределения потоков по дугам сети. Рис. 8.11. Пример задачи о максимальном потоке.
Разрезом называется набор дуг, удаление которых из сети приводит к тому, что источники сток оказываются несвязанными, те. между ними нельзя передать поток. В задаче о минимальном разрезе требуется построить разрез с минимальной суммарной пропускной способностью дуг. Для примера на рисунке 8.11 минимальный разрез состоит из дуги. Заметим, что суммарная пропускная способность этих дуг составляет 9 ед. потока, те. совпадает со значением максимального потока. Разность сумм весов исходящих и входящих дуг для вершины v называется дивергенцией функции весов в этой вершине. Пример 8.5. Для сети на рисунке 8.12. найдем дивергенции вершин. Рис. 8.12. Дивергенция вершины а равна 3+1=4, дивергенция вершины b равна
(4+6)–3=7, дивергенция вершины с равна 12 – (4 + 5) = 3, дивергенция вершины d равна (5+1)–(6+1)= –1, дивергенция вершины e равна 23–1= –22, дивергенция вершины f равна 0 – (12 + 23) = –35.