О коммутативных полугруппах с планарными графами Кэли тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

На правах рукописи

Соломатин Денис Владимирович

О КОММУТАТИВНЫХ ПОЛУГРУППАХ С ПЛАНАРНЫМИ ГРАФАМИ КЭЛИ

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации, на соискание ученой степени кандидата физико-математических наук

Омск-2006

Работа выполнена на кафедре алгебры ГОУ ВПО «Омский государственный педагогический университет»

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

Официальные оппоненты:

доктор физико-математических наук, профессор

Мартынов Леонид Матвеевич

доктор физико-математических наук, профессор

Баранский Виталий Анатольевич

Ведущая организация:

кандидат физико-математических наук, доцент

Беленкова Жанна Тадеушевна

Институт математики им. С.Л.Соболева СО РАН.

Защита диссертации состоится 26 сентября 2006 года в 15:30 на заседании диссертационного совета К 212.179.01 при Омском государственном университете им. Ф.М.Достоевского по адресу: 644077, г.Омск, пр.Мира, 55а.

С диссертацией можно ознакомиться в библиотеке Омского государственного университета.

Автореферат разослан «_» августа 2006 г.

Ученый секретарь диссертационного совета кандидат физ.-мат. наук, доцент

М.А. Шевелин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Граф Кэли первоначально рассматривали как объект, связанный с группой. Идею применения графов в представлении групп предложил английский математик Артур Кэли (1821-1895). Графом Кэли группы является граф, передающий структуру (связь элементов) группы. Это основное понятие в комбина-. торной и геометрической теории групп. Геометрическая и комбинаторная теории групп - две смежные отрасли математики, которые изучают группы. Геометрическая теория групп использует топологические и геометрические методы для изучения группы; основной идеей является получение информации о группе, анализируя её влияние на топологические аспекты. ; ;

. - Изучению графов Кэли групп посвящено много работ. При этом графы Кэли применяют не только для получения классификаций в теории групп. Например, Оливер и Сильва [13] использовали их для построения интересных графов с хорошими свойствами. В том же ракурсе графы Кэли исследовал Бите [б]. .

Понятие графа Кэли для полугрупп ввел в рассмотрение Б.Зелинка [15]. Такой граф является ориентированным графом без петель и многократных ребер. Важность этого понятия для комбинаторной теории полугрупп продемонстрирована в работах С.В.Марголиса и Дж.К.Микина [12], а также Б.Штейнберга [14]. В частности, первые два автора рассматривали Л-унитарные инверсные моноиды и графы Кэли в представлениях полугрупп.

М.-К.Хейдеманн [7] сопоставляет графы Кэли и коммуникационные сети. Активно занимается исследованием графов Кэли АВ.Келарев, изучая неориентированные графы Кэли [8], а также полные и двудольные графы Кэли совместно с С.Дж.Квином [11]. Эти же авторы [10] изучали группы и полугруппы, удовлетворяющие некоторым комбинаторным свойствам, определенным в терминах графов Кэли. В частности, они установили, что эти свойства приводят к новым связям между графом, группой и теоретико-полугрупповыми методами. Кроме того, A.B.Келарев совместно с К.Е.Прогом [9] .изучали транзитивные графы Кэли групп й полугрупп.

■ . Что касается важного свойства планарности графа, то оно изучалось в основном для групп. Описание конечных групп, допускающих плоские графы Кэли, получили Х.Цшпанг, Э.Фогт, Х.-Д.Колдевай [4].

Изучением возможностей, при которых одна ита же группа обладает неизоморфными плоскими графами Кэли, и изучением неизоморфных групп, допускающих изоморфные графы Кэли, занималась Ж.Т.Беленкова [1].

Исследование графов: Кэли групп проводили В.А.Романьков и Ж.Т.Беленкова [3]. Ими описаны все возможные варианты выбора групп и их порождающих множеств, приводящие к регулярным замощениям как графам

Кэли. Проведен полный и:детальный -.анализ групп, допускающих в качестве графа Кэли регулярное замощение плоскости. Кроме того. приведены некото. рые общие свойства плоских графов,Кэли конечных групп [2]. В частности, .охарактеризованы нециклические абелевы группы, вложимые в плоскость. Приведены примеры неабелевых групп, невложим ых в плоскость. В работе [1] описаны все плоские графы Кэли группы S4. ■ - ., , ;

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

Основной целью данной работы является изучение конечных коммутативных полугрупп, допускающих планарные графы Кэли.' \V '

'" При этом мы не ограничиваемся рассмотрением только конечных коммутативных" полугрупп. Кроме того, исследуем некоторые задачи'для произвольных полугрупп. А именно, задачу о допустимости некоторых графов в качестве графов Кэли полугрупп и задачу характеризации рассыпчатых полугрупп, до-■ пускающих пленарный граф Кэли.

Научная новизна." Все основные, результаты диссертации являются новыми. Списание прямых произведений циклических полугрупп, допускающих пленарный граф" Кэли, является обобщением известного результата для' конечных абелевых групп [2]. . "... Основные результаты диссертации:

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

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

3) решена задача о допустимости плоских триашуляций, полного пяти-элементного графа К5 и полного двудольного графа Кзъ с некоторой ориентацией ребер в качестве графов Кэли полугрупп;

4) охарактеризованы рассыпчатые полугруппы с планарными графами

: Кэли.

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

Теоретическая и практическая значимость. Работа носит теоретический характер. Её результаты выделяют довольно широкие, классы полугрупп со свойством планарности графа Кэли и представляют научный интерес для специалистов в теории полугрупп. Результаты также могут быть использованы при чтении спецкурсов, подготовке учебных пособий и монографий. Авторские программы для ЭВМ могут найти применение для решения вопроса о допустимости некоторых графов в качестве графа Кэли конечной полугруппы, для выполнения проверки планарности конечных графов путем автоматического создания запросов в Maple, а также в учебном процессе для демонстрации возможностей языка Паскаль. 4

