Глава 3 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ТЕОРИИ ГРАФОВ

Рассмотренные выше принцип оптимальности и метод ДП решения задач управления многошаговыми процессами допускают ряд важ­ных и естественных обобщений. В рамках стандартных допущений метода ДП — отсутствия последействия и аддитивности целевой функ­ции — одним из главных направлений обобщения является распростра­нение принципа оптимальности и разработка метода ДП для решения задач, формулируемых на основе понятий теории графов. Такие за­дачи имеют исключительно широкую сферу приложений в экономике, технике и естествознании. В задачах такого типа, как правило, число шагов при переходе из начального состояния в конечное может ме­няться, так что непосредственное применение классического метода ДП встречает определенные сложности. Изучению соответствующих обоб­щений принципа оптимальности для задач теории графов и посвящена настоящая глава.

3.1. Основные понятия теории графов

При формулировке и решении широкого класса задач из различных об­ластей деятельности человека естественным образом возникают схемы следующей структуры. Имеется несколько различных точек плоско­сти, называемых вершинами, некоторые пары которых соединены непрерывными линиями, называемыми ребрами. Такого типа схемы называются графами. При этом несущественно, каким образом рас­положены на плоскости вершины друг относительно друга (насколько далеко или близко), какова форма линий, представляющих ребра (пря­мые или кривые). Существенно лишь то, сколько вершин входит в граф и какие именно пары вершин соединены ребрами.

Прообразами графов в реальном мире могут служить транспорт­ная, трубопроводная, электрическая сети, структура связей между отделами в организации, отношения между участниками производ­ственного и торгового процессов, комплексы взаимосвязанных работ,

наличие психологической совместимости между сотрудниками и т. п. На рис. 3.1 представлен пример графа, изображающего ковш созвез­дия Большая медведица. Вершинами графа являются наиболее яркие звезды, входящие в созвездие, ребрами — мысленно проведенные ли­нии, определяющие рисунок созвездия. Обозначены вершины графа греческими буквами начиная с а порядке убывания яркости соответ­ствующих звезд.

Строгое математическое определение графа без привязки к геомет­рической интерпретации можно сформулировать следующим образом.

Графом называется набор из двух объектов: множества вершин и связанного с ним множества ребер. В качестве множества вершин графа принимается некоторое непустое множество V с конечным чис­лом элементов. Элементы множества V называются вершинами графа. В качестве множества ребер графа может быть принято некоторое фиксированное подмножество Н, множества всех неупорядоченных пар вершин графа. Элементы множества Н, называются ребрами графа.

На схемах и чертежах вершины графа изображаются точками или небольшими окружностями, а ребра — непрерывными линиями, не про­ходящими через посторонние вершины и не имеющими точек самопе­ресечения. Вершины графа могут обозначаться с помощью номеров, букв или слов того или иного алфавита или специальных кодов. Ребро графа, образованное парой вершин V и го, будем обозначать через ьгю (подобно отрезку АВ, соединяющему две точки А и В), либо через V — гю (это необходимо, если вершины графа обозначаются несколькими символами; например, ребро, образованное вершинами с обозначени­ями 12 и 34, следует записывать в виде 12 — 34, поскольку запись 1234 допускает неоднозначное толкование). В отдельных случаях, когда нет необходимости конкретно указывать образующие ребро вершины, ребра графа могут обозначаться одним символом, например г. Обозначается граф с множеством вершин V и множеством ребер Я через С{У, В.).

Например, если множество вершин графа состоит из трех точек А, В,С, т.е. V = {А, В,С}, то множество всех неупорядоченных пар вершин имеет вид {АА, АВ, АС, ВВ, ВС, СС}; при этом, в частности, пары АВ и В А не различаются и считаются равными, поскольку по­рядок вершин в паре не важен (как и в случае обычного отрезка на плоскости, который может быть обозначен как АВ, так и В А). В качестве множества И ребер графа может быть принято, в частно­сти, подмножество {АВ,АС, ВС}, элементы которого соответствуют сторонам треугольника АВС.

Приведем ряд основных понятий теории графов, которые будут использованы нами при дальнейшем изучении материала.

Две вершины графа называются смежными, если они образуют ребро. При этом говорят, что вершины являются концами образуемого ими ребра, а само ребро соединяет образующие его вершины. Два ребра графа называются смежными, если они имеют одну общую конце­вую вершину и не совпадают. Если вершина является одним из кон­цов ребра, то такие вершина и ребро называются инцидентными (иными словами, ребро примыкает к инцидентной ему вершине). Вер­шина, не инцидентная ни одному ребру, называется изолированной. Вершина, инцидентная только одному ребру, называется висячей. Вершина, инцидентная более чем двум ребрам, называется узлом. Число ребер, инцидентных некоторой вершине, называется степе­нью вершины. Ребро называется петлей, если обе образующие его вершины совпадают.

Проиллюстрируем введенные основные понятия на графе, изобра­женном на рис. 3.2. В данном примере:

—               вершины «2 ^и "5, «з и /,'4 являются смежными;

—               вершины /,'4 и /,'5 не являются смежными;

—               ребра /,'] /,'2 и )'21'з являются смежными;

—               ребра У2У5 И /,'з/,'4 не являются смежными;

—               вершина У4 и ребро /'2)'4 являются инцидентными;

—               вершина у\ и ребро г'3/,'4 не являются инцидентными;

—               вершина г>б —изолированная;

—               вершина г>5 — висячая;

—               вершина У2 — узел степени 4;

—               ребро р — петля в вершине /• 1.

 дографов и мультиграфов приводит к формальному усложнению из­лагаемого материала и в настоящем пособии не приводится.

Рассмотрим дальнейший ряд основных понятий теории графов. Необходимо отметить, что в этой части теории терминология не яв­ляется вполне устоявшейся и общепринятой и может отличаться от используемой в других источниках.

Маршрутом называется последовательность попарно смежных вершин графа вида

^[0] > ^[1], • • • > Цк] или г>_[0] - -У[_Х] - ... - ущ,

где индексы в квадратных скобках указывают порядковый номер вер­шины в маршруте, к — целое положительное число, равное количеству ребер в маршруте. При этом вершина «[₀] называется началом марш­рута, вершина У[к]' концом маршрута, обе эти вершины называются крайними, а все остальные вершины — внутренними. Говорят, что маршрут соединяет свои начальную и конечную вершины. Более полно и детально маршрут определяется как чередующаяся последо­вательность вершин и ребер графа вида

«[0] > ^г[1] > ^и[1] > ^Г[2]' ^[2]> ' • • > ^гм' ^У1^к]'

в которой ребро гщ образовано смежными вершинами ><'[_г-1] и у^у

Наличие квадратных скобок «[ ]» в обозначениях порядковых номе­ров вершин в маршруте обусловлено следующими обстоятельствами. Как мы уже видели на примере, в обозначениях вершин графа могут использоваться индексы. Во избежание возможной путаницы между индексами в обозначениях вершин и порядковыми номерами вершин в некотором маршруте эти порядковые номера (зависящие, очевидно,от выбора маршрута) мы и условимся заключать в квадратные скобки. Тем самым, для различных маршрутов символ t^j может обозначать разные вершины даже для фиксированных значений ц например, может меняться вершина, обозначаемая через ущ, в то время как обозначение v I обычно относится к некоторой фиксированной вершине графа.

В общем случае в маршруте отдельные вершины и ребра могут повторяться, несмотря на формально различные индексы в их обозна­чениях; соответственно возникает необходимость рассмотреть и сле­дующие более простые структуры. Маршрут называется цепью, если в нем ни одно ребро не встречается более одного раза. Маршрут назы­вается путем, если в нем либо все вершины попарно различны, либо совпадают только крайние вершины. Из данных определений вытекает следующее:

