Поиск множества максимальных клик на основе метода построения дополнительного графа
В работе представлен способ поиска множества максимальных клик в графе. Данный способ основан на методе построения дополнительного графа-пирамиды, что позволяет легко распараллеливать вычисления. Вычислительная сложность представленного способа зависит линейно от количества максимальных клик в...
Збережено в:
| Опубліковано в: : | Штучний інтелект |
|---|---|
| Дата: | 2011 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/59843 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Поиск множества максимальных клик на основе метода построения дополнительного графа / А.В. Агарков // Штучний інтелект. — 2011. — № 3. — С. 190-199. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-59843 |
|---|---|
| record_format |
dspace |
| spelling |
Агарков, А.В. 2014-04-10T12:17:28Z 2014-04-10T12:17:28Z 2011 Поиск множества максимальных клик на основе метода построения дополнительного графа / А.В. Агарков // Штучний інтелект. — 2011. — № 3. — С. 190-199. — Бібліогр.: 8 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/59843 004.931, 519.174 В работе представлен способ поиска множества максимальных клик в графе. Данный способ основан на методе построения дополнительного графа-пирамиды, что позволяет легко распараллеливать вычисления. Вычислительная сложность представленного способа зависит линейно от количества максимальных клик в графе. При решении конкретных задач (распознавании изображений, например) данный способ позволяет ускорять получение решения. Это достигается за счёт сокращения числа строящихся вершин и рёбер путём использования при их построении дополнительных условий, которые учитывают специфику задачи. This paper presents a method of finding the set of maximal cliques in a graph. This method is based on the method for constructing complementary graph-pyramid that makes it easy to parallelize computations. The computational complexity of the given method linearly depends on number ofmaximal cliques in a graph. For specific tasks (for example, image recognition) this method stimulates solutions. This is achieved by reducing number of constructed vertices and edges by the additional conditions in their construction, which take into account characteristics of the tasks. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений Поиск множества максимальных клик на основе метода построения дополнительного графа Search of the Set of Maximal Cliques Based on the Method for Constructing Complementary Graph Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Поиск множества максимальных клик на основе метода построения дополнительного графа |
| spellingShingle |
Поиск множества максимальных клик на основе метода построения дополнительного графа Агарков, А.В. Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений |
| title_short |
Поиск множества максимальных клик на основе метода построения дополнительного графа |
| title_full |
Поиск множества максимальных клик на основе метода построения дополнительного графа |
| title_fullStr |
Поиск множества максимальных клик на основе метода построения дополнительного графа |
| title_full_unstemmed |
Поиск множества максимальных клик на основе метода построения дополнительного графа |
| title_sort |
поиск множества максимальных клик на основе метода построения дополнительного графа |
| author |
Агарков, А.В. |
| author_facet |
Агарков, А.В. |
| topic |
Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений |
| topic_facet |
Интеллектуальные интерфейсы и распознавание образов. Системы цифровой обработки изображений |
| publishDate |
2011 |
| language |
Russian |
| container_title |
Штучний інтелект |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| format |
Article |
| title_alt |
Search of the Set of Maximal Cliques Based on the Method for Constructing Complementary Graph |
| description |
В работе представлен способ поиска множества максимальных клик в графе. Данный способ основан на
методе построения дополнительного графа-пирамиды, что позволяет легко распараллеливать вычисления.
Вычислительная сложность представленного способа зависит линейно от количества максимальных клик
в графе. При решении конкретных задач (распознавании изображений, например) данный способ позволяет
ускорять получение решения. Это достигается за счёт сокращения числа строящихся вершин и рёбер
путём использования при их построении дополнительных условий, которые учитывают специфику задачи.
This paper presents a method of finding the set of maximal cliques in a graph. This method is based on the
method for constructing complementary graph-pyramid that makes it easy to parallelize computations. The
computational complexity of the given method linearly depends on number ofmaximal cliques in a graph. For
specific tasks (for example, image recognition) this method stimulates solutions. This is achieved by reducing
number of constructed vertices and edges by the additional conditions in their construction, which take into
account characteristics of the tasks.
|
| issn |
1561-5359 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/59843 |
| citation_txt |
Поиск множества максимальных клик на основе метода построения дополнительного графа / А.В. Агарков // Штучний інтелект. — 2011. — № 3. — С. 190-199. — Бібліогр.: 8 назв. — рос. |
| work_keys_str_mv |
AT agarkovav poiskmnožestvamaksimalʹnyhkliknaosnovemetodapostroeniâdopolnitelʹnogografa AT agarkovav searchofthesetofmaximalcliquesbasedonthemethodforconstructingcomplementarygraph |
| first_indexed |
2025-11-25T22:31:32Z |
| last_indexed |
2025-11-25T22:31:32Z |
| _version_ |
1850565557771829248 |
| fulltext |
«Искусственный интеллект» 3’2011 190
4А
УДК 004.931, 519.174
А.В. Агарков
Институт проблем искусственного интеллекта МОН Украины и НАН Украины,
г. Донецк
aav@iai.donetsk.ua
Поиск множества максимальных клик
на основе метода построения
дополнительного графа
В работе представлен способ поиска множества максимальных клик в графе. Данный способ основан на
методе построения дополнительного графа-пирамиды, что позволяет легко распараллеливать вычисления.
Вычислительная сложность представленного способа зависит линейно от количества максимальных клик
в графе. При решении конкретных задач (распознавании изображений, например) данный способ позволяет
ускорять получение решения. Это достигается за счёт сокращения числа строящихся вершин и рёбер
путём использования при их построении дополнительных условий, которые учитывают специфику задачи.
Введение
В последнее время во многих работах для распознавания изображений используется
их описание в виде графов, каждой вершине которого соответствует определённая
область изображения [1-5]. При таком подходе поиск объекта на изображении сводится
к поиску подграфа, ему соответствующего. Данный подграф выделяется путём сравнения
графов описывающих рассматриваемое изображение и искомый объект, что приводит к
задаче поиска наибольшей максимальной клики в ассоциированном графе. Однако в
более общем случае искомых объектов на изображении может быть более одного, что
означает необходимость поиска всех возможных максимальных клик.
Одним из эффективных для поиска множества максимальных клик в графе на дан-
ный момент является алгоритм Брона-Кербоша [6]. Его вычислительная сложность
линейна относительно количества клик в графе. Однако данный алгоритм не может быть
распараллелен, что при современной тенденции к увеличению производительности ком-
пьютеров за счёт многоядерности/многопроцессорности и параллельных вычислений
является недостатком.
В настоящей работе предлагается способ поиска множества максимальных клик
на основе метода построения дополнительного графа [7], [8]. Данный метод сам по себе
может быть легко распараллелен, что влечёт за собой возможность распараллеливания и
предлагаемого способа. Его вычислительная сложность, так же, как и алгоритма Брона-
Кербоша, линейна относительно количества клик в графе.
Далее в работе описаны основы метода построения дополнительного графа-пи-
рамиды, а затем и сам предлагаемый способ, основанный на нём.
Целью данной работы является разработка способа поиска множества макси-
мальных клик в графе, который не требует значительных вычислительных затрат, поз-
воляет учитывать специфику решаемых задач и может быть распараллелен.
Поиск множества максимальных клик на основе метода построения...
«Штучний інтелект» 3’2011 191
4А
Построение дополнительного графа-пирамиды
Пирамидой на графе G называется граф P, имеющий следующие свойства:
– каждая вершина пирамиды jiv , принадлежит определённому уровню i ;
– уровни пирамиды упорядочены от нижнего (первого) до верхнего (последнего)
( Ni ,...,1 );
– каждой вершине пирамиды jiv , соответствует подграф )( , jivp , принадлежащий
предыдущему уровню (для вершин начального уровня – это подграфы графа G, т.е.
предыдущим для первого уровня (т.е. нулевым) является сам граф G);
– каждой вершине пирамиды jiv , соответствует подграф )( , jivg , принадлежащий
графу G;
– каждая из вершин подграфа )( , jivp является родителем для вершины jiv , , ко-
торая, в свою очередь, является дочерней для всех вершин множества )( , jivp ;
– каждая вершина пирамиды соединена рёбрами (которые называются межуров-
невыми) со всеми своими родителями;
–
jiv , является предком для klv , , а klv , для jiv , является, соответственно, потомком
( li ), если существует цепь, их соединяющая, которая образована только межуровне-
выми рёбрами, между дочерними и родительскими вершинами, причём не существует
вершин, принадлежащих данной цепи, лежащих в общем уровне;
– множество родителей )( , jivp вершины jiv , образуют подграф, который является
родительским для вершины jiv , ;
– вершина пирамиды P, не имеющая дочерних вершин, называется верхушкой
пирамиды.
Пирамида образуется в результате построения, т.е. начиная с основного графа (ну-
левого уровня) проводится следующая процедура – граф, соответствующий одному
уровню, разбивается на подграфы, для каждого из которых в следующем уровне соз-
даётся новая вершина. Эти новые вершины являются дочерними для вершин соответ-
ствующих подграфов предыдущего уровня, которые, в свою очередь, являются родителями
для новозаведенных вершин.
На рис. 1 представлен пример пирамиды, построенной на графе, состоящем из
вершин a, b, c, d, который представляет собой цепь. Пунктирными линиями обозначены
уровни пирамиды. В данной пирамиде три уровня (нулевой уровень – исходный граф).
Если рассмотреть отдельную вершину 1,2v , принадлежащую второму уровню, то для неё
родителями являются вершины 1,1v и 2,1v , принадлежащие первому уровню. Дочерней
для данной вершины является 1,3v . Данная вершина имеет с 2,2v общего родителя 2,1v ,
поэтому 1,2v и 2,2v соединены ребром. Подграф основного графа, который соответ-
ствует 1,2v , образован вершинами a, b, c.
Вершина 1,3v не имеет дочерних вершин, поэтому является верхушкой данной
пирамиды, и ей соответствует весь основной граф. Она является потоком для всех
остальных вершин этой пирамиды, которые, в свою очередь, являются предками для
верхушки.
Таким образом, каждый уровень пирамиды, представляет собой граф, каждой вер-
шине которого соответствует подграф предыдущего уровня. Вершины данного подграфа
Агарков А.В.
«Искусственный интеллект» 3’2011 192
4А
соединяются рёбрами, если подграфы, которые им соответствуют, пересекаются. Кроме
того, ребрами могут соединяться другие вершины одного уровня, удовлетворяющие пра-
вилу построения пирамиды.
Рисунок 1 – Пример пирамиды
Пирамида может быть построена в соответствии с единым правилом создания вер-
шин нового (следующего) уровня. К примеру, пирамида, представленная на рис. 1, по-
строена по следующему правилу – если две вершины одного уровня соединены ребром,
то создаётся вершина следующего уровня, для которой данная пара является родите-
лями; каждая такая пара может иметь только одну дочернюю вершину.
Построение пирамиды для поиска множества клик
Вид пирамиды и то, какие подграфы соответствуют вершинам пирамиды, зависит
от правил её построения. Если необходимо, чтобы данные подграфы обладали опреде-
лённым свойством, необходимо в качестве подграфов разбиения выбирать такие, ко-
торые бы этим свойством обладали. Новые же вершины пирамиды следует соединять
рёбрами только в том случае, если объединение соответствующих им подграфов раз-
биения также обладает необходимыми свойствами.
Так, если целью является поиск множества клик, необходимо, чтобы подграфы
разбиения являлись кликами, а новые вершины пирамиды соединялись ребрами только
в том случае, если их объединение также является кликой. Если придерживаться дан-
ных правил при построении пирамиды, то каждой её верхушке будет соответствовать
клика.
Однако этого не достаточно для того, чтобы найденные клики были максималь-
ными и образовывали множество всех клик рассматриваемого графа. В двух случаях
будет наблюдаться пропуск решений, т.е. не всем максимальным кликам рассматри-
ваемого графа будут соответствовать вершины пирамиды.
В первом случае это связано с тем, что объединение двух клик может не являться
кликой, вследствие того, что некоторые вершины, принадлежащие данным подграфам,
могут не быть смежными. Кликой может являться объединение неких подграфов дан-
ных клик. Причем, чем больше данные клики – тем больше может быть количество
вариантов.
Поиск множества максимальных клик на основе метода построения...
«Штучний інтелект» 3’2011 193
4А
Во втором случае пропуск решений связан с тем, что возможен такой выбор под-
графов разбиения, при котором некоторые клики не будут иметь общего потомка, что
приведёт к пропуску решений. Для того чтобы не было пропусков решений, необходимо и
достаточно, чтобы все клики-тройки оставались в рассмотрении, т.е. имели хотя бы
одного общего потомка.
Для того чтобы избежать пропусков решений в первом случае, необходимо учесть
все варианты объединения частей подграфов разбиения, которые дают клики. Для этого
необходимо подграфы разбиения, в свою очередь, тоже разбивать на более мелкие под-
графы и ставить им в соответствие новые вершины пирамиды, что, конечно же, ведёт к
росту количества вершин в пирамиде. Поэтому количество вершин в подграфах раз-
биения должно быть как можно меньше, чтобы сократить количество возможных ва-
риантов.
Наиболее подходящей для решения данной задачи является ребёрная пирамида, у
которой в качестве подграфов разбиения выступают пары смежных вершин. То есть
каждой вершине данной пирамиды соответствует ребро с инцидентными ей вершинами.
Данное обстоятельство позволяет избегать создания новых вершин пирамиды, соответ-
ствующих подграфам подграфов разбиения. Действительно, если объединение двух пар
смежных вершин пирамиды кликой не является, но является кликой объединение одной
пары с только одной вершиной другой пары – это достаточно отразить созданием нового
ребра между новой вершиной и единичной вершиной другой пары, что исключит про-
пуск данной клики. Данная единичная вершина оказывается расположенной как бы на
нескольких уровнях пирамиды сразу – это является следствием того, что вместо создания
новой вершины пирамиды, соответствующей только одной вершине предыдущего уровня,
создается новое ребро, соединяющее вершины разных уровней. Следует отметить, что
данные вершины не состоят в родстве (одна не является ни потомком, ни предком дру-
гой), хотя и соединены межуровневым ребром. Данному межуровневому ребру соответ-
ствует клика из трех вершин одного уровня пирамиды – вершины, инцидентной меж-
уровневому ребру, и пары смежных вершин, инцидентных ребру, на котором построена
вершина следующего уровня.
Для того чтобы не было пропусков решений, соответствующих второму случаю,
необходимо и достаточно, чтобы все клики-тройки оставались в рассмотрении. Для
этого необходимо, чтобы каждой клике-тройке либо соответствовало межуровневое
ребро, либо существовало ребро-прообраз для вершины следующего уровня, объедине-
ние с которым данной клики-тройки являлось также кликой.
Если построение новых вершин пирамиды начинать с создания межуровневых
рёбер, то это позволяет унифицировать алгоритмы для создания рёбер между вершина-
ми пирамиды и избежать пропусков решений первого случая.
Действительно, рассмотрим построение ребёрной пирамиды для поиска множест-
ва максимальных клик, с использованием межуровневых рёбер. Для этого обозначим:
),( PP EVP – пирамида;
0E – множество рёбер пирамиды, которые могут быть использованы для по-
строения новых вершин;
1E – множество рёбер пирамиды, которые использовались для построения новых
вершин пирамиды;
2E – множество рёбер пирамиды, которые входят в подграфы-клики, соответ-
ствующие объединению клик, вершины которых соединены ребром;
0V – множество вершин пирамиды, инцидентных рёбрам из множества 0E ;
kijikji vvpvvpvvvp )(,)(),,()( 21 – пара родительских вершин вершины iv ;
Агарков А.В.
«Искусственный интеллект» 3’2011 194
4А
),()( kji vveve – ребро, на котором построена вершина пирамиды iv ;
)( ivg – подграф исходного графа G , который соответствует вершине пирамиды iv ;
T – множество всех клик-троек пирамиды;
Q – множество всех клик пирамиды;
IE – множество межуровневых рёбер пирамиды;
ji eE – операция добавления ребра je в множество iE ;
ji eE – операция удаления ребра je из множества iE ;
Aa – создание нового элемента a множества A .
Условие образования межуровневого ребра между вершинами пирамиды iv и
jv , где iv – вершина более высокого уровня, чем jv , имеет вид:
P
jiji EvveTvvp ),()( . (1)
Условие образования ребра между вершинами одного уровня iv и jv имеет вид:
P
jiji EvveQvpvp ),()()( , (2)
что при условии наличия уже образованных межуровневых рёбер можно переписать
в виде
P
jijiji EvveTvvpTvpv ),()()( .
Причём очевидно, что
TvvpTvpv jiji )()( ,
поэтому условие (2) можно переписать в виде:
P
jiji EvveTvvp ),()( ,
что совпадает с (1). Таким образом, для построения новых рёбер достаточно исполь-
зовать одно условие, что даёт возможность применения только одного алгоритма.
Необходимо, однако, вначале соединять новые вершины со старыми, а потом с друг
другом, т.е. начинать построение новых рёбер с межуровневых.
При образовании нового ребра ),( ji vve oно автоматически добавляется в мно-
жество 0E , а ребра )(, 1 ji vpve , )(, 2 ji vpve , )(, 1 ij vpve , )(, 2 ij vpve удаляются из
0E и добавляются в 2E . Это препятствует образованию новых вершин iv и jv , для
которых )()()()( jjji vgvgvgvg , что позволяет избегать наличия вершин, со-
ответствующие графы которых совпадают.
Если после построения всех новых рёбер остались межуровневые рёбра, принад-
лежащие множеству 0E , то это означает, что объединение подграфов, отвечающих двум
соответствующим новым вершинам, кликой не является. Однако является кликой объе-
динение их частей, т.е. учитывается первый случай, описанный выше, и не происходит
пропуска решений.
Таким образом, построение межуровневых рёбер позволяет упростить процесс
построения рёбер между новыми вершинами пирамиды и избежать попуска решений,
связанных с первым случаем.
Для того чтобы избежать пропусков решений, связанных со вторым случаем,
необходимо выбирать множество 1E таким образом, чтобы выполнялось условие для
клик-троек:
QevvtEvveeTt jiji );,(:),( 1 . (3)
Поиск множества максимальных клик на основе метода построения...
«Штучний інтелект» 3’2011 195
4А
Следует также заметить, что рёбра для множества 1E должны выбираться таким
образом, чтобы в каждой клике-тройке было не более одного такого ребра
teeeeEeeTt jijiji ,;:, 1 . (4)
Это условие необходимо для того, чтобы избежать образования вершин пира-
миды с совпадающими соответствующими подграфами, т.е. для того, чтобы избежать
повторных решений.
Обозначим
kjikji tvvTtvveT ),(:),( – множество клик-троек, которым принадлежит ребро
e и пара инцидентных ей вершин.
Условие добавления ребра e в множество 1E :
eEeEteEeeTtEe ii 1010 ,,:)(, . (5)
То есть при соблюдении данного условия ребро удаляется из множества 0E и до-
бавляется в множество 1E . Перебрав таким образом все ребра из множества 0E форми-
руется множество 1E . Для того чтобы обозначить принадлежность рёбер к тому или иному
множеству, каждому их них присваивается соответствующий маркер. Таким образом,
перенос ребра из одного множества в другое сводится к смене маркера данного ребра.
При таком способе заполнения 1E условие (4) будет выполнено в силу правила
формирования данного множества.
Однако выполнение условия (3) сужает множество возможных вариантов для 1E ,
что усложняет его формирование. Для того чтобы обойти эту трудность, исполь-
зуется следующий приём – если для рассматриваемого ребра e (5) не соблюдается,
но соблюдается условие
QttEeteeTteTtEe jiljlji )(;,:)(:)(, 10 , (6)
то создаётся ребро ),(:),( jijiN vveevvee , которое добавляется в множество 1E . То
есть создаётся копия рассматриваемого ребра, которая и добавляется в 1E . А само ребро
из множества 0E переносится в множество 2E – eEeE 20 , . При создании новых
рёбер, инцидентных новым вершинам пирамиды, учитывается смежность, соответствую-
щая только рёбрам из множеств 0E и 2E . Этот приём позволяет оставить в рассмотрении
все клики-тройки, не допустить создания вершин с совпадающими соответствующими
подграфами и не создавать специального алгоритма выбора рёбер для множества 1E .
Таким образом, учитывая всё вышесказанное, построение одного уровня пирами-
ды выглядит следующим образом:
1) формирование множества 1E из рёбер, принадлежащих множеству 0E ;
2) создание новых вершин на основе рёбер из множества 1E ;
3) создание новых рёбер, инцидентных новым вершинам с одновременным фор-
мированием множества 0E .
Построение пирамиды ведётся до тех пор, пока множество 0E остаётся непустым.
Построение пирамиды ),( PP EVP начинается с её инициализации исходным гра-
фом ),( EVG , т.е. перед началом создания первого уровня пирамиды выполняется от-
ношение ),(),( EVGEVP PP . Также перед началом создания первого уровня все рёбра
пирамиды добавляются в множество 0E , т.е. в начале PEE 0 .
Агарков А.В.
«Искусственный интеллект» 3’2011 196
4А
Обозначим
},:{)( iii teTtteT ,
)}(},,{,:{),( eTtvvvEvvvveV kji
P
kkjiT ,
j
ie – i -е ребро принадлежащее множеству jE ,
)(AN – мощность множества A ,
}),(,:{)( 11 eeeTteEeeeE iiii .
С учётом введенных обозначений условие (5) переписывается в виде:
)( 0
1 ieE ,
а условие (6) – в виде:
QtteEeTteTt jilji )()),((:)( 1 .
Тогда алгоритм формирования множества 1E из рёбер, принадлежащих множеству
0E , на псевдокоде записывается в следующем виде:
1GetE
{
))(,...,1( 0ENifor // цикл по всем 0
0 Eei
{
QtteEeTteTtif jlikjil )()),((:)( 0
1
0
{
)( 0
1 ieEif
{
0
0 ieE ;
0
1 ieE ;
}
else
{
PN Ee ;
)),(:,( 0
mnimn
N vveevvee ;
0
0 ieE ;
0
2 ieE ;
NeE 1 ;
)))(()(/()()(
)(
00
0
1
ik eEe kii
N eTeTeTeT
;
)))(()(/()()(
)(
00
0
1
ik eEe kTiTiT
N
T eVeVeVeV
;
}
}
}
}
Алгоритм создания новых вершин на основе рёбер из множества 1E :
exsGetNewVert
{
P
NV ; // множество новых вершин пирамиды;
Поиск множества максимальных клик на основе метода построения...
«Штучний інтелект» 3’2011 197
4А
))(,...,1( 1ENifor
{
PN Vv ;
)),(:,()( 1
kjikj
N vveevvvp ;
NP
N vV ;
}
}
Алгоритм создания новых рёбер, инцидентных новым вершинам с одновременным
формированием множества 0E :
0sAndEGetNewEdge
{
))(,...,1( P
NVNifor // цикл по всем P
N
N
i Vv
{
)( n
ip vee ; // 1Ee
),( kjp vvee ;
)))((,...,1( pT eVNifor // цикл по всем )( pT
T
l eVv
{
)),(( T
l
N
i vveif
{
PN Ee ;
),( T
l
N
i
N vvee ;
NeE 0 ;
}
),(1 N
ij vvee ;
),(2 N
ik vvee ;
1
0 eE ;
1
2 eE ;
2
0 eE ;
2
2 eE ;
))(,()),(,( 21
N
i
T
l
N
i
T
l vpvevpveif
{
))(,( 1
3 N
i
T
l vpvee ;
))(,( 2
4 N
i
T
l vpvee ;
3
0 eE ;
3
2 eE ;
4
0 eE ;
4
2 eE ;
}
}
}
}
Агарков А.В.
«Искусственный интеллект» 3’2011 198
4А
Таким образом, алгоритм построения пирамиды для поиска множества макси-
мальных клик имеет вид
idBuildPyram
{
),(),( EVGEVP PP ;
PEE 0 ;
)( 0 Ewhile
{
1GetE ;
exsGetNewVert ;
0sAndEGetNewEdge ;
}
}.
После окончания построения пирамиды её верхушкам, т.е. вершинам, которые
являются смежными только со своими родителями, будут соответствовать максималь-
ные клики. Количество верхушек в пирамиде равно количеству всех максимальных
клик исследуемого графа ),( EVG . Количество предков отдельной верхушки есть )( qNO ,
где qN – число вершин в клике, соответствующей рассматриваемой верхушке.
При формировании множества рассматриваются все рёбра пирамиды, коли-
чество которых оценивается как )( 2
qNO . Для того чтобы провести проверку одного
ребра, необходимо проверить все клики-тройки, которым оно принадлежит. Количество
таких клик для одного ребра составляет )( qNO . Таким образом, вычислительная слож-
ность формирования множества 1E и создания вершин пирамиды, относящихся к одной
максимальной клике, составляет )( 3
qNO .
При создании рёбер, инцидентных одной вершине, необходимо проверить все смеж-
ные вершины родителей, количество которых оценивается как )( qNO . То есть вычи-
слительная сложность создания вершин пирамиды, относящихся к одной максимальной
клике, составляет )( 2
qNO . Вычислительная сложность создания подграфа пирамиды,
соответствующей одной максимальной клике, составляет )()()( 323
qqq NONONO .
Если количество всех максимальных клик составляет )( maxQN , а среднее количест-
во вершин в них оценить как )(/)( VNEN , где )(EN и )(VN – количество соответствен-
но рёбер и вершин в исследуемом графе, то оценка для вычислительной сложности
построения пирамиды составит 3
max )()()( VNENQNO .
Таким образом, вычислительная сложность построения пирамиды для поиска
множества максимальных клик зависит линейно от их количества.
Выводы
Предложенный в данной работе способ на основе метода построения дополни-
тельного графа-пирамиды позволяет эффективно проводить поиск множества макси-
мальных клик. Его вычислительная сложность, так же, как и алгоритма Брона-Кербоша,
зависит линейно относительно количества максимальных клик. Однако в отличие от
Поиск множества максимальных клик на основе метода построения...
«Штучний інтелект» 3’2011 199
4А
данного алгоритма предложенный способ легко распараллеливается. Действительно,
создание новых вершин и рёбер может осуществятся независимо друг от друга, т.е.
параллельно.
Следует также заметить, что при решении задач поиска и распознавания изобра-
жений (объектов) данный способ позволяет использовать дополнительные условия, от-
ражающие особенности искомого решения, при создании новых вершин и рёбер пирамиды.
Это позволяет сократить время распознавания, что достаточно важно для построения
систем реального времени и поиска по большим базам данных.
Таким образом, предложенный способ поиска множества максимальных клик в
графе, обладает рядом свойств, делающих его полезным для решения задач распозна-
вания образов, представленных в виде графов.
Литература
1. Alireza Ahmadyfard. Region-Based Object Recognition: Pruning Multiple Representations and Hypotheses /
Alireza Ahmadyfard, Josef Kittler // British Machine Vision Conference. – 2000. – P. 745-754.
2. Karin Kailing. Content-Based Image Retrieval Using Multiple Representations / Karin Kailing, Hans-
Peter Kriegel, Stefan Schonauer // Proc. 8th Int. Conf. on Knowledge-Based Intelligent and Engineering
System. – Wellington, New Zealand. – 2004. – LNAI 3214. – P.982-988.
3. Feng Tang. Object tracking with dynamic feature graph / Feng Tang, Hai Tao // 2nd Joint IEEE International
Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance. – 2005. – P. 25-32.
4. Агарков А.В. Структурное описание изображений в виде графа для решения задач распознавания /
А.В. Агарков // Бионика интеллекта. – 2009. – № 1(70). – С. 95-101.
5. Агарков А.В. Сегментация изображения на основе его описания в виде графа / А.В. Агарков //
Искусственный интеллект. – 2010. – № 3. – С. 274-282.
6. Bron C. Algorithm 457 – Finding all cliques of an undirected graph / С. Bron, J. Kerbosh // Comm. of
ACM. – 1973. – № 16. – P. 575.
7. Агарков А.В. Метод сравнения двух графов за полиномиальное время / А.В. Агарков //
Искусственный интеллект. – 2003. – № 4. – С. 172-184.
8. Агарков А.В. Поиск изоморфных пересечений двух графов за полиномиальное время / А.В. Агарков //
Искусственный интеллект. – 2007. – № 2. – С. 62-74.
Literatura
1. Ahmadyfard A. British Machine Vision Conference. 2000. P. 745-754.
2. Kailing K. Proc. 8th Int. Conf. on Knowledge-Based Intelligent and Engineering System. Wellington,
New Zealand. 2004. LNAI 3214. P. 982-988.
3. Feng Tang. 2nd Joint IEEE International Workshop on Visual Surveillance and Performance Evaluation
of Tracking and Surveillance. 2005. P. 25-32.
4. Agarkov A.V. Bionika intellekta. №.1 (70). 2009. S. 95-101
5. Agarkov A.V. Iskusstvennyj intellekt. № 3. 2010 S. 274-282.
6. Bron C. Finding all cliques of an undirected graph, Comm. of ACM. 16. P. 575.
7. Agarkov A.V. Iskusstvennyj intellekt. № 4. 2003. S. 172-184.
8. Agarkov A.V. Iskusstvennyj intellekt. № 2. 2007. S. 62-74.
А.V. Agarkov
Search of the Set of Maximal Cliques Based on the Method for Constructing Complementary Graph
This paper presents a method of finding the set of maximal cliques in a graph. This method is based on the
method for constructing complementary graph-pyramid that makes it easy to parallelize computations. The
computational complexity of the given method linearly depends on number ofmaximal cliques in a graph. For
specific tasks (for example, image recognition) this method stimulates solutions. This is achieved by reducing
number of constructed vertices and edges by the additional conditions in their construction, which take into
account characteristics of the tasks.
Статья поступила в редакцию 14.06.2011.
|