Некоторые методы и алгоритмы отыскания всех наименьших покрытий графа кликами тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РТБ ОН

- 7 \\Oft ^

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

Братцеиа Елена Викторовна

НЕКОТОРЫЕ МЕТОДЫ И АЛГОРИТМЫ ОТЫСКАНИЯ ВСЕХ НАИМЕНЬШИХ ПОКРЫТИЙ ГРАС'А КЛИКАМИ

специальность 01.01.09 - математическая кибернетига

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 1994

Работа выполнена в Вычислительном центре РАН.

Научный руководитель: доктор физ.-математ. наук, проф. В.К.Леонтьев

Официальные оппоненты: член-корр. РАН, доктор физ.-математ. паук, проф. Л.Д.Кудрявцев

Ведущая организация: Научный Совет'по комплексной проблеме "Кибернетика" РАН

кандидат физ.-математ. наук С.М.Швартин

Защита состоится "Л/л 1994 'юда

в асов на заседании специализированного совета K002.32.0I

при Вычислительном центре РАН по адресу: 117333, Москва, ул. Вавилова, 40.

в

С диссертацией можно ознакомиться в библиотеке Математического института га. В.А.Огеклова.

Автореферат разослан

ЛО« дса/гГд

1994 года.

Ученый секретарь

специализированного совета K0Q2.32.f~ доктор физ.-математ. наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы диссертации. Как известно, в настоящее время теория графов имеет широкое применение в экономике, технической кибернетике, радиотехнике, химии, биологии и медицине. Задачи, возникающие в этих кизненно важных областях} нередко могут быть сведены к задаче теории графов об отыскании наименьших разбиетй графа на полные подграфы. Причем, если в них требуется найти все допустимые решения, то приходится иметь дело с задачей отыскания всех наименьших разбиений графа на полные подграфы или с тесно связанной с ней задачей об отыскании всех наименьших покрытий графа кликами, которая и будет рассматриваться в данной работе. Следует отметить, что задача об отыскании всех наименьших разбиений графа на полные подграфы эквивалентна задаче об отыскании всех наименьших разбиений вершин дополнительного графа на максимальные независимые множества /пустые подграфы/, которая более известна как задача об отыскании всех наименьших раскрасок вершин графа.

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

- задача размещения /загрузки/;

- составление графиков осмотра /проверки/;

- распределение ресурсов;

- схемы электрических соединений, конструирование многослойного печатного монтажа;

- задача о развозке /доставке/;

- оптимальное размещение пунктов обслуживания;

- синтез оптимальных логических структур /упрощение буле-ВЬх выражений/;

- кластеризация и агрегирование.

Последнее может быть использовано для уменьшения размерности других задач. Действительно, пусть задано множество объектов, для каждой пары которых может быть вычислено "расстояние", характеризующее их близость. Для уменьшения размерности задач, возникающих относительно рассматриваемых объектов часто бывает необходимо агрегировать последние, т.е. представить множество объектов в виде суммы таких непересекаяцихся подмножеств, что любые два объекта, входящие в некоторое подмножество, находятся на достаточно близком /не превышающем данное пороговое значение/ "расстоянии" друг от друга. Очевидно, что при з- данном порогр-вом значении требуется найти разбиение на минимальное число таких непересекающихся множеств. В терминах теории графов эта задача является задачей об отыскании всех наименьших разбиений графа на полные подграфы.

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

Научная новизна работы. В работе предлагаются при переборных метода.

- Для непосредственного решения поставленной задачи предлагается использовать метод последовательных расчетов /при :>тоы требуется знание всех клик графа/.

- Для решения задач» путем нахождения всех наименьших разбиений графа на полные'подграфы использован усовершенствованный метод Вэна-Рыжкова дополненный так'называемым "алгоритмом двудольного графа". В данном случае не требуется отыскание

-з-

всех клик. Предварительно находятся только некоторые наименьшие разбиения.

- В третьем - индуктивном методе совуещается построение полных подграфов с отысканием наименьших разбиений, т.е. вместо отщепления клик происходит их наращивание. За исходный граф принимается такой подграф, для которого предыдущим методом легко находятся все науменыпие разбиения, после чего последовательно добавляются вераины заданного гра<!а и решаются параметрические задачи.

- Для второго метода разработан» алгоритмы и составлена программа.

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

Апробация работы. ' Основные положения настоящей работы . докладывались и обсуждались на научных семинарах ЦЭМИ АН СССР /1988,1589/ и ВЦ РАН /1994/.

Публикации. По результатам выполненных исследований опубликовано две печатные работы, одна отдана в печать и выполнен 1 один научный отчет.

Структура и объем диссертации. Работа состоит из введения, трех глав, заключения и списка литературы. Общий объем работы 104 страницы, в том числе 28 рисунков, одна таблица и две распечатки. Библиография включает 38 наименований.

-Ч-

ССЩЕРКАНИЕ РАБОТЫ

Во введении приводятся поставленная задача и содержание работы по главам.

Формулировка задачи также приводится ниже.

Итак, пусть &(]/,[/) - простой /т.е. без петель и кратных ребер/ конечный неориентированный граф с множеством вершин V? | ,..., и~пу и множеством ребер V . Приведем рад определений.

Определение I. Разбиением графа Ст и) на полные подграфы назовем такое разбиение множества вернин 1/ на непересекающиеся множества , ,..., » 41,0 подграфы ^графа . , порождаемые втими множествами вершин, являются полными.

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

Определение 3. Аналогично, покрытием графа V)

кликами назовем такое разбиение множества вершин 1/ на множества ~У1. /в отличие от аналогичных множеств

из определения I, множества Т/с могут иметь

общие вершины/, что подграфы 17^),..., ,

графа С* , порождаемые этими множествами вершин являются кликами.

Определение 4. Покрытие, которое после удаления любой из клик перестает быть покрытием, называется минимальным.

Определение 5. Минимальное покрытие, содержащее наименьшее число элементов, называется наименьшим.

Итак, нам требуется найти все наименьшие покрытия графа кликами.

Способы решения этой задачи разделим на три большие группы! методы, предполагающие предварительное отыскание всех клик графа /глава I/, методы, предполагающие предварительное отыскание некоторых наименьших разбиений графа /глава 2/, и индуктивные методы,, /глава 3/.

Перед описанием самих методов отыскания всех наименьших покрытий графа кликами в §1 главы I рассказывается о методах отыскания всех клик графа, среди которых выделяется индуктивный

"®Т°Д* (п., м

В этом методе граф (1/, и**') и множество

.Л2 -. М 1 его клик рассматриваются как результат последовательного получения подграфов

и множеств

клик , содержапрссся в графах

Граф (¿г^* получается из графа ** путем добав-

ления вершины и тех ребер графа (эг , которые

^ (С-о

соединяют с вершинами из о- , то есть с

гЧ11'1* л / /л л г1*'*) вершинами множества Ь (<') -пспП |/ . Опишем

способ получения множества из множества

Рассмотрим налдую клику М и Обозначим через С'х множество вершин клики £ . . г

Возможны следующие способы получения клик:

I. Сл Я С) ' , тогда С^и / . образуют

клику ¿С'<зг >

2- Сх<£ $и'°(С) .тогда Я* И'" и

Г 6-

3. возможно кликой X порождается еще одна клика

j? е М. образованная вершинами С. 'CQnS '"(i)] U /v£jr

•Л- f ¿t,Г ^

причем эта клика может получаться несколько раз из различных

клик Zr из -/V? . . Чтобы избежать Г - кратного

повторения, договоримся, что клика оставляется в

v /и <г~*>

тогда, когда она получается из клики 3. <£ , для

которой СХ4 является лексикографически первым множеством иэ множеств ' *

Оказывается, что множества всех клик графа и тюдгра—

г1и>

фов Cjr можно представить в виде двоично! - дерева с корнем тМ , а все клики графа можно получить при помощи поиска в глубину с возвращением по этому дереву. Описанный в §1 алгоритм поиска, по которому была составлена и отлажена программа, содержит Q(п1 (M/) тагов, где /Ai/ - число всех кдик графа ö .

В §2 главы I коротко рассказывается о решении задачи об отыскании всех наименьших покрытий методом Магу. Предполагается, что все -Ai клик графа С? заданы матрицей иннидопций ( 7") клик и вершин размерности ¡M! к п. , в которой t-Cj * i , если клике принадлежит вершина ,

и ¿у -О в противном случае. Запишем логическое выражение

Г] ¿il & 9 £ t где - символ юшки иэ ,

равный о или / . Расскрыв скобки в левой части этого равенства /учитывая закон поглощения/, получим минимальную дизъюнктивную нормальную форму, каждое слагаемое которой будет

V

соответствовать некоторому минимальному покрытию, а все слагаемые

ч-

с наименьшим числом сомножителей будут•соответствовать всем наименьшим покрытиям.

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

определяется функция £(<*>) = ! + Ц Сп~ I и С1 /),

где Сг !/ - множество вершин, принадлежащих клике ,

а - достаточно большое положителььч-е число, и доказывает-

ся /теорема 17, что она является супермодулярной, то есть удовлетворяет достаточному условию применимости метода последовательных расчетов. Будем говорить, что функция имеет локальный минимум £(и) на подмножестве Ы а /4 » если ^(ы.) Для всех ц>е Ас// (ы.) на диаграмме Хассе

для булевой структуры, содержащей & вершин, соответствующих подмножествам и> . Все локальные минимумы, которые находятся в слое диаграммы с минимальным номером <о С и будут соответствовать искомым наименьшим покрытиям. Для их отыскания применяются методы поиска в глубину и иирину.

И, наконец в последнем.4-ом параграфе главы I, описывается метод Кристофидеса, в котором используется метод поиска в ширину по дереву с корнем ф и /М! уровнями, в Р -ом уровне которого находится /}- С* ' вершин, а каждая вер-

!М1 /м/

шина является подмножеством и) множества М. .

Первые три параграфа 2-ой главы посвящены алгоритмам отыскания некоторой наименьших разбиений графа на полк ; подграфы. , В §1 говорится о методах Вэна и Рыжкова, на основе которых

-

в §2 строится алгоритм отыскания некоторых разбиений графа,а в §3 дается краткое описание программы, составленной по зтоцу алгоритму и приводятся примеры решенных задач.

Методы из §1 и §2 основаны на следующей теореме /теорема 2/: Кликоматичевкое число <з[(3] равно <}[&]- I + гпсп.

а) «> ^ ы) " '

