Classes of graphs reconstructed with linear time complexity..pdf Рассматривается задача [1] восстановления конечного связного неориентированногографа G без петель и кратных ребер при помощи агента, который премещаетсяпо ребрам графа G, считывает и изменяет метки на вершинах и инциденторах. Наоснове собранной информации агент строит граф H , изоморфный графу G с точностьюдо меток на вершинах и инциденторах графов. Необходимо найти метод обходаи разметки графа G с целью его восстановления.Известен ряд методов восстановления графа [2, 3], которые используют не болеечетырех различных красок, однако имеют верхнюю оценку временной сложности восстановления,равную квадратичной и кубической функцией от числа вершин в восстанавливаемомграфе соответственно. Для каждого метода нижней оценкой временнойсложности восстановления является линейная функция от числа вершин в графеG. Данная работа посвящена выделению классов графов, для которых верхняяоценка временной сложности восстановления является линейной функцией, и построениюопераций над графами, порождающих новый граф, для которого верхняя оценкавременной сложности не ухудшается.Методы основаны на обходе графа «в глубину». Для восстановления ребра агентвычисляет M - номера вершин [4], которым оно инцидентно. Для этого агент выполняетнекоторое количество переходов по ранее посещенным вершинам. Этот отходпорождает нелинейность верхней границы временной сложности восстановления. Длянекоторых классов количество и длина таких отходов могут быть заранее известны иограничены. Очевидны следующие утверждения.Теорема 1. Для графа вида «дерево» верхняя оценка временной сложности восстановленияявляется линейной функцией от числа вершин G.Теорема 2. Для графа вида «кольцо» порождается один отход при восстановленииграфа G.Найдены операции над графами, которые не ухудшают верхнюю оценку T(G) временнойсложности восстановления графа.Теорема 3. Операции добавления в граф висячей вершины и введения вершиныв ребро графа не ухудшают верхнюю оценку временной сложности восстановления.Таким образом, если граф G восстанавливается за линейное время, то и граф,полученный из него при помощи этих операций, восстанавливается за линейное время.Найдена бинарная операция, в результате которой получается граф, для котороговерхняя оценка временной сложности восстановления не превосходит суммы верхнихоценок временной сложности восстановления исходных графов.Теорема 4. Если граф G получен путем соединения двух графов G1 и G2 черезвершину сочленения, то T(G) ^ T(G1) + T(G2).Данная операция допускает естественное обобщение.Теорема 5. Если граф G получен путем древовидного соединения графовG1, ... , Gj через вершины сочленения, то T(G) ^ T(G1) + ... + T(Gj).Если G1, ... , Gj восстанавливаются за линейное время, то G, полученный при помощиэтой операции, также восстанавливается за линейное время.В результате найдены частные случаи классов графов, для которых верхняя оценкавременной сложности является линейной функцией от числа врешин в восстанавливаемомграфе. Найдены операции, которые не ухудшают верхнюю оценку временнойсложности восстановления, и бинарная операция, которая строит граф, для которговерхняя оценка временной сложности не превосходит суммы верхних оценок временнойсложности исходных графов.

Скачать электронную версию публикации