Elektronika_i_skhemotekhnika

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

h H : h D h 1 = D'

D D' .

(3.34) (1)

На графе группе Hv эквивалентна транзитивная группа Lv, действующая на множестве V. При большой размерности матрицы D число перестановок строк и столбцов становится столь значительным (v!), что прямой перебор, согласно формуле (3.34-1) оказывается неприемлемым. Это так называемое NP- полное решение. Поэтому для уменьшения числа сравнений матриц D и D

применим вектор степеней вершин, получающийся в результате разбиения числа 2q согласно (3.30). При графе, заданном матрицей D, числа pi находят, суммируя элементы строки или столбца i матрицы D.

На множестве V введем отношение эквивалентности:

vi , v j V : vi ~ v j pi p j ,

разбивающее V на множество орбит O={Ok}, k=1,0 группы Lv. Все элементы vi V орбиты Ok характеризуются одной и той же степенью вершин pi графа. Присвоим индексу степени pi индекс орбиты k, если vi Ok, т. е.

vi Ok pi pk

и назовем длиной lk орбиты Ok число ее элементов. Чтобы указанное разбиение использовать для уменьшения числа изоморфных графов, упорядочим строки и столбцы матрицы D согласно разбиению [3]

1		0	d12 d1(l1 1)						d1v
D 2	d	(l1 1)1			0			d	(l1 1)v		(3.35)
o		dv1	dv(l 1)			dv(v 1)			0
					1
Теперь		каждая		подстановка		hk Hv		переставляет			элементы,

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

элементы V \ Ok. Поэтому число различных перенумераций вершин графа на

n

новом множестве Lv' равно уже не v!, а lk !.

k 1

Пример2. Определим изменение числа изоморфных графов после упорядочивания номеров его вершин в соответствии с разбиением . У графа Г(7,9) (рис. 3.4,ж) первоначальная нумерация вершин принята как обычно, по часовой стрелке (цифры без скобок). Так как порядок нумерации вершин не связан с параметрами конкретного графа, то число всех изоморфных графов равно 7!=5040. Для такого простого графа это число весьма не малое.

Введѐм правило нумерации вершин согласно его

разбиению (4,3,3,2,2,2,2) : первый номер присваивается вершине с максимальной степенью, последний номер – вершине с минимальной степенью. Вершины, имеющие одинаковые степени, принадлежат одной орбите, т.е. с этой точки зрения эквивалентны, и их нумерация внутри одной орбиты произвольна. Число изоморфных графов для рассматриваемого примера будет

всего 1! 2! 4! 48 , что	в 104 раза меньше произвольной нумерации
вершин, причѐм матрицы D и D имеют вид
1 (6)
7 (3)		2 (2)
6 (4)		3 (7)
5 (1)	4	(5)
Рис. 3.4

=1, sk

1	2 3 4		5	6 7				4 3		3	2 2	2 2
0 1 0 0 0 0 1							0 1 1 1 1 0 0
1 0 1 0 0 0 1								1	0	0 1 0 1 0
0 1 0 1 0 0 0							1		0	0	0 0 1 1
D 0 0		1 0 1 0 1				D		1 1 0 0 0 0 0
0 0		0 1 0 1 0						1	0	0	0 0 0 1
0 0		0 0 1 0 1						0 1 1 0 0 0 0
								0 0 1			0 1 0 0
1 1 0 1 0 1 0													.

Над столбцами матриц D и D указаны соответственно номера вершин и степени вершин согласно . Дальнейшего уменьшения числа изоморфных графов можно добиться укорочением длины lk за счет введения нового отношения эквивалентности на вершинах графа. Это отношение, сохранив предыдущее, должно разбить элементы орбиты Ok на множество подклассов Ok={Zkr}, r . С увеличением числа sk уменьшается

длина lkr lk sk подкласса Zkr, а число возможных перенумераций вершин графа

станет меньшим o sk l ! . Для этого в [2] предложено в матрице D k 1 r 1 kr

заменить dij=1 на элемент dij=tij, где число tij 0 отражает дополнительно

какую-либо одну или несколько характеристик вершин j и ребра (i,j). Пусть, например, сначала такой характеристикой является только степень вершины j, т.е. tij=pj=degvj. Тогда можно сформировать матрицу с новыми элементами

DT dij' , dij' 0, p1,, pv : dij'	p j i, j . ,	(3.36)
которую не трудно образовать из матрицы D :
DT D diag p1, , pv .		(3.37)

Здесь элементы pi диагональной матрицы составлены в соответствии с разбиением . Используем симметрию матрицы для введения эквивалентности.

Из ненулевых элементов dij' каждой i-ой строки матрицы DT образуем вектор tkm tk1, tk 2, , t pm , элементы которого упорядочены по невозрастанию

1, sk

tk1 tk 2 t pm > 0. Считаем вершины vi,vj Ok эквивалентными, если равны соответствующие им векторы:

vi ~ vj<=>(tik)=(tjk): ti1 = tj1, ti2 = tj2,…, tipki t jpkj .

У попарно эквивалентных векторов, множество вершин vi Ok образует класс эквивалентности Zkr, а каждая орбита содержит некоторое число этих

классов r = . В случае, если все вершины орбиты различны, то на ней перенумерация вершин невозможна, а следовательно не образуются изоморфные графы. Если все вершины орбиты эквивалентны, то с помощью перенумераций только этих вершин образуется lkr! изоморфных графов. Упорядочим номера вершин vi Ok на основании лексикографического7 порядка векторов tkm и tkl , вершины которых принадлежат разным классам.

Если выполняется неравенство

tkm tk1,

tk 2, , tkp

lex tkl

tk1, tk 2, , tkp

,

pm pl ,

(3.38)

m

l

то присвоим vm Zkr

и соответствующим векторам tm номера m<l. Из

упорядоченных

векторов

ti образуем

смежностно-степенную

таблицу T

(ССТ),

, , t1p

p1

t11 ,

t12

1

t21,

t22

, , t2 p

2

T p2

tl

1 ,

tl

2

, , t

,

3.39

2

2

l2 p2

p3

t(l

1)1 , t

1) 2 , , t

1) p

не

(l

2

(l

2

2

3

plk

tv1 , tv2 , ,tvp

lk

содержащую нулевые элементы, а также отражающей степени вершин, с которыми смежна вершина i, а не их номера, как в матрице DT' .

7Сравнение двух лексикографически упорядоченных векторов осуществляют по принципу первого различия (как слова упорядочены в словаре). Например, x1, , xn , y1, , yn , , если для некоторого k выполняется xk yk и xi yi для всех i k [энцик матем]. нет ли раньше

В таблице (3.39) слева от черты выписаны степени вершин, в соответствии с разбиением ; tij – степень t вершины смежной с вершиной

i= 1,n , расположенной			в еѐ строке на месте j = 1, pi ;			строки разбиты в
соответствии с множеством орбит O = {Ok} и упорядочены
		k, k 1 I (1,	, v); vk Ok , vk 1 Ok 1 k			k 1.(3.40)

Затем lk строк, соответствующих длине Ok, заново разбиты согласно множеству классов эквивалентности {Zkr} и лексикографически упорядочены

r, r+1 I; tkr> tk(r+1) => vr Zkr, vr+1 Zk(r+1),

(3.41)

Отсюда следует:

Утверждение. Различным смежностно-степенным таблицам (ССТ) T соответствуют неизоморфные графы.

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

Пример 3. Рассмотрим все связные графы Г(7,9) (рис. 3.6) соответствующие одному разбиению =(4,3,3,2,2,2,2). Графы б), в), з), л) – являются разделимыми в вершине сочленения, а граф д) – содержит мост. У всех графов три орбиты: O1={p1|4}, O2={p2|3,3}, O3={p3| 2,2,2,2}, у которых длина соответственно равна: l1=1, l2=2, l3=4.

а)

б)

в)

г)

д)

е)

ж)

з)	и)	к)

л)

м)

н)

Рис. 3.5

Теперь для каждого графа рис. 3.5 построим таблицы (3.37) в соответствии с условиями (3.38) и (3.39). В результате получим таблицы (3.40),

