Обозначим через
Ясно, что если f из 
то 
для 
Предложение 14.
Пусть H из 
и пусть f из 
Тогда для
того, чтобы для l из 
и
выполнялось включение 
достаточно,
чтобы 
Д о к а з а т е л ь с т в о.
Пусть 
тогда
найдется такой v из V, что 
Так как 
то
следует 
Предложение 14. доказано.
Предложение 15.
Пусть 
и пусть выполняется условие 
Если
то
Д о к а з а т е л ь с т в о.
Пусть выполняется включение
тогда 
Так как и
существуют функции 
из
такие, что для графов 
выполнено условие 2.1, то,
применяя предложение 3, имеем 
Предложение 15. доказано.
Обозначим через 
- множество всех локально
f-упорядоченных графов, изоморфных графу G.
Д о к а з а т е л ь с т в о. От противного.
Пусть 
тогда существует граф B из 
,
что 
Из определения 3 имеем, что 
Противоречие, так как из 
следует, что 
Предложение 16. доказано.
Предложение 17.
Пусть H из 
Тогда из
следует,
Д о к а з а т е л ь с т в о. Тривиально.
Предложение 18.
Пусть H из 
из F , 
из
и
пусть выполняется 
и
для каждого 
из 
выполняется условие
Тогда
Д о к а з а т е л ь с т в о. Предположим, что
т.е. существует
такой граф Z из 
что 
Ясно, что существует такая перестановка 
из
Так как 
то 
Заметим, что в левой части выражения (4.1) стоит константа.
Учитывая, что из 
следовательно
Поэтому 
и
Из предложения 3
получаем,
что 
Противоречие.
Предложение 18.
доказано.
Пусть U непустое подмножество множества V и 
(т.е. 
- подгруппа группы 
то фиксатором (поточечным стабилизатором) 
множества U в группе называется
подгруппа всех элементов из 
оставляющая неподвижной
каждую метку
из U. Стабилизатором 
множества
U в группе называется подгруппа всех элементов из
отображающих U на U.
Пусть l < n, тогда полагаем 
Отметим, что 
О п р е д е л е н и е 8.
Пусть H из 
Перестановки 
из 
будем называть ( H, l )-эквивалентными (
и обозначать 
или, если понятно какие H и l, то 
), если выполняются условия:
где 
Если не выполняется хотя бы одно из условий 1,2 данного
определения, то
перестановки 
-неэквивалентны 
Нетрудно видеть справедливость следующих предложений.
Пусть H из 
и пусть 
из 
тогда выполняются:
1. 
2. 
3. 
Используя доказательство предложения 18, нетрудно установить следующее
Предложение 19.
Пусть H из из F, из и пусть
выполняется условие 
и для из выполняется
условие 
тогда перестановки 
-эквивалентны.
Полагаем 
Предложение 20.
Пусть H - простой помеченный граф, изоморфный графу G,
из 
из
и пусть
выполняется условие 
Тогда для того, чтобы для каждого графа Y из 
выполнялось условие
необходимо, чтобы 
Д о к а з а т е л ь с т в о.
От противного. Пусть для каждого графа Y из
выполняется (4.2) и
пусть 
Возьмем граф Z из 
Ясно, что
где 
Так как для графов выполняется условие 1,
то из предложения 3 имеем, что 
т.е.
граф 
следовательно, существует такая
пара 
из 
что 
и
где 
Из
и определения множества 
в котором
вместо H берем и вместо 
берем 
получаем, что для графа Z выполняется
Применяя (4.2) имеем, что
Следовательно,
Противоречие.
Предложение 20 доказано.
Предложение 21.
Пусть H - простой помеченный граф, изоморфный графу G,
и l из и пусть
для любого графа из и любого из
существуют такие функции
из 
что
выполняется условие
и пусть 
тогда
для каждого графа Y из выполняется условие:
Д о к а з а т е л ь с т в о.
Пусть Y из 
Так как 
то
Применяя предложение 3 имеем,
что 
т.е.
Следовательно,
существует такая
пара из 
что 
Ясно, что
где 
Из
и определения
множества в котором
вместо H берем Y и вместо берем
получаем, что для графа 
выполняется
Следовательно, 
Предложение 21 доказано.
Предложение 22.
Пусть H из и 
Тогда для
того, чтобы перестановки 
были
- эквивалентными необходимо, чтобы существовала такая
перестановка из 
что 
Д о к а з а т е л ь с т в о. Так как
графы 
и 
изоморфны, то существует такая
перестановка из 
, что 
Из (H,l)-эквивалентности перестановок 
имеем, что 
следовательно 
Предложение 22 доказано.
Очевидно следующее
Предложение 23.
Пусть H из и пусть из 
Тогда для того, чтобы были -эквивалентными достаточно, чтобы
выполнялось 
и существовала такая перестановка
из что
Предложение 24.
Пусть H из из 
и перестановки 
-эквивалентны, 
и пусть существуют функции 
из такие, что для графов
и 
для любых из 
и v из 
выполняется условие
при условии 
где 
Тогда
Д о к а з а т е л ь с т в о. Следует из предложения 22 и предложения 3.
О п р е д е л е н и е 9.
Пусть 
Простой помеченный граф H порядка n будем называть
сильно локально f-упорядоченным графом,
если выполняются следующие
условия:
для каждой метки
графа H.
Для любого k из V не существует помеченного простого графа B,
изоморфного графу H, такого, что для B выполняется
и для каждой метки
граф B выполняется условие
Обозначим через 
- множество
всех сильно локально
f-упорядоченных графов, изоморфных графу G.
Д о к а з а т е л ь с т в о. Из
определения 9 следует, что
Покажем обратное включение
от противного.
Пусть
существует граф H из такой, что
Ясно, что локально f-упорядоченный граф H изоморфен
графу B из и B - локально f-упорядоченный
граф, следовательно 
Теперь из определения 9 видно, что
H - сильно локально f-упорядоченный граф.
Противоречие.
Предложение 25 доказано.
Д о к а з а т е л ь с т в о.
Ясно, что если 
то
Теперь пусть 
и
граф H из 
Из предложений 16,25refus1 имеем,
что 
Применяя предложение 14 получаем,
что для любого графа Y из 
выполняется
Из определения 9 имеем, что
для каждого графа Y из 
Выберем граф Z из 
Существует такая
пара 
из 
что 
Ясно, что
где 
Из
получаем, что для графа Z выполняется
Следовательно, 
Теперь из определения 9 видно, что
Отсюда
Предложение 26 доказано.
Полагаем
- множество всех меток v из 
для которых существует, по крайней мере, одна перестановка 
(зависящая от v)
из 
такая, что 
и
не пустое подмножество локально
f-упорядоченных графов, изоморфных графу 
не пустое подмножество сильно локально
f-упорядоченных графов, изоморфных графу 
Пусть из 
тогда обозначим через 
- множество всех (H,l)-эквивалентных
перестановок перестановке 
Очевидны следующие предложения:
Если 
то
Если 
то
Пусть 
Выберем из каждого K, 
по представителю
Полагаем
- множество всех представителей
Очевидно, что если 
из и 
то
Предложение 27.
Пусть H из из 
и
и
пусть для любых - (H,l)-эквивалентных
перестановок
существуют функции из такие, что для графов
и для любых из и v из выполняется
условие 
Тогда
Д о к а з а т е л ь с т в о.
Пусть 
то существует
перестановка 
из такая,
что 
Следовательно, в множестве
найдется такая перестановка 
, что 
-эквивалентны. Тогда из предложений 4. имеем, что
Применяя определение 9 имеем, что 
т.е.
Противоречие.
Предложение 27 доказано.
Из предложения 25,предложения 27 следует следующее
Предложение 28.
Пусть 
и
пусть выполняются условия предложения 
Тогда
Предложение 29.
Если f из 
то
помеченный полный граф G конечного порядка является сильно
локальноf-упорядоченным графом.
Пусть 
- множество всех функций из
таких, что для любого графа H из 
для любых
перестановок из 
из V
выполняется условие 2.4 и
для любого l из 
и
для любой из 
выполняется условие
Ясно, что 
где 
Из следствия 1 и предложения 5
имеем, что
Используя доказательство предложения 6, нетрудно
показать.
Предложение 30.
Пусть G - простой помеченный граф. Тогда
В дальнейшем считаем, что 
Так как случай n =1
тривиален.
Пусть граф H из и функция f из 
Предлагается следующий алгоритм сильного локального f-упорядочения графа
H.
Для каждой метки w из 
выберем единственную
перестановку 
такую, что
и
Через 
обозначим все выбранные перестановки,
т.е. 
Обозначим множество графов
через 
Положим также, что 
Заметим, что
когда X и Y принадлежат
Теперь для каждого графа 
строим
множество 
Для каждой метки w из
берем единственную перестановку 
такую, что 
и
Обозначим множество 
через
В множестве 
выделяем подмножество 
всех
графов Z с минимальным (относительно 
) 
Далее, аналогично с предыдущим шагом (числом n-1)
последовательно работаем с числами 
В итоге получим непустое множество графов 
Заметим, что во-первых, алгоритм конечен и не противоречив.
Во-вторых, в алгоритме сильного локального f-упорядочения 
реализован целенаправленный
перебор.
В-третьих, вообще говоря, 
зависит от выбора
перестановок 
Но из теоремы следует, что
не зависит от выбора соответствующих перестановок и
графа H из 
Предложение 31.
Пусть H из 
и пусть граф B
из
Тогда выполняются:
для каждой метки l из V.
Д о к а з а т е л ь с т в о.
Из алгоритма
сильной
локальной f-упорядоченности имеем, что
где
и
Из определений 
и 
следует, что 
Из (4.7) вытекает существование такой последовательности
графов 
что 
Полагаем, что 
Тогда, так как
имеем 
Следовательно, существуют
такие перестановки 
и метки 
что
и
Ясно, что 
для каждого i из 
Последовательно применяя предложение 17
для 
имеем, что
Так как 
то из предложений 3 имеем
для i из 
Напомним, что 
cледовательно, 
для i из
Пусть 
Тогда 
Из 
и (4.8)
следует,
что 
для 
Так как 
то 
и, учитывая, что имеем
для любого из 
Заметим, что 
следовательно
Применяя определение множества 
получаем, что
Отсюда, учитывая, что
и, считая 
для каждой
i из
имеем
где 
т.е.
для 
Из предложения 3 и
определения множества 
получаем, что 
для
Последовательно применяя предложение 18 к множествам
при 
и получаем, что
Следовательно, выполняется условие 
для
Предложение 31 доказано.
Следствие 4.
Пусть H из и пусть граф B
из 
Тогда выполняются:
для каждой
Предложение 32.
Пусть H из и пусть
графы 
из 
тогда 
Д о к а з а т е л ь с т в о. Так как
то
из предложения 2. имеем, что
Из определения множество 
получаем, что
и
для 
Пусть 
Так как 
то
и существует метка v из 
такая, что 
и выполняется
где 
тогда из 
и определения множества 
получаем,
что
для графа 
выполняются
Отсюда и из равенства 
следует
Аналогичным образом работаем с множеством 
и графом
Y.
В итоге получаем, что 
Следовательно, 
Предложение 32 доказано.
Предложение 33.
Пусть 
и
B - сильно локально
f-упорядоченный граф, изоморфный графу G.
Тогда 
Д о к а з а т е л ь с т в о.
Возьмем произвольный граф H из и
подадим на вход алгоритма сильного локального
f-упорядочения.
Ясно, что существует
перестановка из такая, что 
Из определения 9 имеем, что 
для каждой l из V, т.е. 
Из предложения 3 при 
получаем,
что 
Применяя предложение 14, получаем, что для каждого графа Z
из 
выполняется 
Так как B - сильно локально f-упорядоченный граф
и 
то
из предложения 20 при 
для графа B
получаем, что
Поэтому имеем 
т.е.
выполняются условия:
где 
Следовательно, метка 
лежит в 
Из алгоритма имеем
существование перестановки 
из
такой,
что 
Понятно, что для графа
имеем
Так как то
Из предложения 32 получаем, что
Так как по определениям, 
Из определения 8 следует, что
- (H,n)-эквивалентны.
Применяя предложение 22 для графов 
имеем
существование такой
перестановки 
из 
что 
Теперь для графа 
из 
из
предложения 3 при 
получаем, что
Из предложения 20 при для графа B имеем,
что 
и
для Z из
применяя предложение 14,
имеем, что для 
выполняется
Так как 
то 
и,
учитывая, что 
и 
имеем 
и из предложения 32 получаем, что
Применяя определение 9 получаем, что
для 
Из предложения 20t37 при 
для графа B
имеем, что
Поэтому 
т.е.
выполняются условия:
и
где 
Следовательно, метка 
лежит в 
Из алгоритма имеем существование
из 
такой, что 
Понятно, что для графа 
имеем 
Так как 
то 
Из предложения 32 получаем, что
Теперь, учитывая определения сильно локально
f-упорядоченного графа и множества 
в
силу пункта 2 следствия 4, получаем, что 
Из определения 8 следует, что перестановки
- 
-эквивалентны.
Применяя предложение 22 для графов 
имеем
существование такой
перестановки 
из 
что 
Далее, аналогично с предыдущим шагом (числом n-1),
работаем последовательно с числами 
В итоге получаем, что 
Из определения множества 
следует, что 
т.е. 
Так как граф B - сильно локально f-упорядоченный, то
для любого графа Z из
выполняются:
Следовательно, 
Тогда из определения имеем, что
Предложение 33 доказано.
Используя доказательство предложения 33 и предложение 3 нетрудно показать
Следствие 5.
Пусть 
из 
и
пусть B такой, что
для каждого
имеем
и для любого Y из такого,
что 
выполняется
тогда существует
такая последовательность
графов 
при 
Теорема 2.
Пусть G - простой помеченный граф и 
Тогда есть множество всех сильно локально
f-упорядоченных графов, изоморфных графу G.
Д о к а з а т е л ь с т в о. В силу
предложения 33, достаточно
показать, что любой граф из 
где 
является сильно локально f-упорядоченным. (Заметим,
что по пункту 2 следствия 4. для графа B имеем
для 
)
Допустим противное. Тогда в множестве 
существует такое наибольшее число k, что для него найдется
граф
Z из для которого выполняется
и
Если k = n, то из предложения 3 имеем, что
Из предложения 31 получаем
Так как 
то 
Отсюда и из 
имеем, что
Так как
то
Противоречие.
Пусть k < n. В силу выбора k имеем,
что 
при 
и
для 
Подадим на вход алгоритма граф H и
получим последовательность
графов 
такую, что 
Из предложения 3, учитывая, что 
и
определения множества 
получаем, что 
Так как 
то из
предложения 32 имеем, что 
Выберем из множества 
такой граф 
с минимальным
(относительно 
) 
т.е. 
Ясно, что 
и
Из следствия 5 для графа имеем
существование
такой последовательность
графов 
что 
при 
В алгоритме при построении множеств 
и
графов 
выбирается единственная перестановка из множества
равновозможных перестановок, поэтому, в общем случае,
графы 
и множества 
Пусть 
Так как 
то
выполняются условия:
где 
Следовательно, метка 
лежит в
Из алгоритма (получения 
) имеем
существование перестановки 
из такой,
что
Так как 
то
Из предложения 32 получаем, что
Так как по определениям,
Из определения 8 следует, что
- (H,n)-эквивалентны.
Применяя предложение 24 для графов 
имеем
Отсюда и из 
следует, что 
и существует такая перестановка из 
что 
и выполняются условия:
где 
Следовательно, метка 
лежит в 
Из алгоритма (получения ) имеем
существование перестановки 
из
такой,
что 
Понятно, что для графа
имеем
Так как 
то
Из предложения 3 и определения имеем
Так как 
и
то
и по предложению 32 получаем
следовательно 
Теперь, учитывая определения
и множества в силу пункта 2 следствия 4.,
получаем, что 
Из определения 8 следует, что перестановки
- 
-эквивалентны.
Применяя предложение 24 для графов 
имеем
Далее, аналогично с предыдущим шагом (числом n-1 ),
работаем последовательно с числами 
В итоге получаем, что
Так как 
то
получаем
противоречие.
Теорема 2 доказано.
Следствие 6.
Пусть f из 
тогда существует сильно
f-упорядоченный граф B, изоморфный граф G.
Из алгоритма следуют следующие предложения.
Пусть из 
1. 
2. 
3. 
4. 
Сложность алгоритма локального f-упорядочения
для функций из зависит
от сложности алгоритма построения
множеств
т.е. необходимо решить задачи:
Если i =n, то X =H.
Заметим, что построение множеств 
можно
совместить с решением задач. Множество 
формируется за 
перестановок. Оценка сложности
алгоритма построения множеств из
множеств равна 
. 
- множество
представителей множеств 
Автор благодарен А. Н. Фомину за внимание к работе.
Поступила 20.08.96
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ
тогда 
и 
тогда
тогда