Матричная интерпретация и матричное решение задачи агрегирования

В очень многих случаях при решение разнородных задач

,

допускающих графовую интерпретацию

,

далее

рассматриваются только неориентированные не взвешенные графы без кратных ребер

.

Приходится сталкиваться с

задачей агрегирования

.

К ней сводятся задачи

:

размещение графов

,

разрезание

(

кластеризация графов

)

и т

.

д

.

Было

замечено

,

что

удачное

их

решение

приводит

к

графам

,

характеризующимся

матрицами

смежности

,

тождественными исходным

,

но имеющим специфический вид

:

возможное наибольшее количество единиц матрицы

смежности

оказывается вблизи ее главной диагонали

,

либо внутри ленты заданной ширины

,

либо внутри блоков

заданных размеров

.

Обычно решение этих задач производится прямо

,

т

.

е

.

выполняются графовые преобразования

.

Матрица же

используется как структура данных

,

задающая граф

.

Известно и обратное решение

:

преобразуется чисто матрица

.

Результату преобразования соответствует граф

.

Интересно

,

что

такая

постановка

имеет

смысл

и

для

неграфовых

задач

,

особенно

описывающихся

так

называемыми разрешенными матрицами

.

Разряженной называют матрицу

,

имеющую небольшой процент ненулевых элементов

.

В силу указанных выше причин и некоторых других

,

нас будут интересовать не любые разреженные матрицы

,

а

только разреженные симметричные квадратные матрицы

,

допускающие тождественные преобразования к ленточной

форме

,

блочной ленточной форме и к некоторым их разновидностям

.

Рассмотри более подробно некоторые формы разреженных матриц

,

интересующие ввиду рассматриваемых задач

,

и обсудим некоторые подходы к построению алгоритмов непосредственного преобразования их к указанному выше

виду

.

1.

Диагональные блочные формы матрицы

.

Диагональная блочная форма представляет собой матрицу

,

у

которой для всех

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

Рис

.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

б

-

результирующий

.

Им соответствуют

матрицы

,

приведенные на рис

.6

а и

6

б соответственно

.

В качестве алгоритма использован алгоритм

.

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

б

Хорошо видно

,

что ненулевые элементы матрицы смежности

,

определяющей результирующий граф

,

по сравнению с

матрицей смежности

,

соответствующей исходному графу

, “

прижимаются

”

к главной диагонали

.