В данной работе рассматривается задача распознавания предфрактального графа (см.[1,2]) G=(V,E) с непересекающимися старыми ребрами, когда в качестве затравки (см.[3]) H=(W,Q) выступает регулярный n-вершинный граф степени s=n-2.
Пусть множество Q состоит из 
ребер. Найдем количество ребер данного предфрактального графа
(1)
Справедливы следующие теоремы.
Теорема 1. Пусть граф G=(V,E) является таким (n,L)-графом, в котором старые ребра (см.[3]) не пересекаются и его затравка H=(W,Q) является однородным графом степени deg H = n - 2. Тогда его множество вершин V разбивается на два подмножества V1 и V2, где V1 составляют вершины, степень которых равна n-1, а V2 составляют вершины, степень которых равна n-2. При этом мощности этих множеств определяются соотношениями
(2)
(3)
Доказательство. По условию теоремы, старые ребра в графе G не пересекаются. Это значит, что какая-либо из вершин v€ V либо инцидентна одному старому ребру, либо не инцидентна ни одному из старых ребер. В первом случае - вершина инцидентна одному старому ребру и, в силу однородности H=(W,Q), s ребрам затравки, т.е. степень этой вершины равна s+1. Во втором случае вершина v инцидентна только ребрам затравки и, следовательно, ее степень равна s. Таким образом, множество вершин V можно разбить на два подмножества V1 и V2, где V1 составляют вершины, степень которых равна s+1, а V2 составляют вершины, степень которых равна s.
Докажем теперь вторую часть теоремы.
Подмножество V1 составляют только те вершины, которые инцидентны старому ребру. Используем формулу (1), для вычисления количества старых ребер,
и, учитывая, что каждому старому ребру инцидентны две вершины, получим 
. Т.е. соотношение (2) доказано.
Подмножества V1 и V2 образуют разбиение множества V, тогда верно, что V2=V/V1, а мощность 
. Итак, формула (3) доказана.
Теорема доказана.
Лемма 1. Пусть в предфрактальном графе G=(V,E) две вершины v1 и v2, принадлежат одной затравке H=(W,Q)(v1,v2 € W ), и имеют смежность с некоторой вершиной v € V, тогда вершина v, также принадлежит этой затравке H
Доказательство. Допустим, что v € V не является вершиной данной затравки H=(W,Q), тогда она принадлежит другой затравке H´=(W´,Q´), т.е. ребра e = (v1,v) и e = (v2, v) являются старыми.
Заметим, что два старых ребра e = (v1,v) и e = (v2, v) не могут быть инцидентны по обеим вершинам одним и тем же затравкам, в силу того, что кратных ребер в траектории предфрактального графа нет.
Лемма доказана.
Для решения поставленной задачи распознавания предфрактального графа G=(V,E) с непересекающимися старыми ребрами, когда затравка - регулярный граф степени n-2 предлагается следующий алгоритм α1., состоящий из этапов ρ=1,2,...,L-1, которые взаимнооднозначно соответствуют текущим графам G1, l=2,...,L траектории (см.[3]). На входе этапа ρ рассматривается текущий граф G1, где l = L-ρ+1. Этап ρ выделяет в G1 затравки, состоящие из ребер ранга l. После чего, каждая из этих затравок стягивается в вершину. Полученный в результате текущий граф G l-1, представляется на вход этапа l-1.
В процессе результативной реализации L-1 этапов алгоритма α1 получаем последовательность G*L,G*L-1,...,G*1. При этом считаем, что данный граф G, обозначаемый через G*L, является предфрактальным каноническим графом, тогда, когда последовательность имеет длину L. Причем, каждый представитель этой последовательности удовлетворяет необходимым условиям предфрактальности. Выполнение этих условий проверяется в результате реализации всех операций соответствующего этапа.
Опишем вычислительную схему первого этапа в случае, когда на его вход представлен исходный граф G=(V,E).
Этап ρ=1 начинает свою работу с проверки выполнения равенства |V|=nL. Если это равенство не выполняется, то алгоритм α1 заканчивает работу безрезультатно. В случае выполнения этого равенства, в графе G выделяется множество V1, состоящее из вершин степени s=n-1, и V2, состоящее из вершин степени s=n-2. Если разность 
, то алгоритм заканчивает работу безрезультатно. В противном случае, V1 и V2 образуют разбиение множества V и, дальнейшая работа этапа ρ-1 состоит из m0 шагов, где m0 число таких затравок, каждая из которых состоит из новых ребер.
Результатом каждого такого шага является выделенная в графе G очередная затравка. Процедуру выделения этой затравки обозначим через β.
Описание процедуры .
Выделяем во множестве V2 очередную неотмеченную вершину v*1, т.е. вершину, которая не принадлежит какой-либо уже выделенной затравке. Т.к. вершина v*1 € V2, то она имеет степень n-2, т.е. смежна с n-2 новыми вершинами своей затравки H=(W,Q), которые обозначаем через v*k, где 
и окрашиваем. В результате имеем n-1 выделенных вершин n-вершинной затравки, т.е. непомеченной осталась всего одна вершина. Рассмотрим теперь те вершины, которые смежны с выделенными v*k, , но неокрашены и, выделим среди них ту которая будет смежной с n-2 из уже окрашенных n-1 вершин, согласно лемме 1, эта вершина также будет принадлежать этой затравке. Через W´ обозначаем множество всех вершин отмеченных процедурой β. Если мощность |W´| = n, то выделяем и окрашиваем все ребра, у каждого из которых концы представляют собой вершины данного множества W´. Работа процедуры β завершается проверкой: образует ли множество выделенных таким образом вершин и ребер n-вершинный связный однородный граф степени s = n-2. Если да, то шаг, включающий в себя описанную процедуру β, завершается результативно и следует переход к следующему шагу первого этапа. В противном случае, шаг считается безрезультатным и, алгоритм α1 прекращает свою работу.
Этап ρ=1 завершается, когда в данном графе G=(V,E) все вершины множества V окажутся отмеченными.
По окончании первой части алгоритма α1 осуществляем проверку, все ли вершины исходного графа G оказались отмеченными. Если да, то первый этап алгоритма α1 заканчивает свою работу следующей процедурой. Исходный граф G обозначается через G*L и представляется в качестве первого члена последовательности G*L,G*L-1,...,G*1. Каждая выделенная затравка графа G стягивается в одну вершину. Полученный в результате такого стягивания граф обозначается через G*L-1. Далее, по отношению к нему реализуем очередной этап алгоритма.
Теорема 2. Всякий предфрактальный граф G=(V,E), с попарно непересекающимися старыми ребрами и регулярной n-вершинной затравкой H=(W,Q) степени s=n-2 является распознаваемым алгоритмом α1.
Доказательство. Каждая новая затравка ранга L либо сохраняет инцидентность только с n-2 старыми ребрами ранга L-1, либо с n-2 ребрами предыдущего ранга L-1 и одному ребру ранга L-1,L-2,... 1. В первом случае, новая затравка имеет две вершины минимальной степени s=n-2, в силу непересечения старых ребер. Во втором случае, новая затравка имеет одну вершину степени s=n-2. Т.е. мы доказали, что всякая новая затравка имеет хотя бы одну вершину минимальной степени n-2, а это обеспечивает распознавание каждой затравки.
Теорема доказана.
СПИСОК ЛИТЕРАТУРЫ:
- Емеличев В.А. и др. Лекции по теории графов. М.: Наука, 1990г.
- Кочкаров А.М., Перепелица В.А. «Метрические характеристики фрактального и предфрактального графа». Сб.РАН САО, 1999г.
- Кочкаров А.М. Распознавание предфрактальных графов.