среди которых имеются одинаковые ( Tв и Tг' ; Tд и Tе' ; Tи и Tк' ), но они отражают различные графы соответственно: в) и г); д) и е); и) и к).

Если необходимо построить все графы, то помимо степени вершин можно ввести ещѐ один их параметр, например их смежность. Этот вариант построения таблиц T будет рассмотрен в конце данного параграфа, так как он рассчитан на применение ЭВМ.

Τ

à

Tä

4	3, 3, 2, 2				4			3, 3, 2, 2			4						3, 3, 2, 2			4					3, 3, 2, 2
3					3			4, 3, 2			3		4, 3, 2							3		4, 3, 2
	4, 3, 2
3					3		4, 3, 2				3					4, 3, 2					3			4, 3, 2
	4, 3, 2
2				4, 3	T 2					4, 2	T 2								4, 2	T' 2							4, 2
					á						â									ã
2		4, 2			2		4, 2							2			4, 2			2	4, 2
2		3, 2			2	3, 3					2				3, 2					2	3, 2
2		2, 2			2		2, 2				2						3, 2			2	3, 2

4		3, 3, 2, 2				4	3, 3, 2, 2			4	3, 3, 2, 2			4				3, 3, 2, 2
3	4, 2, 2					3	4, 2, 2			3	4, 2, 2			3			4, 2, 2
3	4, 2, 2						4, 2, 2			3	4, 2, 2			3			4, 2, 2
2				4, 3	T'	2			4, 3	T 2			4, 3	T 2						4, 2
					å					æ				ç
																					3.42
2		4, 3				2	4, 3			2	4, 2			2		4, 2
2		3, 2				2	3, 2			2	3, 3			2		3, 3
2		3, 2				2	3, 2			2	3, 2			2	3, 3

	4	3, 2, 2, 2			4		3, 2, 2, 2			4				3, 2, 2, 2			4				3, 2, 2, 2			4			2, 2, 2, 2
	3				3		4, 3, 2			3			4, 3, 2				3		4, 2, 2					3		3, 2, 2
		4, 3, 2
	3				3					3							3							3
		3, 2, 2					3, 2, 2						3, 2, 2						2, 2, 2							3, 2, 2
T'	2			4, 3	T 2				4, 3	T 2						4, 3	T 2						4, 3	T 2					4, 3
è					ê					ë							ì							í
	2	4, 3			2	4, 3				2	4, 2						2	4, 3						2	4, 3
	2	4, 2			2		4, 2			2		4, 2								4, 3				2	4, 3
	2	3, 2			2	3, 2				2	3, 3						2	3, 3						2	4, 3

3.6.3.Синтез графов.

Наоснове вышеизложенногозадача генерации графов сводится к составлению разбиений согласно (3.33) и смежностно-степенных таблиц в соответствии с (3.36) – (3.39).

По своей сущности задача синтеза графов состоит в выборе на множестве вершин V из их декартового произведения V V (т.е. из полного графа, в котором каждая вершина соединена со всеми остальными вершинами) множества рѐбер [q пар (vi,vj)]. Осуществляют этот выбор в последовательности, не допускающей пропуска синтеза какого-нибудь графа и синтеза изоморфных графов.

Построение графа по разбиению осуществляют в таком порядке. Нумеруют вершины в соответствии с неравенствами (3.33). Потом соединяют

i–ю вершину, имеющую степень deg vi pi , c i 1, i 2					и т.д. Так как ранее vi
была	соединена i-1		рѐбрами	с предшествующими,	то она	оставшимися
pi 1 i 0		рѐбрами	соединяется с вершинами, имеющими			номера от
i 1	до i pi 1 i pi 1.			Начинают синтезировать граф с i=1, причѐм
для всех i		> 1 следят за тем,		чтобы текущие степени degvi не превысили

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

Пример 4. Построим графы по разбиению 3=(4, 3, 3, 2, 2, 2) из примера 1. нанесѐм и пронумеруем шесть вершин. соединим вершину v1, имеющей

deg v1 p1 4 , ребрами с вершинами, у которых номера изменяются от

i 1 2 до p1 1 5. В результате образуется подграф, изображѐнный на рис. 3.6. Далее вершина v2 соединяется p2– 1= 2 рѐбрами с вершинами 3 и 4 (рис. 3.6, б). У вершины v3 осталось только одно ребро, которое следует соединить с вершиной v6 (рис. 3.6, в), так как вершина v4 уже имеет степень 2, заданную разбиением. присоединение ребра к вершине 5 приведѐт к несвязному графу, ибо степени вершин с i 5 уже будут соответствовать заданному разбиению, а вершину 6 не подсоединить к этой части графа, не нарушив разбиение. С помощью последнего ребра, соединив вершины v5 и v6 , образуем окончательный граф (рис. 3.6, г). Подчеркнѐм, одному разбиению могут соответствовать несколько неизоморфных графов.

а)	1	4	б)	1	4	в)	1	4
		2	5		2	5		2
	5
	6	3	6		3		6	3
г)	1	4	д)			е)	1	4
				1	4
5			2		2
						5
			5
								2
	6							6
		3	6		3			3

Рис. 3.6

3.6.3. Методика синтеза графа по смежностно-степенным таблицам

1. Представим CCТ в виде 2q мерного вектора и для сравнения двух синтезированных таблиц одинакового размера

(t11,t12, , t1p		,t21,t22, , t2 p ,..., t		l21	, t	l2		2	, , t	,..., tv2 , ,tvp ) tij
1			2							l2 p2	lk
и введѐм	отношение линейного порядка
tij' T '	T tij t11'		, t12' , ,tvp'					t11, t12 , ,tvp ,			(3.43)
				v						v
которое понимается лексикографически.
Для таблиц		Tа - Tм	(3.40)	первые четыре элемента							векторов

(ta ) (tм ) идентичны, но уже следующие 6 элементов (4,3,2,4,3,2) идентичны

только у таблиц Tа – Tг, наконец,		(ta ) (tб ) (tв ) (tг ) , так как выделенные
значками	элементы	соответствующих		векторов
(3,3,2,2,4,3,2,4,3,2,4, 3, 4,2,3,2,2,2)>(3,3,2,2,4,3,2,4,3,2,4, 2, 4,2,3,			3	,2,2)>(3,3,2,2,4,3,
2,4,3 ,2,4,2,4,2,3,	2, 3,2) определяют нумерацию графов и таблиц согласно с

лексикографическим отношением 3 2; 3 2 . Именно так все графы рис.3.5 и их таблицы (3.40) лексикографически упорядочены.

2.Пересоединением вершин графа в рамках заданного разбиения строят CCТ с максимальным вектором (tij) . Присваивают ей номер один и называют канонической для данного разбиения. Методика построения этой таблицы аналогична вышеизложенному алгоритму генерации графа по разбиению.

3.Очередную CCТ получают из предыдущей путѐм минимального лексикографического еѐ уменьшения. На графе этому преобразованию CCТ соответствует пересоединение двух-трѐх рѐбер между вершинами, имеющими возможно большие номера.

Заметим, что при проведении такой операции всегда происходит изменение tijкак минимум в четырѐх строках (вершинах) i при заданном числе рѐбер. Во-первых, в двух строках соединяемых ребром. Во-вторых, чтобы сохранить разбиение , удалѐнное ребро должно быть также подсоединено к двум вершинам, а именно к тем, у которых степени pi были изменены.

4. При изменении элементов ССТ надо учитывать, что строки с одинаковыми элементами неразличимы, что нельзя нарушать неравенство l deg vi и что сумма квадратов элементов CCТ постоянна и равна

v

pi2 const (3.44) i 1

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

Пример 5. Построим все CCТ для разбиения i=(3,3,3,3,2,2) из примера 1 множества графов Г(6,8). Построение CCТ T1 начнѐм с соединения вершины

v1c вершинами v2-v4. Поэтому на первом шаге T11 образуется первая строка,

содержащая степени вершин v2-v4 и столбец, указывающий, что v2 - v4 соединены с вершиной, степень которой равна p1=3. Покажем все шаги построения Т1 (верхние индексы в скобках указывают номер шага):