Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)
 МЕЖДУНАРОДНАЯ ЗАОЧНАЯ НАУЧНО-ПРАКТИЧЕСКАЯ КОНФЕРЕНЦИЯ   «ЕСТЕСТВЕННЫЕ И МАТЕМАТИЧЕСКИЕ НАУКИ В СОВРЕМЕННОМ МИРЕ»

Статья опубликована в рамках: XLIII Международной научно-практической конференции «Естественные и математические науки в современном мире» (Россия, г. Новосибирск, 06 июня 2016 г.)

Наука: Математика

Секция: Математическая логика, алгебра и теория чисел

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Ежова М.А. ВОПРОС ОБ АНАЛОГИИ СИСТЕМ ПРИ АНАЛОГИИ ЭЛЕМЕНТОВ НА ПРИМЕРЕ ПРОБЛЕМЫ РАСКРАСКИ ДОРОГ // Естественные и математические науки в современном мире: сб. ст. по матер. XLIII междунар. науч.-практ. конф. № 6(41). – Новосибирск: СибАК, 2016. – С. 81-85.
Проголосовать за статью
Дипломы участников
У данной статьи нет
дипломов

ВОПРОС ОБ АНАЛОГИИ СИСТЕМ ПРИ АНАЛОГИИ ЭЛЕМЕНТОВ НА ПРИМЕРЕ ПРОБЛЕМЫ РАСКРАСКИ ДОРОГ

Ежова Марина Алексеевна

старший преподаватель кафедра информационных технологий и математики Пермского института (филиала) Российского Экономического Университета имени Г.В. Плеханова,

РФ, г. Пермь

QUESTION OF ANALOG SYSTEMS AT ANALOGIES ELEMENTS ON THE EXAMPLE OF THE ROAD COLORING PROBLEM

Marina Egova

senior lecturer, Department of Information Technology and Mathematics Perm Institute (Branch) of Plekhanov Russia University of Economics,

Russia, Perm

 

АННОТАЦИЯ

Схожесть некоторых элементов систем не порождает эквивалентность систем.

ABSTRACT

The similarity of the some elements of the systems does not generate the equivalence of the systems.

 

Ключевые слова: аналогия; синхронизирующее слово; раскраска дорог.

Keywords: analogy; synchronizing word; road coloring.

 

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

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

Если рассматривать более обще, то многие ещё в школе замечали, что разные разделы математики, изучая одни и те же объекты, но с разных точек зрения, нередко приходят к одним и тем же выводам. Можно ли заключить, что все математические области аналогичны друг другу? Ни в коем случае. Схожесть в одном не порождает схожесть в остальном. Приведём пример в рамках одной проблемы, решаемой двумя разными теориями: теорией графов и теорией автоматов.

Прежде чем приступить к анализу формулировок теорем, определим некоторые основные понятия. Основным объектом приложения знаний является детерминированный конечный автомат (ДКА). Хотя Трахтман [4] предпочитает вести речь о конечном ориентированном сильно связном графе, но он часто ссылается на тесную связь графа и автомата.

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

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

Автомат, чей граф-основа является сильно связным, называется неприводимым. Неприводимый автомат называется апериодическим, если НОД длин циклов его графа равен 1, и периодическим в противном случае.

Исходящей степенью вершины (в англоязычных источниках полустепенью вершины) ориентированного графа называется число ребер, выходящих из этой вершины. Аналогично вводится понятие входящей степени вершины. Ориентированный граф G = (V, E) называется k-допустимым, если все вершины имеют одну и ту же исходящую степень k.

Конечный ориентированный сильно связанный граф с постоянной исходящей степенью всех его вершин, где НОД длин всех его циклов равен единице, будет называться AGW графом (граф, рассматриваемый в статье Адлера, Гудвина и Вейса 1977 года).

Вот такой взаимосвязанный клубок понятий. Перейдём к другому основному набору терминов в рассуждениях под общим названием: синхронизация. Благодаря богатству русского языка можно различить два понятия: синхронизирующее слово (слово, которое синхронизирует что-то) и синхронизированный автомат (автомат, который синхронизирован чем-то). В английском языке имеются аналогичные словосочетания «synchronizing word» и «synchronized automaton», соответственно.

Синхронизирующее слово детерминированного автомата – слово в алфавите цветов (рассматриваемых как символы) его ребер, переводящий автомат в фиксированное состояние (возможно единичное или заранее определённое). На символах: wсинхронизирующее слово, если для любых состояний p и q, pw=qw или fw(p)=fw(q) (fw: V→V – функция перехода на множестве вершин графа V). Тогда, ДКА называется (p, q)-синхронизированным. Иначе, слово s ∈ Σ+ (множество слов над Σ, где Σ={1, .., k} – алфавит для маркировки ребер графа) называется синхронизирующим словом автомата с графом переходов Γ, если |Гs| = 1. Или же слово w называется синхронизирующим, если fw(V) – одноэлементное множество. Всё это эквивалентные определения.

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

Это понятие близко к так называемой сводимости. Пара p, q состояний приводима/сводима (в символах pq), если существует слово w такое, что fw(p) = fw(q), т. е. слово w переводит p и q в одно и то же состояние. Отметим, что сводимость определяется для каждой конкретной пары состояний отдельно.

Синхронизированная пары состояний р и q автомата называется устойчивой (для этого и следующего понятий в английском языке используется слово «stable», что предполагает равнозначность определения), если для любого слова u пары pu, qu также синхронизированы.

В ДКА пара s, t состояний называется стабильной, если для каждого входящего слова u существует слово w (которое может зависеть от u) такое, что слово uw синхронизирует s и t. Другими словами, состояния s и t синхронизируются, и они остаются синхронизированными независимо от того, какое входные слово u применяется к ним. Это же понятие в обозначениях Кари:

(pq)   (p) (q).

Если для пары различных состояний р и q автомата (вершин графа переходов) и для любого слова s∈ Σ+ psqs, то назовём эту пару состояний тупиком.

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

Теорема 1. ( [2], Утверждение 5) Пусть A – ДКА, чей граф-основа сильно связан и апериодичен. Если A обладает свойством, что для каждой входящей буквы a ∈ Σ имеется не более одного состояния, не имеющее ребра с маркировкой a, входящего в это состояние, тогда A может быть перекрашен таким образом, что он станет синхронизированным.

Теорема 2. ( [4], Теоремы 3,4) Любой AGW граф Г имеет раскраску с устойчивыми парами, а значит, каждый AGW граф Г имеет синхронизированную раскраску.

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

Итак, Теорема 1.

  • Автомат A является ДКА, т. е. у него конечное число состояний и из каждой вершины выходит ровно k рёбер, все разной маркировки.
  • Граф-основа этого автомата сильно связан, т. е. для любых двух вершин найдётся ориентированный путь, связывающий их.
  • Граф-основа этого автомата апериодичен, т. е. если в этом графе и есть циклы, то НОД их длин равен 1.
  • Свойство этого автомата говорит о том, что в автомате может быть вершина, но только одна, в которую не входит ребро, отмеченное цветом a. Если в A ребра можно раскрашивать в k цветов, то таких вершин не более k (по одной на каждый цвет).
  • Автомат со всеми этими свойствами может быть синхронизирован.

Теперь попытаемся аналогично разложить Теорему 2.

  • граф Г – AGW, т. е. этот граф:
    • Конечен;
    • Сильно связный;
    • С постоянной исходящей степенью всех его вершин (аналог детерминированности автомата);
    • НОД длин всех его циклов равен 1.
  • Граф со всеми вышеперечисленными особенностями обладает устойчивой парой вершин.
  • Наличие устойчивых пар вершин эквивалентно синхронизированности графа.

Последнее утверждение было указано в [3] в следующим виде: проблема раскраски дорог эквивалентна гипотезе, что всегда существует раскраска с хотя бы одной стабильной парой. А это высказывание было основано на доказательстве теоремы, приведённом в [1], о равнозначности гипотезы раскраски дорог и гипотезы, что для каждого допустимого примитивного графа существуют различные вершины p и q, и раскраска δ, что δ делает (p, q) стабильной парой.

Анализируя всё это, так и хочется сделать вывод, что отсутствие входящего ребра с маркировкой a и наличие устойчивой пары вершин равносильны, но это не совсем так. Ведь каждый AGW граф обладает такой парой вершин, но не всякий ДКА имеет подобное свойство.

 

Список литературы:

  1. Culik N.K., Karhumaki J., Kari J. A note on synchronized automata and Road Coloring Problem / Developments in Language Theory (5th Int. Conf., Vienna, 2001) // Lecture Notes in Computer Science – 2002. № 2295. – P. 175–185.
  2. Kari J., Synchronization and stability of finite automata // J. Universal Comput. Sci. – 2002. № 8. – P. 270–277.
  3. Kari J., Synchronizing finite automata on Eulerian digraphs // Theoret. Comput. Sci. – 2003. № 295. – P. 223–232.
  4. Trahtman A., The road coloring problem // Isael J. Math. – 2009. Vol. 172, № 1. – P. 51–60.
Проголосовать за статью
Дипломы участников
У данной статьи нет
дипломов

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.