Комбинаторные алгоритмы для программистов


Введение


Множество самых разнообразных задач естественно формулируется в терминах графов. Так, например, могут быть сформулированы задачи составления расписаний в исследовании операций, анализа сетей в электротехнике, установления структуры молекул в органической химии, сегментации программ в программировании, анализа цепей Маркова в теории вероятностей. В задачах, возникающих в реальной жизни, соответствующие графы часто оказываются так велики, что их анализ неосуществим без ЭВМ. Таким образом, решение прикладных задач с использованием теории графов возможно в той мере, в какой возможна обработка больших графов на ЭВМ, и поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое значение. В 16 и 17 лекциях мы излагаем несколько эффективных алгоритмов на графах и используем их для демонстрации некоторой общей техники решения задач на графах с помощью ЭВМ.

Конечный граф

G = (V,E)
состоит из конечного множества вершин
V = \{ v_1 v_2,..\}
и конечного множества ребер
E\{ e_1 e_2,\ldots \}
. Каждому ребру соответствует пара вершин: если ребро
(v,w)
соответствует ребру
e
, то говорят, что
e
инцидентно вершинам
v
и
w
. Граф
G = (V,E)
изображается следующим образом: каждая вершина представляется точкой и каждое ребро представляется отрезком линии, соединяющим его концевые вершины. Граф называется ориентированным, если пара вершин
(v,w)
, соответствующая каждому ребру, упорядочена. В таком случае говорят, что ребро
e
ориентированно из вершины
v
в вершину
w
, а направление обозначается стрелкой на ребре. Мы будем называть ориентированные графы орграфами. В неориентированном графе концевые вершины каждого ребра не упорядочены, и ребра не имеют направления. Ребро называется петлей, если оно начинается и кончается в одной и той же вершине. Говорят, что два ребра параллельны, если они имеют одну и ту же пару концевых вершин (и если они имеют одинаковую ориентацию в случая ориентированного графа). Граф называется простым, если он не имеет ни петель, ни параллельных ребер. Если не указывается противное, будем считать, что рассматриваемые графы являются простыми. Всюду в 16 и 17 лекции будем использовать символы
\left| V \right|
и
\left| E \right|
для обозначения соответственно числа вершин и числа ребер в графе
G = (V,E)
.




Начало    Вперед



Книжный магазин