Алгебраическое представление детерминированных графов

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

Full description

Saved in:

Bibliographic Details
Date:	2009
Main Authors:	Сенченко, А.С., Рубан, Н.Н.
Format:	Article
Language:	Russian
Published:	Інститут проблем штучного інтелекту МОН України та НАН України 2009
Subjects:	Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/7839
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Алгебраическое представление детерминированных графов / А.С. Сенченко, Н.Н. Рубан // Штучний інтелект. — 2009. — № 1. — С. 198-203. — Бібліогр.: 9 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859733646475264000
author	Сенченко, А.С. Рубан, Н.Н.
author_facet	Сенченко, А.С. Рубан, Н.Н.
citation_txt	Алгебраическое представление детерминированных графов / А.С. Сенченко, Н.Н. Рубан // Штучний інтелект. — 2009. — № 1. — С. 198-203. — Бібліогр.: 9 назв. — рос.
collection	DSpace DC
description	В статье предлагается задание детерминированных инициальных графов с помощью определяющей пары, первая компонента которой однозначно задает базу графа, а вторая дополняет базу до заданного графа. Предложена процедура построения графа по его определяющей паре, а также процедура построения минимальной определяющей пары графа, названной канонической. Полученные результаты могут быть использованы в дальнейшем исследовании детерминированных графов, в частности при проведении экспериментов с графами с использованием блуждающих по ним агентов. У роботі запропоновано задання детермінованих графів за допомогою визначальної пари, перша компонента якої однозначно задає базу графа, а друга доповнює базу до заданого графа. Запро- поновано процедуру побудови графа за його визначальною парою, а також процедуру побудови мінімальної (канонічної) визначальної пари графа. Отримані результати можуть бути використані в подальшому дослідженні детермінованих графів, зокрема при проведенні експериментів із графами з використанням блукаючих по ним агентів. In this paper is proposed a task of deterministic graphs with the help of a defining pair, the first component of which specifies the base graph, and the second supplements base a given graph. Proposed procedure for constructing a graph on his defining pair, and procedure for constructing the minimum pair graph, called canonical. The results can be used for further study of deterministic graphs, in particular because of experiments with graphs using agents wandering on them.
first_indexed	2025-12-01T14:37:55Z
format	Article
fulltext	«Искусственный интеллект» 1’2009 198 4С УДК 519.7 А.С. Сенченко, Н.Н. Рубан Славянский государственный педагогический университет, Украина Алгебраическое представление детерминированных графов В статье предлагается задание детерминированных инициальных графов с помощью определяющей пары, первая компонента которой однозначно задает базу графа, а вторая дополняет базу до заданного графа. Предложена процедура построения графа по его определяющей паре, а также процедура построения минимальной определяющей пары графа, названной канонической. Полученные результаты могут быть использованы в дальнейшем исследовании детерминированных графов, в частности при проведении экспериментов с графами с использованием блуждающих по ним агентов. Введение Известно, что многие объекты дискретной математики и алгебры можно представить определяющими соотношениями. Так в 1882 году В. Фон Дик предложил задавать группы посредством порождающих элементов и определяющих соотно- шений [1]. Впоследствии было предложено аналогичное задание полугрупп. В связи с таким заданием выше перечисленных объектов возникли знаменитые проблемы Туэ-Дэна [2], самой сложной из которых является проблема изоморфизма: две полугруппы/группы заданы системой определяющих соотношений (СОС), необходимо найти алгоритм, позволяющий по СОС определить, изоморфны ли полу- группы/группы друг другу или нет. В 1947 году была доказана неразрешимость проблем Туэ-Дэна: А.А. Марковым и Эм. Постом для полугрупп [3], а чуть позднее, в 1955, П.С. Новиков и У. Бун доказали неразрешимость для групп. В 1961 Ю.И. Соркин в работе [4] сформулировал и предложил позитивное кон- структивное решение проблем Туэ-Дэна для детерминированных всюдуопределенных автоматов. Тем самым была показана принципиальная возможность использования СОС при решении задач теории автоматов. В дальнейшем идеи Соркина обобща- ются и используются для исследования проблем теории экспериментов с конечными автоматами и лабиринтами. В частности в работе [5] предложен частный случай решения проблемы изо- морфизма всюдуопределенных автоматов без непосредственного построения автоматов по их системе определяющих соотношений, а в работе [6] аналогичным образом ре- шена проблема для частичных автоматов. В связи с определенной схожестью структуры графов и автоматов возникает идея распространить результаты А.С. Сенченко на графы. Наиболее схожими по струк- туре с автоматами, на наш взгляд, являются графы с детерминированной раскраской (детерминированные графы), впервые рассмотренные С.В. Сапуновым в [7]. 1. Основные определения Под автоматом понимается конечный детерминированный инициальный иници- ально-связный частичный автомат без выхода [8]. Будем считать, что  0,,, aXAA  – автомат, у которого A – конечное множество состояний, 0a – начальное состояние, Алгебраическое представление детерминированных графов «Штучний інтелект» 1’2009 199 4С AXA : – функция переходов. Множество всех слов конечной длины в алфавите X обозначается X . Пусть kxxp 1 – произвольное слово в алфавите X . Слово 1xxk будем обозначать через 1p . Длина слова p обозначается )( pd и kpd )( . Одним из известных способов задания автоматов является его представление определяющими соотношениями, то есть такими парами слов ),( qp , что pa0 и qa0 определяют одно и то же состояние. Множество таких определяющих соотношений, однозначно задающих автомат, называется его системой определяющих соотношений. Для частичных автоматов в работе [6] была введена модификация СОС, названная определяющей системой, которая состоит из двух компонент },{ M . Первая ее компонента  , состоящая из таких пар слов ),( qp , что pa0 , qa0 определены и qapa 00  , является аналогом СОС и однозначно задает базу [4] автомата. Вторая компонента M состоит из таких слов px , где Xx , что pa0 определено, а pxa0 не определено. Она однозначно выделяет автомат от других подобных ему по свобод- ному расширению [4]. В работах [5], [6], [9] были решены задачи, связанные с представлением автоматов определяющими соотношениями: найдена минимальная СОС для автомата; найдено преобразование (редукция) СОС, позволяющее опреде- лить, соответствует ли данная СОС данному автомату; соответствуют ли две данные СОС одному и тому же автомату. Для распространения этих результатов на схожие по структуре объекты с автоматами – детерминированные графы – необходимо ввести на них аналог СОС. Пусть  0,,,, gCEGG  – конечный, простой неориентированный граф с отмет- ками вершин, у которого G – множество вершин, E – множество ребер, C – множество отметок вершин, CG : – функция отметок, 0g – инициальная вершина. Окрест- ностью вершины )(gO называется вершина g вместе с множеством всех вершин, смежных с ней:    gEggO )( . Граф  0,,,, gCEGG  называется детерминирован- ным [7], если у любых двух различных вершин из любой окрестности отметки различны, то есть )(,, gOvuGg  из vu  следует )()( vu   . Путем в детерми- нированном графе  0,,,, gCEGG  будем называть произвольную последовательность отметок вершин )()( 1 kggp   , где   Egg ii 1, , для всех ki 1 . Если в окрест- ности вершин v нет вершины с отметкой c , то будем говорить, что путь по c из v не определен, в противном случае путь определен. В работе рассматриваются только связные графы. Пусть  0,,,, gCEGG  – детерминированный граф. Удалим из G все висячие вершины, отличные от инициальной 0g . Будем повторять данную операцию до тех пор, пока это возможно. Получившийся граф назовем базой графа G . Опишем вершины, входящие в базу графа. База может состоять из одной инициальной вершины, если граф является деревом. Если же граф не дерево, то в базу входят только те вершины, через которые проходит некоторый простой цикл и вершины, через которые прохо- дит путь от начальной вершины к некоторому простому циклу. 2. Определяющие слова для детерминированных графов Пусть  LS , – пара конечных множеств слов, таких, что для любого слова p из множества S выполняется равенство 00 gpg  , а для любого слова Mq путь qv0 определен, и соответствующая вершина является висячей. Рассмотрим процедуру построения графа по паре множеств  LS , : Сенченко А.С., Рубан Н.Н. «Искусственный интеллект» 1’2009 200 4С 1. Строим циклы по словам множества S и в любом случае получаем граф с раскрашенными вершинами, причем детерминированность раскраски не обязательно выполняется. 2. Осуществляется детерминизация полученного графа путем отождествления вершин с одинаковой раскраской из каждой окрестности. Ввиду конечности мно- жества S данная операция выполняется конечное число раз и результат однозначен. 3. К полученному графу, используя элементы множества L , добавляем «тупи- ковые» ветки. При необходимости осуществляем повторную детерминизацию. Пару  LS , назовем определяющей для детерминированного графа G , если она однозначно его задает. Определяющая пара является аналогом определяющей системы для частичных автоматов, рассмотренных в [6]. Проиллюстрируем ход выполнения вышеуказанной процедуры на следующем примере. Пример 1. Пусть  abdcbcbaabcdbaS ; и  abcdacabdacabdcaL ;; , тогда в ходе вы- полнения процедуры последовательно получаем такие графы: Детерминизацию можно осуществлять один раз, то есть шаг 2 выполнять после шага 3, но на наш взгляд лучше ее проводить после анализа каждого слова множеств S и L . Не всякая пара множеств  LS , задает граф. Потому что вершина, соответ- ствующая некоторому слову множества L , может быть не висячей. Приведем пример таких множеств S и L , которые не являются определяющими ни для какого графа. Пример 2. Пусть  abdcbcbaabcdbaS ; и  abcdaabdacabdcaL ;; , тогда шаги 1 и 2 приведут к аналогичному результату, первые два слова множества L строят граф такой же, как и в предыдущем примере, а вершина соответствующая третьему слову (она выделена) – не висячая, так как ее степень равна двум. В дальнейшем предполагается формализировать условия для множеств S и L , для которых пара  LS , является определяющими словами для некоторого детермини- рованного графа. Алгебраическое представление детерминированных графов «Штучний інтелект» 1’2009 201 4С 3. Построение по графу его определяющей пары Покажем, что каждый детерминированный граф имеет хотя бы одну определя- ющую пару. Пусть  mccC ,...,1 и mccc  21 – произвольно зафиксированный линейный порядок P на C . Введем линейный порядок  на множестве C всех слов в алфа- вите C таким образом: 1) ii cc  ; 2) если )()( qdpd  , то qp  ; 3) ss ccqpcc   11 , если kk cc  для некоторого sk  , в то время как 1111 ,,   kk cccc  . Другими словами, слово меньшей длины предшествует слову большей длины, а слова одинаковой длины сравниваются в соответствии с лексикографическим порядком (по алфавиту). Очевидно, что порядок  на *C однозначно определяется некоторым порядком P на C . Каждую вершину графа G именуем кратчайшим по введенному порядку  словом, соответствующим ей, то есть строим кратчайший по порядку  базис дости- жимости. Полученное множество имен вершин обозначим через GV . Заметим, что в силу минимальности имен вершин любой начальный отрезок любого слова из GV тоже принадлежит базису достижимости GV . Для всех слов GVccpp  и всех отметок c  , отличных от c , если путь cccp  определен и соответствует невисячей вершине с именем cqq  и cqcccp  , то циклическое слово 1)(  qcp помещаем в множество 1 , если же соответствующая вершина является висячей (ее имя будет cp  ), то слово cp  помещаем в множество G . Затем в множестве 1 из всех пар обратных слов p и 1p оставляем одно кратчайшее по порядку  , а другое исключаем. Получившееся множество обозна- чим через G . Заметим, что если слово p принадлежит G , то для любого его начального отрезка p вершина, соответствующая слову p , содержится в базе графа G . Теорема 1. Пара  GG  , является определяющей для графа G . Доказательство. По паре  GG  , построим детерминированный граф G . Покажем, что графы G и G изоморфны. Пусть вершина g с именем p принадлежит базе графа G . Тогда по построе- нию G в нем существует такое слово q , для которого p или 1p является начальным отрезком. Поэтому g принадлежит базе графа G и имя вершины g есть слово p . Пусть вершина g принадлежит базе графа G . Тогда либо через эту вершину проходит некоторый простой цикл, либо через нее проходит путь к некоторому простому циклу. Рассмотрим первый случай: пусть GV  – базис достижимости графа G и GVp  – имя вершины g в этом базисе. Тогда существует такое слово q , что pqgpg 00  . Поскольку GVpq  , то существует такой начальный отрезок wc слова pq , что GVw  , а GVwc  . Пусть r – такое слово из базиса GV  , что wcgrg 00  . Сенченко А.С., Рубан Н.Н. «Искусственный интеллект» 1’2009 202 4С Тогда по построению G меньшее из слов 1)( rwc и 1)( wcr по порядку  принадлежит G , следовательно, g принадлежит базе графа G и имя вершины g есть слово p . Рассмотрим второй случай. Пусть p – имя вершины g в базисе GV  . Тогда существуют такие слова q и z , что GVpz  и pzqgpzg 00  . Поскольку GVpzq  , то существует такой начальный отрезок wc слова pzq , что GVw  , а GVwc  . Пусть r – такое слово из базиса GV  , что wcgrg 00  . Тогда, так же, как и в первом случае, по построению G меньшее из слов 1)( rwc и 1)( wcr по порядку  принадлежит G , следовательно, g принадлежит базе графа G и имя вершины g есть слово p . Таким образом доказано, что базы графов G и G совпадают. Пусть теперь вершина g графа G не принадлежит его базе и пусть GVp – имя вершины g . Тогда из конечности графа G следует, что существует такое слово q , что Gpq  , поэтому вершина g с именем p принадлежит графу G и не находится в его базе. Обратно, пусть вершина g графа G не принадлежит его базе и GVp  – имя вершины g . Тогда по построению графа G существует такое слово q , что Gpq  , следовательно, вершина g с именем p принадлежит графу G и не находится в его базе. Таким образом, показано, что графы G и G изоморфны. Теорема доказана. Определяющую пару  GG  , назовем канонической для G . Из минималь- ности длин слов из базиса достижимости GV и минимальности циклических слов базиса достижимости G вытекает Следствие 1. Каноническая определяющая пара  GG  , является минимальной по длине слов определяющей парой для графа G . Пример 3. Для заданного графа канонической определяющей парой являются G   abcdba и  abdacabcaG ; . Заключение Таким образом, в настоящей работе предложено представление детерми- нированных графов определяющей парой, которая является аналогом системы опре- деляющих соотношений. Найдены процедура построения графа по его определяющей паре и процедура построения минимальной (канонической) определяющей пары для Алгебраическое представление детерминированных графов «Штучний інтелект» 1’2009 203 4С графа. Полученные результаты являются распространением соответствующих задач теории автоматов на графы и могут быть использованы при проведении диагности- ческих и контрольных экспериментов с детерминированными графами. Литература 1. Чандлер Б., Магнус В. Развитие комбинаторной теории групп. – М.: Мир, 1985. – 255 с. 2. Адян С.И., Дурнев В.Г. Алгоритмические проблемы для групп и полугрупп // Успехи матема- тических наук. – 2000. – Т. 55, вып. 2. – С. 3-94. 3. Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир, 1985. – 440 с. 4. Соркин Ю.И. Теория определяющих соотношений для автоматов // Проблемы кибернетики. – 1961. – Вып. 9. – С. 45-69. 5. Грунский И.С., Сенченко А.С. Каноническая система определяющих соотношений для автоматов // Труды института прикладной математики и механики. – 2002. – Т. 7. – С. 58-63. 6. Сенченко А.С. Свойства определяющих систем для частичных автоматов // Труды института прикладной математики и механики. – 2003. – Т. 8. – С. 111-119. 7. Сапунов С.В. Эквивалентность отмеченных графов // Труды института прикладной математики и механики. – 2002. – Т. 7. – С. 162-167. 8. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука, 1997. – 368 с. 9. Сенченко А.С. Представление автоматов определяющими соотношениями их поведения: Дис… канд. физ.-мат. наук. – К.: Институт кибернетики им. В.М. Глушкова, 2005. О.С. Сенченко, Н.Н. Рубан Алгебраїчне зображення детермінованих графів У роботі запропоновано задання детермінованих графів за допомогою визначальної пари, перша компонента якої однозначно задає базу графа, а друга доповнює базу до заданого графа. Запро- поновано процедуру побудови графа за його визначальною парою, а також процедуру побудови мінімальної (канонічної) визначальної пари графа. Отримані результати можуть бути використані в подальшому дослідженні детермінованих графів, зокрема при проведенні експериментів із графами з використанням блукаючих по ним агентів. A.S. Senchenko, N.N. Ruban The Algebraic Representation of Deterministic Graphs In this paper is proposed a task of deterministic graphs with the help of a defining pair, the first component of which specifies the base graph, and the second supplements base a given graph. Proposed procedure for constructing a graph on his defining pair, and procedure for constructing the minimum pair graph, called canonical. The results can be used for further study of deterministic graphs, in particular because of experiments with graphs using agents wandering on them. Статья поступила в редакцию 01.07.2008.
id	nasplib_isofts_kiev_ua-123456789-7839
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1561-5359
language	Russian
last_indexed	2025-12-01T14:37:55Z
publishDate	2009
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
record_format	dspace
spelling	Сенченко, А.С. Рубан, Н.Н. 2010-04-19T12:15:55Z 2010-04-19T12:15:55Z 2009 Алгебраическое представление детерминированных графов / А.С. Сенченко, Н.Н. Рубан // Штучний інтелект. — 2009. — № 1. — С. 198-203. — Бібліогр.: 9 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/7839 519.7 В статье предлагается задание детерминированных инициальных графов с помощью определяющей пары, первая компонента которой однозначно задает базу графа, а вторая дополняет базу до заданного графа. Предложена процедура построения графа по его определяющей паре, а также процедура построения минимальной определяющей пары графа, названной канонической. Полученные результаты могут быть использованы в дальнейшем исследовании детерминированных графов, в частности при проведении экспериментов с графами с использованием блуждающих по ним агентов. У роботі запропоновано задання детермінованих графів за допомогою визначальної пари, перша компонента якої однозначно задає базу графа, а друга доповнює базу до заданого графа. Запро- поновано процедуру побудови графа за його визначальною парою, а також процедуру побудови мінімальної (канонічної) визначальної пари графа. Отримані результати можуть бути використані в подальшому дослідженні детермінованих графів, зокрема при проведенні експериментів із графами з використанням блукаючих по ним агентів. In this paper is proposed a task of deterministic graphs with the help of a defining pair, the first component of which specifies the base graph, and the second supplements base a given graph. Proposed procedure for constructing a graph on his defining pair, and procedure for constructing the minimum pair graph, called canonical. The results can be used for further study of deterministic graphs, in particular because of experiments with graphs using agents wandering on them. ru Інститут проблем штучного інтелекту МОН України та НАН України Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем Алгебраическое представление детерминированных графов Алгебраїчне зображення детермінованих графів The Algebraic Representation of Deterministic Graphs Article published earlier
spellingShingle	Алгебраическое представление детерминированных графов Сенченко, А.С. Рубан, Н.Н. Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем
title	Алгебраическое представление детерминированных графов
title_alt	Алгебраїчне зображення детермінованих графів The Algebraic Representation of Deterministic Graphs
title_full	Алгебраическое представление детерминированных графов
title_fullStr	Алгебраическое представление детерминированных графов
title_full_unstemmed	Алгебраическое представление детерминированных графов
title_short	Алгебраическое представление детерминированных графов
title_sort	алгебраическое представление детерминированных графов
topic	Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем
topic_facet	Архитектура, алгоритмическое и программное обеспечение интеллектуальных многопроцессорных систем
url	https://nasplib.isofts.kiev.ua/handle/123456789/7839
work_keys_str_mv	AT senčenkoas algebraičeskoepredstavleniedeterminirovannyhgrafov AT rubannn algebraičeskoepredstavleniedeterminirovannyhgrafov AT senčenkoas algebraíčnezobražennâdetermínovanihgrafív AT rubannn algebraíčnezobražennâdetermínovanihgrafív AT senčenkoas thealgebraicrepresentationofdeterministicgraphs AT rubannn thealgebraicrepresentationofdeterministicgraphs

Алгебраическое представление детерминированных графов

Institution

Similar Items