Апробация работы. Результаты диссертации докладывались на заседаниях алгебраических семинаров Омского университета и Омского педагогического университета; секции полугрупп Международной алгебраической конференции в Екатеринбурге, посвященной столетию со дня рождения П.Г.Конторовича и 70-летию Л.Н.Шеврина; алгебраической конференции «Мальцевские. чтения '05» в Новосибирске. Основные результаты диссертации отражены в девяти публикациях автора.

Объем и структура работы. Диссертация содержит 107 страниц, состоит из введения, трех глав, разбитых на восемь параграфов, списка литературы из 78 наименований. Текст диссертации снабжен 97 рисунками. В работе принята тройная нумерация утверждений и иллюстраций. Например, номер 3.2.1 означает, что данное утверждение или рисунок находится во втором параграфе третьей главы, и имеет порядковый номер 1. ■ • ■

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во ВВЕДЕНИИ обоснована актуальность исследования, сформулированы основные задачи и результаты, приведены необходимые определения и некоторые известные факты.

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

Граф Кэли группы й относительно её подмножества X состоит из множества вершин й и дуг от я к Для всех элементов ge й, хе X.

Как отмечалось ранее, аналогичную конструкцию на полугруппы перенес Б.Зелинка в [15], где графом Кэли Сау^.Т) полугруппы 5 относительно её подмножества Т называется граф с множеством вершин 5 и множеством дуг, состоящим из таких упорядоченных пар (х,_у), что х Ф у и х( = у для некоторого Т. Данный граф является ориентированным графом без петель и многократных ребер. Существуют и некоторые другие подходы к определению этого понятия, например, в [8] рассматриваются неориентированные графы Кэли.

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

Графом Кэли полугруппы 5 относительно множества X порождающих её элементов мы назьюаем ориентированный мультиграф Сау(3,Х) с помеченными дугами, состоящий из множества вершир 5 и множества помеченных дуг - всевозможных троек (а,х,Ь), где а,Ье хе. X и ах = Ь.

Такое определение графа Кэли аналогично определению графа Кэли, связанного с группой. Оно несколько отличается от введенного Б.Зелинка.

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

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

Основой графа Кэли мы называем обыкновенный граф, полученный из данного графа удалением петель, меток и заменой всех дуг, соединяющих две вершины одним ребром, соединяющим эти вершины. Ориентированной основой графа Кэли будем называть ориентированный граф, полученный из заданного удалением петель, меток, а также заменой всех одинаково направленных дуг одной дугой. Граф Кэли естественно назвать планарным, если его основа является планарным графом. Будем говорить, что полугруппа ¡5 допускает пла-нарный граф Кэли, если для некоторого её подмножества X образующих элементов основа графа Сау{Б,Х) является планарным графом.

Заметим, что любая циклическая полугруппа допускает пленарный граф Кэли. Например, конечная циклическая полугруппа типа (г,т)> заданная ко-

представлением (а | аг+т = , имеет в качестве графа Кэли граф, изображенный на рис. 1; бесконечная циклическая полугруппа имеет граф Кэли, изображенный на рис. 2.

: сГ^ ' ' '

у'сГг

Рис. I. Граф Кэли циклической полугруппы типа (г, т). а аг с?

Рис. 2. Граф Кэли бесконечной циклической полугруппы.

Условимся различать операции присоединения единицы [нуля] и внешнего присоединения единицы [нуля] к полугруппе 5. В первом случае единицу [нуль] будем добавлять только в случае, когда она [он] отсутствует в полугруппе 5, и соответствующую полугруппу обозначать, как обычно, через 51 [5'0]. . Во втором случае единицу [нуль] будем присоединять всегда и полученную полугруппу обозначать через 5+1 [5+0].

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

Заметим, что любой циклический моноид и любая циклическая полугруппа с нулем допускают пленарный граф Кэли. Ниже изображены графы Кэ-

ли только тех из них. которые не являются циклическими полугруппами:

Рас. 3. Граф Кэли конечного циклического моноида 5= ^д|аг+.т = а' ^ е а а1 с?

ог—о—

Рис. 4. Граф Кэли бесконечного циклического моноида.

а"""1

Рис. 5. Граф Кзпи конечной циклической полугруппы

с нулем.

г.-5 = (а|аг+га =

Рис. 6. Граф Кэли бесконечной циклической полугруппы с нулем.

В ПЕРВОЙ ГЛАВЕ диссертации охарактеризованы полугруппы, являющиеся коммутативно-свободными произведениями [5, с.69] циклических полугрупп (§1.1), циклических моноидов (§1.2) и циклических полугрупп с нулем (§1.3) с пленарными графами Кэли. При этом мы рассматриваем сначала случаи конечных полугрупп, а затем в качестве следствий получаем описания бесконечных полугрупп с указанным свойством.

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

Конечную полугруппу [моноид, полугруппу с нулем], являющуюся коммутативно-свободным произведением циклических полугрупп [моноидов, полугрупп с нулем], условимся называть конечной свободной коммутативной полугруппой [моноидом, полугруппой с нулем]. ■

Основным результатом первого параграфа является следующая

Теорема 1.1.1. Граф Кэли конечной свободной коммутативной полугруппы 5 относительно множества свободных образующих планарен тогда и только тогда, когда задана копредставлением одного из следующих видов:

1) Л' = (а | аг+т = где гит —любые натуральные числа;

2) &' = (а,Ь | аЬ = Ьа,аг+т =аг,ЬШ где для натуральных чисел г,

т. И, I выполняется одно из следующих ограничений:

а) т<. 2, г<2;.

б) г = 1, А = 1, 1=2;или г = \, Л = 2,/ = 1;

в) г= 1, А= I, т-2; или г-2, А= 1, т= 1;

г) г = 1, т = 1; или к = 1, / = 1;

3) Б = (а, Ь, с | аЬ = Ъа,ас = са, Ьс = сЬ, а2.= а, Ь2 - Ь,ск+1 = ск}, где к и I

-натуральные числа, причем 1< 2.

Заметим, что в каждом условии теоремы присутствуют бесконечные серии полугрупп. Тем не менее, число образующих соответствующих полугрупп с пленарными графами Кэли в данном случае ограничено числом 3.

Прежде чем сформулировать аналогичный результат для бесконечного случая, заметим, что для бесконечной циклической полугруппы можно записать копредставление = (а\^аг+т =ДГ)> гДе т = по форме похожее на ко-

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

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

1) Б = {а | а - а), то есть Б — бесконечная циклическая полугруппа,

2) 5 = (а, Ь | аЪ = Ьа, Ьк*' = где А — любое натуральное число м / — неотрицательное целое число такое, что / < 2;

3) &' = (а,Ь,с | аЬ = Ъа, ас = са, Ьс = сЬ, а2 = а, Ь2 = Ъ^.

Заметим, что среди полугрупп бесконечной серии 2) при г = 0 содержится коммутативно-свободное произведение двух бесконечных циклических полугрупп, то есть свободная коммутативная 2-порожденная полугруппа. Из следствия 1.1.2 вытекает, что свободная коммутативная «-порожденная полугруппа при п > 3 не допускает пленарного графа Кэли.

Основным результатом второго параграфа является следующая

Теорема 1.2.1. Граф Кэли конечного свободного коммутативного моноида Б относительно множества свободных образующих планарен тогда и только тогда, когда задан копредставлением одного из следующих видов:

1) 5 = (а | ат =1^, где т -любое натуральное число',

2.1) 51 = (а, Ь \аЬ = Ьа, апт = а', Ь* =1), где для натуральных чисел г,т,

( выполнено одно из следующих ограничений: а) / < 2; б) т<2, Г >2;

. 2.2) 6' = (а, ь\ аЬ = Ьа, ат = 1, Ь' = 1 где т и 7 - натуральные числа,

причем I < 2\ '

3.1) = | аЬ = Ьа,ас = са,Ьс = сЬ,аг+т = а',Ь>,+' = Ь'\ск =1), г<Э<;

для натуральных чисел г, т, /г, /г выполнено одно из следующих условий:

а") А = 1, / = Л =1; б) от52,/22, £=1; в) ш< 2, >г = 1.'/ = 1, к = 2;

3.2) 5' = (а, Ь, с | аЬ = Ьа, ас = са, Ьс - сЬ, аГ+т = аг,Ь2 =1, с2 =1 где г и т - натуральные числа, причем т < 2 ;

3.3) 3 = (а,Ь,с | аЬ = Ьа,ас = са,Ьс = сЬ,а2 =1,62 = 1,с2 =1^;

4) 5 = (а, Ь,с,с1 | аЬ = Ьа, ас = са, а/Л = ¿а, Ьс = сЬ, Ьс! = с!Ь, с<Л = с/с,

аг+т = г/, Ь2 = Ь,<? = с. <1 =1 где гит— натуральные числа, причем т <, 2.

Используя этот результат, получаем: .

Следствие 1.2.2. Бесконечный моноид являющийся коммутативно-свободным произведением циклических моноидов в классе всех моноидов, имеет планарный граф Кэли относительно множества свободных образующих тогда и только тогда, когда 5' задан копредставлением одного из следующих видов'. 1)5 = (а, Ъ | аЪ = Ьа, Ь' = 1 где I — любое натуральное число',

2.1) 5= (а, Ь, с | аЬ = Ьа, ас = са, Ьс = сЬ, Ь2 -Ъ,ск = при к <, 2;

2.2) .5" = (а, ¿>, с | аЬ = ¿>д, ас = са, Ьс = сЬ, с =1};

2.3) 5 = (а, Ь, с | аЬ = ¿а, яс = са, Ьс = сб, б2 = 1, с2 - ;

3)5 = (а, Ь,с,<Л | аЬ = Ьа, ас - са, ас1 = (¡а, Ьс = сЬ, Ьс1 = М, сс1 = <3с,

Ь2 =Ь,с2 =с,(1 = \у

Основным результатом заключительного параграфа первой главы является Теорема 1.3.1. Граф Кэли конечной свободной коммутативной полугруппы 5 с нулём 0 относительно множества свободных образующих планарен тогда и только тогда, когда Б задана копредставлением одного из следующих видов:

1) 5 = (а | <яг = о\, где г —любое натуральное число',

2) 6' = (а, Ь | аЬ = Ьа, аг = О, ЬИ = где г, И-любые натуральные числа',

3) 5 = (а, Ь | аЬ = Ьа, аг+т = аг ,ЬЬ = где г, т, И — натуральные числа, причем т<, 2, либо г = 1 и Л = 1;

4) 5 = (а, Ь, с | аЬ = Ьахас = са, Ьс = сЬ, а2 = а, Ь2 = Ь, ск = где к -

любое натуральное число.

Для случая бесконечных полугрупп справедливо

Следствие 1.3.2. Бесконечная полугруппа 5' с нулём О, являющаяся коммутативно-свободным произведением циклических полугрупп с нулем в классе всех полугрупп с нулем, имеет планарньш граф Кэли относительно множества свободных образующих тогда и только тогда, когда 5 задана копредставле-нием 5 = (а, Ь | аЪ = Ьа, ЬН = или 5 = (а, Ъ, с | аЬ = Ьа, Ь2 = Ь, с = в классе

полугрупп с нулем, где Л —любое натуральное число.

ВО ВТОЮЙ ГЛАВЕ характеризуются полугруппы, являющиеся прямыми произведениями циклических полугрупп, моноидов и полугрупп с нулем, допускающие пленарные графы Кэли.

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

Теорема 2.1.1. Конечная полугруппа &', являющаяся прямым произведением неодноэлементных ^циклических полугрупп, допускает планарньш граф Кэли тогда и только тогда, когда выполнено одно из условий:

1) | аг+т =яг^х (ъ | Ьш = где для натуральных чисел г, т. А,

Г выполняется одно из следующих ограничений:

1.1) г = 1, А = 1,#ОДО,0<3; 1.2) г = 1, т = 2, /<3;

1.3) г = 2, т = 1. А<4, *<3; 1.4) г= 2, т = 1, А<5, * =

1.5) г = 3, т = \, А=3, 1 = 1;

2) 5 2 (а | аг+т = | Ъш =Ьъ)х(с | см =ск), где для натуральных

чисел г, т,И, I, к, I выполняется одно из следующих ограничений:

2.1) г = 1, т=2, А —1, 1 = 2, к = 1, /=2;

2.2) г = 1, т=2, А = 2, /= I, к =2, / = 1;

2.3) г=2, т = \, А = 2, Г = 1, к = 2, /<3;

2.4) г=2, т = 1, А = 2. 1 = 1, к = 3. 1 = 1;

3) 5 = ^>о| ао+т = ао)х ПГ=1 | а|2+1 =а1~)> где для натуральных чисел

гит выполняется одно из следующих ограничений:

3.1) г = 1, л!=2; 3.2) г = 2, тис 3; 3.3) г = 3, т = 1.

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

Следствие 2.1.2. Граф Кэли бесконечной полугруппы 5, являющейся прямым произведением конечного чивла неодноэлементных циклических полугрупп, допускает ' плоскую укладку) тогда и только тогда, когда а3=а)х(Ь| Ь=Ь).

В §2.2 второй главы найдены необходимые и достаточные условия планарности графов Кэли прямого произведения циклических моноидов.

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

гда и только тогда, когда выполняется одно из следующих условий :

1) 5 £ (а | аг+т = х (Ь | ЬИ" = ¿''У, где для натуральных г, т. А, / и

выполняется одно из следующих ограничений:

1.1) г = 1, т = 2; ' 1.2) ?н<2, /<2; 1.3) г = 1, т > 2, 2;

2) .У = (а | й3 = а^х (ь | Л3 = Ь^х (с | ск+1 = , где I принимает указанные ниже значения, и для натуральных к, I выполняется одного ю следующих ограничений:

2.1)/ = 1,/<2; '2.2) /= +1, А = 1.

3) 5 = (а | ах*т = а1х (ь | Ъш = Ь^', где т, Л, I - натуральные числа, /е {1,+1} и выполняется одно из следующих ограничений:

3.1) ш = 1; . . 3.2)/ = 1, А=1. Г=2;

3.3) от = 2, А = 1, /=1; 3.4) т = 2, А=1, Г=2,/ = +1.

4) 5 = (а0| ао+т=0о)1хП"=]{^|й.2 =°.)+1. г<3е т<2, и< 2; или г = 1, »1 = 1, м<3.

Эта теорема позволяет получить результат для бесконечных моноидов.

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

1) | аг+т = х(Ь | Ь = Ь^, где для натуральных г, т выполняется одно из следующих ограничений:

1.1)г = 1, м>2; 1.2) т<,2\

2) £! = (а | аг = а)х(ь | Ь3 = б)х(с | с = с)';'

3) 3 = (а | а,+т =«1)+1 *{Ь \ Ь = Ь)\где т£2.

В §2.3 второй главы получены необходимые и достаточные условия пла-нарности графов Кэли прямого произведения циклических полугрупп с нулем.

Теорема 2.3.1. Конечная полугруппа Б. с нулем, являющаяся прямым произведением неодноэлементных циклических полугрупп с нулем, допускает пла-нарный граф Кэли тогда и только тогда, когда выполняется одно из следующих условий:

1) (а | аг+т = аг^ х (Ь | ЬЬ+> = , где для натуральных чисел г, т,

А, I выполняется одно га следующих ограничений:

1.1) г =2, т = \, А<5, /=1; 1.2) г = Ъ,т = \, А = 3, / = 1; 1.3) г=2, т = \, А = 1, / = 2; .

2) 5 = = ад^х | аг2+| = а?^, . где г — натуральное число, причем г<, 3;

3.2) S s(a j ar+m = ar^ x (b | b2 = bj , где г и m - натуральные числа, причем m<2 \ >

4) S = = af^x ]af = a,^ , где n < 2; или r = 1, «<3.

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

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

S = {a|a = a)°x^|ft2 = b^. ' •

При получении сформулированных выше результатов для обоснования планарности обыкновенного графа использовались различные критерии. Наиболее часто применялся хорошо известный критерий Понтрягина-Куратовского: обыкновенный граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных полному двудольному графу K2i или полному пятиэлементному графу . Кроме того, применялась теорема Вагнера: обыкновенный граф планарен тогда и только тогда, когда он не содержит подграфов, стягиваемых к графам К5 или К3}.

Для полугруппы, удовлетворяющей условиям соответствующего утверждения, строится плоская укладка её графа Кэли. Если полугруппа не удовлетворяет этим условиям, то основа её графа Кэли содержит подграф, либо го-меоморфный К5 или Кг 3, либо стягиваемый к графу К5 или К33 .

Как видим, при исследовании вопроса планарности графов важную роль играют не планарные графы К5 или К33. С другой стороны, максимальными

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

В ТРЕТЬЕЙ ГЛАВЕ, в частности, решена задача о допустимости графов К3 з , К5 и плоских триангуляций в качестве графов Кэли конечных полугрупп.

Теорема 3.1.1. Если Cay(S,X) — граф Кэли конечной полугруппы S, то Cay(S,X):

1) не изоморфен полному двудольному графу } с любой ориентацией и пометкой ребер,

2) изоморфен плоской триангуляции с единственной ориентацией ребер тогда и только тогда, когда S имеет копредставление S = (а | а4

3) изоморфен полному графу с единственной ориентацией ребер moil

гда • и - только тогда, .когда имеет копредставление

(■* - | » О *• ^ О т'' ■ "> \

а,Ь\аЬ = Ьа,а = Ь'—аЬ,а4=аЬ',Ь-а''=а"Ь'). 1

Заметим, что полугруппа , указанная в условии 3) этой теоремы, на самом деле является циклической группой порядка 5 (при выборе одного образующего она имеет копредставление-.5' = (а | а6 =а^) и поэтому допускает планарный

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

Изучению свойства планарности графов Кэли в классе Полугрупп, совпадающих с любым своим минимальным множеством Образующих посвящен §3.2. Нетрудно показать, что этот класс совпадает с классом всех рассыпчатых полугрупп, то есть таких полугрупп 51, в которых для любых элементов а, Ь из 5 выполняется аЬ = а или аЬ=Ь, Известно, что любая рассыпчатая полугруппа является ординальной суммой сингулярных полугрупп [5, с.50]. Напомним, что ординальной суммой попарно непересекающихся полугрупп где е пробегает цепь Р, называется полугруппа 8 = Це р^'е > в которой при е< /'для любых ае и Ь е действует правило умножения а-Ъ-Ъа = а. Полугруппа называется сингулярной, если она является полугруппой левых или правых нулей.

Заключительным результатом последней главы является

Теорема 3.2.1. Пусть Б — рассыпчатая полугруппа и = [Д^р^е ~ со~

ответствующая ординальная сумма сингулярных полугрупп. Тогда Б допускает планарный граф Кэли, если и только если выполняется одно из следующих условий:

1)|Р|='1 и < 5, если 5 —полугруппа правых нулей;

2)|Р|=2 и выполнено одно из условий: „ .

а) обе компоненты — полугруппы правых нулей и < 5;

б) только одна из компонент является полугруппой правых нулей и (¿Г, | < 3, а другая компонента содержит менее трех элементов (при | = 3);

в) обе компоненты — полугруппы левых нулей, и одна из них содержит менее трех элементов',

• 3) [Р| = 3 и выполнено одно из условий:

а) все компоненты — полугруппы правых нулей и ¡^ < 5;

б) две из компонент содержат по одному элементу, а третья компонента - полугруппа левых нулей;

в) все компоненты являются полугруппами левых нулей и :£ 5 или |£\,| = 2 для любого ее Р;

4) |Р| = 4 и

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

Литература

[1] Беленкова Ж.Т. Все плоские графы Кэли группы SA. Препринт. - Омск: ОмГУ, 1997.-12 с.

[2] Беленкова Ж.Т., Романьков В.А. Плоские графы Кэли конечных групп. Препринт. - Омск: ОмГУ, 1997. - 8 с.

[3] Беленкова Ж.Т., Романьков В.А. Регулярные графы Кэли. Сиб. мат. журн. . Депонирована в ВИНИТИ, 1997, №802-В97,-37 е., 57 рис.

[4] Цишанг X., Фогт Э., Колдевай Х.-Д. Поверхности и разрывные группы. — М.: Наука, 1988.-688 с.

[5] Шеврин Л.Н. Полугруппы // Общая алгебра / Под ред. Л.А. Скорнякова. -М.: Наука, 1991.-Т. 2.-Гл.IV-С. 11-191..

[6] Biggs N. Algebraic Graph Theory. - Cambridge University Press, 1994.

[7] Heydemann M.-C. Cayley graphs and interconnection networks. In G.Hahn and G.Sabidussi, editors, Graph Symmetry: Algebraic Methods and Applications. — Kluwer: Dordrecht, - 1997. - P. 167-224.

[8] Kelarev A.V. On undirected Cayley graphs // Australasian Journal Combinatorics. - 2002. - Vol. 25. - P. 73-78.

[9] Kelarev A.V., Praeger C.E. On transitive Cayley graphs of groups and semigroups U European Journal of Combinatorics. - 2003. - Vol. 24. - P. 59-72.

[10] Kelarev A.V., Quinn S.J. A Combinatorial Property and Cayley Graphs of Semigroups. // Semigroup Forum. - 2003. - Vol. 66. - P. 89-96.

[11] Kelarev A.V., Quinn S.J. On complete and bipartite Cayley graphs // European Journal of Combinatorics. - 2002.

[12] Margolis S.W., Meakin J.C. E-unitary inverse monoids and the Cayley graph of a group representation // Journal of Pure and Applied Algebra. - 1989. - Vol. 58. - P. 45-76.

[13] Oliveira A., Silva P. Inverse automata and monoids and the undecidability of the Cayley subgraph problem for groups // Glasg.MathJ. - 2000. - Vol. 42 (3). - P. 421-437..

[14] Steinberg B. Finite state automata: a geometric approach // Trans.Amer. Math. Soc. - 2001. - Vol. 353 (9) - P. 3409-3464.

[15] Zelinka B. Graphs of Semigroups // Casopis. Pest. Mat. - 1981. - Vol. 106. - P. 407-408. ;;

Работы автора по теме диссертации

[16] Соломатин Д.В. Конечные свободные коммутативные полугруппы с пленарными графами Кэли // Математика и информатика: наука и образование: Межвузовский сборник научных трудов: Ежегодник- Омск: Изд-во ОмГПУ. - 2003. - Вып. 3. - С. 32-38.

[17] Соломатин Д.В. О допустимости некоторых графов в качестве графов Кэли полугрупп // Математика и информатика: наука и образование: Межвузовский сборник научных трудов: Ежегодник. - Омск: Изд-во ОмГПУ. - 2004. - Вып. 4. - С. 32-34.

[18] Соломатин Д.В. Рассыпчатые полугруппы с планарными графами Кэли // Международная алгебраическая конференция в Екатеринбурге, посвященная столетию со дня рождения П.Г.Конторовича и 70-летию Л.Н.Шеврина (тезисы докладов). - Екатеринбург: Изд-во УрГУ, 2005. -С. 14-15.

[19] Соломатин Д.В. Конечные свободные коммутативные моноиды, допускающие планарный граф Кэли // Вестник Омского университета. - Омск: Изд-во ОмГУ. - 2005. - Вып. 4. - С. 36-38.

[20] Соломатин Д.В. Рассыпчатые полугруппы с планарными графами Кэли // Известия ВГПУ: Серия «Естественные и математические науки». -Волгоград: Изд-во «Перемена». - 2005. -№4 (13). - С. 27-31.

[21] Соломатин Д.В. Прямые произведения циклических моноидов и полугрупп с нулем, допускающие планарный граф Кэли. // Математика и информатика: наука и образование: Межвузовский сборник научных трудов: Ежегодник. - Омск: Изд-во ОмГПУ. - 2006. - Вып. б. - С. 51-63.

[22] Соломатин Д.В. Прямые произведения циклических полугрупп, допускающие планарный граф Кэли // Сибирские Электронные Математические Известия, http://semr.math.nsc.ru - 2006. - Т. 3. - С. 238-252.

[23] Соломатин Д.В. Определение планарности графов Кэли прямых произведений циклических полугрупп. Программа для ЭВМ, зарегистрированная в ОФАП №50200501609 от 24 ноября 2005 года.

[24] Соломатин Д.В. Проверка допустимости графа в качестве графа Кэли полугруппы. Программа для ЭВМ, зарегистрировать в ОФАП №50200600078 от 02 февраля 2006 года.

Лицензия ЛР Подписано в печать 10.08.06 Бумага офсетная Усл. печ. л. 1 Тираж 100 экз.

№020074

Формат бумаги 60 х 84 1/16.

Ризография

Уч.-изд. л. 1

Заказ 032

Издательство ОмГПУ: 644099, Омск, наб. Тухачевского, 14

Введение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Граф Кэли первоначально. рассматривали как объект, связанный с группой. Идею применения графов в представлении групп предложил английский математик Артур Кэли (1821-1895).

Изучению графов Кэли групп, посвящено много работ. При этом графы Кэли применяют не только для создания классификаций в теории групп. Например, Оливер и Сильва [64] использовали их для построения интересных графов с хорошими свойствами. В том же ракурсе графы Кэли исследовал Бигс [48].

Понятие графа Кэли для полугрупп ввел в рассмотрение Б.Зелинка [68]. Такой граф является ориентированным графом без петель и многократных ребер. Важность этого понятия для комбинаторной теории полугрупп продемонстрирована в работах С.В.Марголиса и Дж.К.Микина [60], а также Б.Штейнберга [66]. В частности, первые два автора рассматривали ^-унитарные инверсные моноиды и графы Кэли в представлениях полугрупп.

М.-К.Хейдеманн [52] сопоставляет графы Кэли и коммуникационные сети. Активно занимается исследованием графов Кэли А.В.Келарев, изучая неориентированные графы Кэли [57], а также полные и двудольные графы Кэли совместно с С.Дж.Квином [59]. Эти же авторы [56] изучали группы и полугруппы, удовлетворяющие некоторым комбинаторным свойствам, определенным в терминах графов Кэли. В частности, они установили, что эти свойства приводят к новым связям между графом, группой и теоретико-полугрупповыми методами. Кроме того, А.В.Келарев совместно с К.Е.Прогом изучали транзитивные графы Кэли групп и полугрупп [58].

Что касается важного свойства планарности графа, то оно изучалось в основном для групп. Описание конечных групп, допускающих плоские графы Кэли, получили Х.Цишанг, Э.Фогт, Х.-Д.Колдевай [45].

Изучением возможностей, при которых одна и та же группа обладает неизоморфными плоскими графами Кэли, и изучением неизоморфных групп, допускающих изоморфные графы Кэли, занималась Ж.Т.Беленкова [9].

Исследование графов Кэли групп проводили В.А.Романьков и Ж.Т.Беленкова [10], [11]. Ими описаны всевозможные варианты выбора групп и их порождающих множеств, приводящие к регулярным замощениям как графам Кэли. Проведен полный и детальный анализ групп, допускающих в качестве графа Кэли регулярное замощение плоскости. В результате подробных рассмотрений получили 6 групп с графом Кэли, составленным из треугольников, 16 групп с графом, составленным из квадратов, и 6 групп с графом из шестиугольников. С точностью до изоморфизма, полученные графы, исчерпывают 14 кристаллографических групп (из 17 возможных). Кроме того, приведены некоторые общие свойства плоских графов Кэли конечных групп. В частности, охарактеризованы нециклические абелевы группы, вло-жимые в плоскость. Приведены примеры неабелевых групп, невложимых в плоскость.

В работе [9] описаны все плоские графы Кэли группы Оказалось, что группа ^ обладает четырьмя плоскими графами Кэли, два из которых являются графами Кэли двух групп, не изоморфных группе S4. Кроме того, выписаны все минимальные по включению порождающие множества группы S4. Их 10 штук: 3 из них состоят из двух элементов, а 7 - из трех элементов.

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

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

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

Все основные результаты диссертации являются новыми. Описание прямых произведений циклических полугрупп, допускающих планарный граф Кэли, является обобщением известного результата для конечных абелевых групп [10].

Основные результаты диссертации:

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

2) найден критерий планарности графов Кэли прямых произведений циклических полугрупп, моноидов и полугрупп с нулем;

3) решена задача о допустимости плоских триангуляций, полного пяти-элементного графа К5 и полного двудольного графа АГ3 3 с некоторой ориентацией ребер в качестве графов Кэли полугрупп;

4) охарактеризованы рассыпчатые полугруппы с планарными графами

Кэли.

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

Работа носит теоретический характер. Её результаты выделяют довольно широкие классы полугрупп со свойством планарности графа Кэли и представляют научный интерес для специалистов в теории полугрупп. Результаты также могут быть использованы при чтении спецкурсов, подготовке учебных пособий и монографий. Авторские программы для ЭВМ могут найти применение для решения вопроса о допустимости некоторых графов в качестве графа Кэли конечной полугруппы, для выполнения проверки планарности конечных графов путем автоматического создания запросов в Maple, а также в учебном процессе для демонстрации возможностей языка Паскаль.

Результаты диссертации докладывались на заседаниях алгебраических семинаров Омского университета и Омского педагогического университета; секции полугрупп Международной алгебраической конференции в Екатеринбурге, посвященной столетию со дня рождения П.Г.Конторовича и 70-летию Л.Н.Шеврина; алгебраической конференции «Мальцевские чтения '05» в Новосибирске. Основные результаты диссертации отражены в девяти публикациях автора [70]—[78].

Диссертация содержит 107 страниц, состоит из введения, трех глав, разбитых на восемь параграфов, списка литературы из 78 наименований. Текст диссертации снабжен 97 рисунками.

1. Аксенов В.А. Об одном структурном свойстве плоских графов // Дискретный анализ и исследование операций. Сер. 1. - 2000. - Т. 7. - Вып. 4. -С. 5-19.

2. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов (учебное пособие для студентов). М.: Издательский отдел ф-та ВМиК МГУ, 2000.-58 с.

3. Алексеев В.Е., Кошелева Ю.В. О двух критериях планарности и внеш-непланарности // Комбинаторно-алгебраические методы в дискретной оптимизации. Нижний Новгород. - 1991. - С. 152-157.

4. Андерсон Д.Ф., Фразир А., Лаиве А., Ливингстон П. Граф делителей нуля коммутативного кольца II // Лекции по чистой и прикладной математике. Нью-Йорк: Марсель Деккер. - 2001. - Вып. 220. - С. 61-72.

5. Андерсон Д.Ф., Ливингстон П. Граф делителей нуля коммутативных колец // Алгебра. 1999. - Вып. 217. - С. 434-447.

6. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. - 288 с.

7. Ахо X. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

8. Багаев Г.Н. Предельные распределения метрических характеристик случайного неразложимого отображения // Комбинаторный и асимптотический анализ. Красноярск. - 1977. - С. 55-61.

9. Беленкова Ж.Т. Все плоские графы Кэли группы £4. Препринт. Омск:ОмГУ, 1997.- 12 с.

10. Беленкова Ж.Т., Романьков В.А. Плоские графы Кэли конечных групп. Препринт. Омск: ОмГУ, 1997. - 8 с.

11. Беленкова Ж.Т., Романьков В.А. Регулярные графы Кэли. Сибирский мат. журнал. Депонирована в ВИНИТИ, 1997. №802-В97, 37 е., 57 рис.

12. Березина JI.IO. Графы и их применение. М.: Просвещение, 1979.

13. Берж К. Теория графов и ее применения. М.: Просвещение, 1962.

14. Бобрикова JT.H. Тождественное включение конечных моногенных полугрупп; О максимальном количестве подполугрупп конечных полугрупп; Строение конечных полугрупп, наиболее богатых подполугруппами. // Современная алгебра.-1998.-Вып. 3,-С. 8-10,11-13,14-18.

15. Бородин Д.В. Строение и раскраска плоских графов (01.01.09) / Рас. АН., Сиб. Отделение, ин-т математики. Новосибирск, 1994. 23 с.

16. Воблый В.А. О перечислении помеченных связных гомеоморфно несводимых графов // Мат. заметки. 1991. - Т.49. Вып. 3. - С. 12-22.

17. ДэМайер Ф., Шнейдер К. Автоморфизмы и граф делителей нуля коммутативных колец // Международный журнал по коммутативным кольцам (выступление).

18. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985.

19. Емеличев В. А., Мельников О.И., Сараванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. - С. 150-187.

20. Живкова О., Живков Д., Зверович И.Э. Планарные расщепляемые последовательности и планарные разложимые графы // Докл. АН БССР. -1987.-Т.31. Вып. 10.-С. 881-883.

21. Захарова JI.E. Алгоритмы дискретной математики: Учебное пособие. -Моск. гос. ин-т электроники и математики. М., 2002. - 120 с.

22. Зыков А.А. О существовании плоской прямоугольной укладки планар-ного графа: Теория конечных графов. Новосибирск: Наука, 1969.

23. Зыков А.А. Основы теории графов. М.: Наука. Гл.ред.физ.-мат.лит., 1987.-384 с.

24. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. М.: Лаборатория Базовых Знаний, 2003. - 288 с.

25. Иорданский М.А. Функциональный подход к представлению графов // Докл. Рас.АН. 1997. - Т.353. Вып. 3 - С. 303-305.

26. Кларнер А. Математический цветник; Пер. с англ. Данилова Ю.А.; Под ред., с предисл. и прилож. И.М. Яглома. М.: Мир, 1983. - 494 с.

27. Клиффорд А., Престон Г. Алгебраическая теория полугрупп. — Т. 1. Перевод с английского В.А.Баранский и В.Г. Житомирский под редакцией Л.Н.Шеврина. М.: Мир, 1972. - с. 286.

28. Колчин В.Ф. Случайные графы / В.1. М.: Физматлит, 2000. - 256 с.

29. Липский В. Комбинаторика для программистов: Пер. с польск. М.: Мир, 1988.-213 с.

30. Ляпин Е.С. Полугруппы. М.: Государственное Издательство Физико-математической литературы, 1960. - 592с.

31. Новиков Ф.А. Дискретная математика для программистов СПб: Питер, 2000.-304 с.

32. Орлова Г.И. Три метода решения задачи о максимальном разрезе непла-нарного графа // Изв. АН СССР. Техн. кибернетика. 1988. - Вып. 6. -С. 186-188.

33. Орэ О. Теория графов / Пер. с англ. И.Н. Врублевской; Под ред. Н.Н. Воробьева 2-е издание, стереотип. - М.: Наука, 1980. - 336 с.

34. Петренко А.И., Тетельбаум А.Я., Шрамченко Б.Л. Алгоритм построения плоской укладки планарного графа: Автоматизация конструирования электронной аппаратуры (топологический подход). Киев: Вища школа, 1980.

35. Петров А.А. О классах полугрупп, разложимых в связку // Математический анализ. Вопросы теории и методики преподавания математики. -СПб.- 1993.-С. 43-48.

36. Полесский В.П. Оценки вероятности связности случайного графа // Проблемы передачи информации. 1990. - Т. 26. Вып. 1. - С. 90-98.

37. Полякова О.П. Поведение функции неплотности при операциях над графами // Современные проблемы математики и информатики. 1999. -Вып. 2. - С. 24-30.

38. Полякова О.П. Поведение функции неплотности при операциях над графами // Современные проблемы математики и информатики. 2000. -Вып. 3.-С. 52-61.

39. Татт У. Теория графов: Пер. с англ. М.: Мир, 1988. - 424 с.

40. Тетельбаеум А .Я. Силовые размещения планарного графа // Изв. АН СССР. Техн. кибернетика. 1988. - Вып. 3. - С.131-137.

41. У ил сон Р.Дж. Введение в теорию графов. Пер. с англ. И.Г. Никитиной; Под ред. Г.П. Говрилова М: Мир, 1977. - 207 с.

42. Харари Ф. Перечисление графов. М.: Мир, 1977.

43. Харари Ф. Теория графов: Пер. с англ. -М.: Мир, 1973. 302 с.

44. Харари Ф. Теория графов / Ф. Харари; Пер. с англ. и предисл. В.П. Козырева; Под ред. Г.Л. Гаврилова. 2-е изд. - М.: Эдиториал ХРСС, 2003. -300с.

45. Цишанг X., Фогт Э., Колдевай Х.-Д. Поверхности и разрывные группы. -М.: Наука, 1988.-688 с.

46. Шеврин Л.Н. Полугруппы // Общая алгебра / Под ред. Л.А. Скорнякова. -М.: Наука, 1991.-Т. 2.-Гл. IV-С. 11-191.

47. Шнеперман Л.Б. О максимальных компактных подполугруппах полной линейной полугруппы // Разбиения и гомоморфные отображения полугрупп СПб. - 1992. - С. 121-126.

48. Biggs N. Algebraic Graph Theory. Cambridge University Press, 1994.

49. Bogdanovich S. Semigroups with a system of subsemigroups. Novi Sad: Institute of Matematics, 1985.

50. Chartland G., Lesniak L. Graphs and Digraphs. London: Chapman & Hall, 1996.

51. DeMeyer F.R., McKenzie Т., Schneider К. The Zero-divisor Graph of a Commutative Semigroup. // Semigroup Forum. 2002. - Vol.65 - P. 206214.

52. Heydemann M.-C. Cayley graphs and interconnection networks. In G. Hahn and G. Sabidussi, editors, Graph Symmetry: Algebraic Methods and Applications. Kluwer: Dordrecht, - 1997. - P. 167-224.

53. Hopcroft J. E., Tarjan R. E. Efficient planarity testing // J. Assoc. Comput. Mach. 1974. - Vol. 21.-P. 549-568.

54. Italo J. Dejter, Hector Hevia, Oriol Serra. Hidden Cayley graph structures // Discrete Mathematics. 1998. - Vol.182. - P. 69-83.

55. Jurgensen H. Computers in semigroups // Semigroup Forum. 1977. - Vol. 15.-P. 1-20.

56. Kelarev A.V., Quinn S.J. A Combinatorial Property and Cayley Graphs of Semigroups. // Semigroup Forum. 2003. - Vol. 66. - P. 89-96.

57. Kelarev A.V. On undirected Cayley graphs // Australasian Journal Combinatorics. 2002. - Vol. 25. - P. 73-78.

58. Kelarev A.V., Praeger C.E. On transitive Cayley graphs of groups and semigroups // European Journal of Combinatorics. 2003. - Vol. 24. - P. 59-72.

59. Kelarev A.V., Quinn S.J. On complete and bipartite Cayley graphs // European Journal of Combinatorics. 2002.

60. Margolis S.W., Meakin J.C. E-unitary inverse monoids and the Cayley graph of a group representation // Journal of Pure and Applied Algebra. 1989. -Vol. 58.-P. 45-76.

61. Meir A., Moon J.W. On nodes of degree two in random trees // Mathematika. 1968.-Vol. 15. -P. 188-192.

62. Moon J.W. Enumerating labeled trees // Graph Theory and Theoretical Physics. London: Academic Press. - 1967. - P. 261-272.

63. Oberschelp W. Kombinatorische Anzahlbestimmungen in Relationen // Math Ann. 1967. - Vol. 174. - P. 53-78.

64. Oliveira A., Silva P. Inverse automata and monoids and the undecidability of the Cayley subgraph problem for groups // Glasg.Math.J. 2000. - Vol. 42 (3). -P. 421-437.

65. Petrich M. Introduction to Semigroups / Columbus, Ohio: Charles E. Merrill, 1973.

66. Steinberg B. Finite state automata: a geometric approach // Trans.Amer. Math.Soc. 2001. - Vol. 353 (9) - P. 3409-3464.

67. Surender В., Sandeep S. Planar Graph Blocking for External Searching // Al-gorithmica. 2002. - Vol. 34. - P. 298-308.

68. Zelinka B. Graphs of Semigroups // Casopis. Pest. Mat. 1981. - Vol. 106. -P. 407-408.

69. Zhonghao Jiang. An Answer to a Question of Kelarev and Praeger on Cayley Graphs of Semigroups // Semigroup Forum. 2004. - Vol. 69. - P. 457-461.Работы автора по теме диссертации

70. Соломатин Д.В. Конечные свободные коммутативные полугруппы с планарными графами Кэли // Математика и информатика: наука и образование: Межвузовский сборник научных трудов: Ежегодник- Омск: Изд-во ОмГПУ. 2003. - Вып. 3. - С. 32-38.

71. Соломатин Д.В. О допустимости некоторых графов в качестве графов Кэли полугрупп // Математика и информатика: наука и образование: Межвузовский сборник научных трудов: Ежегодник. Омск: Изд-во ОмГПУ. - 2004. - Вып. 4. - С. 32-34.

72. Соломатин Д.В. Конечные свободные коммутативные моноиды, допускающие планарный граф Кэли // Вестник Омского университета. Омск: Изд-во ОмГУ.-2005.-Вып. 4.-С. 36-38.

73. Соломатин Д.В. Рассыпчатые полугруппы с планарными графами Кэли // Известия ВГПУ: Серия «Естественные и математические науки». -Волгоград: Изд-во «Перемена». 2005. - №4 (13). - С. 27-31.

74. Соломатин Д.В. Прямые произведения циклических полугрупп, допускающие планарный граф Кэли // СЕМИ (Сибирские Электронные Математические Известия) http://semr.iTiath.nsc.ru. 2006. - т. 3. - С. 238-252.

75. Соломатин Д.В. Определение планарности графов Кэли прямых произведений циклических полугрупп. Программа для ЭВМ, зарегистрированная в ОФАП №50200501609 от 24 ноября 2005 года.

76. Соломатин Д.В. Проверка допустимости графа в качестве графа Кэли полугруппы. Программа для ЭВМ, зарегистрированная в ОФАП №50200600078 от 02 февраля 2006 года.