РАЗДЕЛ 2
МЕТОДЫ И АЛГОРИТМЫ РАСПОЗНАВАНИЯ
ДЛЯ ОТДЕЛЬНЫХ КЛАССОВ
КАНОНИЧЕСКИХ ПРЕДФРАКТАЛЬНЫХ ГРАФОВ
Как было сказано в главе 1, в зависимости от построения предфрактальные графы делятся на такие, старые ребра которых не пересекаются и старые ребра которых пересекаются. В дальнейшем по умолчанию будем рассматривать предфрактальные графы, старые ребра которых не пересекаются.
На рис. 2.1 представлен процесс построения канонического предфрактального графа G=(V,E) ранга 2, порожденного однородной 3-вершинной затравкой H, старые ребра которого не пересекаются.
а) б)
Рис. 2.1 Порождение канонического предфрактального графа G=(V,E) ранга 2, порожденного однородной 3-вершинной затравкой
На шаге 1 (рис.2.1(а)) задается затравка H - однородный 3-вершинный граф. В результате применения к каждой ее вершине операции "замещение вершины затравкой" (рис.2.1(б)) получаем канонический предфрактальный граф ранга 2 (рис.2.1(в)).
В данном разделе исследуются свойства канонических предфрактальных графов порожденных следующими затравками: полной n-вершинной затравкой, n-вершинным колесом и n-вершинной звездой. Изучены свойства полных канонических предфрактальных графов старые ребра которых пересекаются, а также предлагаются алгоритмы распознавания перечисленных выше графов на предфрактальность.
2.1. Исследование свойств некоторых канонических предфрактальных графов и обоснование методов
распознавания их на предфрактальность
Под полным каноническим предфрактальным графом понимается предфрактальный граф, порожденный полной затравкой, т. е. в качестве затравки H=(W,Q) берется полный n-вершинный граф G=(V,E) [66].
Пусть граф G=(V,E) является таковым. Тогда так же, как и для предфрактального графа, порожденного связной однородной n-вершинной затравкой [72], множество вершин V графа G разбивается на два подмножества вершин V1 и V2 степеней n-1 и n соответственно:
?V1?=n, (2.1)
?V2?=n(n L-1 -1). (2.2)
По аналогии с разбиением множества V множество вершин W каждой затравки H разбивается на два подмножества вершин W1 и W2 степеней n-1 и n соответственно.
Для графа, изображенного на рис. 2.2 множества V1 и V2 имеют вид: V1={2,6,3}, V2={1,9,7,5,4,8}.
Рис.2.2. Полный канонический предфракатальный граф ранга 2,
порожденный 3-вершинной затравкой
Данный граф содержит в себе три затравки H(1)=(W(1),E(1)), H(2)=(W(2),E(2)), H(3)=(W(3),E(3)), порожденные множествами вершин {1,2,9}, {3,4,8} и {5,6,7} соответственно. Каждое из этих множеств разбивается на два подмножества вершин степеней 2 и 3 соответственно. А именно: W(1)1={2} W(1)2={1,9}; W(2)1={3} W(2)2={4,8}; W(3)1={6} W(3)2={5,7}.
Из леммы 1.2 следует, что для полного канонического предфрактального графа G, порожденного n-вершинной затравкой, размерность максимальной клики не превосходит n-1.
Теорема 2.1. Пусть G=(V,E) - полный канонический предфрактальный граф, порожденный связной n-вершинной затравкой. Тогда множество всех его затравок можно разбить на затравки двух видов:
- те, для которых мощность ?W1?=1, и количество таких затравок равно n;
- те, для которых мощность ?W1?=0.
Доказательство. По построению для каждой затравки существует не менее n-1 старых ребер, смежных с ее вершинами. А так как ?V1?=n и
V1=?i=1nL-1W(i)1, то имеем, что только для n затравок ?W1?=1.
Теорема 2.2. Пусть H=(W,Q) - n-вершинная затравка, порождающая полный канонический предфрактальный граф G. Тогда, если множество W1 не пусто, то вершина v?W1 смежна с каждой вершиной из множества W2.
Доказательство. Так как затравкой является полный граф, то все вершины множества W смежны между собой. Следовательно если множество W1 не пусто, то вершина v?W1 смежна с каждой вершиной из множества W2.
Теорема 2.3. Пусть G=(V,E) - полный (n,L)-граф, порожденный затравкой H=(W,Q). Тогда для каждой затравки H=(W,Q) графа G подграф, индуцированный множеством вершин W2, является полным графом.
Доказательство. Так как по условию теоремы граф Н - полный, то любой подграф, индуцированный подмножеством его вершин, будет тоже полным графом.
На рис. 2.3 изображен полный канонический предфрактальный граф ранга 3 (n=4).
Рис. 2.3. Полный канонический предфрактальный граф (L=3, n=4)
В данном графе содержатся 16 затравок H(i)=(W(i),E(i)) (i=1,...,16). Как видно из рисунка только четыре из них содержат вершину степени 3, все остальные содержат в себе только вершины степени 4.
Так же из рисунка видно, что для каждой i-й затравки подграф, индуцированный множеством W(i)2, является полным.
Рассмотрим теперь канонический предфрактальный граф, порожденный n-вершинной звездой H=(W,Q) (n=4,5,...) (под n-вершинной звездой понимаем такой n-вершинный граф, (n-1) вершина которого имеет степень 1, и только одна - степень (n-1) [91]). Пусть граф G=(V,E) является таковым.
Лемма 2.1. Множество вершин V канонического предфрактального графа G=(V,E), порожденного n-вершинной звездой, разбивается на три подмножества вершин V1, V2, V3 у которых степени вершин равны s1=1, s2=2, s3=n-1 соответственно и мощности этих подмножеств определяются следующими равенствами:
?V3?=n L-1,
?V2?=2(n L-1-1),
?V1?=n L-3n L-1 +2. (2.5)
Доказательство. Так как по условию старые ребра графа G не пересекаются, то произвольная вершина из множества V либо инцидентна одному старому и одному новому ребру и, соответственно, имеет степень 2, либо инцидентна только новым ребрам. Согласно [72] удвоенное количество старых ребер строго меньше количества вершин графа G. По построению старым ребрам инцидентны вершины, имеющие степень 2, и таких вершин