Содержание к диссертации
Введение
Глава 1. Коммутативно-свободные произведения цикличе ских полугрупп, моноидов и полугрупп с нулем, допускающие планарный граф Кэли 23
1.1. Коммутативно-свободные произведения циклических полугрупп 23
1.2. Коммутативно-свободные произведения циклических моноидов 36
1.3. Коммутативно-свободные произведения циклических полугрупп с нулем 45
Глава 2. Прямые произведения циклических полугрупп, моноидов и полугрупп с нулем, допускающие планарный граф Кэли 51
2.1. Прямые произведения циклических полугрупп 51
2.2. Прямые произведения циклических моноидов 72
2.3. Прямые произведения циклических полугрупп с нулем 83
Глава 3. Некоторые вопросы общей теории графов Кэли 89
3.1. О допустимости некоторых графов в качестве графов Кэли конечных полугрупп 89
3.2. Рассыпчатые полугруппы, допускающие планарный граф Кэли 95
Литература
- Коммутативно-свободные произведения циклических моноидов
- Коммутативно-свободные произведения циклических полугрупп с нулем
- Прямые произведения циклических моноидов
- Рассыпчатые полугруппы, допускающие планарный граф Кэли
Введение к работе
Одним из наиболее важных понятий, относящихся к структуре дискретных систем, является понятие графа. Это понятие, описывающее структуру связей между отдельными частями системы, в силу своей общности используется во многих математических моделях. Графы очень часто используются в приложениях, поскольку они возникают как модель при изучении многих объектов.
Тематика исследований, связанных с графами, очень широка. Это и исследование структуры и свойств графов, изучение специальных классов графов, построение быстрых алгоритмов для решения различных задач на графах и т. д.
Множество самых разнообразных задач естественно формулируется в терминах графов. Так, например, могут быть сформулированы задачи составления расписания, анализа цепей в электротехнике, в программировании, в проектировании электронных схем и телекоммуникационных сетей, в экономике, в социологии, в информатике и т.д. При этом важную роль играет свойство планарности графа. Это свойство играет существенную роль в радиоэлектронике при изготовлении печатных плат. Поскольку печатные проводники не изолированы, они не должны пересекаться. Поэтому важно знать, является ли планарным графом электрическая схема печатной платы. Если этот граф непланарен, то невозможно изготовить однослойную печатную плату.
Графы естественным образом появляются и в математике, в частности, как производные объекты некоторых математических структур. Не является исключением и теория полугрупп, так как каждой полугруппе можно сопоставить её граф Кэли, тесно связанный с полугрупповой операцией.
Граф Кэли первоначально. рассматривали как объект, связанный с группой. Идею применения графов в представлении групп предложил английский математик Артур Кэли (1821-1895).
Изучению графов Кэли групп, посвящено много работ. При этом графы Кэли применяют не только для создания классификаций в теории групп. Например, Оливер и Сильва [64] использовали их для построения интересных графов с хорошими свойствами. В том же ракурсе графы Кэли исследовал Бигс[48].
Понятие графа Кэли для полугрупп ввел в рассмотрение Б.Зелинка [68]. Такой граф является ориентированным графом без петель и многократных ребер. Важность этого понятия для комбинаторной теории полугрупп продемонстрирована в работах С.В.Марголиса и Дж.К.Микина [60], а также Б.Штейнберга [66]. В частности, первые два автора рассматривали -унитарные инверсные моноиды и графы Кэли в представлениях полугрупп.
М.-К.Хейдеманн [52] сопоставляет графы Кэли и коммуникационные сети. Активно занимается исследованием графов Кэли А.В.Келарев, изучая неориентированные графы Кэли [57], а также полные и двудольные графы Кэли совместно с С.Дж.Квином [59]. Эти же авторы [56] изучали группы и полугруппы, удовлетворяющие некоторым комбинаторным свойствам, определенным в терминах графов Кэли. В частности, они установили, что эти свойства приводят к новым связям между графом, группой и теоретико-полугрупповыми методами. Кроме того, А.В.Келарев совместно с К.Е.Прогом изучали транзитивные графы Кэли групп и полугрупп [58].
Что касается важного свойства планарности графа, то оно изучалось в основном для групп. Описание конечных групп, допускающих плоские графы Кэли, получили Х.Цишанг, Э.Фогт, Х.-Д.Колдевай [45].
Изучением возможностей, при которых одна и та же группа обладает неизоморфными плоскими графами Кэли, и изучением неизоморфных групп, допускающих изоморфные графы Кэли, занималась Ж.Т.Беленкова [9].
Исследование графов Кэли групп проводили В.А.Романьков и Ж.Т.Беленкова [10], [11]. Ими описаны всевозможные варианты выбора
групп и их порождающих множеств, приводящие к регулярным замощениям как графам Кэли. Проведен полный и детальный анализ групп, допускающих в качестве графа Кэли регулярное замощение плоскости. В результате подробных рассмотрений получили 6 групп с графом Кэли, составленным из треугольников, 16 групп с графом, составленным из квадратов, и 6 групп с графом из шестиугольников. С точностью до изоморфизма, полученные графы, исчерпывают 14 кристаллографических групп (из 17 возможных). Кроме того, приведены некоторые общие свойства плоских графов Кэли конечных групп. В частности, охарактеризованы нециклические абелевы группы, вло-жимые в плоскость. Приведены примеры неабелевых групп, невложимых в плоскость.
В работе [9] описаны все плоские графы Кэли группы S4. Оказалось, что группа обладает четырьмя плоскими графами Кэли, два из которых являются графами Кэли двух групп, не изоморфных группе S4. Кроме того, выписаны все минимальные по включению порождающие множества группы 4. Их 10 штук: 3 из них состоят из двух элементов, а 7 - из трех элементов.
Что касается полугрупп, то подобные задачи не исследовались. Объясняется это, по-видимому, тем, что описание всех конечных полугрупп с пла-нарными графами Кэли, на наш взгляд, представляет собой чрезвычайно сложную задачу. Поэтому естественно сузить изучаемый класс полугрупп. Зачастую в таких случаях отправляются от некоторого хорошо изученного класса групп с этим свойством и исследуют соответствующий класс полугрупп. В качестве такого класса групп мы выбираем класс конечных абеле-вых групп.
Основной целью данной работы является изучение конечных коммутативных полугрупп, допускающих планарные графы Кэли.
Однако и для этого класса полугрупп соответствующая задача оказывается трудно обозримой. Поэтому за отправную точку нами взят тот факт, что любая конечная абелева группа является прямым произведением циклических групп. В связи с этим, естественно в качестве исследуемых полугрупп взять прямые произведения и близкие к ним коммутативно-свободные произведения конечных циклических полугрупп, моноидов и полугрупп с нулем. Они являются основными объектами изучения в нашей работе. При этом мы не ограничиваемся рассмотрением только конечных коммутативных полугрупп. Кроме того, исследуем некоторые задачи для произвольных полугрупп. А именно, задачу о допустимости некоторых графов в качестве графов Кэли полугрупп и задачу характеризации рассыпчатых полугрупп, допускающих планарный граф Кэли.
Все основные результаты диссертации являются новыми. Описание прямых произведений циклических полугрупп, допускающих планарный граф Кэли, является обобщением известного результата для конечных абелевых групп [10].
Основные результаты диссертации:
1) получен критерий планарности графов Кэли коммутативно- свободных произведений циклических полугрупп, моноидов и полугрупп с нулем;
2) найден критерий планарности графов Кэли прямых произведений циклических полугрупп, моноидов и полугрупп с нулем;
3) решена задача о допустимости плоских триангуляции, полного пяти-элементного графа К5 и полного двудольного графа АГ3 з с некоторой ориентацией ребер в качестве графов Кэли полугрупп;
4) охарактеризованы рассыпчатые полугруппы с планарными графами Кэли.
При получении основных результатов широко используются методы теории полугрупп, теории графов и компьютерной алгебры.
Работа носит теоретический характер. Её результаты выделяют довольно широкие классы полугрупп со свойством планарности графа Кэли и представляют научный интерес для специалистов в теории полугрупп. Результаты также могут быть использованы при чтении спецкурсов, подготовке учебных пособий и монографий. Авторские программы для ЭВМ могут найти применение для решения вопроса о допустимости некоторых графов в качестве графа Кэли конечной полугруппы, для выполнения проверки планарности конечных графов путем автоматического создания запросов в Maple, а также в учебном процессе для демонстрации возможностей языка Паскаль.
Результаты диссертации докладывались на заседаниях алгебраических семинаров Омского университета и Омского педагогического университета; секции полугрупп Международной алгебраической конференции в Екатеринбурге, посвященной столетию со дня рождения П.Г.Конторовича и 70-летию Л.Н.Шеврина; алгебраической конференции «Мальцевские чтения 05» в Новосибирске. Основные результаты диссертации отражены в девяти публикациях автора [70]—[78].
Диссертация содержит 107 страниц, состоит из введения, трех глав, разбитых на восемь параграфов, списка литературы из 78 наименований. Текст диссертации снабжен 97 рисунками.
В работе принята тройная нумерация утверждений и иллюстраций. Например, номер 3.2.1 означает, что данное утверждение или рисунок находится во втором параграфе третьей главы, и имеет порядковый номер 1.
Прежде чем перейти к формулировке основных результатов, напомним некоторые определения теории графов и теории полугрупп.
Обыкновенный граф - это пара (V,E), где V - конечное непустое множество вершин, Е - множество ребер, являющееся произвольным подмножеством множества неупорядоченных пар вершин графа.
Ориентированный граф {орграф) - это пара (V,A), где V - конечное непустое множество вершин, А - множество дуг (упорядоченных пар (v,-,v ) элементов из V), являющееся произвольным подмножеством декартова квадрата множества вершин графа.
Если пара (v,-,v •) встречается в А более одного раза, то говорят, что (v/5v •) - кратная дуга. Граф с кратными дугами называют ориентированным мультиграфом. Определим понятие помеченного графа. Пусть Sv и Se -множества меток. Пометкой (распределением меток) графа G = (V, А) называется пара функций f:V- Sv - распределение меток вершин, g:E- Se -распределение меток дуг. Ориентированный мультиграф, с заданным распределение меток дуг, состоящий из конечного непустого множества вершин V и множества помеченных дуг - упорядоченных троек (vhx,Vj), для которых упорядоченная пара (v/5v) является элементом декартова квадрата множества вершин этого графа, х - элемент множества меток дуг, называем ориентированным мулътиграфом с помеченными дугами.
Плоским графом называется обыкновенный граф, если при изображении его на плоскости вершины являются точками плоскости, а ребра - непрерывными плоскими линиями без самопересечений, соединяющими вершины так, что никакие два ребра не имеют общих точек, кроме инцидентной им обоим вершины. Такое изображение графа будем называть плоской укладкой. Любой граф, изоморфный плоскому графу, называется планарным. Аналогичную терминологию будем иногда применять и для других видов графов.
Основой ориентированного мультиграфа с помеченными дугами мы называем обыкновенный граф, полученный из данного графа удалением петель, меток и заменой всех дуг, соединяющих две вершины, одним ребром, соединяющим эти вершины. Ориентированной основой ориентированного мультиграфа с помеченными дугами будем называть ориентированный граф, полученный из заданного удалением петель, меток, а также заменой всех одинаково направленных дуг одной дугой с той же ориентацией. Ориентированный мультиграф естественно назвать планарным, если его основа является % планарным графом.
Графом Кэли группы является граф, передающий структуру (связь эле- ментов) группы. Это основное понятие в комбинаторной и геометрической теории групп. Геометрическая и комбинаторная теории групп - две смежные отрасли математики, которые изучают группы. Геометрическая теория групп использует топологические и геометрические методы для изучения группы; основной идеей является получение информации о группе, анализируя её влияние на топологические аспекты. .
Напомним, что граф Кэли группы G относительно её подмножества X, состоит из множества вершин G и дуг от g к gx для всех элементов geG,xeX.
Как отмечалось ранее, аналогичную конструкцию на полугруппы перенес Б.Зелинка в [68], где графом Кэли Cay{S,T) полугруппы S относительно её подмножества Т называется граф с вершинами из S и множеством дуг, состоящим из таких упорядоченных пар (х,у), что хїу и xt = y для некоторого t є Г. Данный граф является ориентированным графом без петель и многократных ребер. Существуют и некоторые другие подходы к определению этого понятия, например, в [57] рассматриваются неориентированные графы Кэли.
Естественно, что такие определения вполне оправданы, если изучать задачи, не требующие восстановления полугруппы по графу. Для изучения планарности эти определения, вообще говоря, вполне пригодны. Но если изучать вопрос, который затрагивается в диссертации, о допустимости некоторых графов в качестве графов Кэли полугрупп, то необходимо.модифицировать эти определения.
Графом Кэли полугруппы S относительно множества X порождающих её элементов мы называем ориентированный мультиграф Cay(S, X) с помеченными дугами, состоящий из множества вершин S и множества помеченных дуг - всевозможных троек (а, х, Ъ), где a,beS, хеХ и ах = Ь.
Такое определение графа Кэли аналогично определению графа Кэли, связанного с группой. Оно несколько отличается от введенного Б.Зелинка.
Вершины графа, как обычно изображаются точками на плоскости, а дуга (а,х,Ь) - стрелкой, направленной от а к Ь и помеченной элементом х. В случае, когда метка ребра легко восстанавливается, мы будем опускать её. При изображении графов в общем виде, для удобства восприятия, пунктирными линиями или стрелками будем обозначать легковосстановимые цепи из одинаково помеченных ребер, соединяющие соответствующие вершины.
Очевидно, две полугруппы будут изоморфны тогда и только тогда, когда их графы Кэли будут изоморфны. Естественно, что при изучении свойства планарности графов Кэли полугрупп, вполне достаточно исследовать основы эти графов.
Будем говорить, что полугруппа S допускает планарный граф Кэли, если для некоторого её подмножества X образующих элементов основа графа Cay{S,X) является планарным графом.
Заметим, что любая циклическая полугруппа допускает планарный граф Кэли. Например, конечная циклическая полугруппа типа (г, т), заданная копредставлением la аг+т=аҐ), имеет в качестве графа Кэли граф, изображенный нарис. 0.1.1; бесконечная циклическая полугруппа имеет граф Кэли, изображенный на рис. 0.1.2.
Условимся различать операции присоединения единицы и внешнего присоединения единицы к полугруппе S. В первом случае единица добавляем только в случае, когда она отсутствует в полугруппе S, и соответствующую полугруппу обозначаем как обычно через S]. Во втором случае единицу присоединяем всегда и полученную полугруппу будем обозначать через S+].
Аналогично, будем различать операции присоединения нуля и внешнего присоединения нуля к полугруппе S. В первом случае нуль добавляем только в случае, когда он отсутствует в полугруппе S, и соответствующую полугруппу обозначаем как обычно через S°. Во втором случае нуль присоединяем всегда и полученную полугруппу будем обозначать через S+0.
Под циклическим моноидом будем понимать любой гомоморфный образ свободного моноида с одним образующим. Очевидно, что любой цикли ческий моноид есть либо конечная циклическая группа, либо получен из циклической полугруппы внешним присоединением единицы.
Циклической полугруппой с нулем назовем любой гомоморфный образ свободной однопорожденной полугруппы с нулем. Очевидно, что любая циклическая полугруппа с нулем есть либо циклическая нильполугруппа, либо получена из циклической полугруппы внешним присоединением нуля.
Заметим, что любой циклический моноид и любая циклическая полугруппа с нулем допускают планарный граф Кэли. Ниже изображены графы Кэли только тех из них, которые не являются циклическими полугруппами:
Россыпью называется дизъюнктное семейство полугрупп. В терминах определяющих соотношений можно определить ряд известных теоретико- полугрупповых конструкций. Например, полугруппа S будет свободным произведением полугрупп {S,}lt, тогда и только тогда, когда {S,}ltl есть порождающая россыпь в S, и S может быть задана множеством определяющих соотношений, равным объединению множеств определяющих соотношений для каждой полугруппы Sr Если полугруппа S имеет порождающую россыпь {S,}iel и задана множеством определяющих соотношений, состоящим из определяющих соотношений каждой полугруппы Ss и соотношений, диктующих перестановочность любых двух элементов из различных полугрупп S, и S (i,j пробегают /), то S назовем коммутативно-свободным произведением полугрупп Sr Свободная коммутативная полугруппа разложима в коммутативно-свободное произведение бесконечных циклических полугрупп [46, с.69]. Понятно, как модифицировать определение коммутативно- свободного произведения для моноидов и полугрупп с нулем в соответствующих классах полугрупп. •
В ПЕРВОЙ ГЛАВЕ диссертации охарактеризованы полугруппы, являющиеся коммутативно-свободными произведениями циклических полугрупп (§1.1), циклических моноидов (§1.2) и циклических полугрупп с нулем (§1.3), допускающие планарный граф Кэли. При этом рассматриваются сначала случаи конечных полугрупп, а затем в качестве следствий получаем описания бесконечных полугрупп с указанным свойством.
Под множеством свободных образующих свободного коммутативного произведения циклических полугрупп [моноидов, полугрупп с нулем] мы понимаем множество полугрупповых образующих соответствующих циклических сомножителей.
Конечную полугруппу [моноид, полугруппу с нулем], являющуюся коммутативно-свободным произведением циклических полугрупп [моноидов, полугрупп с нулем], условимся называть конечной свободной коммутативной полугруппой [моноидом, полугруппой с нулем].
Основным результатом первого параграфа является
Теорема 1.1.1. Граф Кэли конечной свободной коммутативной полугруппы S относительно множества свободных образующих планарен тогда и только тогда, когда S задана копредставлением одного из следующих видов:
1) S = (а аГ+т = аг V где г и т -любые натуральные числа;
2) S = (a,b ab = ba,ar+m =ar ,bh+t =bh), где для натуральных чисел г, т, h, t выполняется одно из следующих ограничений:
a)m 2, t 2;
б) г = 1, /г = 1, t = 2; или г = \, А = 2, t = \; в)г = 1, /г = 1, т = 2;илиг = 2, h = \, т = \; г) г = 1, т = 1; или h = 1, t = 1;
3) S = la,b,c ab = ba,ac = ca,be = cb,a2 =a,b =b,c + =c ), где k и I - натуральные числа, причем l 2.
Заметим, что в каждом условии теоремы присутствуют бесконечные серии полугрупп. Это говорит о том, что допускающих планарный граф Кэли коммутативно-свободных произведений циклических полугрупп бесконечно много. Тем не менее, число образующих соответствующих полугрупп с пла-нарными графами Кэли в данном случае ограничено числом 3.
Прежде чем сформулировать аналогичный результат для бесконечного случая, заметим, что для бесконечной циклической полугруппы S можно записать копредставление S = (a аг+т =аг), где т = 0, по форме похожее на копредставление конечной циклической полугруппы.
Следствие 1.1.2. Бесконечная полугруппа S, являющаяся коммутативно-свободным произведением циклических полугрупп, имеет планарный граф Кэли относительно множества свободных образующих тогда и только тогда, когда S задана копредставлением одного из следующих видов:
1) S = (a J а = а), то есть S - бесконечная циклическая полугруппа;
2) S = (a, b ab = ba,b +t =b ), где h - любое натуральное число и t -неотрицательное целое число такое, что t 2;
3) S = (a, b,c ab = Ьа, ас = ca, bc = cb,a =a,b = b).
Заметим, что среди полугрупп бесконечной серии 2) содержится коммутативно-свободное произведение двух бесконечных циклических полугрупп, то есть свободная коммутативная 2-порожденная полугруппа. Из следствия 1.1.2 вытекает, что свободная коммутативная «-порожденная полугруппа при п 3 не допускает планарного графа Кэли.
Основным результатом второго параграфа является
Теорема 1.2.1. Граф Кэли конечного свободного коммутативного моноида S относительно множества свободных образующих планарен тогда и только тогда, когда S задан копредставлением одного из следующих видов:
1) S = (а ат = \), где т -любое натуральное число;
2.1) S = (а,Ъ ab = ba,ar+m =ar,b = 1), где для натуральных чисел г, т, t выполнено одно из следующих ограничений:
а)/ 2;
б) т 2, t 2;
2.2) S = (a,b ab = ba,am = \,bl =1), где m и t - натуральные числа, причем t 2;
3.\)S = (a,b,c\ab = ba,ac = ca,bc = cb,ar+m=ar,bh+t =b\ck =l), где для натуральных чисел г, т, h, t, к выполнено одно из следующих ограничений:
a) h = \, t = \, k = \;
6)т 2, t 2, k = \;
в) m 2, h = \, t = \, k = 2;
3.2) S = la, b,c ab = ba, ac = ca, be = cb, ar+m = ar, b2 = 1, c2 = 1V где r и m - натуральные числа, причем m 2;
3.3) S = (a,b,c ab = ba,ac = ca,be = cb,a2 =l,b2= 1,c2 = 1);
4) S = (a, b,c,d \ab = ba, ac = ca, ad = da, be = cb, bd = db, cd = dc, ar+m=ar,b =b,c =c,d = l), где rum- натуральные числа, причем m 2.
Используя этот результат, получаем:
Следствие 1.2.2. Бесконечный моноид S, являющийся коммутативно-свободным произведением циклических моноидов в классе всех моноидов, имеет планарный граф Кэли относительно множества свободных образующих тогда и только тогда, когда S. задан копредставлением одного из следующих видов:
1) S = (a, b ab = ba, bl = lV где t -любое натуральное число;
2.\)S = (a,b,c ab = ba,ac = ca,bc = cb,b -b,c = l)npuk 2;
2.2) S = (a,b,c ab = ba, ac = ca, be = cb,c = l);
2.3) S = (a,b,c ab = ba,ac = ca,bc = cb,b =1,c2 =\); V
3) S = [a, b,c,d \ab = ba, ac = ca, ad = da, be = cb, bd - db, cd = dc, b2=b,c2=c,d = \y
Основным результатом данного параграфа является
Теорема 1.3.1. Граф Кэли конечной свободной коммутативной полугруппы S с нулём 0 относительно множества свободных образующих пла-нарен тогда и только тогда, когда S задана копредставлением одного из следующих видов:
1) S = (а аг = 0), где г -любое натуральное число;
2) S = (a, b ab = ba,ar=0,b = 0), где г, h-любыенатуральные числа;
3) S = (a,b ab = ba, ar+m = ar, b =0), где r, m, h -натуральные числа, причем m 2, либо r = \ и h = l;
4) S = (a, b,c ab = ba, ac = ca, be = cb, a2 =a,b2= b, ck - 0), где k -любое натуральное число.
Для случая бесконечных полугрупп справедливо
Следствие 1.3.2. Бесконечная полугруппа S с нулём 0, являющаяся коммутативно-свободным произведением циклических полугрупп с нулем в классе всех полугрупп с нулем, имеет планарный граф Кэли относительно множества свободных образующих тогда и только тогда, когда S задана копредстав лением S = (а,Ь ab = ba,b =0) или S = (a,b,c ab = ba,b =b,c = 6) в клас се полугрупп с нулем, где h -любое натуральное число.
ВО ВТОРОЙ ГЛАВЕ характеризуются полугруппы, являющиеся прямыми произведениями циклических полугрупп (§2.1), моноидов (§2.2) и полугрупп с нулем (§2.3), допускающие планарные графы Кэли.
В первом параграфе этой главы получен критерий планарности графов Кэли прямых произведений циклических полугрупп. Так как граф Кэли конечной циклической полугруппы является планарным, то в дальнейшем предполагаем, что число сомножителей в рассматриваемых ниже прямых произведениях более одного.
Теорема 2.1.1. Конечная полугруппа S, являющаяся прямым произведением неодноэлементных циклических полугрупп, допускает планарныи граф Кэли тогда и только тогда, когда выполнено одно из условий:
1) S = (a ar+m = ar)x(b b +t =b ), где для натуральных чисел г, т, h, t выполняется одно из следующих ограничений:
1.1) г = 1, А = 1,НОД(ти,0 3; r = \,m = 2,t 3; 1.3) = 2, т = \, h A, t 3;
1.4) r = 2, т = \, h 5, t = \;
1.5) r = 3, m = \, h = 3, t = \;
2) S = (a ar+m = ar)x(b bh+t = Ьн)х(с ck+l =ck), где для натуральных чисел г, т, h, t, k, I выполняется одно из следующих ограничений:
2.1) г = 1, т = 2, h = \, t = 2, к = \, 1 = 2; 2.2)r = \,m = 2, h = 2, t = \, к = 2, / = 1;
2.3) г = 2, т = \, h = 2, t = \, к = 2, / 3; 2.4)r = 2, т = \, /2 = 2, t = \, к = 3, 1 = 1;
3) S = (а0 а[+т = 0/ П"=і(а/ ai+ =at ) г е дДЯ натуральных чисел гит выполняется одно из следующих ограничений:
3.1) = 1, т = 2;
3.2) г = 2, т 3;
3.3) г = 3, т = \.
В качестве расширения на бесконечный случай, сформулируем следующее представляющее самостоятельный интерес утверждение, при обосновании которого применяется предыдущая теорема.
Следствие 2.1.2. Граф Кэли бесконечной полугруппы S, являющейся прямым произведением конечного числа неодноэлементных циклических полугрупп, допускает плоскую укладку тогда и только тогда, когда S = la a3 =a)x(b\b = b).
В §2.2 второй главы найдены необходимые и достаточные условия планарности графов Кэли прямого произведения циклических моноидов.
Теорема 2.2.1. Конечный моноид S, являющийся прямым произведением неодноэлементных циклических моноидов, допускает планарный граф Кэли тогда и только тогда, когда выполняется одно из следующих условий:
1) S = (a ar+m = ar) xlb Ъ н =b ) , где для натуральных г, т, И, t и выполняется одно из следующих ограничений:
1.1) г = \, т = 2\
1.2) m 2,t 2\
1.3) r=l, т 2, t 2;
2) S = (a a =a)x(b b = b)x(c с+ =с ) , где і принимает указанные ниже значения, и для натуральных к, I выполняется одного из следующих ограничений .
2.1)/ = 1, / 2; 2.2)/ = +1, к = \, / 2;
3) S = (a al+m =al) xlb bhH =bh) , где т, h, t - натуральные числа, /є {1,+1} и выполняется одно из следующих ограничений:
3.1)/и = 1;
3.2)/ = 1,/2 = 1,/ = 2;
3.3) т = 2, h-\, / = 1;
3.4) /и = 2, А = 1, / = 2, / = +1.
4) S = (a0 йо+/"=ао) хПы(а ai =ai) г е w 2, п 2; или г = \, т = 1, п 3.
Эта теорема позволяет получить аналогичный результат для бесконечных моноидов.
Следствие 2.2.2. Граф Кэли бесконечного моноида S, являющегося прямым произведением конечного числа неодноэлементных циклических моноидов, допускает плоскую укладку тогда и только тогда, когда выполняется одно из условий:
2)S = (a 3)S = (a
1) S = (а ar+m =ar) x(b\b = b) , где для натуральных г, т выполняется одно из следующих ограничений: 1.1) г = \, т 2; 1.2)/и 2;
a3=a)x(b b3 =b)x(c c = c) ; a +m = a1 \ x(b b = b) , где натуральное m 2. В §2.3 второй главы получен критерий планарности графов Кэли прямого произведения циклических полугрупп с нулем.
Теорема 2.3.1. Конечная полугруппа S с нулем, являющаяся прямым произведением неодноэлементных циклических полугрупп с нулем, допускает планарный граф Кэли тогда и только тогда, когда выполняется одно из следующих условий: \) S = (a x(b b +l =b ) , где для натуральных чисел г, „г+т „г а =а т, h, t выполняется одно из следующих ограничений: 1.1) г = 2, т = \, h 5, t = \; 1.2) r = 3, m = l, h = 3, t = l; \.3)r = 2, m = \, h = l, t = 2; 2+1 „2 ai = ai где г - натуральное число, +o 2)S (a0\a =ar0)xUl(ai причем r 3; a2+l=a2)xlb b2+]=b2 +o 3.1)5 = ( 3.2) S = (a ar+m=ar) x(b b =b) , где г и m - натуральные числа, причем m 2\ A)S = (aQ ar0+l =aQjxYl"=](a; af =a{) , где п 2;или r = l, n 3. Эта теорема позволяет получить аналогичный результат для бесконечных полугрупп с нулем.
Следствие 2.3.2. Граф Кэли бесконечной полугруппы S с нулем, являющейся прямым произведением конечного числа неодноэлементных циклических полугрупп с нулем, допускает плоскую укладку тогда и только тогда, когда S = (а\а = а)+ x(bb2=b) .
Рис. 0.1.7. Полный пятиэлементный граф К5 могут быть получены из одного и того же графа подразбиением его ребер.
Для полугруппы, удовлетворяющей условиям соответствующего утверждения, строится плоская укладка её графа Кэли. Если полугруппа не удовлетворяет этим условиям, то основа её графа Кэли содержит подграф, либо гомеоморфный К5 или ЛГ33, либо стягиваемый к графу К5 или К32
Как видим, при исследовании вопроса планарности графов важную роль играют не планарные графы К5 или К33. С другой стороны, макси-мальными плоскими графами (графами, которые перестают быть плоскими при добавлении любого ребра) являются плоские триангуляции (графы, каждая грань которых - треугольник). Поэтому, при исследовании планарных графов Кэли конечных полугрупп возникает задача перечисления всех полу-. групп, графы Кэли которых являются таковыми с некоторой ориентации ребер.
В §3.1 ТРЕТЬЕЙ ГЛАВЫ решается задача о допустимости графов К3 3, К5 и плоских триангуляции в качестве графов Кэли конечных полугрупп.
Теорема 3.1.1. Если Cay{S,X) -граф Кэли конечной полугруппы S, то Cay{S,X):
1) не изоморфен полному двудольному графу К3 з с любой ориентацией и раскраской ребер;
2) изоморфен плоской триангуляции с единственной ориентацией ребер тогда и только тогда, когда S имеет копредставление S = (а а =а);
3) изоморфен полному графу К5 с единственной ориентацией ребер тогда и только тогда, когда S имеет копредставление
I О 1 О 7 1 О \
S = (a,b ab = ba,a = b -ab,a =ab ,b = a =a b ).
Заметим, что полугруппа S, указанная в условии 3) этой теоремы, на самом деле является циклической группой порядка 5 (при выборе одного образующего она имеет копредставление S = (a а6 = а)) и поэтому допускает планарный граф Кэли.
Данное замечание иллюстрирует известный факт, что свойство планар-ности графа Кэли полугруппы существенно зависит от выбора множества образующих. В связи с этим естественно рассматривать графы относительно минимального по включению множества образующих.
В §3.2 третьей главы изучается класс полугрупп, совпадающих с любым своим минимальным множеством образующих. Нетрудно показать, что этот класс совпадает с классом всех рассыпчатых полугрупп, то есть таких полугрупп S, в которых для любых элементов a, b из S выполняется ab = a или ab = b. Известно, что любая рассыпчатая полугруппа является ординальной суммой сингулярных полугрупп [46,с.50]. Напомним, что ординальной суммой попарно непересекающихся полугрупп Se, где е пробегает цепь Р, называется полугруппа S = {J№l,Se, в которой при e f для любых aeSc и beSf действует правило умножения a-b = b-a = a. Полугруппа называется сингулярной, если она является полугруппой левых или правых нулей.
Заключительным результатом последней главы является
Теорема 3.2.1. Пусть S -рассыпчатая полугруппа и S = (J 5,, - соответствующая ординальная сумма сингулярных полугрупп. Тогда S допускает планарный граф Кэли, если и только если выполняется одно из следующих условий: \)\Р\ = \ и \S 5, если S - полугруппа правых нулей;
2) \P\ = 2 и выполнено одно из условий:
а) обе компоненты - полугруппы правых нулей и р 5;
б) только одна из компонент Se является полугруппой правых нулей и \Se\ 3,a другая компонента содержит менее трех элементов (при \Se\ = 3);
в) обе компоненты - полугруппы левых нулей, и одна из них содерэ/сит менее трех элементов;
3) Р = 3 и выполнено одно из условий:,
а) все компоненты - полугруппы правых нулей и \S\ 5;
б) две из компонент содержат по одному элементу, а третья компонента - полугруппа левых нулей;
в) все компоненты являются полугруппами левых нулей и \S\ 5 или \Se\ = 2 для любого ееР;
4)Р = 4 u\S\ 5.
Автор выражает глубокую благодарность своему научному руководителю профессору Леониду Матвеевичу Мартынову за постановку задач, полезные обсуждения результатов и постоянное внимание к работе.
Коммутативно-свободные произведения циклических моноидов
Заметим, что в каждом условии теоремы 1.1.1 присутствуют бесконечные серии полугрупп. Это говорит о том, что допускающих планарный граф Кэли коммутативно-свободных произведений циклических полугрупп, бесконечно много. Тем не менее, число образующих таких полугрупп, в данном случае ограничено числом 3.
В качестве следствия теоремы 1.1.1 получаем характеризацию бесконечных коммутативных полугрупп, являющихся коммутативно-свободным произведением циклических полугрупп и допускающих планарный граф Кэли. Заметим сначала, что для бесконечной циклической полугруппы S можно записать копредставление S = (а аг+т = аг\, где т - 0, по форме похожее на копредставление конечной циклической полугруппы. Напомним, что граф Кэли бесконечной циклической полугруппы, очевидно, имеет плоскую укладку, изображенную на рис. 0.1.2.
Понятно, что произвольная полугруппа S, являющаяся коммутативно-свободным произведением циклических полугрупп имеет копредставление вида S = (x ху = ух,хг +т =хг\хеХ,уеХ\, где тх 0, г, 0, X -не которое непустое множество образующих. Результат для бесконечного случая сформулирован в следующем утверждении.
Следствие 1.1.2. Бесконечная полугруппа S, являющаяся коммутативно-свободным произведением циклических полугрупп, имеет планарный граф Кэли относительно множества свободных образующих тогда и только тогда, когда S задана копредставлением одного из следующих видов: 1) S = (а а = а), то есть S - бесконечная циклическая полугруппа , 2) S = la,b\ ab = ba,bh+t =b V где h -любое натуральное число и t неотрицательное целое число такое, что t 2; 3) S = (а,Ъ,с ab = Ьа,ас = са,be = cb,а2 = я,b2 = о).
Схема доказательства данного утверждения аналогична доказательству рассмотренной выше теоремы 1.1.1. Пусть бесконечная полугруппа S, являющаяся коммутативно-свободным произведением циклических полугрупп, допускает планарный граф Кэли. Тогда среди образующих бесконечной полугруппы S, должен быть хотя бы один элемент бесконечного типа, ибо в противном случае, по теореме 1.1.1, полугруппа обязана содержать не боле трех образующих а, следовательно, конечна. Для графов Кэли полугрупп удовлетворяющих условиям следствию строится плоская укладка. В противном случае, в графе Кэли обнаруживается подграф, гомеоморфный графу К5 или К33 Действительно, легко понять какую именно плоскую укладку имеет граф Кэли полугруппы, для каждого из приведенных условий. В первом случае S является бесконечной циклической полугруппой, и для бесконечного числа её элементов можно распространить укладку изображенную на рис. 0.1.2. Во втором случае, при ґ = 0 полугруппа S представляет собой коммутативно-свободное произведение двух бесконечных циклических полугрупп, и плоская укладка соответствующего графа Кэли получается аналогично изображенной на рис. 1.1.1 для конечных полугрупп сколь угодно большего числа элементов. Причем элементы сомножителей располагаются бесконечно как по горизонтали, так и по вертикали. Если же вторым сомножителем является конечная полугруппа (при t = \ или t = 2), то бесконечное число вершин можно расположить горизонтально. Для трех образующих, единственно возможной полугруппой с неограниченным числом элементов представлена в третьем случае, и плоская укладка соответствующего ей графа Кэли представляет собой бесконечную модификацию изображенной на рис. 1.1.10. По теореме 1.1.1, иные полугруппы, допускающие планарный граф Кэли и содержащие сколь угодно большое число элементов, отсутствуют. Кроме того, не может присутствовать бесконечное число коммутативно-свободных конечных циклических сомножителей, поскольку, как показано в теореме 1.1.1, уже при числе сомножителей более трех полугруппа не допускает планарного графа Кэли.
Заметим, что среди полугрупп бесконечной серии 2) содержится коммутативно-свободное произведение двух бесконечных циклических полугрупп, то есть свободная коммутативная 2-порожденная полугруппа. Частным случаем этого следствия является
Следствие 1.1.3. Свободная коммутативная полугруппа, порожденная множеством X, при \Х\ 3 не допускает планарного графа Кэли. Для контраста отметим Предложение 1.1.4. Свободные произведения циклических полугрупп допускают планарный граф Кэли для любого числа сомножителей любых типов. Для обоснования этого утверждения на рис. 1.1.13 приведём фрагмент плоской укладки графа Кэли свободного произведения п циклических полугрупп, состоящего из п связных компонент.
Коммутативно-свободные произведения циклических полугрупп с нулем
В третьем параграфе описываются все конечные свободные коммутативные полугруппы с нулём, графы Кэли которых являются планарными.
Напомним, что мы условились во введении различать операции присоединения нуля и операции внешнего присоединения нуля к полугруппе S. В первом случае нуль добавляем только в случае, когда он отсутствует в полугруппе S, и соответствующую полугруппу обозначаем как обычно через S . Во втором случае нуль присоединяем всегда и полученную полугруппу будем обозначать через S+0.
Внешнее присоединение нуля происходит следующим способом: присоединяем к полугруппе S новый элемент 0 и доопределяем операцию на множестве S и {0}, полагая 0-0 = 0-x = x-0 = 0 для любого xeS.
Под циклической полугруппой с нулем понимается любой гомоморфный образ свободной однопорожденной полугруппы с нулем. Очевидно, что любая циклическая полугруппа с нулем изоморфна либо циклической ниль-полугруппе, либо получена из циклической полугруппы внешним присоединением нуля. Во введении отмечалось, что граф Кэли циклической полугруппы с нулем является планарным, его плоская укладка изображена на рис.0.1.5 и рис. 0.1.6. Конечная полугруппа с нулем называется свободной коммутативной, если она является коммутативно-свободным произведением циклических полугрупп с нулем.
Легко понять, что конечная свободная коммутативная полугруппа с ну лем имеет в классе коммутативных полугрупп с нулем копредставление вида S = (aua2,...,an arj =0, ар+т =a[l,iel,jеЛ, где /иУ = 1;и, /nJ = 0, JФ0. Заметим, что соотношение вида aj = 0 эквивалентно со-отношениям вида: aj =а!\ ака/ =а/ для любого к el, п. Граф Кэли будем рассматривать относительно множества образующих, указанных в ко-представлении; понятно, что это множество является множеством свободных образующих полугруппы S.
Теорема 1.3.1. Граф Кэли конечной свободной коммутативной полугруппы S с нулём 0 относительно множества свободных образующих пла-нарен тогда и только тогда, когда S задана копредставлением одного из следующих видов: 1) S = (а аг = 0), где г -любое натуральное число; 2) S = (a,b ab = ba,ar =0,b = О), где г, h-любые натуральные числа; 3) S = (a,b ab = ba,ar+m -ar,b =0), где r, m, h -натуральные числа, причем т 2,либо г = \ и h = \; 4) S = (a,b,c ab = ba,ac = ca,bc = cb,a2 =a,b2 =b,ck =0), где k любое натуральное число.
Доказательство. Доказательство проводится по схеме, аналогичной доказательству предыдущей теоремы.
1) Граф Кэли полугруппы S = (a аг =0), где г 1, содержащий г вершин, по числу элементов полугруппы, является планарным. Его укладка на плоскости близка к изображенной на рис. 0.1.1 с единственным отличием в том, что агА соединена с 0, и вершины аг,...,аг+т ] отсутствуют (цикл заменяется петлёй).
2) С графом Кэли полугруппы S = (a,b ab = ba, ar = 0, b =0j, где r 1, h 1, аналогичная ситуация. В этом случае его плоская укладка содержит подграф графа, изображенного на рис. 1.1.1. с вершинами, соответствующими элементам, содержащим а и b в степенях, не превышающих (г -1) и (т -1). Кроме того, она содержит вершину 0, соединенную ребрами с элементами вида ar ]b и a bh x, где / h и j r.
3) Докажем что граф Кэли полугруппы S имеющей копредставление (a, b ab = ba, ar+m = ar, b - 0) планарен тогда и только тогда, когда: г 1, т 2, h \ или г = 1,т 1,/г = 1.
Достаточность указанных ограничений на г, h и т для планарности доказывается приведением плоской укладки графа Кэли. Полугруппа S содержит {{r + m)-h) элементов, следовательно, в каждом из указанных случаев граф имеет {{г + m)-h) вершин. Расположим горизонтально элементы полугруппы, полученные при умножении на образующий элемент а, вертикально - на Ь. Как видно по рис. 1.3.1, при выполнении выше перечисленных ограничений на показатели степеней образующих элементов, ребра графа Кэли не пересекаются. Получили плоскую укладку графа.
Для доказательства необходимости ограничений, воспользуемся законом контрапозиции. Покажем, что если не выполняются условия: r \, т 2, h \ или r = l, т \, h = 1, то граф Кэли полугруппы S =-{a,b ab = ba,ar+m =a\bh =0 не является планарным.
Выполнив преобразования, получаем: -i([(r l)A(w 2)A(/? l)]v[(r = l)A(m l)A(/2 = l)]) = = (m 2)A[(r l)v(/z l)] Таким образом: если т 2, а также г 1 или h 1 то граф не является планарным, так как в этих случаях граф Кэли имеет вид, указанный на рис. 1.3.1, и содержит подграф, стягиваемый к графу К5.
Прямые произведения циклических моноидов
Основным результатом данного параграфа является Теорема 2.2.1. Конечный моноид S, являющийся прямым произведением неодноэлементных циклических моноидов, допускает планарный граф Кэли тогда и только тогда, когда выполняется одно из следующих условий: 1)5 = (a ar+m=ar) xlb b+t =b ) , где для натуральных r, m, h, t и выполняется одно из следующих ограничений: 1.1) г = 1, т = 2; \2)т 2, t 2; 1.3) г = 1, т 2, t 2; 2) S = (a a =a)x(b b =b)x(c с =с \ , где і принимает ука занные ниже значения, и для натуральных k, I выполняется одного из сле дующих ограничений: 2.1)/ = 1,/ 2; 2.2)/ = +1, к = \, / 2; 3) S = (a a]+m=al\ x(b bh+t =bj, где т, h, t - натуральные числа, /є {1,+1} и выполняется одно из следующих ограничений: 3.1) /и = 1; 3.2)/ = 1, h = \, t = 2; 3.3) т = 2, h = \, / = 1; 3.4) т = 2, h = l, / = 2, / = +1. 4) S = (a0 а[+т =arQ\ П/=і\а/ af=ai) где т 2 п 2; или г = \, т = \, п 3. Доказательство. Рассмотрим каждый из возможных вариантов.
1) Достаточность указанных ограничений на г, т, h и / для планарно 73 сти доказывается приведением плоской укладки графа Кэли.
Уже известен результат для случая, когда каждый из сомножителей является циклической группой. Поскольку, как показано в [10, с.5], нециклическая абелева группа А допускает плоский граф Кэли в том и только в том случае, когда А = С2хС2т, или А = С2хС2хС2 .Первый случай присутствует
в условии 1.1 при h = 1, а второй присутствует в условии 2 при к = 1 и 1 = 2 рассматриваемой теоремы. Более того, прямым произведением циклических групп взаимно простых порядков является циклическая группа, очевидно допускающая планарный граф Кэли.
Таким образом, будем рассматривать возможные варианты, при которых среди сомножителей присутствуют полугруппы с присоединенной внешним образом единицей.
Плоская укладка графа Кэли, для двух сомножителей, каждый из которых является полугруппой удовлетворяющей условию 1.2 теоремы, приведена на рис. 2.2.1, с указанием соответствующего множества образующих элементов приводящего к данному графу.
Последним вариантом выбора двух сомножителей является случай, при котором лишь один из сомножителей является группой. При этом плоские укладки графов Кэли прямых произведений удовлетворяющих условиям 1.1, 1.3 изображены соответственно на рис. 2.2.2 и рис. 2.2.3. с указанием выбранных множеств образующих элементов приводящих к такому графу Кэли.
Покажем, что во всех остальных случаях граф Кэли прямого произве дения двух циклических полугрупп не имеет плоской укладки, поскольку его основа содержит подграф гомеоморфный графу Къъ, при любом выборе множества образующих.
Для доказательства необходимости ограничений, воспользуемся законом контрапозиции и покажем, что если не выполняется ни одно из условий теоремы для двух сомножителей, то граф Кэли не является планарным. Дополнив условия теоремы для двух сомножителей, возможностью одноэлементного сомножителя и симметричные варианты, проведем преобразования на языке алгебры логики и получим следующие серии ограничений: -. [((г=1) л (/2=1) л (НОД(/и,0=2)) v (г 1) л (т 2) л (А 1) л (t 2)) v v ((г=1) л (ти=2) л {h 1) л (t 1)) v ((А=1) л (t=2) л (г 1) л (m 1)) v v ((г=1) л (т 2) л {h 1) л (t 2)) v ((Л=1) л (t 2) л (г 1) л (т 2)) v v ((г=1) л (т=1) л (h 1) л (/ 1)) v ((/7=1) л (t=\) л (г 1) л (т 1))] = (1) = ((г=1) л (w 3) л (А=1) л (f 3) л (НОД(т,0 Ф2))\/ (2)v((r 2)A(m 3)A(h 2)A(t l))v((h 2)A(t 3)A(r 2)A(m l))v (3)v((r=l)A(m 3)A(h 2)A(t 3))v((h=l)A(t 3)A(r 2)A(m 3))
Прямое произведение двух групп, удовлетворяющих условию (1), не допускает плоской укладки по известному результату для групп.
Подграфы ориентированных основ графов Кэли прямых произведений полугрупп удовлетворяющих условиям (2) и (3), гомеоморфные графу Кгг, изображены соответственно на рис. 2.2.4 и рис. 2.2.5. " ґ Г+тА.і2 ісҐтА;Ь2) {d-\e) Ґ\Ь2)(сГп «л\,ь (d;b2) (сҐт-\Ь) Рис. 2,2.4. Подграф ориентированной основы графа Кэли прямого = 6") і h+t произведения моноидов А=-(а\ аг+т =я/ и B = (b npur 2, т 3, h 2, t \. При этом следует учитывать, что для прямого произведения двух циклических моноидов A = (a ar+m =ar) , B-{b bh+t =bh) в каждом из возможных множеств образующих содержатся очевидные неразложимые элементы, относительно которых и рассматривался граф Кэли.
Как уже отмечалось ранее, при изображении графов в общем виде, например на рис. 2.2.5, для удобства восприятия, пунктирными линиями или стрелками обозначены легковосстановимые цепи из одинаково помеченных ребер, соединяющие соответствующие вершины.
2) Перейдем к описанию прямых произведений трех циклических моноидов с планарными графами Кэли. Следует учитывать тот факт, что попарно каждый из трех сомножителей должен удовлетворять условиям планарно-сти графа Кэли прямого произведения двух полугрупп. Итак, если все три сомножителя полугруппы S группового типа, то для планарности соответствующего графа Кэли, по известному результату для групп, необходимо и достаточно выполнение условия S = C2xC2xC2. Рассмотрим случай, при котором только один из сомножителей является полугруппой с присоединенной единицей. Плоская укладка графа Кэли такого произведения приведена на рис. 2.2.6, с указанием соответствующего множества образующих.
Если каждый из сомножителей является полугруппой с присоединенной единицей, то, опираясь на условия планарности графа Кэли, полученные для свободного произведения циклических полугрупп, заключаем, что два из трех сомножителей обязаны являться идемпотентами. Поэтому сразу переходим к рассмотрению смешанного прямого произведения, то есть среди сомножителей должны присутствовать как группы, так и полугруппы с присоединенной единицей.
Если два из трех сомножителей являются группами, не удовлетворяющими условию теоремы, то соответствующие графы Кэли содержат подграфы изображенные на рис. 2.2.7, рис. 2.2.8, гомеоморфный графу К3 3, следовательно, не являются планарными.
Рассыпчатые полугруппы, допускающие планарный граф Кэли
Рассмотрим теперь случай, когда среди сомножителей прямого произведения присутствуют полугруппа, полученная внешним присоединением нуля к циклической полугруппе. +0 e "i)+W+o , полученной внеш Граф Кэли полугруппы А = (а ним присоединением нуля к циклической полугруппе, изображен на рис.2.3.8. Заметим, что его основа и множество образующих идентичны основе и множеству образующих графа Кэли полугруппы B = (b br+ =br) , изображенного на рис. 2.3.9. Таким образом, граф Кэли циклической полугруппы с нулем, среди сомножителей которой присутствует полугруппа В, будет допускать плоскую укладку тогда и только тогда, когда плоскую укладку допускает граф Кэли полугруппы, полученной заменой В на А.
Для сомножителей с присоединенным нулем, среди серии условий 1) и 2) теоремы 2.3.1, таким ограничениям удовлетворяет только условие 1.3. Соответствующая циклическая полугруппа с нулем, среди сомножителей которой присутствует циклическая полугруппа с нулем, присоединенным внешним образом, имеет вид, указанный в условиях 3) данной теоремы. + Для условия 4) проводятся аналогичные рассуждения. Таким образом, получили критерий планарности графа Кэли прямого произведения циклических полугрупп с нулем. Теорема 2.3.1 доказана. Эта теорема позволяет получить аналогичный результат для бесконечных полугрупп с нулем.
Следствие 2.3.2. Граф Кэли бесконечной полугруппы S с нулем, являющейся прямым произведением конечного числа неодноэлементных циклических полугрупп с нулем, допускает плоскую укладку тогда и только тогда, когда S = (а\а = a) x(bb2=b) .
Анализ ограничений типов сомножителей в теореме 2.3.1 показывает, что среди полугрупп, являющихся прямым произведением циклических полугрупп с нулем и допускающих планарные графы Кэли, может содержать среди сомножителей полугруппы сколь угодно большого числа элементов лишь в случае 3.2. Действительно, в условии 1.1, теоремы 2.3.1, заданы двухэлементная и не более четырехэлементная полугруппы; в условии 1.2 оба сомножителя трехэлементные; а в 1.3 присутствуют лишь двух- и трехэлементные сомножители. Что касается условия 2 теоремы 2.3.1, то каждый из конечного числа представленных сомножителей содержит не более трех элементов. Более того, прямые произведения иных полугрупп с нулем не допускают планарного графа Кэли.
В заключительной главе диссертации решены некоторые задачи общей теории графов Кэли, а именно, задача о допустимости графов Кгг, К5 и плоских триангуляции в качестве графов Кэли конечных полугрупп (3.1) и задача об описании рассыпчатых полугрупп, допускающих планарные графы Кэли (3.2).
В теории графов существует особый класс графов - плоские триангуляции (графы, каждая грань которых - треугольник). Это максимальные плоские графы (графы, которые перестают быть плоскими при добавлении любого ребра), т.е. всякий плоский граф является остовым подграфом плоской триангуляции. Гранью плоского графа называется максимальное по включению множество точек плоскости, каждая пара которых может быть соединена жордановой кривой, не пересекающей ребра графа. Границей грани считают множество вершин и ребер, принадлежащих этой грани. Грань плоского графа, ограниченная треугольником (3-циклом), также называется треугольником.
Таким образом, при исследовании планарных графов Кэли конечных полугрупп возникает задача перечисления всех полугрупп, графы Кэли которых являются плоскими триангуляциями с некоторой ориентацией ребер.
С появления электронных вычислительных машин началось их приме 90 нение в математических исследованиях. В данном параграфе автор предоставляет результаты, в большей мере полученные с использованием ЭВМ. В теореме 3.1.1 указываются все возможные полугруппы, графы Кэли которых изоморфны графам плоской триангуляции, полному графу К5 или полному двудольному графу Кгі с некоторой ориентацией и раскраской ребер. Теорема 3.1.1. Если Cay(S,E) - граф Кэли конечной полугруппы S, то Cay(S,E): 1) не изоморфен полному двудольному графу К33 с любой ориентацией и раскраской (разметкой) ребер; 2) изоморфен плоской триангуляции с единственной ориентацией ребер тогда и только тогда, когда S имеет копредставление S = (a а =а); 3) изоморфен полному графу К5 с единственной ориентацией ребер тогда и только тогда, когда S имеет копредставление S = (a,b ab = ba,a = b =а b,a =ab ,b = a =a b ).
Доказательство. Для обоснования данного утверждения построим компьютерную модель исследуемых графов, по графам при помощи ЭВМ восстановим соответствующие им группоиды, а в завершение проверим выполнение тождества ассоциативности на полученных множествах.
