43951

Игры Эренфойхта в теории графов

Дипломная

Информатика, кибернетика и программирование

Граф (G,(V,Е)) задается множеством вершин (V) и набором (Е) неупорядоченных или упорядоченных пар вершин. Неупорядоченная пара вершин называется ребром, упорядоченная - дугой. Граф, содержащий только ребра, называется неориентированным графом; граф, содержащий только дуги, ориентированным графом. Пара вершин может соединяться двумя и более ребрами...

Русский

2013-11-08

1.33 MB

28 чел.

Департамент образования города Москвы

Государственное образовательное учреждение высшего профессионального образования

МОСКОВСКИЙ ГОРОДСКОЙ ПСИХОЛОГО-

ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет  Информационных технологий

Кафедра   Прикладной математики      

ВЫПУСКНАЯ

КВАЛИФИКАЦИОННАЯ РАБОТА

Тема: «Игры Эренфойхта в теории графов»

Автор              Сараев Сергей Александрович                      

Научный руководитель работы

доцент В. Н. Кривцов

(подпись, дата)

Консультанты (с указанием относящихся к ним разделов):

________________________________________________________

________________________________________________________

Рецензент доктор физико - математических наук, профессор А.Д.Яшин

Работа допущена к защите

Заведующий кафедрой   _________________(А.Д. Яшин)

« 20 »     мая    2010г.

Департамент образования города Москвы

Государственное образовательное учреждение высшего профессионального образования

МОСКОВСКИЙ ГОРОДСКОЙ ПСИХОЛОГО-

ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет  Информационных технологий

Кафедра   Прикладной математики

ЗАДАНИЕ

по подготовке выпускной квалификационной работы

Студент                  Сараев Сергей Александрович                                      5.2

Ф.И.О.        Группа

Получаемая квалификация (степень)          математик-программист    

Тема: «Игры Эренфойхта в теории графов»

Утверждена:    15.03.2010             07-03/220-y   

дата      № приказа

Научный руководитель                                                       доцент В.Н. Кривцов

должность  звание    Ф.И.О.

Консультант (ы) __________________________________________________

должность   звание   Ф.И.О.

_________________________________________________________________

должность   звание   Ф.И.О.

Срок сдачи студентом оформленной выпускной квалификационной работы

                    24.05.2010                                                          

СОДЕРЖАНИЕ ЗАДАНИЯ

1. Создания алгоритмов программы.                                                                  

2. Разработка программного решения.                                                               

3. Сбор рекомендуемой литературы по теме.                                                    

4. Анализ и разработка теоретической части.                                                   

5. Усовершенствование программы и дополнение  функциями.                                        

КАЛЕНДАРНЫЙ ГРАФИК РАБОТЫ

п/п

Содержание разделов

Срок выполнения

Отметка о

выполнении

  1.  

Подбор литературы

Январь

  1.  

Отбор материалов для дипломной работы

Февраль

  1.  

Разработка алгоритма

Март

  1.  

Написания программы

Апрель

  1.  

Оформление дипломной работы

Май

РЕКОМЕНДУЕМАЯ ИСХОДНАЯ ЛИТЕРАТУРА

  1.  Poizat, B., A Course in Model Theory. An Introduction to Contemporary          Mathematical Logic, Springer-Verlag,  New-York, 2000.
  2.  Ehrenfeucht, A., An application  of games to the completeness problem for        formalized theories, Fund. Math. 49 (1961), 129-141.

3. Верещагин Н.К., Шень А. - «Языки и исчисления», МЦНМО, 2000

Зав. кафедрой _______________________

Научный руководитель _______________

Студент ___________________________

Дата ________24.05.2010_____________

СОДЕРЖАНИЕ

введение 5

граф и теория графов 6

изоморфизм графов 10

игра ФРАИССЕ - ЭРЕНФОЙХТА 15

Реализация программного решения, основанного на методе игры фраиссе - эренфойхта 24

О языке action script 42

Заключение 45

Список используемой литературы 46

приложение 47

ВВЕДЕНИЕ

 Графы G1 и G2 называются изоморфными, если существует биективное отображение f множества вершин графа G1 на множество вершин графа G2,  такое, что (a,b) является ребром графа G1 в том и только в том случае, если (f(a),f(b)) – ребро графа G2. Указанное отображение f называется изоморфизмом между графами G1 и G2.

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

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

Для решения задачи алгоритмической проверки наличия изоморфизма применяется хорошо известный теоретико-модельный метод Фраиссе - Эренфойхта.  В силу этого предлагаемый программный продукт позволяет осуществлять (и демонстрировать) проверку существования локальных изоморфизмов и, следовательно, локальной элементарной эквивалентности. В качестве языка программирования используется Action Script 2.0. Отличительной особенностью этого языка является наличие векторной графики, благодаря которой реализуются интерактивность объектов и движение.

ГРАФ И ТЕОРИЯ ГРАФОВ

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

 Определение. Графом G называется упорядоченная пара              G = <V,E>, где V — непустое конечное множество элементов, называемых вершинами, а E – это множество неупорядоченных пар различных элементов из V. Элементы множества V называются вершинами графа, элементы множества E - его ребрами. Из-за этого следует, что граф является математическим объектом, заданным множеством вершин и набором упорядоченных или неупорядоченных пар вершин.1 На рисунке 1 представлен граф.

рисунок 1 (граф)

Определение. Теория графов — это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Основной объект теории графов является граф.

Граф (G,(V,Е)) задается множеством вершин (V) и набором (Е) неупорядоченных или упорядоченных пар вершин. Неупорядоченная пара вершин называется ребром, упорядоченная - дугой. Граф, содержащий только ребра, называется неориентированным графом; граф, содержащий только дуги, ориентированным графом. Пара вершин может соединяться двумя и более ребрами (дугами одного направления; направление дуги отвечает упорядоченности соответствующей пары вершин). Зарождение теории графов можно отнести к концу XVIII века, к работам Эйлера, посвященным решению математических  развлекательных задач. В двадцатом веке толчком к развитию теории графов служат задачи, возникающие в физике, химии, электротехнике, биологии, экономике, социологии, а также во многих математических дисциплинах. Современная теория графов включает различные подходы к решению соответствующих задач: комбинаторно-логические, геометрические (типологические), теоретико-вероятностные. В социологии теория графов используется в основном при изучении малых групп. Обычно графы используются для описания схем дорог, газопроводов, электросетей. 2

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

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

 Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней вершиной.

Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i,j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).3

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

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

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

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

Однако возможны и другие способы. Например, с помощью списка ребер (в первом столбе пишутся ребра, а во втором столбце вершины графа инцидентные им). Или  с помощью матрицы инцидентности (по вертикали указываются вершины, по горизонтали - ребра. aij=1, если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1, если в вершину i входит ребро j. Если ребро - петля, то aij=2).

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

ИЗОМОРФИЗМ ГРАФОВ

Для того чтобы понять смысл метода Фраиссе - Эренфойхта рассмотрим, что же такое изоморфизм графов и какие два графа являются изоморфными. Самое простое объяснение изоморфизма состоит в следующем выражении. Один и тот же граф геометрически можно изобразить различными способами и такие графы называют изоморфными. Также можно сказать, что изоморфизм можно представить как модификацию исходного графа, путем перемещение расположения его вершин и ребер. Но это не является математическим определением, и данные высказывания несут лишь цель наглядного толкования о понятии изоморфизма.

Математическое определение изоморфизма графов повествует. Определение. Графы G1 и G2 называются изоморфными, если существует биективное отображение f множества вершин графа G1 на множество вершин графа G2,  такое, что (a,b) является ребром графа G1 в том и только в том случае, если (f(a),f(b)) – ребро графа G2. Указанное отображение f называется изоморфизмом между графами G1 и G2.4

 Изоморфизм — это бинарное отношение на множестве графов. Можно сказать, что такое отношение изоморфизма между графами является отношением эквивалентности, это значит также, что оно рефлексивно, симметрично и транзитивно. Напомним, что рефлексивность — это свойство бинарных отношений, выражающее выполнимость их для пар объектов с совпадающими членами,  например  отношение R называется рефлексивным, если для любого объекта х из области его определения выполняется xRx. Симметричность - свойство бинарных отношений, выражающее независимость выполнимости данного отношения для какой-либо пары объектов от порядка, в котором эти объекты входят в пару, например отношение R называется симметричным, если для любых объектов x и y из области определения xRy влечёт yRx. Транзитивность (с латинского обозначает переходный) - свойство логического отношения величин, например отношение (а * b) называется транзитивным, если из выражений (а * b) и (b * c) вытекает выражение (а * c).5

Следовательно, отношение эквивалентности разбивает класс всех графов на непустые и попарно непересекающиеся подклассы, называемые классами изоморфизма или классами изоморфных графов. Два произвольных графа принадлежат одному и тому же классу изоморфизма тогда и только тогда, когда они изоморфны друг другу. Изоморфные графы естественно отождествлять, то есть считать совпадающими, поэтому можно считать, что их можно изобразить одним рисунком. Математическая теория графов интересуется такими свойствами графов, которые инвариантны относительно изоморфизма (например, количеством вершин в графе, количеством петель или количеством вершин данной валентности и так далее). Для специалиста по теории графов естественно отождествлять изоморфные графы. Поэтому обычно речь идет о классах изоморфизма (называемых также абстрактными графами). Вопрос об изоморфизме двух графов, в общем случае оказывается сложным. Для изоморфизма двух n-вершинных графов само определение этого отношения дает теоретически безукоризненный способ проверки: надо просмотреть все n! взаимно однозначных соответствий между множествами вершин и установить, совмещаются ли полностью ребра графа хотя бы при одном соответствии. Однако даже весьма грубая оценка показывает, что такое решение задачи простым перебором практически непригодно: уже при   n равная двадцати перебор всех n! вариантов потребовал бы несколько десятков лет машинного времени. Конечно, существуют несколько определенных свойств для установки изоморфизма, так например подсчет вершин и ребер этих графов. Но все эти способы скорее направлены для того, чтобы показать, что эти два графа являются неизоморфными. Для графов, которые выглядят внешне идентичными, нужна проверка всех биекций множества вершин одного из графов на множество вершин другого графа, и для каждой из этих биекций нужно проверить, является ли она изоморфизмом.

Два графа, являющиеся изоморфными, имеют общие характеристики, эти характеристики называются инвариантами. Поэтому с помощью основных инвариантов также можно определить - неизоморфны ли определенные два графа. Среди основных инвариантов — число вершин и ребер или набор степеней. Конечно, если удастся установить, что у двух исследуемых графов один из инвариантов принимает разные значения, то эти графы неизоморфны. Однако для установления изоморфизма двух графов соответственное равенство значений всех инвариантом является необходимым, но недостаточным.

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

рисунок 2 

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

Однако, говоря о проблеме изоморфизма, стоит упомянуть, что тема установление изоморфизма также имеет практическое значение не только в математики, но и в ряде других дисциплин. Одна из этих дисциплин — биология, или точнее одна из её отраслей — генетика. Так, например, хромосомы можно представить в виде графов. А изоморфизм можно использовать для описания типов признаков популяции, с помощью которого можно будет сравнивать качественные и количественные различия между хромосомами. Так установление локального изоморфизма двух графов можно будет интерпретировать как эволюционный процесс живых организмов, в котором общий «кусок» хромосом (соответствующий локальному изоморфизму) можно интерпретировать как наследственность. Поэтому решение проблемы изоморфизма поможет в скором времени лучше разобраться в данной области генетики. Как видно, если развивать эту тематику, то она принесет неоценимый вклад в другие области различных наук.

ИГРА ФРАИССЕ - ЭРЕНФОЙХТА

Принцип метода Фраиссе - Эренфойхта для проверки изоморфизма двух графов рассказан в следующем изложении. Сформулируем общий критерий элементарной эквивалентности двух интерпретаций некоторой сигнатуры. Сигнатура содержит только предикатные символы. (Это ограничение не очень существенно, так как функцию f(x1,...,xn) можно заменить предикатом f(x1,...,xn)=y, имеющим на один аргумент больше). Кроме того, будем считать, что сигнатура конечна.

Определение. Структура — множество G с заданным на нём набором операций и отношений, удовлетворяющим некоторой системе аксиом.

Интерпретация (от латинского interpretatio) - построение моделей для абстрактных систем (исчислений) логики и математики.6

Критерий будет сформулирован в терминах некоторой игры, называемой игрой Фраиссе - Эренфойхта. В ней участвуют два игрока, называемые Новатором и Консерватором. Игра определяется выбранной парой интерпретаций; как мы докажем, интерпретации элементарно эквивалентны тогда и только тогда, когда Консерватор имеет выигрышную стратегию в этой игре.

В начале игры Новатор объявляет натуральное число k. Далее они ходят по очереди, начиная с Новатора; каждый из игроков делает k ходов, после чего определяется победитель.

На i-м ходу Новатор выбирает элемент в одной из интерпретаций (в любой из двух, причем выбор может зависеть от номера хода) и помечает его числом i. В ответ Консерватор выбирает некоторый элемент из другой интерпретации и также помечает его числом i. После k ходов игра заканчивается. При этом в каждой интерпретации k элементов оказываются помеченными числами от 1 до k (не учитываем, кто именно из игроков их пометил). Обозначим эти элементы a1,a2,..,ak (для первой интерпретации; элемент ai имеет пометку i) и b1,b2,...,bk (для второй). Элементы ai и bi (с одним и тем же i) будем называть соответствующими друг другу. Посмотрим, найдется ли предикат сигнатуры, который различает помеченные элементы первой и второй интерпретации (то есть, истинен на некотором наборе помеченных элементов в одной интерпретации, но ложен на соответствующих элементах другой). Если такой предикат найдется, то выигрывает Новатор, в противном случае — Консерватор. Данные рассуждения были взяты в основу создания функции, которая определяет изоморфизм двух графов до определенного хода. На рисунке 3 наглядно показано действие игры Фраиссе — Эренфойхта и поочередность ходов Новатора и Консерватора.

Прежде чем доказывать, что эта игра дает критерий элементарной эквивалентности, рассмотрим несколько простых примеров:

1) Среди элементов a1,..,ak и b1,...,bk могут быть одинаковые. Если в нашей сигнатуре есть предикат равенства и в обеих интерпретациях он интерпретируется как совпадение элементов, то Консерватор обязан повторять ходы, если их повторил Новатор (скажем, если ai=aj, а        bibj, то Новатор выигрывает, поскольку предикат равенства истинен в одной интерпретации, но ложен на соответствующих элементах другой).

рисунок 3 

 

2) Если интерпретации изоморфны, то у Консерватора есть очевидный способ выиграть: изоморфизм заранее группирует все элементы в пары соответствующих. (Это согласуется с тем, что изоморфные интерпретации элементарно эквивалентны).

3) Рассмотрим сигнатуру упорядоченных множеств          (предикаты = и <) и ее естественные интерпретации в N и Z. Они не являются элементарно эквивалентными, поскольку среди натуральных чисел есть наименьшее, а среди целых — нет. Покажем, что в игре Фраиссе - Эренфойхта для данных интерпретаций выигрывает Новатор.

Новатор объявляет, что игра будет проведена в два хода и на первом ходу помечает число 0 из интерпретации N. В ответ Консерватор вынужден пометить некоторое число m из Z. На втором ходу Новатор помечает в Z некоторое число, меньшее m (например, m - 1). Теперь Консерватор проигрывает при любом ответном ходе, поскольку пометить число, меньшее нуля, он не может.

4) Для той же сигнатуры рассмотрим интерпретации в Z и Q. Эти интерпретации не элементарно эквивалентны, поскольку порядок на рациональных числах плотен, а на целых — нет. Покажем, что в игре Фраиссе - Эренфойхта снова выигрывает Новатор.

Игра будет проходить в три хода. На первых двух ходах Новатор помечает числа 0 и 1 из Z. Консерватор должен пометить некоторые элементы b1 и b2 из Q. При этом должно быть b1 < b2 (иначе Новатор заведомо выиграет). Тогда на третьем ходу Новатор помечает любое рациональное число, лежащее строго между b1 и b2. Так как между 0 и 1 нет натуральных чисел, Консерватор не может соблюсти требования игры, и проигрывает при любом ходе.

5) Рассмотрим теперь упорядоченные множества Z и Z+Z. Как мы видели, они элементарно эквивалентны, и потому должна существовать выигрышная стратегия для Консерватора. Конечно, разумно поддерживать одинаковые расстояния между соответствующими элементами в Z и Z+Z. Проблема в том, что в Z+Z некоторые расстояния бесконечны (между элементами разных слагаемых).

Если Новатор пометил два таких элемента, то стратегия Консерватора следующая. Так как Консерватор знает заранее, сколько ходов осталось до конца игры. Ясно, что если игра скоро кончится, то Новатор не удастся отличить бесконечное расстояние от достаточно большого. Более точно, если до конца игры остается s ходов, то Консерватор может считать все расстояния, большие или равные 2s, бесконечно большими. В конце (при s=0) это означает, что все ненулевые расстояния отождествляются (что правильно, так как в конце важен лишь порядок). Таким образом, Консерватор стремится поддерживать такой "инвариант": соответствующие элементы в A и в B идут в одном и том же порядке, и расстояния между соответствующими парами соседей одинаковы (при этом все бесконечно большие расстояния считаются одинаковыми). Ясно, что такая стратегия гарантирует ему выигрыш; надо лишь проверить, что поддержать инвариант можно.

При очередном ходе Новатора возможно несколько случаев. Новатор мог разбить "конечный" (меньший 2s, где s — число оставшихся ходов) промежуток на две части. В этом случае соответствующий промежуток в другом множестве также "конечен" и имеет ту же длину, так что Консерватор должен лишь выбрать элемент на том же расстоянии от концов. Пусть Новатор разбил "бесконечный" (длины 2s или больше) промежуток на две части. Тогда хотя бы одна из частей будет иметь длину 2s-1 или больше, то есть на следующем шаге будет считаться "бесконечной". Если обе части "бесконечны" (с точки зрения следующего шага), то Консерватор должен разбить "бесконечный" (длины 2s или более) промежуток другого множества на две "бесконечные" (длины 2s-1 или более) части. Если одна часть "бесконечна", а другая "конечна", то надо отложить то же "конечное" расстояние в другом множестве. Наконец, обе части не могут быть "конечными" (если каждая меньше 2s-1, то в сумме будет меньше 2s).

Наконец, новый элемент мог быть больше (или меньше) всех уже отмеченных элементов интерпретации; в этом случае Консерватор должен отметить элемент другой интерпретации, находящийся на том же расстоянии от наибольшего (наименьшего) отмеченного элемента (или на "бесконечном" расстоянии, если такова была ситуация с выбранным Новатором элементом).

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

1) Глубина атомарных формул равна нулю.

2) Глубина формул φ ˅ ψ и φ ˄ ψ  равна максимуму глубин формул φ и ψ.

3) Глубина формулы ┐φ  равна глубине формулы φ.

4) Глубина формул ∃ᶓφ и ∀ᶓφ на единицу больше глубины формулы φ.

Другими словами, глубина формулы — это наибольшая "глубина вложенности" кванторов (максимальная длина цепочки вложенных кванторов).

Рассмотрим позицию, которая складывается в игре после k ходов Новатора и Консерватора (перед очередным ходом Новатора) и за L ходов до конца игры (таким образом, общая длина игры есть k+L). В этот момент в каждой из интерпретаций совместными усилиями Новатора и Консерватора выбрано по k элементов. Пусть это будут элементы a1,..,ak в одной интерпретации (назовем ее A) и b1,...,bk в другой (B).

Теорема 1. Если существует формула глубины L с параметрами  x1,...,xk, отличающая a1,..,ak от b1,...,bk, то в указанной позиции Новатор имеет выигрышную стратегию; в противном случае ее имеет Консерватор.

Поясним смысл условия теоремы. Пусть φ — формула глубины L, все параметры которой содержатся в списке x1,...,xk. Тогда имеет смысл ставить вопрос о ее истинности в интерпретации A при значениях параметров a1,..,ak, а также в интерпретации B при значениях параметров b1,...,bk. Если окажется, что в одном случае формула φ истинна, а в другом ложна, то мы говорим, что φ отличает a1,..,ak            от b1,...,bk.

Пусть такая формула φ существует. Она представляет собой логическую (бескванторную) комбинацию некоторых формул вида ∀ᶓφ и ∃ᶓφ, где ψ — формула глубины L-1. Хотя бы одна из формул, входящих в эту комбинацию, должна также отличать a1,..,ak от b1,...,bk. Переходя к отрицанию, можно считать, что эта формула начинается с квантора существования. Пусть формула φ, имеющая вид ∃xk+1ψ (x1,...,xk,xk+1), истинна для a1,..,ak и ложна для b1,...,bk. Тогда найдется такое ak+1, для которого в A истинно ψ(a1,...,ak,ak+1).

Это ak+1 и будет выигрывающим ходом Новатора; при любом ответном ходе bk+1 Консерватора формула ψ(b1,...,bk,bk+1) будет ложной. Таким образом, некоторая формула глубины L-1 отличает a1,...,ak,ak+1 от b1,...,bk,bk+1 и потому, рассуждая по индукции, мы можем считать, что в оставшейся (L-1)-ходовой игре Новатор имеет выигрышную стратегию. (В конце концов, мы придем к ситуации, когда некоторая бескванторная формула отличает k+L элементов в A от соответствующих элементов в B, то есть Новатор выиграет.)

Обратное рассуждение (если наборы неотличимы никакой формулой глубины L, то Консерватор имеет выигрышную стратегию в оставшейся L-ходовой игре) аналогично, но чуть более сложно. Здесь важно, что по существу есть лишь конечное число различных формул глубины k.

Точнее говоря, будем называть две формулы (с параметрами) эквивалентными, если они одновременно истинны или ложны в любой интерпретации на любой оценке. Поскольку сигнатура конечна, существует лишь конечное число атомарных формул, все параметры которых содержатся среди u1,...,us. Существует лишь конечное число булевых функций с данным набором аргументов, поэтому существует лишь конечное число неэквивалентных бескванторных формул, все параметры которых содержатся среди u1,...,us. Отсюда следует, что существует лишь конечное число неэквивалентных формул вида ∃usψ(u1,...,us), и потому лишь конечное число неэквивалентных формул глубины 1, параметры которых содержатся среди u1,...,us-1. (Используем утверждение о конечности числа булевых функций с данным конечным списком аргументов, а также возможность переименовывать переменную под квантором, благодаря которой мы можем считать, что эта переменная есть us). Продолжая эти рассуждения, мы заключаем, что для любого L и для любого набора переменных u1,...,un существует лишь конечное число неэквивалентных формул глубины L, все параметры которых содержатся среди u1,...,un. (Здесь мы существенно используем конечность сигнатуры).

Теперь можно закончить рассуждения про игру Фраиссе - Эренфойхта. Пусть элементы a1,..,ak нельзя отличить от элементов b1,...,bk с помощью формул глубины L. Опишем выигрышную стратегию для Консерватора. Пусть Новатор выбрал произвольный элемент в одной из интерпретаций, скажем, ak+1. Рассмотрим все формулы глубины L-1 с k+1 параметрами (с точностью до эквивалентности их конечное число); некоторые из них будут истинны на a1,..,ak+1, а некоторые ложны. Тогда формула, утверждающая существование ak+1 с ровно такими свойствами (после квантора существования идет конъюнкция всех истинных формул и отрицаний всех ложных) будет формулой глубины L, истинной на a1,..,ak. По предположению эта формула должна быть истинной и на b1,...,bk, и потому существует bk+1 с теми же свойствами, что и ak+1. Этот элемент bk+1 и должен пометить Консерватор. Теперь предположение индукции позволяет заключить, что в возникшей позиции (где до конца игры L-1 ходов) у Консерватора есть выигрышная стратегия.

Теорема доказана. Ее частным случаем является обещанный критерий элементарной эквивалентности:

Следствие 1. Интерпретации A и B элементарно эквивалентны тогда и только тогда, когда в соответствующей игре Фраиссе - Эренфойхта выигрывает Консерватор.

Условие конечности сигнатуры существенно (без него из элементарной эквивалентности не следует существование выигрышной стратегии для Консерватора).

Некоторых случаях (например, для Z и Z+Z) игра Фраиссе - Эренфойхта дает нам новый способ доказательства элементарной эквивалентности.7

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

Реализация программного решения, основанного на методе игры Фраиссе - Эренфойхта

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

Разработка велась от простого к сложному. Первая стадия — это разработка алгоритма автоматической проверки изоморфизма двух графов, что было отображено в первой курсовой работе и более детально раскрыто во второй курсовой работе. Проанализировав теоретические пособия и предыдущие попытки создания аналогичных программ, пришел к выводу, что существуют две главные проблемы в создании данного программного пособия:

  1.  большое количество всевозможных проверок вариантов ходов игроков для графов, с более тремя вершинами;
  2.  большое количество машинного времени, которое нужно для проверки вариантов.

Для решения первой проблемы в код программы были введены «отсекания» невозможных вариантов с помощью нескольких проверок. Первая проверка основана на сравнении количества вершин обоих графов. Если графы имели не допустимое значение количества вершин, то программа сразу входила в заключительную стадию работы и выдавала результат, что графы не  изоморфны. Данные проверки сокращали время работы программы до минимума в очевидных случаях не изоморфизма графов.

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

 В основе алгоритма «дерево» было то, что ходы игроков, которые на данном этапе разработки программы совершал компьютер, раскладывались в виде дерева. Каждая ветвь являлась определенной последовательностью (чередованием) ходов обоих игроков, а каждая ячейка на этой ветви являлась одним ходом, причем ветвь начиналась с хода первого игрока, ход второго игрока всегда следовал за ходом первого (данный алгоритм рассмотрен на рисунке 3). Однако данный алгоритм имел один существенный минус, из-за которого на данном этапе разработки его пришлось отложить (после устранения проблемы часть идеи этого алгоритма было использовано для реализации метода игры Фраиссе — Эренфойхта в нынешней дипломной работе  вместе с алгоритмом проверки с помощью матриц смежности). Этот минус состоял в том, что при прохождении всего «дерева» и проверки всех его ветвей, при графе свыше трех вершин, программе требовалось большое количество времени, а при восьми - вершинном графов превышалось время ожидания ответа программы и она «зависала» (не отвечала на любые манипуляции пользователя).

рисунок 3

 

Второй алгоритм благодаря простоте проверки был избавлен от этой ошибки, связанной с большим количеством времени выполнения программы. Идея алгоритма состояла в том, что для проверки изоморфизма использовалось отображение не графов, а их матриц смежности (благодаря которым также в дальнейшем строились отображения графов). Варианты хода второго игрока на ход первого игрока отображались с помощью различных вариаций матрицы смежности второго графа. Вариации матрицы смежности получались с помощью перестановки ячеек этой матрицы (по аналогии с возможностью выбора вторым игроком любой вершины из графа, данный алгоритм замены строк и столбцов второй матрицы смежности представлен на рисунке 4). Эта перестановка не нарушала никакой связи между вершинами данного графа, что не позволяло в ходе проверки случайно создать новый граф. Каждая вариация матрицы смежности второго графа сравнивалась с матрицей смежности первого графа, и при появлении полного сходства обоих матриц, программа останавливала проверку и выдавала результат (сообщение о том, что оба графа изоморфны). Если же после перебора всех вариаций матрицы смежности второго графа так и не была найдена полностью идентичная матрица смежности первого графа, то программа выдавала сообщение, что эти два графа не изоморфны. Проверка двух матриц смежности занимала мало времени, и в данном алгоритме не было ветвлений, которые усложняли бы работу программы и увеличивали бы время её выполнения. Данный алгоритм помимо того, что охватывал всевозможные варианты графов, также был оптимальным с точки обеих глобальных проблем в данной теме.

рисунок 4   

 

После разработки алгоритма, следующая стадия состояла в создании отображения графов. Если в первой курсовой работе отображение графов исполняло дизайнерский характер, то во второй курсовой и дипломной работах оно также несло и функциональность. Задать графы можно как с помощью матриц смежности, так и визуально. Так как рассматривается определенный тип графов: конечный, ненаправленный и без петель, то в матрицах смежности на главной диагонали выставлены всегда нули, и пользователь никак не сможет их изменить. В начале работы программы пользователю будет предложено ввести количество вершин первого и второго графа. Так как основной инвариант для определения изоморфизма двух графов состоит в равном количестве вершин этих графов, то пользователю будет предложено ввести только один раз это значение, которое будет равно и для первого и для второго графов. Вершины вводятся с помощью списка цифр, дабы избежать ошибки ввода неправильных символов. После этого на основе введенного количества вершин строятся матрицы смежности обоих графов. В первой версии дизайна матриц смежности «единицы» в ячейках, которые соответствуют тому, что между этими двумя вершинами есть ребро, ставились вручную. Однако после тестирования оказалось, что это путает пользователей и приносит некоторую невнятность в процесс использования программы. После усовершенствования, «единицы» можно было ставить простым кликом мышки на данную ячейку, а также после второго клика мышки на ту же ячейку «единица» опять превращалась в «ноль», что означало, что между этими вершинами нет ребра.

 После того, как работоспособность программы была опробована, и с помощью неё можно было автоматически проверить изоморфизм двух графов, началась третья стадия. Она заключалась в наглядном отображении метода игры Фраиссе - Эренфойхта и возможности проверки изоморфизма двух графов вручную с помощью игры. Для создания данной стадии код программы был построен на основе усовершенствованного алгоритма «дерево», описанного выше.

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

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

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

рисунок 5

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

рисунок 6

Затем необходимо перейти в меню «Режим игры» для выбора сложности и как будут задаваться графы. Легкая игра означает, что консерватор при выборе не правильной вершины имеет возможность выбрать другую. А вот сложная игра не дает ему такой возможности и игра заканчивается. Рекомендуется выбрать легкую игру (рис. 7).

рисунок 7

После того как все выбрано, можно нажимать на «Файл» - «Новая игра» для того, чтобы начать новую игру. Так же в этом меню имеется выход из приложения (рис. 8).

рисунок 8

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

рисунок 9

Рассмотрим режим легкой игры и задание графов с помощью матриц.

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

рисунок 10

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

рисунок 11

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

рисунок 12

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

рисунок 13

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

рисунок 14

Когда вершины проверены, они помечаются черным цветом, дабы видеть локальный изоморфизм, так же помечаются и их ребра. В данном случае, мы завершили игру в два хода. Результат: присутствует локальный изоморфизм. Заметьте, что сами графы не изоморфны. Для этого можно нажать в меню «Действие» - «Проверить графы» (рис. 15), а так же можно добавить дополнительный ход для проверки (рис. 16).

рисунок 15

рисунок 16

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

рисунок 17

Теперь давайте рассмотрим сложную игру и графический ввод графов.

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

рисунок 18

Для начала мы указываем расположение вершин. Для этого достаточно нажать на область Графа 1 или Графа 2 (рис 19).

рисунок 19

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

рисунок 20

Проделываем тоже самое для второго графа.

рисунок 21

Затем также выбираем вершины по методу Фраиссе-Эренфойхта. Проверяем их. Но на этот раз, выбран сложный режим игры, в котором не допускаются ошибки для консерватора. В данном примере показано, что консерватор ответил не правильной вершиной (рис. 22).

рисунок 22

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

рисунок 23

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

О языке ActionScript

ActionScript — это объектно-ориентированный язык программирования для рабочей среды Flash Player'а, он является одним из диалектов ECMAScript. Он делает возможным интерактивность, обработку данных и большое количество других функций в среде и приложениях Flash. С помощью  ActionScript  можно создавать интерактивные мультимедиа-приложения, игрывеб-сайты  и многое другое.  ActionScript выполняется интерпретатором ActionScript, который является частью Flash-плеера.  ActionScript исполняется виртуальной машиной (ActionScript Virtual Machine), которая является составной частью Flash Player.

Код ActionScript компилируется в байткод с помощью компилятора, например в среде разработки Flex. Байткод переносится в файлы SWF, которые выполняются в рабочей среде Flash Player'а. Flash Player существует в виде плагина к веб-браузеру, а также как самостоятельное исполняемое приложение (standalone). Во втором случае возможно создание исполняемых exe-файлов (projector), когда swf-файл включается во Flash Player.

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

ActionScript как язык появился с выходом 5 версии Macromedia Flash, которая стала первой программируемой на ActionScript средой. Первый релиз языка назывался ActionScript 1.0. Flash 6 (MX). В 2004 году Macromedia представила новую версию ActionScript 2.0 вместе с выходом Flash 7 (MX 2004), в которой было введено строгое определение типов, основанное на классах программирование. То есть появились новые ключевые слова:

class (класс),

interface (интерфейс),

extends (установка наследования)

модификаторы доступа: private, public;

и прочие.

Также Macromedia была выпущена модификация языка Flash Lite для программирования под мобильные телефоны.

ActionScript 1.0 является прототипным ООП (prototype-based). То есть он вполне реализует все три принципа объектно-ориентированного программирования.

ActionScript 2.0 является не более чем надстройкой над ActionScript 1.0, то есть на этапе компиляции компилятор осуществляет некую проверку и превращает классы, методы ActionScript 2.0 в прежние прототипы, «функции-классы» с их свойствами-методами и пр. ActionScript 1.0.

В 2006 году вышел ActionScript 3.0 в среде программирования Adobe Flex, а позже в Adobe Flash 9.

ActionScript 3.0 представляет, по сравнению с ActionScript 2.0 качественное изменение, он использует новую виртуальную машину AVM 2.0 и даёт взамен прежнего формального синтаксиса классов настоящее классовое (class-based) Объектно-ориентированное программирование. ActionScript 3.0 обеспечивает возрастание производительности, по сравнению с ActionScript 1.0/2.0, до 700 раз (это лишь обработка инструкций, не затрагивая графику). ActionScript 3.0 позволяет работать с бинарными данными, с BitMap (что обеспечивает значительный прирост производительности: до 10000 раз). ActionScript 3.0 по скорости приблизился к таким языкам программирования, как Java и C#. Увеличение производительности основано на динамической трансляции кода (JIT). Такое увеличение производительности возможно лишь для некоторых типов данных и требует особой организации кода. Объём кода, как правило, увеличивается в несколько раз (по сравнению с AS1).

ЗАКЛЮЧЕНИЕ

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

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

Кроме того, планируется создать соответствующий интерактивный сайт на FLASH. (В результате, программу можно будет использовать как on-line на сайте, так и посредством скачивания приложения на ПК.)

Программа может служить хорошим «помощником» для школьников и студентов при подготовке к различным математическим испытаниям или просто для изучения математики. Она может применяться в школах и вузах для визуального объяснения.

БИБЛИОГРАФИЯ

1. Poizat, B., A Course in Model Theory. An Introduction to Contemporary Mathematical Logic, Springer-Verlag,  New-York, 2000.

2. Ehrenfeucht, A., An application  of games to the completeness problem  for formalized theories, Fund. Math. 49 (1961), 129-141.

3.  Верещагин Н.К., Шень А. - «Языки и исчисления», МЦНМО, 2000

4.  Большая советская энциклопедия, «Советская энциклопедия» , 1981

5. Нефедов В. Н., Осипова В.А. -  «Курс дискретной математики», МАИ, 1992

6. Лихтарникова Л.М., Сукачева Т.Г.  – «Математическая логика», "Лань", 1999

7. Кристофидес Н. – «Теория графов. Алгоритмический подход», МИР, 1978

8. Уилсон Р.  - «Введение в теорию графов», МИР, 1977

9. Берже К.  – «Теория графов и ее применение» , ИЛ, 1962

10. Оре О.  – «Графы и их применение», Наука, 1980

11. Зыков А.А.  – «Теория конечных графов», Наука, 1969

12. Харари Ф. - «Теория графов», МИР, 1973

13. Колин Мук - «Основы Action Script 2.0», Символ-Плюс, 2006

14. Малинин Л.И., Малинина Н.Л. - «Изоморфизм графов в теоремах и алгоритмах», ЛИБРОКОМ, 2009

15. Онлайн — словарь http://www.vseslova.ru/

ПРИЛОЖЕНИЕ

//Меню программы

var myMenuBar:mx.controls.MenuBar;

var myMenu:mx.controls.Menu;

myMenuBar = this.attachMovie("MenuBar", "menubar_mc", 1);

myMenuBar._x = 0;

myMenuBar._y = 0;

myMenuBar.setSize(825, 22)

_global.styles.MenuBar = new mx.styles.CSSStyleDeclaration();

_global.styles.MenuBar.setStyle("themeColor","haloBlue");

_global.styles.MenuBar.setStyle("font","arial");

FileMenu = myMenuBar.addMenu("Файл");

FileMenu.addMenuItem({label:"Новая игра", instanceName:"NewGame"});

FileMenu.addMenuItem({label:"Выход", instanceName:"Exit"});

СhangeMenu = myMenuBar.addMenu("Режим игры");

subСhangeMenu = СhangeMenu.addMenuItem({label:"Сложность"});

subСhangeMenu.addMenuItem({label: "Легкая", type:"radio", selected:true, enabled:true, instanceName:"EasyGame", groupName:"group1"});  

subСhangeMenu.addMenuItem({label: "Сложная", type:"radio", selected:false, enabled:true, instanceName:"HardGame", groupName:"group1"});

subСhangeMenu = СhangeMenu.addMenuItem({label:"Ввод графов"});

subСhangeMenu.addMenuItem({label: "По матрицам", type:"radio", selected:true, enabled:true, instanceName:"MatrixEnter", groupName:"group2"});  

subСhangeMenu.addMenuItem({label: "Графически", type:"radio", selected:false, enabled:true, instanceName:"PicEnter", groupName:"group2"});

ActionMenu = myMenuBar.addMenu("Действие");

ActionMenu.addMenuItem({label:"Проверить графы", instanceName:"ProvGraphs"});

subActionMenu = ActionMenu.addMenuItem({label:"Показать"});

subActionMenu.addMenuItem({label: "Показать матрицы", type:"radio", selected:false, enabled:true, instanceName:"ShowMatrix", groupName:"group3"});  

subActionMenu.addMenuItem({label: "Показать графы", type:"radio", selected:true, enabled:true, instanceName:"ShowGraphs", groupName:"group3"});

FileMenu = myMenuBar.addMenu("Помощь");

FileMenu.addMenuItem({label:"Справка", instanceName:"Help"});

FileMenu.addMenuItem({label:"О программе", instanceName:"About"});

//события меню

choiceGame = "легкая";

choiceGameMode = 1;

choiceGame2 = "по матрицам";

GameMode = 1;

var fileListener:Object = new Object();  

fileListener.change = function(eventObj : Object) : Void

{         

switch (eventObj.menuItem)

{  

 case eventObj.menu.NewGame: statusGame(); if (GameMode == 1) {matrixMode();} else {picMode();}; break;  

 case eventObj.menu.Exit:  fscommand("quit",true); break;

 case eventObj.menu.EasyGame: choiceGame = "легкая"; choiceGameMode = 1; break;

 case eventObj.menu.HardGame: choiceGame = "сложная"; choiceGameMode = 2; break;

 case eventObj.menu.MatrixEnter: choiceGame2 = "по матрицам"; GameMode = 1; break;

 case eventObj.menu.PicEnter: choiceGame2 = "графически"; GameMode = 2; break;

 case eventObj.menu.Help: helpGame(); break;

 case eventObj.menu.About: aboutGame(); break;

 case eventObj.menu.ProvGraphs: proverka(); break;

 case eventObj.menu.ShowMatrix: ShowMat(); break;

 case eventObj.menu.ShowGraphs: ShowGraph(); break;

}   

}

// подписываем листенер на события компонента

myMenuBar.addEventListener("change", fileListener);

//отключаем меню "Действие"

myMenuBar.setMenuEnabledAt(2, false);

//привязываем вместо стандартного меню

this.onResize = function(){myMenuBar.setSize(Stage.width, myMenuBar._height);};

Stage.scaleMode = "noScale";

Stage.showMenu = false;

Stage.align = "TL";

Stage.addListener(this);

this.onResize();

//для нажатия кнопки "проверить"

action.onRelease = function ()

{

 flag = 0;

 prov = 0;

 step++;// увеличивыем шаг

 pro = ((step*0.5)-0.5)*step;

 function Rec(k)  //функция полного перебора

 {

  var il:Number;

  prov = 0;

  if (k<=step)

  {

   for (il=1;il<=step;il++)

   {

    if (wMas[il] == 0)

    {

     wMas[il] = 1;

     aMas[k] = il;

     Rec(k+1);

     wMas[il] = 0;

     aMas[k] = 0;

    }

   }

 }

 else

 {

  if ((_root.green == 1) and (_root.blue == 1)) //если выбраны две вершины

  {  

   nameVer1[step] = name1; //записываем в массив вершины

   nameVer2[step] = name2;

  for (i=1;i<=step;i++)   //цикл проверки действий

  {

   for (j=1;j<=step;j++)

    {

    if (masMat1[nameVer1[i]][nameVer1[j]] == masMat2[nameVer2[aMas[i]]][nameVer2[aMas[j]]])    //если вершины равны

     {

      prov++;

      if (prov == step*step)  { flag = 1;}

      }

       else { break; }

     }

    }

   }

  }

 }

}

Rec(1);

if (flag == 1)

{

if (step <> _root.numeric2.value+1)

{

 hod--;

 res.text += "Верно! "+hod+" осталось";

 izo++;

 nameVer1[step] = name1; //записываем в массив вершины

 nameVer2[step] = name2;

}

}

else

{

 if (step == _root.numeric1.value)

 {

  izoGraph1.text = "ГРАФЫ НЕ ИЗОМОРФНЫ";

  izoGraph1._visible = true;

  izoGraph2._visible = false;

 }

 else

{

 step--;

 if (choiceGameMode == 1)

 {

  res.text += "<b>Не верный ход. Попробуйте другую вершину</b>" + '\n';

  _root.graphPole["2ver"+name2].gotoAndStop(1);

  }

  else

  {

    izoGraph1.text = "<b>Консерватор проиграл. Выбрана не допустимая вершина.</b>";

  }

 }

}

}

if (izo == _root.numeric2.value)

{

 izoGraph1._visible = true;

 izoGraph2._visible = true;

 if (izo == _root.numeric1.value) {addStep.enabled = false; izoGraph2.text = izoGraph2.text + "ГРАФЫ ИЗОМОРФНЫ" + "\n";} else {addStep.enabled = true; izoGraph2.text = izoGraph2.text + "ЛОКАЛЬНЫЙ ИЗОМОРФИЗМ" + "\n";}

 }

}

1  Уилсон Р.  - «Введение в теорию графов»

2  Оре О.  – «Графы и их применение»

3  Берже К.  – «Теория графов и ее применение»

4  Малинин Л.И., Малинина Н.Л. - «Изоморфизм графов в теоремах и алгоритмах»

5  Большая советская энциклопедия

6 Онлайн — словарь http://www.vseslova.ru/

7  Верещагин Н.К., Шень А. - «Языки и исчисления»

PAGE   \* MERGEFORMAT 55


 

А также другие работы, которые могут Вас заинтересовать

80234. Організація як функція управління 20.39 MB
  Сутність функції організації. Основи теорії організації. Сутність функції організації В процесі вивчення цієї теми важливо усвідомити сутність трьох ключових категорій: організація організаційний процес діяльність організаційна структура. Реалізація функції організації здійснюється у процесі організаційної діяльності.
80235. Мотивація. Процесні теорії мотивації 10.37 MB
  Потреби поділяють на: потреби першого роду первісні які за своєю сутністю є фізіологічними потреби в їжі сні тощо; потреби другого роду вторинні які носять соціально психологічний характер потреби в повазі владі визнанні заслуг тощо. Потреби першого роду закладені в людину генетично а другого – є наслідком її соціальної життєдіяльності. Потреби неможливо безпосередньо спостерігати або вимірювати. Потреба яка реально відчувається людиною викликає у неї прагнення здійснити конкретні дії спрямовані на задоволення цієї потреби.
80236. Управлінський контроль. Контроль поведінки працівників в організації 10.37 MB
  Управлінський контроль Поняття та процес контролю. Інструменти управлінського контролю. Поняття та процес контролю Контроль – це процес забезпечення досягнення цілей організації шляхом постійного спостереження за її діяльністю та усунення відхилень які при цьому виникають. В межах процесу контролю модель якого наведена на рис.
80237. Лідерство. Ситуаційні теорії лідерства 142.5 KB
  Наявність права впливати на діяльність підлеглих є необхідною передумовою керування але ще не гарантує ефективності такого впливу. Але перебуванням нагорі визначає лише видимість керування а не його сутність. Отже поведінковий підхід спирається на стиль керування. Стиль керування це манера поведінки керівника щодо підлеглих через яку і здійснюється вплив на працівників організації.
80238. Комунікації. Управління комунікаційними процесами 160 KB
  Процес комунікації. Міжособистісні та організаційні комунікації. Процес комунікації У вузькому розумінні комунікація – це процес обміну інформацією фактами ідеями поглядами емоціями тощо між двома або більше особами. Для здійснення процесу комунікації необхідні принаймні 4 умови: наявність щонайменше двох осіб: відправника особи яка генерує інформацію що призначена для передачі; одержувача – особи для якої призначена інформація що передається; наявність повідомлення тобто закодованої за допомогою...
80239. Ефективність управління. Напрямки підвищення ефективності управлінської праці 98.5 KB
  Ефективність управління можна вимірювати за результатами керованих обєктів і процесів. І все ж встановлення ефективності власне управління можливе, але за допомогою іншого використання вихідної логічної формули. Наприклад, способи управління, що дозволяють досягти заданого фіксованого результату за найменших витрат
80240. Поняття і сутність менеджменту. Менеджмент як вид професійної діяльності 6.35 MB
  Важко дати єдине абсолютно чітке та повне визначення поняття «менеджмент». Функції, сфери, рівні менеджменту та ситуації у яких вони реалізуються значно різняться між собою. Щоб з’ясувати сутність менеджменту на нього треба подивитись з різних точок зору
80241. Розвиток науки управління. Ранні теорії менеджменту 1.78 MB
  Розвиток науки управління. Остаточно ідея управління як наукової дисципліни професії та галузі досліджень сформувалася у США. Навпаки на першому етапі до середини ХХ століття наука управління розвивалася одразу за кількома відносно самостійним напрямкам або як кажуть підходам до управління кожний з яких концентрував увагу на різних аспектах менеджменту. Класична теорія підхід менеджменту включає дві школи: а школу наукового управління...
80242. Прийняття управлінських рішень. Методи творчого пошуку альтернатив 6.79 MB
  Прийняття управлінських рішень. Основи теорії прийняття рішень. Процес прийняття рішень. Основи теорії прийняття рішень У науковій літературі зустрічається як розширене так і вузьке розуміння процесу прийняття рішень в управлінні.