О коммутативных полугруппах с планарными графами Кэли

• Автор: Соломатин, Денис Владимирович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 107 с. : ил.

Глава 1. Коммутативно-свободные произведения циклических полугрупп, моноидов и полугрупп с нулем, допускающие планарный граф Кэли

:ф 1.1. Коммутативно-свободные произведения циклических полугрупп

1.2. Коммутативно-свободные произведения циклических моноидов

1.3. Коммутативно-свободные произведения циклических полугрупп с нулем

Глава 2. Прямые произведения циклических полугрупп, моноидов и полугрупп с нулем, допускающие планарный граф Кэли

2.1. Прямые произведения циклических полугрупп

2.2. Прямые произведения циклических моноидов

4 2.3. Прямые произведения циклических полугрупп с нулем

Глава 3. Некоторые вопросы общей теории графов Кэли

3.1. О допустимости некоторых графов в качестве графов Кэли конечных полугрупп

3.2. Рассыпчатые полугруппы, допускающие планарный граф Кэли

Литература

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

группой. Идею применения графов в представлении групп предложил английский математик Артур Кэли (1821-1895).
Изучению графов Кэли групп, посвящено много работ. При этом графы Кэли применяют не только для создания классификаций в теории групп. Например, Оливер и Сильва [64] использовали их для построения интересных графов с хорошими свойствами. В том же ракурсе графы Кэли исследовал Бигс [48].
Понятие графа Кэли для полугрупп ввел в рассмотрение Б.Зелинка [68]. Такой граф является ориентированным графом без петель и многократных ребер. Важность этого понятия для комбинаторной теории полугрупп продемонстрирована в работах С.В.Марголиса и Дж.К.Микина [60], а также Б.Штейнберга [66]. В частности, первые два автора рассматривали ^-унитарные инверсные моноиды и графы Кэли в представлениях полугрупп.
М.-К.Хейдеманн [52] сопоставляет графы Кэли и коммуникационные сети. Активно занимается исследованием графов Кэли А.В.Келарев, изучая неориентированные графы Кэли [57], а также полные и двудольные графы Кэли совместно с С.Дж.Квином [59]. Эти же авторы [56] изучали группы и полугруппы, удовлетворяющие некоторым комбинаторным свойствам, определенным в терминах графов Кэли. В частности, они установили, что эти свойства приводят к новым связям между графом, группой и теоретико-полугрупповыми методами. Кроме того, А.В.Келарев совместно с К.Е.Прогом изучали транзитивные графы Кэли групп и полугрупп [58].
Что касается важного свойства планарности графа, то оно изучалось в основном для групп. Описание конечных групп, допускающих плоские графы Кэли, получили Х.Цишанг, Э.Фогт, Х.-Д.Колдевай [45].
Изучением возможностей, при которых одна и та же группа обладает неизоморфными плоскими графами Кэли, и изучением неизоморфных групп, допускающих изоморфные графы Кэли, занималась Ж.Т.Беленкова [9].
Исследование графов Кэли групп проводили В.А.Романьков и Ж.Т.Беленкова [10], [11]. Ими описаны всевозможные варианты выбора

ся два элемента бесконечного порядка, то её граф Кэли не будет планарным, поскольку обнаруживается подграф, изображенный на рис. 1.1.10 справа, го-меоморфный графу К5. Если среди образующих лишь один бесконечного
типа, то типы остальных сомножителей ограничивают условия теоремы 1.3.1. Анализ ограничений типов сомножителей в теореме 1.3.1 показывает, что среди сомножителей может содержаться циклическая полугруппа, сколь угодно большого конечного числа элементов, лишь в случае 3) и 4). Удовлетворяющие этим условиям полугруппы имеют копредставления 5 = (а,Ь аЬ = Ьа,Ьи =0) и 5 = {а,Ь,с аЬ = Ьа, Ъ1 =Ь, с = 0). Во всех остальных случаях графы Кэли содержат подграфы, гомеоморфные графам К5 или К33, аналогичные подграфам, содержащимся в графах Кэли конечных полугрупп являющихся коммутативно-свободным произведением циклических полугрупп с нулем.
Пусть 5 является коммутативно-свободным произведением неодноэлементной нильполугруппы и бесконечной циклической полугруппы с нулем, то есть 5 2 (а, Ъ аЪ- Ьа, Ь = Оу, где И > 1. Плоскую укладку полугруппы 5 можно получить аналогично изображенной на рис. 1.3.1, продолжив влево расположение элементов содержащих большие степени образующих.
Если
Б -1а, Ь,с
же полугруппа имеет копредставление

аЬ = Ьа, Ъ" = Ъ, с = Оу, то основа её графа Кэли допускает плоскую укладку, фрагмент которой приведен на рис. 1.3.4.
Рис. 1.3.4. Фрагмент плоской укладки ориентированной основы графа

Кэли полугруппы Б = [а, Ь,с аЬ-Ьа,Ь =Ь,с = 0). Следствие 1.3.2 доказано.