1) Первая стратеия: поиск базисных инвариантов графов.

Базис инвариантов графов может быть определен разными способами. В Главе 1 введены три определения базиса, доказан ряд теорем о свойствах базисов, предложены возможные наборы базисных инвариантов, на основе полученных теоретических результатов разработаны общие методы построения моделей связи «структура-свойство».

? Определение 1 базиса инвариантов графов. Набор инвариантов {gj} (j=1,…,M) графов множества {Gi} (i=1,…,N) назовем базисным, если любой инвариант f(G) графов этого множества однозначно представляется в виде линейной функции от них, т.е.:

f(G)=?ajgj(G), (G?{Gi},j=1,…,N),

где aj (j=1,…,M) - некоторые константы, не зависящие от G, а зависящие только от f.

Сформулированы и доказаны теоремы о свойствах базиса в смысле определения 1.

ТЕОРЕМА 1.1 (необходимые и достаточные условия на набор инвариантов, при которых они образуют базис). Набор инвариантов {gj} (j=1,…,M) образует базис множества инвариантов графов {Gi} (i=1,…,N) в смысле определения 1 тогда и только тогда, когда M=N и detB?0, где B=(bij) - матрица с элементами bij=gj(Gi), i, j=1,…,N.

ТЕОРЕМА 1.2 (описание множества всех базисов инвариантов). Пусть {gj} (j=1,…,N) – некоторый базис инвариантов графов множества {Gi} (i=1,…,N) в смысле определения 1, A – произвольная невырожденная квадратная матрица размера N. Построим набор инвариантов {hj} (j=1,…,N) по формуле:

h=Ag , (2)

где g=(g1,…,gN), h=(h1,…,hN) - вектора – столбцы. Тогда:

Инварианты {hj} (j=1,…,N) также являются базисом инвариантов графов в смысле

определения 1; 2) Любые два базиса h и g связаны между собой при помощи формулы (2) с некоторой невырожденной матрицей А.

ТЕОРЕМА 1.3 (о существовании базиса инвариантов, равных числам вхождения в граф определенных подграфов). Рассмотрим множество графов {Gi} (i=1,…,N). Тогда инварианты gj(G), равные числам вхождения подграфа Hj=Gj (j=1,…,N) в граф G, образуют базис инвариантов графов заданного множества.

ТЕОРЕМА 1.4 (о существовании базиса инвариантов, часть которых постоянна на выделенном подмножестве графов). Пусть в множестве графов {Gi} (i=1,…,N) выделено подмножество {Gi} (i=1,…,k; k?N). Тогда существует базис {fp} (p=1,…,N) инвариантов графов множества {Gi} (i=1,…,N), такой, что его N-k+1 элемент постоянен на подмножестве {Gi} (i=1,…,k). При этом N-k+1 - максимальное число базисных инвариантов, обладающих вышеуказанным свойством.

ТЕОРЕМА 1.5 (характеристическое свойство графов выделенного подмножества графов). Пусть в множестве графов {Gi} (i=1,…,N) выделено подмножество {Gi} (i=1,…,k; k?N), а {fp} (p=1,…,N-k+1) - базис инвариантов, постоянных на подмножестве графов {Gi} (i=1,…,k), т. е. fp(Gi)=cp, где cp - некоторые константы, зависящие только от индекса p (p=1,…,N-k+1) (см. теорему 1.4). Тогда не существует графа Gi (i=k+1,…,N), такого, что fp(Gi)=cp (p=1,…,N-k+1).

ТЕОРЕМА 1.6 (Об общем виде произвольного инварианта на выделенном подмножестве графов). Пусть в множестве графов {Gi} (i=1,…,N) выделено подмножество {Gi} (i=1,…,k; k?N), а инварианты {fp} (p=N-k+2,…,N) и константы cp (p=1,…,N-k+1) те же, что и в теоремах 1.4 и 1.5. Тогда на любом графе G=Gi (i=1,...,k) инвариант f представляется в виде:

N N-k+1

