Алгебраические методы анализа изображений, использующие группы симметрий и оптимизацию на графах тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Потанин, Николай Иванович

• Потанин, Николай Иванович
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Потанин, Николай Иванович

Содержание

■ А

Введение

Список обозначений

ГЛАВА 1. Изоморфизм простых графов

1. Локально ^-минимальные простые графы и полные инварианты

2 . Группа автоморфизмов простого графа

3. Алгоритм построения сильного локально ^минимального

простого графа для функции I из ^

ГЛАВА 2. Параметрический анализ экстремальных задач на множестве подстановок

4 . Параметрический анализ экстремальной задачи на множе-

стве подстановок

5 . Параметрический анализ задачи последовательного про-

граммирования

6 . Последовательности задач последовательного программи-

рования

ГЛАВА 3. Алгебраические методы анализа изображений, использующие группы симметрий и оптимизацию на простых графах

7 . Применение групп к сжатию произвольного множества

8 . Сжатие двумерных изображений с помощью групп симме-

трий

-39 . Задачи распознавания образов и анализа изображений

Заключение

Литература

ч

Введение диссертации (часть автореферата) на тему «Алгебраические методы анализа изображений, использующие группы симметрий и оптимизацию на графах»

Введение

Краткий обзор

Диссертация посвящена исследованию и разработке новых методов решения задачи классификации в распознавании образов и анализе изображений.

Так как задачи классификации, излагаемые в работе, являются разделом теории распознавания, то представляется целесообразным кратко рассмотреть содержательные истоки данной теории. Не претендующий на полноту и окончательность оценок обзор этой теории и будет нашей ближайшей целью. Отметим, что в основном обзор базируется на статьях Ю. И. Журавлева, Вл. Д. Мазурова, К. В. Рудакова, К. Фу, У. Гренандера, Д. Марра [8, 20, 21, 39, 51, 72, 81].

Появление вычислительных машин в 50-х годах привело к возникновению соображений, касающихся возможности использования ЭВМ для решений задач обработки плохо формализуемой информации, т.е. таких задач, для которых отсутствуют адекватные математические модели. К таким задачам, например, относятся задачи распознавания объектов на изображениях, задачи распознавания образов, задачи медицинской и технической диагностики.

На начальном этапе работы над проблемой распознавания было потрачено много усилий на попытки построить процесс распознавания, используя понятие "образ". Они сводились, сознавая условность клас»-сификации, к следующим направлениям:

1. Изучение образа как такового с целью выяснить, что представляют собой образы разных типов, какова их структура;

2. Построение системы распознавания на основе имитащщ способностей человека.

В последнем направлении можно выделить два подхода,

В первом подходе основной массив составили работы, авторы которых считали, что процесс решения плохо формализовашщх зада*} на ЭВМ должен моделировать основные аспекты процесса мышлений

Персептрон, предложенный Ф.Розенблаттом в 1957 году в качестве простой модели, воспроизводящей некоторые принципы работы мозга, послужил основой для создания целого класса обучающихся систем [54], что привело к исследованию некоторых конструкций для систем линейных неравенств. В последнее время работы в этом подходе приобрели практическую направленность в построении экспертных и нейронных систем [48, 49, 59].

Представители второго подхода (на основе которого сформировался алгебраический подход) исходили из посылки, что, несмотря на отсутствие модели того, как человек решает задачу, и несмотря на отсутствие адекватной математической модели реальной ситуации, можно, опираясь на здравый смысл, строить алгоритмы, которые реализуют нужный процесс преобразования информации.

К середине 1970-х годов, следуя обзору Ю. И. Журавлева, отметим формирование параметрических семейств алгоритмов, которые принято называть моделями алгоритмов распознавания, поскольку они, как правило, создаются в результате формализации интуитивных представлений о характере связей между входными и выходными данными конкретных задач. Решение практических задач в этой ситуации свелось к "настройке параметров", т.е. к решению проблемы выбора значений параметров, выделяющих из семейства оптимальный для данной задачи алгоритм.

Наибольшую известность среди моделей алгоритмов имеют алгоритмы метода потенциальных функций [1], комитетные алгоритмы [39, 42, 43, 44, 45], алгоритмы вычисления оценок, статистические [б] и т.д. Исследования каждой модели алгоритмов имеет свои особенности. Например, для школы Ю. И. Журавлева (ABO - алгоритмы вычисления оценок) — алгебрологические построения, для школы Вл. Д. Мазурова (комитетные алгоритмы) - двойственные конструкции для линейных неравенств [14, 16, 17].

Существенным представляется то, что на теоретическом фундаменте были разработаны универсальные пакеты прикладных программ распознавания Парк [32], Квазар [26, 40] и другие, с помощью которых были решены и решаются практические задачи распознавания

образов [3, 55, 58, 91].

Исходным пунктом развития алгебраического подхода послужила идея: из имеющихся семейств можно определенным образом выбирать некоторые алгоритмы и, используя корректирующие операторы, строить оптимальные алгоритмы для конкретных задач. Отметим, что при построении алгоритмов, в общем случае, не проводится детального анализа структуры распознаваемых объектов, а основное внимание уделяется исследованию самих процессов распознавания.

В*структурном подходе основной упор делается на исследование структуры образа и распознаваемых объектов. Начало структурного подхода положили работы Н. Хомского [85], в которых было показано, что в качестве метода описания естественного языка можно использовать порождающую грамматику. Оказалось, что в качестве метода описания образов можно тоже использовать грамматику. Также следует упомянуть анализ образа методом сверху вниз, введение древовидных структур данных, что послужило основой построению общих моделей описания образов: теория образов У. Гренандера [8] и информационный подход Д. Марра [51].

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

Об основных конструкциях и проблемах теории

распознавания

Одним из основных понятий в теории распознавания является образ. Образ (класс) есть множество всех объектов, сходных друг с другом в каком-либо фиксированном отношении. Распознать объект или образ объекта — значит указать, к какому образу он относится.

В задачах распознавания рассматривается некоторое множество объектов ш; предполагается что в этом множестве имеется набор подмножеств К-к,К-2,... ,Л*П, называемых классами. Точное описание классов неизвестно. Необходимо по известной информации о классах построить алгоритм, который относил бы неизвестный объект к некоторому классу.

Если объекты ги задаются значениями некоторых признаков

.7 = М,... ,п,

Х](и>) принимает значения из множества допустимых значений, то говорят, что исходная информация, представлена моделью стандартной обучающей информации. Описание объекта

1(ш) = (х1(ч]),х2{'ш),... ,хп(ии))

называется стандартным в алгебраическом подходе [23].

Заметим, во-первых, что в модели стандартной информации не учитываются организация (структура) объектов данных, а при решении многих практических задач, особенно в анализе изображений, это необходимо.

Во-вторых, требования представления исходной информации в стандартном виде для некоторых классов задач трудно выполнить, т.е. объекты представляются векторами разной длины (проблема "пустот" в данных).

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

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

Отметим, что в практических задачах распознавания образов структурный и алгебраический подход часто дополняют друг друга.

Во-первых, структурная информация об образах и объектах важна и должна быть использована, но непроизводные элементы (т.е. подо-бразы, структурой которых на данном этапе пренебрегаем) не всегда легко выделить, особенно при наличии шума и искажений.

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

Проблемы, возникающие в связи с представлением

формы объекта

Д. Ма'рр [51] указывал в 1982 году, что в задачах распознавания и выделения объектов на изображении особое место занимает информация о форме объекта. Так как для представления большинства видов информации о форме объектов необходимо использовать какую-либо систему координат, позволяющую описывать пространственные отношения, то поиск способов задания этой системы является одной из актуальных задач в анализе изображений. Если координаты задаются относительно положения наблюдателя, то Марр говорит, что в представлении используется система координат, привязанная к наблюдателю. Если местоположение задается в системе координат, определенной на наблюдаемом объекте, то это означает, что соответствующем представлении используется система координат, привязанная к объекту наблюдения.

При решении задач распознавания описания, ориентированные на наблюдателя, легче получать, но труднее использовать, так как различные виды объектов должны рассматриваться как различные объекты. В более сложных задачах распознавания, в которых учитывается пространственное расположение его компонентов, любое представление, привязанное к наблюдателю, будет, вероятно, чувствительно к ориентации объекта.

Альтернативой полному перебору является использование какой-либо из систем координат, привязанных к объекту наблюдения, и переход в результате к построению некоторого канонического описания,

не зависящего от расположения точки наблюдения. Было бы идеально, если бы для распознавания объекта даже при неизвестных положениях точки наблюдения, требовалось хранить в памяти лишь по одному описанию пространственной структуры каждого объекта (см. [51] 300 - 305 е.).

Отметим, что И. Б. Гуревич отмечал в статье [9] в 1989 году, что до сих пор отсутствуют < и» тематические математические методы формализации и анализа изображений. В подавляющем большинстве методы работы с изображениями являются чисто эвристическими и достоинство их, в сущности, определяется тем, сколь успешно им удается преодолевать "изобразительный" характер изображения "неизобразительными" средствами, т.е. опираться на процедуры, не зависящие от организации обрабатываемой информации в виде изображений.

Исходной целью исследований, результаты которых представлены в настоящей работе, было создание метода, который строит каноническое описание, пригодное для распознавания объекта (простого графа) по изображению.

Отметим, что если объект является простым графом, то проблема построения канонического описания объекта, как будет показано ниже, эквивалентна проблеме построения полного инварианта простого графа.

Особенность работы состоит в том, что при изучении изображений используются факты из теории групп, теории графов, теории дискретного программирования, теории распознавания образов.

1. Факты и определения из теории групп, которые используются в работе можно найти в книге [29].

2. Факты и определения из теории графов можно найти в книге [25] и статье [24].

3. Факты и определения из теории математического программирования, необходимые при изучении данной работы, читатель может найти в книгах и статьях И. И. Еремина [14, 15, 17, 18, 19].

4. Факты и термины из теории распознавания образов, необходимые при изучении данной работы, читатель может найти в книгах и статьях Вл. Д. Мазурова и его соавторов [ 39 - 46 ].

Отметим, что мы без оговорок используем теоретико-множественные аксиомы (в частности, лемму Цорна).

Перейдем к изложению содержания диссертационной работы, состоящей из введения, трёх глав и списка литературы.

Первая глава посвящена вопросам изоморфизма простых графов. Вводится основное для всей работы понятие "локально /-^ минимальный" граф, изучаются его свойства, предлагается алгоритм ■ нахождения для произвольного простого графа О всех локальных /минимальных графов, изоморфных данному графу О. В § 2, используя множество всех локально /-минимальных графов, изоморфных графу

строится группа автоморфизмов графа (?.

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

Третья глава состоит из 3 параграфов, в которых описывается применение алгебраических методов для обработки изображений.

В § 7, 8 исследуются вопросы сжатия изображений и множеств, с помощью групп, частичных групп и взаимно-однозначных отображений.

В параграфе 9 решается задача классификации простых графов. Предложена схема построения системы координат, привязанной к объекту (простому контуру) и ориентированной на представление его формы для задач распознавания, описывается технология анализа текстур.

Автор выражает глубокую признательность всем коллегам из отделов математического программирования, алгебры и топологии и теории приближения функций ИММ УрО РАН и других научных организаций за доброжелательное и конструктивное отношение к его результатам.

Выражаю благодарность доктору физ.- мат. наук Вл. рЦ. Мазурову и кандидату физ.- мат. наук А. Н. Фомину, которые о тжиманием и тактом руководили исследованием. *

Список обозначений

В работе используются следующие обозначения: □ — помечает конец доказательства.

def

== — есть равенство по определению. R — множество вещественных чисел. N — множество натуральных чисел. G — простой помеченный граф порядка п. AÍG) — матрица смежности графа G. Aut(G) - группу автоморфизмов графа G. Ga — абстрактный граф порядка п. Vq — множество вершин графа G, п = \Уд\

V = Vn = {1,2,..., п} — множество меток.

¡i — взаимно однозначное отображение множества Vq на V.

|Х| обозначает мощность множества X.

B(Vn) ■— булеан на множестве Vn.

■< — отношение линейного порядка на В(Уп).

B*(Vn) непустое подмножество из B(Vn),

6 В*(У)} обозначает минимальный элемент, относительно порядка :<, в B*(V).

Ujei ¿>(Mj(G')) — прямое произведение симметрических групп S(Mj(G)) подстановок на MjiG).

V — группа всех подстановок множества меток Vn вершин графа GjTr.jyeP;

е — тождественная подстановка из V, т.е. единица группы V. N^q^ig)) = 7Zg(k{íg)) ~ множество меток вершин смежных вершине с меткой 7г(г'с) в графе 7г(G).

Vi{G) — множество всех 7г из V таких, что 7r(j) = j и ^(Ncij)) — Nc{j) для любого j G {п, п — 1,..., I + 1}, 1 < I < n,Tn{G) = V. S¡(G) =mmveVltne<p¡{G){f(G,v,ir)\TT{v) = /},

X¡(G) — множество всех пар (V, тг*) из V¡ х V¡(G) таких, что Sf(G) = f(G,v*.ir*) и 7T*(v*) = l.

= п}.

Х£{С) - множество всех пар (и*, 7г*) из V х V таких, что 7г*(у*) = п и Для 1 < I < п,

N¡(0) & К(б'), Хс{п),Хс(п - 1),...,5/(6'),Мс(1)},

^ = Щ(0) ^ [Кс(п), Л^п - 1),..., X — знак полупрямого произведения групп. <1(0,У,1Т) = \Хж(0)(тг(У))\,

1 ' ' 0, если = 0-

Г(5 — множество всех помеченных графов вида 7г(<3), тг EV.II е Тс-

0{ (О) & {К^Ш) 1к7г) е Х[(0)}, 1е{ 1,2,...,«}. г(°(с?) *й i х2{1) = е г/(6')}, £ е г[(6)}.

Т - множество всех помеченных простых графов порядка п.

— множество всех функций / Е Р таких, что если Я Е Г^ и (у, 7г) 6 Х[(Н), то для графа 7г(Я) выполняется (/, е) £ Х[(7т(Н)) для любого I £Уп.

Рд - множество всех функций / е для которых выполняется условие: (I, е) е л"/(тг(я)) для любых I еУп, ж е ^(Я), я е гс.

— множество всех функций / из ^ таких, что если Я 6 Г<?, (г/,£) Е Х[ (Н

= тт-<{а;|х Е ф((Я)}, то для графа £(Я) выполняются $((«#)) < 3{(Н)~Мт(1) = пшь<{ф Е (С(Я))}. Т7^ — множество всех функций / £ ^ таких, что для любых простых помеченных графов Б, Я из Г^ выполняется условие Г{(Б) = Г£(Я).

— множество всех функций из Гд таких, что для любого графа Я из Г<з, для любых подстановок 7г, £ из "Р, V из выполняется условие: /(Я, V, 7г£) = f(tl(H),t;(v), 7г) и для любого I из {2,3,..., п} и для любой 6 из Т1-\{Н) выполняется /(Я, I, е) = /(Я, 6).

Р* — множество всех функций вида -к) : Т х V —>■ Л. Тд - множество всех локально /-минимальных графов, изоморфных графу С. Г^ - множество всех сильно локально /-минимальных графов, изоморфных графу С.

Г5/* — не пустое подмножество сильно локально /-минимальных графов, изоморфных графу Г^/* С Г^Л

Р^'1 — множество н,сех (Я, ^-эквивалентных подстановок подстановке тг из -Р/(Я).

ГЛАВА1

»

к Т

ИЗОМОРФИЗМ ПРОСТЫХ ГРАФОВ

Как отмечалось во введении задача описания объекта (простого помеченного графа) распознавания в данной работе сводится к проблеме изоморфизма простых помеченных графов.

Пусть Ус — множество вершин графа С, п = '

Уп = {1,2,..., п} — множество меток.

Если задано взаимно-однозначное отображение /< множества вершин графа (? на множество Уп, то С? назовем помеченным графом. Число /.¿(а) называем меткой вершины а.

Пусть V — группа всех подстановок множества меток Уп верпшн графа О, 7Г, г) €/Р; е — тождественная подстановка из V, т.е. единица группы V.

• Для любой подстановки тт из V под 7т(С) понимается граф, множества вершин и рёбер которого совпадают с соответствующими множествами графа С ив котором метка любой вершины а есть тг(р(а)).

В настоящей работе под графами понимаются помеченные простые графы с одним и тем же числом вершин п. Для графа С через N(1) = N0(1) обозначим множество меток всех вершин, смежных с вершиной с меткой г = гд.

-^тг(С)(7Г(гс)) = T^gW^g)) ~ множество меток вершин смежных вершине с меткой tt(i'g) в графе тг(с?).

Граф, полученный из G удалением всех меток, называется абстрактным графом и обозначается через Ga.

Два помеченных графа G'i, G'2, будем считать изоморфными (т.е. Gi = G2), если они изоморфны как абстрактные графы (т.е. G\ = Gf)-

S:

I'

Определим отношение линейного порядка ■< на B(Vn):

1. Если X = 0, У € B(Vn), то считаем X -< У.

2. Если X = {¿1, ¿2,is}, Y = {л, ¿2, где гь г2,..., гв, и Jbhi • • • * jp — числа, упорядоченные по возрастанию, то X -< У, если ¿1 < л или ц = л, г2 = л, • • •, ¿4-= Л? и ¿¿+1 < jk+i для к < min{s, р}.

3. Если |Х| < |У| и ik = jk при 1 < к < |Х|, то полагаем

X<Y.

Положим X ■< У, если X -< У или X = У.

Для любого натурального числа s отношение ^ можно продолжить на 5(K)S. Пусть

X* = [Х„ Xs_b... ,Xi], У* = [У„ ys_i,.. •, У1] £ B(Vn)\

тогда

x* у*,

если

Х8 -< у5

или

xs = у«, х5_! = у5_1,..., = ys-fc+i,

и xs-k -< Ys-k Для некоторого к, 0 < к < $.

Положим X* ^ У*, если X* -ч У* или X* = У*. Пусть B*(V) непустое подмножество из B(V), тогда

пш1ч{ф £ B*(V)}

обозначает минимальный элемент (относительно порядка <) в B*(V).

§1. Локально ¿-минимальные простые графы и полные инварианты

Конечный неориентированный граф называется простым, если он не содержит петель и кратных ребер (см., например, [25], стр. 6). Сложность работы алгоритма - количество элементарных операций, вы- , полняемых этим алгоритмом в худшем случае. Алгоритм называется ! алгоритмом полиноминальной сложности, если его сложность ограничена полиномом от длины входного слова. Задача распознавания, изоморфны ли два данных графа или нет, считается трудной. Остается открытым вопрос - принадлежит ли она классу задач распознавания, решаемых за полиноминальное время (см. обзор [24]).

Определение 1.1.1. Пусть ф - функция, относящая каждому помеченному графу £ некоторый элемент ф(0) из множества М произвольной природы. Эту функцию будем называть инвариантом, если на изоморфных графах её значения совпадают, то есть для любых иО':

в ^ С ф{в) = ф{С).

Инвариант назовем полным, если он дает необходимое и достаточное условие изоморфизма:

Ясно, что построение полного инварианта, вычислимого за полиномиальное время, означало бы решение проблемы изоморфизма графов (см. обзор [24], стр. 130). О некоторых неудачных попытках построения быстро вычислимых полных инвариантах можно прочесть в [93, 94].

Определение 1.1.2. ([25], стр. 25). Пусть О - помеченный граф с п вершинами. Составим п х п матрицу А(0) = (аг;-) :

(1, если вершины с метками г, ]' в графе С смежны, 0, если эти вершины не смежны.

Матрица А{Сг) называется матрицей смежности помеченного графа С.

Матрица смежности однозначно определяет граф, но не является инвариантом графа: при переходе от одной нумерации его вершин к другой она претерпевает перестановку строк и точно такую же перестановку столбцов. Функция от элементов а^, не меняющая ни при каких перестановках строк и столбцов матрицы А(С), является инвариантом абстрактного графа С (например, наименьший или наиболь-шийсдвоичный код матрицы А(С) ([25], стр. 26)).

Напомним, что для 1 <1 < п

N[(0) У [31(С1М0(п18и(0)^0(п - 1),... ,5/(а),ДГс(0],

Определение 1.1.3. Пусть / € Р. Простой помеченный граф Н порядка п будем называть локально /-минимальным графом, если выполняются следующие условия:

(1) (I, е) € Х[(Н) для каждой метки I (1 < / <п) графа,Н.

(2) Не существует помеченного простого графа В, изоморфного графу Н, такого, что для В выполняется условие (1) настоящего определения и N{(1!) -< N/(Я).

Заметим, что термин "локально" используется во многих разных смыслах, в настоящей работе термин "локально /-минимальный" введен в силу того, что граф упорядочивается с помощью окрестностей его вершин.

Отметим также, что не для всех функций

f{G,v1'lг):T хУпхТ-> В.

существует локально /-минимальный граф. Например, легко проверить, что для функции

1, если 7г = е, О, если тс ф е,

не существует локально /-минимального графа.

/(С, г/, 7г)

Теорема 1.1.1. Пусть С - простой помеченный граф порядка п, и пусть функция / Е Рд- Тогда существует локально /минимальный граф, изоморфный графу С.

Доказательство. Выберем из Г<? все графы Я, для которых выполняется включение (1,е) Е Х({Н) для любого I из {1,2,...,п}. гЧерез Г^ обозначим множество выбранных графов. Из условия / Е Рв следует, что Г^ ф 0.

Введем в Г^ линейный порядок, считая Л" ^ У, если

Х{(Х) < М{(У).

Понятно, что минимальные относительно порядка ^ элементы из Г^ являются локально /-минимальными графами, изоморфными графу й. Теорема 1.1.1 доказана. □

Заметим, во-первых, доказательство теоремы 1.1.1 конструктивно, т.е. позволяет находить для произвольного простого помеченного графа О локально /'-минимальные графы, при / Е Рв-

Во-вторых, из / Е Рд не следует равенство Г^ = Тд- Например, для с1(С,и, 7г) и графа 6', заданного матрицей смежности А(С?) :

0 10 0 0 10 110 0 10 0 1 0 10 0 1 0 0 110

имеем, что О Е так как (5,е) не принадлежит Х~(С).

В следующей теореме показывается, что если Я — локально /минимальный граф, то М{(Н), А(Н) являются инвариантами.

Теорема 1.1.2. Пусть Сг", изоморфные (в частности, равные) простые графы порядка п. - помеченный граф, полученный из с помощью меток из Уп = {1,2,..., п}, г = 1,2. Если ~

локально /-минимальные графы, то

N{(0^ = N{(0-2), А(01) = А(С2).

Доказательство. Из условий предложения следует, что 0\ = Так как С\ - локально /-минимальный граф, то Ьг{(С 1) ^ N{(02), но 6'2 - также локально /-минимальный граф, поэтому ]У/(£2) :< N({0^. Таким образом,

Г ■(

Из определения Щ (О) и (*) следует, что

Л(б?0 = А(<32).

Теорема 1.1.2 доказана. □

С л-едствие 1.1.1. Матрица смежности локально f-минимального графа является полным инвариантом:

Теорема 1.1.3. Пусть С?",^ — простые абстрактные графы порядка п. — помеченный граф, полученный из 0е- с помощью меток из Уп = {1,2,..., п},г = 1,2. Если 0\, О2 — локально /-минимальные графы и

iY1/(G1) = М{(02), то = -А((?2), и графы С^ С^ изоморфны.

Следствие 1.1.2. Если Н — локально f -минимальный граф, то К{ (Н) — полный инвариант.

Отметим, что изменяя функцию / и линейное отношение -<, мы можем построить бесконечное число полных инвариантов.

Обозначим через Тд - множество всех локально /-минимальных графов, изоморфных графу й.

Предложение 1.1.1. Пусть / 6 тогда С Г£(С?).

Доказательство. От противного. Пусть Г£((?), тогда существует такой граф В из Г^, что В £ Г{((?). Из определения 1.1.3 имеем, что (п,е) Е Х£(В). Противоречие, так как из / Е Рд следует, что

ТЦВ) = Г{(С). Предложение 1.1.1 доказано. □

§2. Группа автоморфизмов простого графа

Напомним: Са — абстрактный простой граф порядка п, УСа = #2, • • •' хп] ~ множество вершин графа Оа. Если р, взаимно-однозначное отображение множества вершин графа С на множество Уп {1,2,..., п} натуральных чисел, то говорим, что (7 — помеченный граф и число, соответствующее вершине, называем её меткой ц(х{) = г.

Обозначим через АЫ(0) - группу автоморфизмов графа которая действует на множестве Уд.

Ясно, что АЫ(в) = АЫ{Оа).

Каждому автоморфизму а из АЫ(С) поставим взаимно - однозначным соответствием подстановку тта из V такую,что

2' П

\ ки к-2, ..., кп I

где а(Уг) = уМ{).

Ясно, что а = (71*(72 —»• 1га — тг^*^,, множество Аи^(С) = {тг^сг Е Aгií(G') - есть группа подстановок, действующая на V.

Отметим, что и(0) — помеченный граф, в котором вершина с меткой % в графе 6 имеет метку к{. Далее нам понадобится определение группы и частичной группы.

Определение 1.2.1. ([?], с.504) Пусть 71,72 — допустимые преобразования, т.е. преобразования, которые не выводят преобразуемые объекты за пределы рассматриваемого класса, образуют группу преобразований 0. Это означает, что для любых 71,72 из О их произведение 7172 ( последовательное выполнение преобразований 71 и 72) гпакже допустимо. Тождественное преобразование е( сохраняющее преобразуемый объект неизменньш ), очевидно, всегда

допустимо. Оно обязательно включается в любую группу преобразований. Кроме того, в группу включаются преобразования 7-1, обратные всем преобразованиями группы. Обратное преобразование, выполненное после прямого преобразования, возвращает объект в исходное состояние, т.е. 7-17 = 77"1 ==

Если произведение 7172 не обязательно принадлежит допустимому множеству преобразований (или вообще не существует), то говорят о частичной группе преобразований.

Поясним необходимость введения частичных групп преобразований, рассмотрим пример распознавания буквы Е. При небольших поворотах исходного образца этой буквы она продолжает идентифицироваться как та же буква. Однако при повороте на 90° против часовой стрелки она примет вид Ш и будет идентифицироваться как другая буква (буква "ш"). Поскольку поворот на 90° может быть представлен в виде малых поворотов, то в данном случае допустимой будет лишь частичная группа.

Теорема 1.2.1. Пусть Са - абстрактный граф порядка п и Тд - непустое множество всех локально f—минимальных графов, полученных из С1 с помощью меток из Уп = {1,2,..., п}, Gi 6 1 < г < ¡4|. Тогда подстановка

есть автоморфизм графа (?а, где ^ - вершина с меткой 3 в помеченном графе (?г-,1 < г < 1 < к < |г£|, а множество А11/{С) {<5г&|1 < г,к < есть частичная подгруппа группы

автоморфизмов абстрактного графа О.

Если для каждого ж — 8182, 8\, $2 Е А£//((?) и для любого 2 из {1,2,..., выполняется:

/(<^,г,е) = /(тг (С',-),2-,е), (1.2.1)

то множество А11/{0} есть подгруппа группы автоморфизмов абстрактного графа Оа.

Доказательство. Не ограничивая общности, считаем, что О € Из теоремы 1.1.2 имеем, что

N{(0$ = #/(<?*),

для любых г,*, 1 < г,* < \Тд\. Отсюда легко увидеть, что

8и е Аи^Оа), \

т.е. А11/(С) есть подмножество из АЫ(Оа).

Заметим, что тождественный автоморфизм е графа С принадлежит А\7/(0), и

8ц8ц = е , 6^ = буби, 6ц, 6ц, 8{р, 8^ € А£//((?), 1 < < |Г£|.

Следовательно, АЛ ¡{С] — частичная группа (по определению 1.2.1).

Пусть выполняется (1.2.1). Покажем, что множество А11/(0) есть подгруппа группы автоморфизмов абстрактного графа Са.

Ясно, что если \Тд\ = 1, то А11/(С) = {е} — подгруппа группы автоморфизмов абстрактного графа Са. Пусть \Тд\ > 1. Рассмотрим два случая.

1. Пусть вершины ух, уу с метками х,у в графе О смежны. Выберем, произвольным образом, подстановки <51? 6-2 из А1/¡(О). Так

как А11/(С) подмножество группы АЫ{0), то 8182 — автоморфизм графа Поэтому вершины ^1^2(^3/) смежны. Следовательно,

смежны вершины с метками ^^(ух)), ^^(Уу)).

Отметим, что непосредственно проверяется справедливость следующего равенства:

Отсюда имеем, что в графе ^¿^(С?) вершины с метками ^^(ж), кв^у) смежны.

2. Если вершины с метками х, у не смежны в графе <3, то аналогично первому случаю доказывается, что в графе тт^(0) вершины с метками 7^,5,(2),б,(у) не смежны.

В силу выбора меток х, у получаем, что

Щ(С) = Щ(тг51б2(С)). Из условия 1.2.1 следует, что для любого г из Уп выполняется

5/ (С) = 5/ (тгМ2((?)).

I

•п Таким образом имеем

т.е. ¿162 6 Аи¡{О). Следовательно, множество Аи^{С) есть подгруппа группы автоморфизмов абстрактного графа (?а. Теорема 1.2.1 доказана.П

Ясно,что если сг автоморфизм графа С, то сг(0) = О и 7га(С?) = С. Следовательно, очевидно следующее

Предложение 1.2.1 Пусть выполняются условия теоремы 1.2.1 и пусть для любого графа Н *из Тд, для любых V из V иттизТ выполнено

/(Я,г/,тг) = /(тга(Я),г;,7г), тг„ € Аи^{С). (1.2.2)

Тогда

Аи/(0) = Аиг{в).

§3. Алгоритм построения сильного локально ¿-минимального простого графа для функции из ^

Определение 1.3,1. Пусть / (е К Простой помеченный граф Н порядка п будем называть сильно локально /-лшнимальным графом, если выполняются следующие условия:

1. (/, е) Е Х{(Н) для каждой метки I (1 < I < п) графа Н;

2. Для любого к из Уп не существует помеченного простого графа В, изоморфного графу Я, такого, что для В выполняется -< М[(Н) и для каждой метки т, (т > к) графа В выполняется условие (т,е) е л"£(б).

Отметим, что условия пунктов 1 в определениях локального /минимального графа и сильно локально /-минимального одинако-- вы; различие между определениями заключается во вторых пунктах. Условие пункта 2 определения 1.3.1 более сильное, чем условие пункта 2 определения 1.1.3, т.е. сильно локально /-минимальный граф всегда будет локально /-минимальным графом (смотри следующее предложение), а обратное не верно. Например, пусть

/№,г,е) = 1, /(#1,г,тг) > 1, для 7Г ф е /(#2,п,е) = 0, /(#2,п-1,е) = 5, /(#2, п - 1, тг) = О, /(Я;-,г,е)>1, /(Л>,»,тг) >1,

ЯЬЯ2,Я,- Е Гс,Е\фЕчф Ну

Ясно, что локально /-минимальный граф Н\ не является сильно локально /-минимальным графом, так как

1 МЦН2) -< мЦНг).

Обозначим через Г^/ - множество всех сильно локально /-минимальных графов, изоморфных графу С.

Следующее предложение показывает, что если для / из Р существует сильно локально /-минимальный граф, то любой изоморфный локально /-минимальный граф будет сильно локально /-минимальным графом.

Предложение 1.3.1. Пусть / е Р и Г^/ ф 0, тогда

т3^ _ г/ .

1 в — 1 в-

Доказательство. Из определения 1.3.1 следует, что Г5/ С

Покажем обратное включение от противного. Пусть существует граф Я из Гд такой, что Я 0 Г^Л Ясно, что локально /-минимальный граф Я изоморфен графу В из Г^/ и В - локально /-минимальный граф, следовательно ^/(Б) = N[(11). Теперь из определения 1.3.1 видно, что Я - сильно локально /-минимальный граф. Противоречие. Предложение 1.3.1 доказано. □

Предложение 1.3.2. Пусть / е Рд г) Рд, тогда

г5/ с г£°((?).

Доказательство. Ясно, что если Твд = 0, то Г^ С Г£°(<3). Теперь пусть Г^/ ф 0 и граф Н принадлежит Г^/. Из предложений 1.1.1, 1.3.1 имеем, что Г^ = Г^ С Г£((?). Применяя предложение 2.4.5, получаем, что для любого графа У из Г{(Я) выполняется (п,е) Е Х1(У). Из определения 1.3.1 имеем, что АГ1(Н) -< для каждого графа У из Г'{(Я). Выберем граф 2 из

Г£°(Я). Тогда существует такая пара (г>,£) из что X — £(Я).

Ясно, что

Nг(п) = Пн{^(у*) = ттч{х|1 € <2{(Я)},

где <&(Я) = {ТгяМг;))|(я;,7г) 6 ХЦН)}.

Из / Е Гд получаем, что для графа Е выполняется

1Ъ(п) < ^я(п).

Следовательно, N1*^) < Л'/*(Я). Теперь из определения 1.3.1 видно, что = Я/*(Я). Отсюда Я Е Г£°(<3). Предложение 1.3.2 доказано.П

Полагаем У/(Я) = {¿|(г,тг) Е Х/(Я)}. У/°(Я) - множество всех меток г из У/(Я), для которых существует, по крайней мере, одна подстановка 8 (зависящая от г) из ^(Я) такая, что (г, 8) Е Х{{Н) и

7гя(ед) = ы^{7гя(тг(0)|(*>) е Х[(Н)}.

Гд не пустое подмножество локально /-минимальных графов, изоморфных графу С, Тд С Г д.

Гд^* не пустое подмножество сильно локально /-минимальных графов, изоморфных графу С, Г^/* С Г^Л

Пусть 7Г из 'Р/(Я), тогда обозначим через VI1,1 — множество всех (Я, ^-эквивалентных подстановок подстановке 7г. Очевидны следующие предложения:

1. Если 7г то = 1

2. Если 7Г то -рв'1 П V*'1 = 0. Пусть

^(Я) {^я''|тг е Р/(Я)}.

Выберем из каждого X, X £ /С/(Я), по представителю 7г.

Полагаем Ф/(Я) - множество всех представителей тт. Очевидно, что

Н,1

если 7Г, £ из Ф;(Я) и £ ^ 7Г, ТО 7Г

Предложение 1.3.3. Пусть Я из Г<?, / из / £ {2,3,..., п} и

Г^*СГ/(Я),

и пусть для любых 7Г1,7Г2 - (Н,1)-эквивалентных подстановок существуют функции ф{_1 из такие, что для графов 'щ(Н) и 7Г2(Я), для любых тг из Т>1-1(п1{Н)) и V из выполняется условие (2.6.18). Тогда

Г&" С и^я)^(тг(Я)).

Доказательство. Пусть В 6 Г^*, то существует 7Гх из 7^(Я) такая, что В = 7Г¡(Я), (г, ттх) £ Х[(Н), г е V/. Следовательно, в множестве Ф/(Я) найдется такая подстановка 7Г2, что 7гь 7Г2 (Я, ^-эквивалентны. Тогда из предложения 2.6.5 имеем, что Г[_1(тг2(Я)) = Г^^тг^Я)). Применяя определение 1.3.1 получаем, что (I - 1,е) £ Х[^(В) т.е. В £ Г{^(В) = ¡^(^(Я)). Противоречие. Предложение 1.3.3 доказано.П

Из предложений 1.3.1, 1.3.3 следует следующее

Следствие 1.3.1. Пусть ф 0, С Г {(Н) и пусть выполняются условия предложения 1.3.3. Тогда

Г£ С ия-6ф,(я)Г/_1 (7г(Я)).

Алгоритм построения сильного локально ¿минимального простого графа для функнди f из

т

-к.т

Напомним: Рд — множество всех функций из Гд таких, что для любого графа Я из Г^, для любых подстановок 7Г, ^ из г> из Уп выполняется условие: /(Я, 1>,7г£) = /(£(Я),£(г;),7г) и для любого I из {2,3,...,п} и для любой 8 из Т^^Н) выполняется

Пусть граф Я из Тс и функция / из В дальнейшем считаем, что 2 < п. Так как случай п = 1 тривиален. Предлагается следующий алгоритм построения сильного локально /-минимального графа.

Для каждой метки V из У/°(Я) выберем единственную подстановку 7Гу такую, что (г>, тт") £ ХЦН) и

Яя (<М) = пш^ЯяМОЖ», Е А'/(Я)}.

Через У/(Я) обозначим все выбранные подстановки, т.е.

У/(Я) = {тг> € У/°(Я)}.

Обозначим множество графов {"7г(Я)|7г £ У/(Я)} через Т/(Я). Положим также, что

бЦЩ^ТКН).

Заметим, что ]Ух(п) = Ху(п), когда X и У принадлежат Г/(Я).

Теперь для каждого графа X £ ^(Я) строим множество Уп-\{Х). Для каждой метки v из у^^х) берем единственную подстановку тг™~1 такую, что (г?, 7т"-1) £ ХЦ^Х) и

^л-«'1^)) = тш^{7гл-(<0)1М) € л:их)}.

Обозначим множество {тг(Х)|7г £ У/_1(Л") через Т{_г(Х).

В множестве VxeDL(H)Tn-i(X) выделяем подмножество D{_i(H)

всех графов Z с минимальным (относительно -<) N^l^Z).

Далее, аналогично с предыдущим шагом (числом п — 1) последовательно работаем с числами п — 2, п — 3,..., 2.

В итоге получим непустое множество графов D[(H). Заметим, что во-первых, алгоритм конечен и не противоречив. Во-вторых, в алгоритме сильной локально /-минимизации (/ € Fjj) реализован целенаправленный перебор. В-третьих, вообще говоря, D{(Я) зависит от выбора подстановок ттгу. Но из теоремы 2.6.1 (смотри стр 53) следует, что D{(H) не зависит от выбора соответствующих подстановок и графа Я из TG.

Отметим, что из алгоритма следуют следующие предложения. Пусть X, Y из D{(Я), г е {2,..., п}. Тогда 1 .T/(X)eD{(H).

2. N{*(X) = Ni*{Y).

3. Т/(Х) П T/(Y) = 0 для X ф Y.

Сложность алгоритма сильной локально /-минимизации для функций из Fq зависит от сложности алгоритма построения множеств

vf\x\ vf(H), ie{2,...,2}, xeD{(H),

т.е. необходимо решить задачи:

v£Vi,TT£Vi{X)

mm^{1Zx(7r(v))\(v^)eX((X)}.

Если г = п, то X = Я. Заметим, что построение множеств У'/(Х) можно совместить с решением задач. Множество Т/(X) формируется за \Y/(X)\ подстановок. Оценка сложности алгоритма построения множеств D{(Я) из множеств Т/(Х) равна 0{\D*(H)\log \D*{H)\) (см. например, [2]). D*(H) — множество представителей множеств Т/(Х), х е Dfi+l(H).

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Потанин, Николай Иванович

Основные результаты, полученные в работе:

1.гРешена задача приведения простых графов к виду, удобному для распознавания с помощью предложенного Ю. И. Журавлевым алгебраического подхода.

2. Введено новое понятие "локально /-минимальный граф" и исследованы его свойства. Обоснован алгоритм построения для произвольного простого помеченного графа О локального /минимального графа, изоморфного С для функции / из класса введенного в данной работе. С помощью множества всех локально /-упорядоченных графов строится частичная подгруппа группы автоморфизмов простого графа, получены условия, когда данная частичная подгруппа есть группа автоморфизмов графа.

3. В результате проведенного параметрического анализа дискретных задач оптимизации на допустимом множестве подстановок, в которых целевая функция выбирается из множеств введенных в данной работе, получены критерии устойчивости.

-74-Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Потанин, Николай Иванович, 1999 год

Литература

[1] Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. -М.: Наука, 1970. -320 с.

[2] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979. -536 с.

[3] Беляков В.В., Кисляк В.М., Потанин Н.И. Задача диагностики и прогнозирования детской заболеваемости // Информ. бюлл. АМП. - Екатеринбург: УрО РАН, 1995, № 5. - С. 114.

[4] Берж К. Теория графов и ее применения. -М.: ИЛ, 1962. -319 с.

[5] Бурбаки Я. Теория множеств. -М.: Мир, 1965. -455 с.

[6] Вапник В.Н., Червоненкис А.Я. Теория распознавания образов. -М.: Наука, 1974. -418 с.

[7] Глушков В.М. Основы безбумажной информатики. -М.: Наука, 1982.-552 с.

[8] Гренандер У. Лекции по теории образов. Том 1. -М.: Мир, 1979. -384 с. Том 2. -М.: Мир, 1981. -448 с. Том 3. -М.: Мир, 1983. -432 с.

[9] Гуревич И. Б. Проблема распознавания изображений // Распознавание, классификация, прогноз. -М.: Наука, 1988. Вып. 1. -С. 280 - 329.

[10] Дубровин Б.А., Новиков С.П., Фоменко А.Т. Современная геометрия: методы и приложения. -М.: Наука, 1986. -760 с.

[11] Емеличев В.А., Супруненко Д.А., Танаев В.С. О работах белорусских математиков в области дискретной оптимизации // Изв. АН СССР. Сер. техническая кибернетика. -1981. № б. - С. 25 - 45.

[12] Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. -М.:

Наука, 1981.-207 с. *

Ъ

[13] Емеличев В.А. Лекции по теории графов. -М.: Наука, 1990. -384 с.

[14] Еремин И. И. Обучение распознаванию образов в условиях линейной разделимости//Метод комитетов в распознавании образов. -Свердловск: УНЦ АН СССР, 1974. -С. 41 - 57.

[15] Еремин И.И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. -М.: Наука, 1976. -191 с.

[16] Еремин И.И., Мазуров Вл.Д. Вопросы оптимизации и распознавания образов. -Свердловск: УНЦ АН СССР, 1979. -64 с.

[17] Еремин И.И., Мазуров Вл.Д. Нестационарные процессы математического программирования. -М.: Наука, 1979. -288 с.

[18] Еремин И. И. Противоречивые модели оптимального планирования. -М.: Наука, 1988. -160 с.

[19] Еремин И. И. Двойственность для Парето-последовательных задач линейного программирования // Тр. ИММ УрО РАН. -Екатеринбург: УрО РАН, 1996. -Т. 3. -С. 245 - 260.

[20] Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. Вып. 33.-1978.-С. 5-68.

[21] Журавлев Ю.И. Корректные алгебры над множествами некорректных алгоритмов // Кибернетика. -Ч. I, -1977. № 4. -С. 14 - 21. ~Ч. И, -1977. № 6. -С. 21 - 27. -Ч. III, -1978. № 2. -С. 35 -43.

[22] Журавлев Ю.И., Рудаков K.B. Об алгебраической коррекции процедур обработки (преобразования) информации // Проблемы прикладной математики и информатики. М.: Наука, 1987. -С. 187 - 198.

[23] Журавлев Ю.И., Гуревич И. Б. Распознавание образов и анализ изображений // Искусственный интеллект. В 3-х кн. Кн. 2. Модели и методы: Справочник / Йод ред. Д.А. Поспелова. -М.: Радио и связь, 1990. - С. 149- 191.

[24] Зесляченко В.Н., Корниенко Н.М., Тышкевич Р.И. Проблема изоморфизма графов // Зап. научн. семин. ЛОМИ. - Л.: Наука, 1982. Т. 118. -С. 83 - 158.

[25] Зыков A.A. Основы теории графов. -М.: Наука, 1987. -381 с.

[26] Казанцев B.C. Задачи классификации и их программное обеспечение (Пакет КВАЗАР). -М.: Наука, 1990. -135 с.

[27] Калужнин Л.А., Сущанский В.И., Устименко В.А. Применение ЭВМ в теории групп подстановок и её приложениях // Кибернетика, 1982. 6. - С. 83 - 101.

[28] Калужнин Л.А., Сущанский В.И. Преобразования и перестановки.-М.: Наука, 1985.-160 с.

[29] Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. -М.: Наука, 1982.-288 с.

[30] Ковалев М.М. Метод частичных порядков // Доклады АН БССР, 1980.-Т. 24, № 2.-С. 113 - 116.

[31] Ковалев М.М. Матроиды в дискретной оптимизации. -Минск: ВГУ, 1987.-220 с.

[32] Кольцов П.П., Кочетков Д.В. Пакет ПАРК // Организация вычислительной процедуры. -М.: ВЦ РАН, 1981. -18 с.

[33] Корн Г., Корн Т. Справочник по математике для научных работников и инженеров / Под общ. ред. И.Г. Арамановича. М.: Наука, 1975.-831 с.

[34] Кочетков Д. В. Распознающие алгоритмы, инвариантные относительно пространства признаков // Распознавание, классификация, прогноз. -М.: Наука, 1988. Вып. 1. - С. 82 - 113. %

W-f

[35] Кузнецов О. П. Неклассические парадигмы в искусственном интеллекте // Теория и системы управления. -М.: 1995. 5. -С. 3-23.

[36] Кухтенко А. И. О физике и кибернетике // Кибернетика, 1981.

4. - С. 133 - 138.

[37] Лабунец В.Г. Алгебраическая теория сигналов и систем. -Свердловск.: У ПИ, 1989. -196 с.

[38] Левит В.Е., Переверзев-Орлов B.C. Структура и поле данных при распознавании образов. -М.: Наука, 1984. -124 с.

[39] Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. -М.: Наука, 1990. -248 с.

[40] Пакет КВАЗАР прикладных программ распознавания образов (версия 2) / Мазуров Вл.Д., Казанцев B.C., Белецкий Н.Г., Мезенцев C.B., Сачков Н.О. -Свердловск: УНЦ АН СССР, 1979. -121 с.

[41] Мазуров Вл.Д. О комитете системы выпуклых неравенств // Труды ICM-66. -М.: МГУ, 1966. 14. -С. 41.

[42] Мазуров Вл.Д. О построении комитета системы выпуклых неравенств // Кибернетика, 1967. 2. - С. 56 - 59.

[43] Мазуров Вл.Д. Об одном методе обучения узнаванию // Кибернетика, 1970. 2. -С. 92 - 94.

[44] Мазуров Вл.Д. Распознавание образов как средство автоматического выбора процедуры в вычислительных методах // Журн. вычислит. матем. и матем. физики. -1970. -Т. 10, № б. -С. 1520 -1525.

[45] Мазуров Вл.Д. Комитеты систем неравенств и задача распознавания // Кибернетика, 1971. 3. -С. 140 - 146. \

[46] Мазуров Вл.Д., Кривоногое А.И., Казанцев B.C., Сачков И.О., Белецкий Н.Г. Комитеты в принятии решений // Кибернетика, 1984. - №1.-С. 90 - 95.

[47] Мазуров Вл.Д., Потанин Н.И. О некоторых подходах к анализу многомерных данных // Методы оптимизации и их приложения (Тез. докл. 10-й Байкальской школы-семинара, Иркутск, 14 -19 августа 1995 г.). -Иркутск: СЭИ СО РАН, 1995. -С. 97 - 98.

[48] Мазуров Вл.Д., Потанин Н.И. Сети нейронов, обучающиеся интерпретации данных // Проблемы создания систем обработки, анализа и распознавания изображений. Ч. 1 (Тез. докл. II Респу-бл. семинара). -Ташкент: АН УзССР, -1989. -С. 63 - 65.

[49] Мазуров Вл.Д., Потанин Н.И. Оптимизация и распознавание в экспертных системах для горно-геологических задач // Компьютерные технологии в горном деле (Тез. докл. науч. конф.). -Екатеринбург, -1996. -С. 41 - 45.

[50] Мазуров Вл.Д., Потанин Н.И. Структурное распознавание в анализе текстур // Непрерывные и смежные логики в технике, экономике и социологии (Тез. межд. науч.-тех. конф.). - Пенза, -1996. -С. 57 - 59. -

[51] Марр Д. ЗРЕНИЕ: информационный подход к изучению представления и обработки зрительных образов. -М.: Радио и связь, 1987. -400 с.

[52] Математическая энциклопедия. -М.: МЭ, 1977. -Т. 1. -1151 с.

[53] Метельский H.H. Об экстремальных значениях линейной формы на некоторых множествах подстановок // Вестник АН БССР. Сер. физ.-мат. наук. -1972. № 5. - С. 5 - 10.

[54] Минский М., Пейперт С. Персептроны / Под ред. Ковалевского В.А.-М.: Мир, 1971.-262 с.

[55] Михайлов С.Г., Осипов В.В., Потанин В.И., Потанин Н.И., Соломонов В. И. Комплекс технических и программных средств идентификации минералов // Распознавание образов и анализ изображений (РОАИ-2-95) (Тез. докл.). -Ульяновск, 1995. -С. 148 - 150.

[56] Нильсон Н. Обучающиеся машины. -М.: Мир, 1967. -180 с.

[57] Ope О. Теория графов. -М.: Наука, 1968. -352 с.

[58] Ползик Е.В., Потанин Н.И. Комплексный анализ факторов, влияющих на продолжительность трудовой деятельности рабочих старшего возраста // Советское здравоохранение: Медицина. -1989. 8. -С. 26 - 30.

[59] Потанин Н.И. Один из подходов к построению нейронной сети // Проблемы теоретической и прикладной математики. -Свердловск: УрО АН СССР, 1989. - С. 43 - 44.

[60] Потанин Н.И., Фомин А.Н. Об одной задаче .анализа изображений // Математические методы распознавания образов (Тез. докл. 4-ой Всесоюз. конф. Ч. 3). -Рига, 1989. - С. 73 - 74.

[61] Потанин Н.И., Фомин А.Н. Применение групп к анализу изображений // Свердловск: ПММ УрО РАН, 1989. -10 с; -Деп. в ВИНИТИ 30.06.89, № 5008-В89.

[62] Потанин Н.И., Тагилъцев В.А. Один из алгоритмов сравнения изображений//Проблемы теоретической и прикладной математики. -Свердловск: УрО АН СССР, 1990. - С. 43 - 44.

[63] Потанин Н.И. Об одном свойстве обыкновенных графов // Проблемы теоретической и прикладной математики (Тез. докл. молодежных конференций). - Екатеринбург: УрО РАН, 1993. - С. 66.

[64] Потанин Н.И. Некоторые числовые свойства помеченных простых графов // Тр. ИММ УрО РАН. -Екатеринбург: УрО РАН, 1995.-Т. 3.-С. 267 - 273.

[65] Потанин Н.И. Применение теории групп к сжатию произвольного множества // Информ. бюлл. АМП. -Екатеринбург: УрО РАН, 1995, №5.-С. 167 - 168.

[66] Потанин Н.И. Решение системы уравнений с перестановками // Проблемы теоретической и прикладной математики (Тез. докл. молодежной конференции). - Екатеринбург: УрО РАН, 1996. -С. 48 - 49.

[67] Потанин Н.И. О некоторых свойствах помеченных простых графов // Тр. ИММ УрО РАН. -Екатеринбург: УрО РАН, 1996. -Т. 4.-С. 346- 368.

[68] Потанин Н.И. О проблеме изоморфизма простых графов // Екатеринбург, ИММ УрО РАН, 1996. -33 с. -Деп. в ВИНИТИ 27.11.96, № 3436-В96.

[69] Потанин Н.И. Об одной оптимизационной задаче на простых графах // Проблемы теоретической и прикладной математики. Тез. докл. молодежной конференции. - Екатеринбург: УрО РАН, 1997. -С. 68 - 69.

[70] Растригин Л.А. Теория и применение случайного поиска. - Рига: Зинатне, 1969. -305 с.

[71] Растригин Л.А. Системы экстремального управления. -М.: Наука, 1974. -630 с.

[72] Рудаков К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания. Дисс. д-ра физ.-мат. наук. -М., 1991. -274 с.

[73] Сергиенко И.В. О некоторых направлениях в развитии методов дискретной оптимизации и их программного обеспечения // Кибернетика, 1982. 6. - С. 45 - 62.

[74] Сергиенко И. В. Математические модели и методы решения задач дискретной оптимизации. - Киев: Наукова Думка, 1985. -380 с.

[75] Стоян Ю.Г., Соколовский В.З. Решение некоторых многоэкстре-.мальных задач методом сужающихся окрестностей. -Киев: Наукова Думка, 1980. - 205 с.

[76] Супруненко Д. А. О значениях линейной формы на множестве подстановок // Кибернетика, 1968. -К0- 2. - С. 59 - 63.

[77] Супруненко Д.А. Отношение порядка на подстановках и экстремальные задачи // Кибернетика, 1981. -К* 4. - С. 22 - 29.

[78] Tamm, У. Теория графов. -М.: Мир, 1988. -424 с.

[79] Файн В. С. Опознавание изображений. -М.: Наука, 1970. -296 с.

[80] Френкель А., Бар-Хиллел И. Основания теории множеств. -М.: Мир, 1966. -555 с.

[81] Фу К. Структурные методы в распознавании образов. -М.: Мир, 1-977. -320 с.

[82] Харари Ф. Теория графов. -М.: Мир, 1973. -300 с.

[83] Харди Г.Г., Литтльвуд Д.Е., Полиа Г. Неравенства. -М.: ИЛ, 1948. -456 с.

[84] Холл М. Теория групп. -М.: ИЛ, 1962. -468 с.

[85] Хомский Н, Миллер Дж. Введение в формальный анализ естественных языков // Кибернетический сборник. Новая серия. -1965. 1. -С. 229 - 290.

[86] Хомяков Ю.Н., Саушкин В.А. Методы классификации текстур // Зарубежная радиоэлектроника, 1986. 2. -С. 33 - 46.

[87] Mazurov VI.D., Obuhov A.D., Potanin N.I. Use of the Committe Method and Group Theory in Videoinformation Analysis Problems // 1th ITIAPR'90 Conf. -Lvov, 1990. -P. 347 - 352.

[88] Mazurov Vl.D. Duality in Pattern Recognition and Operation Research // Pattern Recognition and Image Analysis. -19^1. -V. 1, №4.-P. 376 - 384.

[89] Mazurov Vl.D. Recognition and Choice in a Multistage Procedure of Modeling Complex Systems // Pattern Recognition and Image Analysis. -1994. -V. 4, № 2. -P. 87 - 92.

[90] Mazurov Vl.D. Generalized Existence in Nonequilibrium Models of Choice in Modeling Complex Systems // Pattern Recognition and Image Analysis. -1995. -V. 5, № 1. -P. 7-12.

[91] Polzik E. V., Potanin N.I., Kogan F.M., Kochneva M.Ju. Risk factors for asbestosis in workers of asbestos mills //La medicena del Lavoro. -1989. -V. 80, № 5, - P. 363 - 370.

[92] Potanin N.I., Fomin A.H. Image Compression by Symmetry Groups // Pattern Recognition and Image Analysis. -1992. -V. 2, №1.-P. 29-31.

[93] Turner J. Generalized Matrix Function and the Graph Isomorphism Problem // SIAM J. Appl. Math., 1968. -V. 16, № 3. -P. 520 - 526.

[94] Read R.C., Cornell D.G. The graph isomorphism disease //J. Graph Theory, 1977. -V. 1. -P. 339 - 363.