ЗАДАЧИ ОПТИМИЗАЦИИ НА ГРАФАХ

Элементы теории графов

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

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

Дадим более строгое определение графа. Графом G называется пара множеств G = (X, Е), гдеХ— непустое множество вершинх, х2, ..., х„}, а элементами множества Е являются некоторые двухэлементные подмножествах, т.е. Е = {(х,-,ху)}. Элементы этих двухэлементных подмножеств называются ребрами. Например, G = = ({хх, х2, х3, х4}, {(хх, хх), (хх, х2), (х1; х3), (х2, х3), (х3, х4)}) — граф, состоящий их четырех вершин и пяти ребер.

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

Если вершины х, и х, принадлежат некоторому ребру (х„ х;), то говорят, что это ребро инцидентно вершинам х, и х;, которые в свою очередь называются смежными. Если ребро инцидентно одной и той же вершине, то оно называется петлей (см. рис. 16.1). Вершина, не инцидентная никакому ребру, называется

изолированной. Если в графе есть вершины, соединенные двумя или большим числом ребер, то такой граф называют мультиграфом (рис. 16.2).

Различные изображения одного и того же графа
 Рис. 16.2. Мультиграф

Рис. 16.1. Различные изображения одного и того же графа Рис. 16.2. Мультиграф

Число ребер, инцидентных данной вершине, называется степенью (кратностью) данной вершины. В графе, изображенном на рис. 16.2 вершина х2 имеет степень 6, так как ей инцидентны ребра 04, а2, а4, а5, а6, а7, а вершина имеет степень 3. Вершина хЛ имеет степень 0, т.е. это изолированная вершина. Ребро, связывающее данную вершину с этой же вершиной, называется петлей. Граф без петель и кратных ребер называется простым, или обыкновенным.

Граф может быть задан и в виде квадратной таблицы—матрицы смежности графа. Номера строк и столбцов этой матрицы совпадают с номерами вершин графа, а ее элемент с* есть число ребер, соединяющих вершины х, и Ху Для графа, изображенного на рис. 16.2, матрица смежности имеет вид

Нумеровать вершины графа можно произвольным образом. Например, в графе, изображенном на рис. 16.2, перенумеруем вершины следующим образом: хг —> х5, х3 —> х1; х5 —> х4, х4 —> х3. При этом матрица смежности изменится (сравните матрицы С hCj):

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

В целом ряде задач принципиальную важность имеет направленность связей между вершинами. Характерным примером являются отношения порядка. Например, х, старше Xj, но в этом случае х; не может быть старше х,. Следовательно, отношение «быть старше» может быть формализовано графом, у которого связи между вершинами имеют определенную ориентацию. Такие графы принято называть ориентированными. Ориентированным графом (или орграфом) D называется пара D = (X, А), где X — произвольное множество вершин и А — множество упорядоченных пар вершин, называемых дугами, А с X х X. В паре (х„ хф первая вершина х, называется началом дуги, а вторая X: — концом дуги. На рисунках дуги изображаются стрелками (рис. 16.3).

Ориентированный граф

Рис. 16.3. Ориентированный граф

Орграф также может иметь петли и кратные дуги (рис. 16.4).

Ориентированный граф с петлей

Рис. 16.4. Ориентированный граф с петлей

Чтобы лучше понять отличие ориентированного графа от неориентированного, можно привести следующую аналогию. Если ориентированный граф используется для описания системы улиц города с односторонним движением, то неориентированный граф — улиц с двусторонним движением. Очевидно, что ребро неориентированного графа, соединяющее две вершины, эквивалентно двум разнонаправленным дугам, соединяющим эти же вершины. Таким образом, неориентированный граф можно рассматривать как частный случай ориентированного графа.

Ориентированные графы удобно задавать в виде таблиц — матриц инцидентности. Номера строк матрицы инцидентности равны номерам вершин, а номера столбцов — номерам дуг. Если дуга а, выходит из вершины xt, то соответствующий элемент матрицы инциденций х^ равен -1. Если же дуга а; входит в вершину хк, то элемент xkj равен +1. Все другие элементы столбца; равны нулю. Таким образом, в каждом столбце матрицы инциденций ровно один элемент +1, ровно один элемент -1, остальные элементы — нули. Для ориентированного графа, изображенного на рис. 16.4, матрица инцидентности имеет вид

Граф Gb(Xb, ?ь) называется частичным графом (суграфом) графа G(X, Е), если он содержит все вершины исходного графа и лишь часть ребер исходного графа, т.е. Xb = X и Еъ с Е. Подграфом Ga(Xa, Еа) графа G(X, Е) называется граф, в который входит подмножество вершин исходного графа а с X) и все ребра, соединяющие вершины Ха этого графа (?а с ?). На рис. 16.5 представлены подграф и частичный граф для данного исходного графа G(X, ?).

Граф, его частичный граф и подграф

Рис. 16.5. Граф, его частичный граф и подграф

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >