X Международная студенческая научная конференция Студенческий научный форум - 2018

В очень многих случаях при решении разнородных задач, допускающих графовую интерпретацию, приходится сталкиваться с задачей агрегирования. К ней сводятся задачи: размещение графов, разрезание (кластеризация графов) и т.д. [1]

Было замечено, что удачное их решение приводит к графам, характеризующимся матрицами смежности, тождественными исходным, но имеющим специфический вид: возможное наибольшее количество единиц матрицы смежности оказывается вблизи ее главной диагонали, либо внутри ленты заданной ширины, либо внутри блоков заданных размеров. [1,2]

Обычно решение этих задач производится прямо, т.е. выполняются графовые преобразования. Матрица же используется как структура данных, задающая граф. Известно и обратное решение: преобразуется чисто матрица. Результату преобразования соответствует граф. Интересно, что такая постановка имеет смысл и для неграфовых задач, особенно описывающихся так называемыми разрешенными матрицами. Разряженной называют матрицу, имеющую небольшой процент ненулевых элементов. [2,3,4]

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

Диагональные блочные формы матрицы. Диагональная блочная форма представляет собой матрицу, у которой для всех i ≠ j подматрицы A[i,j] и все диагонали подматрицы A[i,j] являются квадратными подматрицами. Очевидно, что граф, соответствующий матрице, приведенной к такой форме, состоит из несвязных подграфов, и каждый подграф соответствует отдельному диагональному блоку (рис.1). Ниже описывается три эвристических алгоритма, приводящие матрицу к интересующему нас виду, и оценивается их эффективность.

1	2	3	4	5	6	7	8	9	10
1	1	1
1	1
1		1
			1		1	1
				1		1
			1		1	1
			1	1	1	1
							1	1
							1	1
									1

рис.1.

На рис. 1 представлена первая из них. Это так называемая полная диагональная блочная форма. Она соответствует случаю, когда исходный граф состоит из полных несвязанных подграфов. Каждый подграф характеризуется блоком по диагонали. Если подграфы связаны, то имеет место неполная диагональная блочная форма. Здесь в диагональных блоках при­сутствуют ненулевые элементы, а вне их есть и ненулевые (рис.2). Нас интересует случай, когда между блоками будет минимум единичных элементов.

1	2	3	4	5	6	7	8
1			1
	1	1	1	1
1	1	1	1
	1	1	1	1	1	1
			1	1	1	1
			1		1	1
			1	1	1	1	1
						1	1

Рис.2.

На рис.3 представлена так называемая полная ленточная матрица. Ширина ее ленты β=7.

1	2	3	4	5	6	7	8	9	10
1	1	1	1
1	1	1	1	1
1	1	1	1	1	1
1	1	1	1	1	1	1
	1	1	1	1	1	1	1
		1	1	1	1	1	1	1
			1	1	1	1	1	1	1
				1	1	1	1	1	1
					1	1	1	1	1
						1	1	1	1

Рис.3.

На рис.4 показана неполная ленточная матрица. Здесь β=5. Неполную ленточную матрицу называют обычно просто ленточной матрицей. Нас интересует случай ленточной матрицы с минимально возможной шириной ленты.

1	2	3	4	5	6	7	8
1			1
	1	1	1	1
1	1	1	1
	1	1	1	1	1	1
			1	1	1	1
			1		1	1
			1	1	1	1	1
						1	1

Рис.4.

На рис.5 показана частичная ленточная матрица. В ней единицы присутствуют и вне ленты. Нас интересует так называемая минимальная частичная ленточная матрица, т.е. неполная ленточная матрица, у которой возможное наибольшее число единиц приведено в ленту заданной ширины. Введем в рассмотрение минимум – минимальную матрицу. Это такая минимальная частичная матрица, у которой ширина ленты минимально возможная. Напомним, что все выделенные виды матриц характеризуют “хорошие” решения таких разновидностей задачи агрегирования, как размещение графов, разрезание графов и т.д. В качестве примера на рис.5 показан результат решения задачи размещения. На рис.5а приведен исходный граф, а на рис. 5б результирующий. Им соответствуют матрицы, приведенные на рис.5а и 5б соответственно. В качестве алгоритма использован алгоритм [3].

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
							1			1			1	1
		1	1	1	1		1		1		1			1	1
	1						1					1			1
	1				1	1	1	1
	1				1	1						1			1
	1		1	1					1						1
		1	1					1	1
1	1	1	1										1
			1			1			1
	1				1	1					1
1								1			1			1
	1								1	1			1
		1		1									1	1
1							1				1	1
1	1					1				1		1
	1	1		1	1

Рис.5а.

5	6	10	7	16	2	4	9	3	8	12	11	13	14	1	15
	1		1	1	1							1
1		1		1	1	1
	1		1		1					1
1		1				1	1								1
1	1				1			1
1	1	1		1		1	1	1	1	1
	1		1		1		1		1
			1		1	1					1
				1	1				1			1
					1	1		1					1	1
		1			1						1		1
							1			1				1	1
1								1					1		1
									1	1		1		1
										1	1		1		1
			1								1	1		1

Рис.5б.

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

Библиографический список

Браверман Э.М. и др. Структурные методы обработки эмпирических данных. - М.: Наука, 1982.

Кодачигов В.И., Бондарев А.И. Минимальные матрицы и некоторые их применения // Автоматизация проектирования, программирования и конструирования. – Таганрог: изд-во ТРТИ, 1982.

Курейчик В.М. и др. Методы разбиения схем РЭА на конструктивно-законченные части. - М.: Сов. Радио, 1978.

Тьюарсон Д. Разреженные матрицы. - М.: Мир, 1975.

Курейчик В.М. Генетические алгоритмы. – Таганрог: изд-во ТРТУ, 1998.

Код для цитирования: Скопировать