Автор: Грунский И.С.,Сапунов С.В., Татаринов Е.А.
Источник:
Грунский И.С. В Эксперименты с помечеными графами /
И.С. Грунский, С.В. Сапунов, Е.А. Татаринов
// Восьмая международная научная конференция «Дискретные модели в теории управляющих систем» М: МГУ 2009. – С. 43–44.
Одной из центральных и актуальных как в теоретическом, так и в прикладном аспектах проблем, возникающих при исследованиях взаимодействия автоматов и графов, является проблема анализа или распознавания свойств графа при различной априорной информации и при различных способах взаимодействия автомата и графа.
При решении проблемы анализа графа операционной среды наметилось несколько подходов. Один из подходов основывается на том, что операционная среда рассматривается как неориентированный граф с помеченными вершинами [1]. Такие графы возникли первоначально как блок-схемы и схемы программ, а в настоящее время находят применение в задачах навигации роботов.
В настоящей работе рассматривается проблема минимизации ориентированных графов с отмеченными вершинами. Эта проблема позволяет находить эквивалентные графы, с помощью которых можно представить различные системы. Проблема эквивалентности программ относится к числу наиболее важных проблем теории программирования. Особое значение проблемы эквивалентности обусловлено тем, что именно к этой проблеме эквивалентных преобразований сводится большинство задач оптимизации, верификации и анализа программ. Поэтому разработка и внедрение эффективных алгоритмов проверки эквивалентности программ оказывает заметное влияние на повышение производительности и качества многих инструментальных средств анализа и преобразования программ. В последние годы наряду с задачами повышения эффективности и надёжности программ не меньшую актуальность приобрела задача своевременного обнаружения постороннего кода, которая включает выявление не декларированных возможностей программных продуктов, а также обнаружение и устранение программ–вирусов. Задача минимизации ориентированных графов с отмеченными вершинами является основой для создания различных методов эквивалентности схем программ. Она является актуальной в теоретическом и прикладом аспектах. Её прикладная актуальность определяется тем, что проблемы самолокализации и контроля для таких графов далеки от разрешения и их исследования находятся в зачаточном состоянии. Теоретическая важность и актуальность определяются тем, что анализ графов проводится методами, аналогичными методам теории автоматов. Эти методы созданы для графовых систем, не являющихся конечными автоматами, но являющимися в некотором смысле автоматоподобными системами.
Пусть G=(S, E, M, μ) конечный, связный, помеченный, ориентированный граф, без петель и кратных дуг [2], где S – конечное множество вершин, E – множество рёбер, M – множество меток, μ: S→M – сюррективная функция размечивания вершин такая, что отметки всех вершин, смежных одной вершине, попарно различны, то есть что граф детерминирован [1]. Конечную последовательность вершин p=g1…gk такую, что ‹gi,gi+1› ∈ EG, 1<i<=k, назовём путём длины (k-1) в графе G. Слово μ= μ(g1)… μ(gk) назовём отметкой пути p. Отметку любого пути, исходящего из вершины g ∈ S, будем называть словом, порожденным вершиной g. Язык Lg определим как множество всех слов, порождённых вершиной g ∈ S [1]. Вершины g, h – назовём эквивалентными, если Lg=Lh, и отличимыми в противном случае. Граф G называется приведенным, если все его вершины попарно отличимы.
Пусть Lg={Lg}g ∈ G. Графы G и H называются эквивалентными, если Lg=Lh. В работе рассматривается задача минимизации графов, то есть задача построения по произвольному графу G эквивалентного ему графа с наименьшим числом вершин. Следуя [1] эта задача сводится к нахождению классов эквивалентных вершин графа G. В [1] показано, что минимальный граф получается из исходного отождествлением его эквивалентных вершин. Известно несколько алгоритмов минимизации – это алгоритм Сапунова [1] написанный, на основе алгоритма Мура [3] для детерминированных графов. Его временная сложность равна O(m*n2), где n – это количество вершин, а m – количество отметок графа. В [5] был разработан алгоритм для общего вида детерминированных графов с временной сложностью O(m*n*log(n)).
В данной работе предложен новый алгоритм минимизации ациклических графов и их частного вида – деревьев. Он состоит в следующем.
Алгоритм
ВХОД: множество вершин S из n элементов, разбиение p={B[1],…,B[k]} и функция f: S→S.
ВЫХОД: разбиение p’={B[1],…,B[q]} множества S, совместимое c p и f.
ОБЪЕКТЫ: граф заданный списком вершин, где каждая вершина представлена структурой:
Next_degree – степень вершины по f+1;
Prev_list – список предыдущих вершин f-1;
Prepared – степень готовности v[k].prepared вершины v[k] к разбиению (изначально соответствует степень вершины по f+1);
class – класс принадлежности;
Mark – отметка вершины.
МЕТОД:
1. Просмотрим все вершины и выберем те, у которых степень готовности равна 0. разобьём их на классы эквивалентности в соответствии с метками v.class = v.mark. Полученные классы запишем в список будущей готовности PREPAREDNEXT.
2. Пока список PREPAREDNEXT не пуст, ОБРАБОТАТЬ = PREPAREDNEXT, и выполняем пункты 3–5.
3. Очистим список PREPAREDNEXT
4. Для каждой вершины v в каждом классе из списка ОБРАБОТАТЬ берём f-1(v) (родителей) и уменьшаем её степень готовности на 1.
5. Берём любой номер i класса из списка ОБРАБОТАТЬ, и удаляем его.
Просматриваем для каждой вершины v класса B[i] множество f-1(v). Если степень готовности вершин f-1(v) равна 0, то помещаем их во временный класс, иначе ничего не делаем.
Если количество элементов временного класса и элементов пересекаемого класса различны, то создаём новый класс q = q+1 и всем вершинам временного класса v[k].class = q. В любом случае номер полученного класса помещаем в список PREPAREDNEXT, если он там не содержится.
Если не все классы из списка ОБРАБОТАТЬ просмотрены, переходим к пункту 5
Доказано, что результатом работы алгоритма являются классы эквивалентных вершин, то есть он решает задачу минимизации. Определена временная сложность алгоритма для ориентированных ациклических графов и их частного случая – деревьев
– детерминированные деревья – O(n);
– недетерминированные деревья – O(n);
– детерминированные ациклические графы общего вида – O(m*n);
– недетерминированные ациклические графы общего вида – O(n2).
1. Сапунов С.В. Анализ графов с помеченными вершинами / С.В, Сапунов // Дисс. канд. физ.-мат. наук: 27.09.07. – Донецк.: 2007. – 150 с.
2. Сэджвик Р. Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах / Р. Сэджвик – М.: diasoft. 2002. – 484 с.
3. Гилл А. Введение в теорию конечных автоматов / А. Гилл – М.: Наука, 1966. – 272 с
4. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж.Ульман. – М.: «МИР». 1979. – 235с.
5. Чепурко В.А. Минимизация графов с отмеченными вершинами // Материалы региональной межвузовской научно-практической конференции студентов «Современная информационная Украина: информатика, экономика, философия». Донецк, 13–14 мая 2007 г. Донецк: 2007. – Т.5. – С. 47–49