DM3

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

	Задача состоит в нахождении одного из nn-2 деревьев.
	Пусть G=(X, U) связный граф, и каждому
	ребру uiU ставится в соответствие
	некоторое неотрицательное число νi,
	называемое мерой. Необходимо найти
	покрывающее дерево Т, для которого сумма
	мер, взятая по всем ребрамm	минимальна.
	∑ν (ui ) = min
	Метод Краскала i=1		(х2х6)=1
			(х2х4)=1
	1.В связном графе G=(X, U), | X | = n,
			(х6х3)=2
	определяется ребро с наименьшей мерой.		(х3х5)=1
			(х3х1)=2

2.Строится по индукции последовательность ребер u2, u3,…, u n-1, причем на каждом шаге выбирается ребро с наименьшей мерой, не совпадающее с выбранными и не образующее циклов с предыдущими ребрами ui.

3.Полученный подграф Т графа G является искомым деревом.

Понятие метрики графа
Метрика графа основана на понятии расстояния. Назовем	расстояни-
ем d(xi, xj) = dij между вершинами xi,xjÎX графа G=(X, U)	длину крат-

чайшей цепи, соединяющей эти вершины. Под длиной цепи понимается число входящих в нее ребер.

Функция d(xi, xj), определенная на множестве ребер графа G, называется метрикой графа. Метрика удовлетворяет аксиомам Фреше:

"xi xj Î X[d(xi, xj) ³ 0];

"xi xj Î X[d(xi, xj) = 0 « xi = xj];

"xi xj Î X[d(xi, xj) = d(xj, xi)];

"xi,xj,xk Î X[d(xi, xj) + d(xj, xk) ³ d(xi, xk)] т.к. d(xi, xk) кратчайшая цепь

Функция расстояний задается матрицей

0, если xi = xj;

D = || dij|| =

dij, если xi ¹ xj;

1 2 3 4 5

1 0 3 1 3 2

D = 2 3 0 2 1 1

3 1 2 0 2 1

4 3 1 2 0 1

5 2 1 1 1 0

Рисунок 7.24

Список расстояний можно задать в виде множества кортежей длины три < xi ,xj ,dij >.

Для графа, приведенного на рисунке 7.24.

D={<1,2,3>, <1,3,1>, <1,4,3>, <1,5,2>, <2,3,2>, <2,4,1>, <2,5,1>, <3,4,2>, <3,5,1>, <4,5,1>}

Диаметр графа D(G) определяется как максимальное расстояние между его вершинами.

D(G) = max dij, xi xj X

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

Gr = (Xr, Ur)

В графе Gr = (Xr, Ur) множество Xr соответствует узлам решетки, а Ur - вертикальным и горизонтальным отрезкам, соединяющим узлы решетки.

Введем декартову систему координат с осями s и t. t

x1 x2 x3 x4 x5 x6	s
	Рисунок 25

Расстояние между соседними узлами решетки называют шагом решетки и принимают равным единице. Расстояние между двумя произвольными вершинами в решетке Gr рассчитывается:

dij = |si – s j| + |ti – t j| , где si, sj и ti, tj - координаты xi и xj .

Обычно задаются размеры решетки p x q, где p – число узлов решетки по оси s, q – по оси t. Например, d(7, 13) =|5 – 0| + |1 – 2| = 6.

Граф Gr удовлетворяет аксиомам Фреше. Если произвольный граф G отображается в Gr так, что любые вершины G размещаются в узлах решетки, то расстояние между вершинами G определяется как расстояние между соответствующими узлами решетки Gr.

Любой граф G может быть отображен в решетку Gr.

Для подсчета суммарной длины L(G) ребер графа G, отображенного в решетку Gr, введем понятие матрицы геометрии Dν.

Dν представляет собой часть матрицы расстояний D, в которой исключены элементы dij, если вершины xi xj X не смежны в графе G.

0, если xi, xj не смежны ;

dνij =

dij, в другом случае.

Сумма элементов матрицы Dν определяет удвоенную суммарную длину L(G) ребер графа G при данном его отображении в решетку Gr.

Раскраской вершин графа называется разбиение множества вершин графа на l непересекающихся классов (подмножеств)

l

X1 , X 2 ,..., X l ; X = U X i ; X i I X j = O/ ; i, j Î1, l; i ¹ j.

i=1

таких, что внутри каждого подмножества Хi не должно быть смежных вершин.

Если каждому подмножеству Хi поставить в соответствие определенный цвет, то вершины внутри подмножества можно окрасить в один цвет, вершины другого – в другой и т.д. до полной раскраски. В этом случае граф называется l-раскрашиваемым. Наименьшее число подмножеств, на которое разбивается граф при раскраске, называется хромати-

ческим числом K(G).

Очевидно, полный граф Kn можно раскрасить только в n цветов K(Kn)=n.

Для связного графа G = (X, U) с	n-1 ≤ m ≤	n(n-1)/2		верхняя оценка
хроматического числа:			3 +
	K ( G ) =			9 + 8 ( m − n )
Нижней оценкой K(G) является
				2
число вершин в наибольшем полном подграфе графа G.

Хроматическое число обычно определяется с помощью методов линейного программирования.

(Например, политическая карта мира.)

Важное практическое применение имеют 2-раскрашиваемые или двудольные (граф Кёнига) (бихроматические) графы. Обозначается дву-

дольный граф Gn1,n2 =(X1, X2, U), где X1ÈX2=X, X1ÇX2=Æ, а ребра соединяют только подмножества X1 и X2 между собой.

Пример двудольного графа.

Gn1,n2 =(X1, X2, U); |X1| = n1 = 4; |X2| = n2 = 3; X1 = {x1, x2, x3, x4}; X2 = {x5, x6, x7}.

Рисунок 7.27. Двудольный граф

Граф Kn1, n2 называется полным двудольным графом, если любая вершина xiÎX1 смежна каждой вершине xjÎX2 (i¹j).

В двудольном графе множество X1 можно раскрасить одним цветом, Х2 – другим цветом.

Рисунок 7.28. Полный двудольный граф К32.

При	разработке
алгоритмов	компоновки,
размещения	и трассировки
возникает	необходимость

определения двудольности некоторого графа или выделения в этом графе максимальных непересекающихся двудольных частей.

Теорема 4. Граф Gn1, n2 является двудольным тогда, и только тогда, когда он не имеет простых циклов нечетной длины.

Рассмотрим число внутренней устойчивости. Если любые вершины x’i, x’j ÎX’ в графе G = (X, U) X’ÍX, не смежны, то это подмножество называется внутренне устойчивым.

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

Изоморфизм графов

Два графа G=(X, U) и G’=(X’, U’) называют изоморфными, если можно установить взаимно-однозначное соответствие X↔X’ , U↔U’ такое,

что если (xi, xj) X↔(x’i, x’j) X’, то ребро u=(xi, xj) U↔u’=(x’ i, x’j) U’.

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

В общем случае для определения изоморфизма необходимо сделать n! сравнений.

При покрытии функциональной схемы набором стандартных модулей или при решении задачи типизации необходимо устанавливать изоморфизм между графом G и какой-либо частью другого графа G’.

	а	б
z1	z2	z3

z4

z5

z6

в

Рисунок 29. Граф G и изоморфные ему