f(G)=a0+?apfp(G) , (a0=?apcp=const), (3)

p=N-k+2 p=1

причем коэффициенты a=(a0,aN-k+2,...,aN) однозначно определяются по значениям f(Gi) (i=1,...,k).

ТЕОРЕМА 1.7.(необходимое и достаточное условие для восстановления значения инварианта графа по набору значений этого инварианта для других графов). Пусть в множестве графов {Gi} (i=1,…,N) выделено подмножество {Gi} (i=1,…,k; k?N). Значение инварианта f(G) для графа G(Gi (i=1,...,k) определяется по уравнению (3) тогда и только тогда, когда инвариант f и граф G удовлетворяют условию:

?apfp(G)=a0 . (4)

Следствие из теоремы 1.7.

Из теоремы 1.7 следует, что для проверки возможности вычисления f(G) (G(Gi, i=1,...,k) по f(Gi) (i=1,...,k) необходимо знать значения ap (p=1,...,N-k+1) (значения fp(G) и a0 - известны). Однако их невозможно определить по исходным данным. Следовательно, без дополнительных предположений относительно инварианта f и графа G в принципе невозможно решить вышеуказанный вопрос. Однако можно указать следующие достаточные условия на f и G, при которых выполнено условие (4). Предположим, что инвариант f такой, что ap=0 при некоторых значениях p (1?p ?N-k+1) (причем хотя бы для одного значения p), а граф G из множества {Gi} (i=k+1,…,N) такой, что fp(G)=cp для остальных значений p, 1?p?N-k+1. Легко видеть, что в этом случае выполнено условие (4).

Поставим следующий вопрос: можно ли вообще не накладывать вышеуказанные ограничения на инвариант f, а ввести ограничения только на граф G? Предположим, что fp(G)=cp для любого p, 1?p?N-k+1. Однако, как было доказано ранее, такого графа G вообще не существует, и эти ограничения становятся бессмысленными.

ТЕОРЕМА 1.8 (обобщение теоремы 1.7). Предположим, что задана допустимая точность ((0 расчета значения инварианта f(G), G=Gi (i=1,…,N) и для графов G=Gi (i=1,…,k) получено приближенное уравнение вида

f’(G)=(ap’fp(G)+a0’ , (5)

где S1 -некоторое подмножество множества S={N-k+2,…,N} и (f(G)-f’(G)(?(, а f(G) определено по формуле (3). Обозначим S2={1,…,N-k+1}. Значение f(G) для графа G=Gi (i=k+1,...,N)) вычисляется с точностью ( по уравнению (5) (т.е. (f(G)-f’(G)(?() тогда и только тогда, когда

((fp(G)(ap-ap’)+(fp(G)ap+(fp(G)ap-a0’(?(. (6)

p(S1 p(S\S1 p(S2

Следствие из теоремы 1.8.

Сформулируем достаточные условия, при которых f(G) определяется по уравнению (5). Как и в случае теоремы 1.7, предположим, что f и G таковы, что при p(S2 либо ap=0, либо fp(G)=cp.

Тогда (apfp=a0 ,

а условие (6) примет вид:

((fp(G)(ap-ap’)+(fp(G)ap+a0-a0’(?(. (7)

S1 S\S1

Все величины, входящие в это неравенство, определяются по начальным данным, поэтому его можно использовать на практике.

ТЕОРЕМА 1.9 (аналог теоремы 1.8). Предположим, что задана допустимая точность ((0 расчета значения инварианта f(G), G=Gi (i=1,…,N) и для графов G=Gi (i=1,…,k) получено точное уравнение (3), а из него - приближенное уравнение путем замены некоторых инвариантов fp (p=N-k+2,...,N) на их средние значения

bp=(1/k)(fp(Gi)

на подмножестве графов Gi (i=1,...,k). Обозначим: S={N-k+2,...,N}, S2={1,...,N-k+1}, S1 - множество номеров базисных инвариантов, оставшихся в приближенном уравнении. Таким образом, приближенное уравнение будет иметь следующий вид: