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

• Соломатин, Денис Владимирович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Соломатин, Денис Владимирович

Введение.

Глава 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 рисунками.

Список литературы диссертационного исследования кандидат физико-математических наук Соломатин, Денис Владимирович, 2006 год

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 года.