Введение к работе
Актуальность темы диссертации. Как известно, в настоящее время теория графов имеет широкое применение в экономике, технической кибернетике, радиотехнике, химии, биологии и медицине. Задачи, возникающие в этих кизненно важных областях} нередко могут быть сведены к задаче теории графов об отыскании наименьших разбиеїшй графа на полные подграфы. Причем, если в них требуется найти все допустимые решения, то приходится иметь дело с задачей отыскания всех наименьших разбиений графа на полные подграфы или с тесно связанной с ней задачей об отыскании всех наименьших покрытий графа кликами, которая и будет рассматриваться в данной работе. Следует отметить, что задача об отыскании всех наименьших разбиений графа на полные подграфы эквивалентна задаче об отыскании всех наименьших разбиений вершин дополнительного графа на максимальные независимые множества /пустые подграфы/, которая более известна как задача об отыскании всех наименьших раскрасок вершин графа.
Приведем некоторые конкретные примеры прикладных задач, сводимых к указанным выше задачам теории графов. Это
задача размещения /загрузки/;
составление графиков осмотра /проверки/;
распределение ресурсов;
схемы электрических соединений, конструирование многослойного печатного монтажа;
задача о развозке /доставке/;
оптимальное размещение пунктов обслуживания;
синтез оптимальных логических структур /упрощение булевых выражений/;
- кластеризация и агрегирование.
Последнее может быть использовано для уменьшения размерности других задач. Действительно, пусть задано множество объектов, для каждой пары которых может быть вычислено "расстояние", характеризуючеє их близость. Для уменьшения размерности задач, возникающих относительно рассматриваемых объектов часто бывает необходимо агрегировать последние, т.е. представить множество объектов в виде суммы таких непересекающихся подмножеств, что любые два объекта, входящие в некоторое подмножество, находятся на достаточно близком /не превышаицем данное пороговое значение/ "расстоянии" друг от друга. Очевидно, что при з-данном пороговом значении требуется найти разбиение на минимальное число таких непересекающихся множеств. В терминах теории графов эта задача является задачей об отыскании всех наименьших разбиений графа на полные подграфы.
Цель работы. Целью работы является разработка методов, алгоритмов и программ для отыскания всех наименьших покрытий графа кликами, а также описание некоторых уже известных методов.
Научная новизна работы. В работе предлагаются три переберных метода.
Для непосредственного решения поставленной задачи предлагается использовать метод последовательных расчетов /при :>тоы требуется знание всех клик графа/.
Для решения задачи! путем нахождения всех наименьших разбиений графа на полные'подграфы использован усовершенствованный метод Вэна-Рыжкова дополненный так'называемым "алгоритмом двудольного графа". В данном случае не требуется отыскание
всех клик. Предварительно находятся только некоторые наименьшие разбиения.
В третьем - индуктивном методе совуещаетея построение полных подграфов с отысканием наименьших разбиений, т.е. вместо отщепления клик происходит их наращивание. За исходный граф принимается такой подграф, для которого предыдущим методом легко находятся все наикеньиие разбиения, после чего последовательно добавляются верпины заданного гра<|а и решаются параметрические задачи.
Для второго метода разработали алгоритмы и составлена программа.
Практическая ценность работы заключается в построении алгоритмов отыскания всех наименьших покритий графа кликами, а также программ* отыскания некоторых наименьших разбиений графа на полные подграфы. Кроме того, вышеуказанная программа ' включает программу отыскания всех клик графа, представляюпг/ю самостоятельный инзерес.
Апробация работы. ' Основные положения настоящей работы . докладывались и обсуждались на научных семинарах ЦЭМИ АН СССР /1983,1989/ и ВЦ РАН /1994/.
Публикации. По результатам выполненных исследований опубликовано две печатные работы, одна отдана в печать и выполнен 'один научный отчет.
Структура и объем диссертации. Работа состоит из введения, трех глав, заключения и списка литературы. Общий объем работы 104 страницы, в том числе 28 рисунков, одна таблица и две распечатки. Библиография включает 38 наименований.