1)               из любого маршрута можно выделить путь, соединяющий те же крайние вершины;

2)               любой путь является цепью, поскольку отсутствие повторяю­щихся вершин гарантирует и отсутствие повторяющихся ребер.

Маршрут, цепь или путь называются замкнутыми, или цикли­ческими, если в них крайние вершины совпадают. Замкнутая цепь называется циклом. Граф называется связным, если любые две его вершины можно соединить цепью. Связный граф без циклов называ­ется деревом.

Возвращаясь к рис. 3.2, отметим:

—               последовательность v\ — v₂ — Уь — v₂ — V4 — V3 образует маршрут, соединяющий вершины г>1 и г>₃ и дважды содержащий ребро ^v2 — Щ • В соответствии с принятым соглашением об обозначениях для данного маршрута справедливо:

V[0]=Vl, V[!]=V2, V[2]=V₅, ..., V[5]=V3;

—               последовательность — V2 — V4 — vs — г>2 — V\ образует цепь, со­единяющую вершины î'5 и î;i ;

—               последовательность V4 — V3 — V2 — образует путь, в котором

^и[0] = щ, «[1] = V₃, V[2] = V2, V[3] = V₅\

—               путь г/з — V4 ~ V2 — ьз является замкнутым.

Приведенный граф не является связным, поскольку содержит изо­лированную вершину ?.'б; если же данную вершину отбросить, то вновь полученный граф, очевидно, станет связным. Если при этом отбро­сить петлю р и одно из ребер у₂ - у я, у 2 ~ ^VA, V3 — V4, то граф станет деревом.

Графам могут быть поставлены в соответствие матрицы следую­щих типов. Пусть G(V,R) —некоторый граф, содержащий п вершин

VI, У2, ■ • •, ь_п и т ребер г\, Г2, ■ ■ ■, г_т. Матрицей смежности графа <2(У, Я) называется квадратная матрица 5 порядка п (по числу вер­шин), элементы ву которой определяются следующим образом:

Г 1, если вершины VI и V] смежные, ^ ^ з — I

( 0, если вершины г>г и V] не смежные.

Матрица смежности является симметричной, т.е. ее элементы удо­влетворяют условию = вц, и имеет нули на главной диагонали (если в графе нет петель). Обратно, любая состоящая из нулей и единиц мат­рица с указанными свойствами однозначно определяет граф с пронуме­рованными вершинами. Матрицей инцидентности графа К) называется матрица ф размерности пхт, элементы ^ которой опре­деляются следующим образом:

Г 1, если вершина и ребро г,- инцидентны,

Щ ⁼ 1

[ 0, если вершина и ребро г^ не инцидентны.

Матрица инцидентности в каждом столбце имеет две единицы и не содержит одинаковых столбцов. Обратно, любая состоящая из нулей и единиц матрица с указанными свойствами однозначно определяет граф с пронумерованными вершинами и ребрами. Например, для при­веденного на рис. 3.2 графа без учета петли р матрицы смежности и инцидентности имеют вид

 

если ребра графа пронумеровать следующим образом:

П = Ь_ХЬ2, Г2 =          Гз = ^4, П = г/2^5, Г₅ =

при иной нумерации ребер графа может поменяться порядок столбцов матрицы инцидентности.

Как видно из представленного примера, матрицы смежности и ин­цидентности являются громоздкими даже для весьма простых графов. По этой причине графы удобно задавать списками смежности, которые представляют собой список всех вершин графа с перечнями смежных с ними вершин; во избежание повторений среди смежных вершин достаточно указать лишь те, которые имеют больший по зна­чению индекс. Например, изображенный на рис. 3.2 граф без учета петли р может быть задан следующим списком смежности:

Щ — У2\ «2 — «з, «4, ь₃ —                         ь₆.

Допустимы и иные формы списков смежности.