где С? - , ~ клики, содержание некоторую

вершину графа Сг , а - кликовая степень

вершины гХ/число клик графа С? , содержащих ^ / ч Среди разбиений,-получающихся в результате последовательного отщепления клин от оставшихся подграфов, будут найдены на основании этой теоремы и наименьшие. Процесс получения разбиений можно представить'в виде дерева поиска, вершинам которого соответствуют подграфы графа • & , а ребрам - клики. Кратчайшим цепочкам от корня до концевых вершин этого дерева будут соответствовать наименьшие разбиения.

С целью минимизации числа вершин дерева поисков в методе Вэна в качестве очередной вершины Vв соответствующем под-

^ (¿-I)

графе С?- предложено выбирать вершину, имеющую наименьшую

кликовую степень , а в методе Рыжкова - вершину, име-

ющую наименьшую степень . Такой выбор вершины ^

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

однако при этом минимальному не всегда соответствует и>

минимальное К . В §2 было предложено компромикное решение:,

ищется верлина с минимальным ^ «= /шл ^ ,

<е> , 7 ¿/у-еу

где ^ - а- , а / - число вершин в

некоторой возможно наибольшей клике X. из О-

4 »

содержащей вершину

йце одним преимуществом метода из §2 перед другими методами является систематическое использование принципа декомпозиции. При помощи алгоритма отыскания компонент связности /связных частей/ находятся связные части как исходного графа, так и подгра-

^ч ¡е-*.)

фов Ц- , в результате чего исходная задача рас-

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

В последнем - 4-ом параграф« главы 2 рассматривается "алгоритм двудольного графа", позволяющий получить все наименьшие покрытия графа кликами и все наименьшие разбиения графа на пол-гае подграфы из некоторых наименьших разбиений, найденных методами, описанными в предыдущих параграфах этой главы /теорема 3/.

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

И наконец, в 3-*й главе речь пойдет об индуктивном методе.

-ю-

В 1-ом параграф« этой главы рассматривается параметрическая задача, которая формулируется следующим образом.

Пусть дан граф и известно множество всех его наимень-

ших разбиений ?У1Г . Требуется показать, как использовать знание для отыскания всех наименьших разбиений графа

+ гг . и & -ь (м, а) . В первом случае граф гг

получается из гра'Уа добавлением вершины V и ребер,

соединяххцих ее с некоторыми вершинами из . Во втором

случае граф 0 и) имеет те же вершины, что и граф (•г , но содержит на одно ребро (с(.1Г) больше.

Введем два определения.

Определение I. Добавляемая вершина V называется квазидоминируемой, если йс^' (V) 3" С £ , где - какой-то полный подграф из некоторого наименьшего разбиения графа <3-. Определение 2. Ребро (и, -ь') , добавляемое к графу С? , объединяющее при этом два полных подграфа некоторого наименьшего разбиения графа С? в один подграф, условимся также называть квазвдоминируемым ребром, поскольку обе его вершины квазидоминируеш в .

В §1 доказывается, что параметрическая задача успешно решается, если добавляемая вершина квазидоминируема или изолирована, а ребро квазидоминируемо.

Также доказывается /теорема 4 и теорема 5/, что&ССг'Т= <лСИ] тогда и только тогда, когда- « г/" - квазвдоминируема, а

6 сб"1~. осаз - *

тогда и только тогда, когда (и,

квазедоыинируемо.

В индуктивном методе из §2 будем наращивать граф, начиная

с какой-то произвольной вершигш, и отыскивать для каждого графа

^г (¡- все наименьшие разбиения

руководствуясь при этом результатами, полученными в предыдущем параграфе. Отметим, что <э ^^ [<3-^'] является воз-

растающей функцией: при -Т^п. она изменяется от ± до <о - <3 . Таким образом, оказывается, что примени-

мость индуктивного метода будет тем эффективнее, чем раньше

б/^ достигнет значения /т.е. д. -

~ <о /, так как для = <0 не будет

изменяться и все при £ /1 легко

находятся как решения параметрических задач.

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

Основные положения диссертации опубликованы в следующих работах:

1. Братпева Е.В., Черенин В.П. Алгоритмы агрегирования. //М.Препринт ВЦ АН СССР,1990

2. Братцева Е.В. О восстанавливаемости основных инвариантов графа. //Дискретная математика, т.5,И'4,МЛ993,с./£>5 -Н9.

3. Братцева Е.В., Черенин В.П. Отыскание всех наименьших покрытий графа кликами. //Журнал выч. математики я матем. физики. /в печати/