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

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

Фомина Евгения Олеговна КОНГРУЭНЦИИ ЦЕПЕЙ И ЦИКЛОВ

01.01.09 - Дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

2 у янз т

Москва-2014

005558299

Работа выполнена на кафедре теоретических основ компьютерной безопасности и криптографии Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Саратовский государственный университет имени Н.Г. Чернышевского».

Научный руководитель: кандидат физико-математических наук, профессор Салий Вячеслав Николаевич. Место работы: заведующий кафедрой теоретических основ компьютерной безопасности и криптографии Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Саратовский государственный университет имени Н.Г. Чернышевского». Официальные оппоненты:

• кандидат физико-математических наук, доцент, доцент кафедры прикладной математики и информатики Саратовского социально-экономического института (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Российский экономический университет имени Г.В. Плеханова» Богомолов Сергей Анатольевич;

• доктор технических наук, профессор, профессор кафедры высшей прикладной математики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московского государственного университета путей сообщения» Сперанский Дмитрий Васильевич.

Ведущая организация: Федеральное государственное автономное образовательное учреждение высшего образования «Национальный исследовательский Томский государственный университет».

Защита состоится 26 февраля 2015 года в 15 часов 00 минут на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении науки «Вычислительный центр им. A.A. Дородницына Российской академии наук» по адресу 119333, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН и на сайте http://www.ccas.ru/.

Автореферат разослан_2015 года.

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

профессор

В.В. Рязанов.

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

Актуальность темы. Нормальные подгруппы, введенные Галуа в начале

XIX века, привели к определению факторгрупп и к доказательству теорем о

гомоморфизмах, сыгравших основополагающую роль в развитии теории групп.

Точно так же идеалы колец, введенные Дедекиндом во второй половине XIX века,

позволили определить факторкольца и получить соответствующие теоремы о

гомоморфизмах для колец. Эта аналогия не могла не навести на мысль о

существовании некоторых общих конструкций, имеющих смысл для алгебр в

самом широком понимании этого слова. Такой объединяющей идеей явилось

понятие конгруэнции и тесно связанные с ним понятия факторалгебры и

гомоморфизма. Доказанные Нетер в 1920-х годах теоремы о гомоморфизмах для

произвольных алгебр заложили основы теории алгебраических систем, в

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

решеток (см. [2], [3], [8], [9]). Достижения в этой области математики вызвали

интерес у исследователей, работавших с дискретными системами различной

природы, и стимулировали развитие алгебраической теории для соответствующих

объектов (см. [4], [12], [13]).

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

ориентированным графом (далее орграфом) понимается пара й = (К «), где V -

конечное непустое множество, а а — отношение на V. Множество V называется

множеством вершин, отношение а - отношением смежности, а пары, входящие в

а, дугами орграфа б. Если (и, у) 6 а , то говорят, что вершина V смежна с

вершиной и. Пусть е — некоторое отношение эквивалентности на множестве

вершин V. Факторграфом орграфа б по эквивалентности е называется орграф б/с

= (У/е, ас), где К/с - множество классов эквивалентности е, а ае= {(ФО, фъ)):

(Зи, е ф,), Зи2 е е(у2)Х(и1, иг) е а)}.

Если К - некоторый класс графов и й « К, то под Х-конгруэнцией графа О

понимается такая эквивалентность в = Vх V , что О в 6 К. Одна из известных

задач следующая: как устроены минимальные (по включению) А'-конгруэнции

данного графа? Например, если К - класс бесконтурных графов, то отношение а

3

взаимной достижимости вершин данного графа С является его наименьшей К-конгруэнцией. Факторграф С/<т называется конденсацией графа (3, эта конструкция хорошо известна в прикладных разделах теории графов.

Дня класса К функциональных графов М. А. Кабанов [5] указал наименьшую /^-конгруэнцию на произвольном графе и установил некоторые свойства решетки функциональных конгруэнций графа. Он же решил аналогичные задачи для классов, входящих и выходящих ориентированных деревьев, описал графы со специальными решетками циклических и ациклических конгруэнций.

М.Р. Мирзаянова [11] рассматривал случай, когда К - класс сильно связных орграфов, и предложил способ построения сильно связной конгруэнции произвольного орграфа, наибольшей по числу вершин в факторграфе. Им установлено также [10], что «-элементная ориентированная цепь имеет 2""3 минимальных сильно связных конгруэнций.

Пусть К - некоторый класс орграфов. Конгруэнцией ЛТ-графа С называется такое отношение эквивалентности в на V, что факторграф С,)0 является К-графом.

Здесь известны результаты, представленные в заметке А.В.Киреевой [6], посвященной древесным конгруэнциям ориентированных деревьев. В своей работе [7] она охарактеризовала функциональные графы, у которых каждый подграф изоморфен подходящему факторграфу, и функциональные графы, у которых каждый факторграф изоморфен подходящему подграфу.

В [4] рассматривались конгруэнции бесконтурных графов.

Возьмём в качестве класса К класс неориентированных графов.

Неориентированным графом (или, для краткости, графом) называется пара С= (V, а), где а - симметричное и антирефлексивное отношение на множестве вершин V. В неориентированном графе пара встречных дуг (и, у),(у, и) рассматривается как один элемент графа, называемый ребром {и, у}.

Далее символами К„ , Рт , Ст, будем обозначать соответственно полный граф с п вершинами и /я-реберные цепь, цикл и звезду.

Множество вершин в графе называется независимым, если любые две вершины из этого множества несмежны.

Очевидно, что отношение эквивалентности в на множестве вершин графа G = (V, а) тогда и только тогда будет конгруэнцией этого графа, когда каждый 0-класс образует в G независимое подмножество.

Известен следующий результат Продингера и Тихого [14]: i(P„) = F(n+2), где ¡(G) - число независимых множеств в графе G, Fin) - числа Фибоначчи. Верхней оценке числа максимальных независимых множеств в графе посвящена работа В.Е. Алексеева [1].

NP-полной является задача о факторизации: можно ли для заданного графа сказать, является ли он факторграфом другого заданного графа?

К числу нерешенных проблем комбинаторной теории графов относятся следующие задачи: сколько неизоморфных факторграфов имеет «-реберная цепь; сколько неизоморфных факторграфов имеет /и-реберный цикл?

Для неориентированных графов понятие конгруэнции тесно связано с раскрасками. В контексте конгруэнции, и-раскраска неориентированного графа G — это разбиение множества вершин графа G на и независимых классов, т.е. конгруэнция с п классами. Полной раскраской графа G является конгруэнция в такая, что факторграф GIO будет полным графом. Если граф GI6 имеет п вершин, то мы говорим о полной я-раскраске. Хроматическое число %(G) графа G можно рассматривать как число классов конгруэнции в графа G с наименьшим возможным числом классов, причем G/в будет полным графом. Проблема нахождения хроматического числа для произвольного графа является NP-полной.

Ахроматическим числом будет число классов конгруэнции графа G с наибольшим возможным числом классов, причем, заметим, что факторграф по данной конгруэнции будет полным графом. Другими словами, если п -ахроматическое число, то полный граф с наибольшим возможным числом вершин, на который факторизуется граф G, будет «-вершинным. Проблема нахождения ахроматического числа также является NP-полной.

Цель работы. Исследовать конгруэнции цепей и циклов; выяснить какие графы являются факторграфами заданной цепи и заданного цикла; подсчитать

5

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

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

Научная новизна и выносимые на защиту положения.

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

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

3. Найдена длина наикратчайшей цепи, факторизующейся на данный связный граф, получены точные оценки для этой величины.

4. Выделены циклические конгруэнции т-реберной цепи, связанные с делителями числа /я+1.

5. Результаты, аналогичные 1-4, получены также для циклов.

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

7. Показано, что главные идеалы полурешетки конгруэнций цепи, порожденные однотипными конгруэнциями, являются изоморфными решетками.

8. Показано, что каждая конечная решетка вложима в решетку четных конгруэнций подходящей цепи.

9. Результаты, аналогичные 6-8, получены также для циклов.

Теоретическая и практическая значимость работы. Работа носит

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

Апробация результатов. Результаты представляемой работы обсуждались на научных семинарах кафедры теоретических основ компьютерной безопасности

6

и криптографии Саратовского государственного университета имени Н.Г. Чернышевского (г. Саратов, 2009-2013 гг.). Результаты исследований также докладывались на следующих научных мероприятиях: Международная научная конференция «Компьютерные науки и информационные технологии» (г. Саратов, 2009, 2010, 2012 гг.); XVIII и XIX Международные научные конференции студентов, аспирантов и молодых ученых «Ломоносов - 2011» и «Ломоносов -2012» (г.Москва, 2011 и 2012 гг. соответственно); XVI Международная конференция «Проблемы теоретической кибернетики» (г. Нижний Новгород, 2011 г.); 2011 Fall Central Section Meeting: University of Nebraska-Lincoln (Lincoln, NE, October 14-16, 2011); X Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» - SIBECRYPT'll (г. Томск, 2011 г.); XI Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» — SIBECRYPT'12 (г. Иркутск, 2012 г.); 55-й научная конференция МФТИ: Всероссийская научная конференция «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» (г. Москва, 2012 г.), семинар по теории графов в университете Пьера и Марии Кюри (г. Париж, 2012 г.).

Публикации. Основные результаты опубликованы в работах автора [А1-А13]. Работы автора [А5], [А9], [А13] опубликованы в изданиях, включенных в «Перечень ведущих рецензируемых научных журналов и изданий» ВАК, в которых должны быть опубликованы основные научные результаты диссертаций на соискание учёных степеней доктора и кандидата наук.

Структура и объем работы. Диссертационная работа состоит из введения, двух глав, заключения, списка использованных источников, включающего 37 наименований, и четырех приложений. Диссертация изложена на 100 листах.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1. В первом параграфе вводятся все основные определения теории графов, используемые в работе.

Во втором параграфе рассматриваются конгруэнции цепей.

Теорема 3. Любой связный граф является факторграфом подходящей цепи.

Подсчитано количество конгруэнций для цепи Рт. Через Con Рт обозначим множество всех конгруэнций цепи Рт, а через Е(т) - множество всех эквивалентностей на /я-элементном множестве.

Теорема 4. |Соп Рт\ = |Е(/я)|.

Количество элементов в Е(т) называется числом Белла В(т).

Определим цепную конгруэнцию цепи как такую конгруэнцию, факторграфом по которой будет цепь.

Теорема 5. Количество цепных конгруэнций цепи Рт равно 2""'.

К числу конгруэнций цепи Рт относятся особые конгруэнции, связанные с делителями числа т+1. В контексте таких конгруэнций, для удобства будем рассматривать цепь Р„, где п = т+1. Пусть d - делитель числа п, т.е. п = dk Разобьем множество вершин цепи Р„ на классы вычетов по модулю d. Так как у этого разбиения Oj все классы будут независимыми подмножествами, то мы получаем конгруэнцию цепи Р„. Конгруэнции вида 0d будем называть <5-конгруэнциями цепи Р„.

Теорема 6. Пусть Oj, d Ф п, является ¿-конгруэнцией цепи Р„. Тогда р /

факторграф будет циклом.

Найдена цепь с минимальным возможным числом ребер p(G), факторграфом которой является данный граф G.

Теорема 7. Пусть G - связный граф. Тогда p(G) = trfrl-k, где т - количество ребер графа G, I — количество ребер в минимальном цепном паросочетании на множестве нечетных вершин графа G, к — максимальная из длин цепей в таких паросочетаниях.

Следствие 1. Для полного графа К„ имеем: 1) р(К„) = ^, если п п2

нечетно; 2) р{К„) — — -1, если п четно.

Следствие 2. Для звезды S„cm ребрами p{Sm) = 2т-2.

Найдены верхняя и нижние оценки для p(G).

Теорема 8. Для связного графа Gern ребрами т i p(G) £ 2т-2.

Диаметром дерева Т называется максимальное расстояние между его вершинами.

Теорема 9. Если Т- дерево с m ребрами и с диаметром d, то р(Т) = 2m—d.

Во втором параграфе рассматриваются конгруэнции циклов по аналогии с конгруэнциями цепей.

Теорема 10. Связный граф G тогда и только тогда является факторграфом m-реберного цикла, когда в нем есть циклический обход длины т.

Любой граф является факторграфом подходящего четного цикла.

С нечетными циклами ситуация обстоит иначе.

Теорема 11. Если граф является факторграфом нечетного цикла, то он содержит циклы нечетной длины.

Подсчитано количество всех конгруэнций цикла Ст.

т-2

Теорема 12. |Соп Ст\ =£(-l)iß(m-/:-l)) где В(п) - число Белла.

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

Теорема 13. Количество цепных конгруэнций четного цикла Ст равно 2J '.

Пусть d — делитель числа т, т.е. т = dk Разобьем множество вершин цикла С„ на классы вычетов по модулю d. Так как у этого разбиения Oj все классы будут независимыми подмножествами, то мы получаем конгруэнцию цикла Ст. Конгруэнции вида 9j будем называть (5-конгруэнциями цикла С„. Количество S-конгруэнций цикла С„ равно т(т)-1, т.е. количеству неединичных делителей числа т.

Теорема 14. Пусть 6j является ¿-конгруэнцией цикла Ст. Тогда факторграф будет циклом.

Для данного связного графа G найден цикл с минимальным возможным числом ребер c(G), факторграфом которого является данный граф.

Теорема 15. Пусть G - связный граф. Тогда c(G) = т+l, где т — количество ребер графа G, I - количество ребер в минимальном цепном паросочетании на множестве нечетных вершин графа G.

Следствие 1. Для полного графа К„ имеем: 1) с(К„) = ^, если п -п1

нечетно; 2) с(К„) = —, если п четно.

Следствие 2. Для звезды S„cm ребрами c(S„) = 2т.

Найдены верхняя и нижняя оценка для c(G).

Теорема 16. Для любого связного графа с т ребрами т < c(G) < 2т.

Глава 2. В первом параграфе вводятся основные определения теории графов и теории решеток, используемые в главе.

Говорят, что в упорядоченном множестве (S, <) элемент b является верхним соседом элемента а, если а < b и не существует х е S такого, что а < х < Ь, при этом говорят, что а - нижний сосед для Ь. Верхние соседи наименьшего элемента называются атомами упорядоченного множества 5. Нижние соседи наибольшего элемента называются коатомами упорядоченного множества S.

Во втором параграфе рассматривается полурешетка конгруэнций цепи.

Так как для любых двух элементов в\ и 02 в упорядоченном множестве (Con Рт, £) существует iпГ(,¿?2) = 0¡n 02, то (Con Рт, -) - нижняя полурешетка.

10

Теорема 1. В полурешетке (Con Рт, с) высота конгруэнции в равна h(6) = т+\-с(0), где с(0) - число классов конгруэнции в.

Теорема 2. Полурешетка (Con Рт, с) имеет длину т-1.

Теорема 3. Конгруэнция в будет максимальной в (Con Рт, '=), тогда и только тогда, когда факторграф руд будет полным графом.

Типом конгруэнции называется последовательность мощностей классов конгруэнции, записанная в порядке убывания.

Теорема 4. Главные идеалы, порожденные конгруэнциями одного типа в полурешетке (Con Рт, с), являются изоморфными решетками.

Далее в этом же параграфе подсчитано количество элементов главного идеала Id в, порожденного конгруэнцией 9 типа (t\, h, ..., /„): B(t\)B(ti)...B(t„),

количество коатомов главного идеала: ä2('i,2)+ ^2(^2,2)+...+ s2(t„,l) = ¿5,(г,,2) и

ы

количество атомов главного идеала: С*+С,*+...+С,= ^С? .

i=i

Конгруэнция в цепи Р„ называется правильной, если (/', J) б в: => (;' и j — вершины цепи Рт одной четности). Обозначим множество правильных конгруэнций через Соппр Р„. Определим четную конгруэнцию цепи Рт как такую конгруэнцию в, что (/, J) е в: => (/ и j — четные вершины цепи Рт), а нечетную конгруэнцию в, как (;',/) е 0:=> (i и j — нечетные вершины цепи Рт). Обозначим множество четных конгруэнций через Сопч Рт, а множество нечетных конгруэнций - через ConнРт.

Так как (Соппр Рт, —) является нижней полурешеткой и в ней есть наибольший элемент, то (Con„p Рт, - решетка.

Теорема 5. ConnpP„ s ConЧР„ х Con„Pm.

В своей работе [15] Пудлак и Тума показали, что любая конечная решетка вложима в подходящую конечную решетку эквивалентностей.

Теорема 6. Любая конечная решетка вложима в решетку четных конгруэнций подходящей цепи.

Теорема 7. Полурешетка ¿-конгруэнций цепи Р„ дуально изоморфна полурешетке неединичных делителей числа п.

В третьем параграфе по аналогии с цепями рассматривается полурешетка конгруэнций цикла.

Совокупность всех конгруэнций цикла Ст, как уже было сказано выше, обозначается через Con Cm. Количество главных конгруэнций цикла Ст равно 2(от-3)+(от-4)+(ш-5)+.. .+1.

Теорема 8. В полурешетке (Con Ст, е) высота конгруэнции в равна h{6) = т-с(6), где с(в) - число классов конгруэнции 9.

Теорема 9. Полурешетка (Con Ст, с) имеет длину т-2, если т - четное, и длину т-3, если т - нечетное.

Теорема 10. Конгруэнция в будет максимальной в (Con Cm, £), тогда и

только тогда, когда факторграф С'"/д будет полным графом.

Теорема 11. Главные идеалы, порожденные конгруэнциями одного типа в полурешетке (Con Ст, с), являются изоморфными решетками.

Для главного идеала Id в, порожденного конгруэнцией в типа (/¡, tг, ..., t„), подсчитано количество элементов, количество коатомов и количество атомов.

Конгруэнция в четного цикла Ст называется правильной, если (i,j) е в: => (/ и j — вершины цикла С„ одной четности). Обозначим множество правильных конгруэнций через Соп„р Ст. По аналогии с цепями определим четную и нечетную конгруэнции цикла Ст . Обозначим множество четных и нечетных конгруэнций соответственно через Con, Ст и Соп„ Ст.

Рассмотрим полурешетку конгруэнций четного цикла Ст. Так как (Соппр С„, S) является нижней полурешеткой и в ней есть наибольший элемент, то (Соппр Ст, S) - решетка.

Теорема 12. Соппр Ст s Con, Ст х Соп„ С„.

Теорема 13. Любая конечная решетка вложима в решетку четных конгруэнций подходящего четного цикла.

Теорема 14. Полурешетка ¿-конгруэнции цикла С„ дуально изоморфна полурешетке неединичных делителей числа т.

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

Приложение 1. Здесь указываются все конгруэнции и факторграфы цепей Рг, Рг, Р* и Р5, а также все неизоморфные факторграфы цепей Р2, Рз, Рл и Р5.

Приложение 2. Здесь указываются все конгруэнции и факторграфы циклов СCs и Сб, а также все неизоморфные факторграфы циклов Сц, С5 и Сб.

Приложение 3. Здесь показаны диаграммы полурешеток конгруэнций для цепей Рг, Р), Р4 и Р$.

Приложение 4. Здесь показаны диаграммы полурешеток конгруэнций для циклов Ca, Cs и Сб.

Автор выражает искреннюю благодарность своему научному руководителю В.Н. Салию за помощь и внимание к работе.

СПИСОК ЛИТЕРАТУРЫ

1. Алексеев, В.Е. Верхняя оценка числа максимальных независимых множеств графа / В.Е. Алексеев // Дискретная математика. - 2007. - Т. 19. Вып. 3. -С. 84-88.

2. Общая алгебра / В. А. Артамонов [и др.]; ред. Л. А. Скорняков. - М.: Наука, 1991 - Т. 2. - 480 с. - (Справочная математическая библиотека). - ISBN 502-014427.

3. Теория решеток / Г. Биркгоф; пер. с англ. В. Н. Салий; под ред. Л. А. Скорнякова. - М: Наука, 1984. - 566 с.

4. Алгебраические основы теории дискретных систем: монография / А.М. Богомолов, В.Н. Салий. - М.: Наука; Физматлит, 1997. - 368 с. - ISBN 5-02015033-9.

5. Кабанов, М.А. Функциональные конгруэнции ориентированных графов / М.А. Кабанов // Упорядоченные множества и решётки. — Саратов, 1995. — Вып. 11. — С. 15-23.

6. Киреева, А.В. О конгруэнциях и автоморфизмах корневых деревьев / А.В. Киреева // Теория полугрупп и ее приложения. — Саратов, 1991. -— Вып. 10, —С. 37-42.

7. Киреева, А.В. Подграфы и факторизации функциональных графов / А.В. Киреева // Успехи мат. наук. — 1993. — Т. 48, № 2 (290). — С. 183-184.

8. Универсальная алгебра = Universal Algebra: перевод с английского / П. М. Кон; под ред. А. Г. Курош. — Москва: Мир, 1968. — 351 с.

9. Алгебраические системы: монография/ А.И. Мальцев — Москва: Наука. Главная редакция физико-математической литературы [Физматлит], 1970.

— 392 с.

10. Мирзаянов, М.Р. О минимальных сильно связных конгруэнциях ориентированных цепей / М.Р. Мирзаянов // Изв. Сарат. ун-та Сер. Математика. Механика. Информатика. —2006. —Т. 6, вып. 1/2. — С. 91-95.

11. Мирзаянов, М.Р. Сильно связные конгруэнции ориентированных графов / М.Р. Мирзаянов // Теоретические проблемы информатики и ее приложений.

— Саратов: Изд-во Саратовского университета, 2006. — Вып. 7. — С. 104114.

12. Universal algebra and automata / G. Birkhoff, J.D. Lipson // Proc. Tarski Symp. (Proc. Symp. Pure Math., V. 25). — Providence, R.I., 1974. — Vol. 2. — p. 4151.

13. Factorization, congruences, and the decomposition of automata and systems / J.A. Goguen, J.W. Thatcher, E.G. Wagner, J.B. Wright // Lect. Notes Comput. Sci. — 1975. — Vol. 28. — p. 33-45.

14. Fibonacci numbers of graphs / H. Prodinger, R.F. Tichy // Fibonachi Quarterly. -1982.-Vol. 20, № l.-p. 16-21.

15. Every finite lattice can be embedded in a finite partition lattice / P. Pudlak, J. Tuma // Algebra Universalis. — 1980. — Vol.10. — p.74-95.

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ AI. Карманова, Е.О. Конгруэнции цепей / Е.О. Карманова // Компьютерные науки и информационные технологии: Материалы Междунар. науч. конф. -Саратов: Изд-во Саратовского университета, 2009. - С. 238. А2. Карманова, Е.О. О конгруэнциях цепей и циклов / Е.О. Карманова // Компьютерные науки и информационные технологии: Материалы науч. конф. Саратов, 1 июля 2010 г. - Саратов: Изд-во СГУ, 2010. - С. 70-74 A3. Карманова, Е.О. О факторизациях цепей / Е.О. Карманова // Ломоносов-2011: Материалы XVIII Международной научной конференции студентов, аспирантов и молодых ученых: секция «Вычислительная математика и кибернетика»; 11-15 апреля; Москва, МГУ имени М.В. Ломоносова, факультет ВМК: Сборник тезисов. - М.: Издательский отдел факультета ВМК МГУ (лицензия ИД 05899 от 24.09.2001), 2011. - С. 17-18. ISBN 978-5-89407-450-4. A4. Карманова, Е.О. О конгруэнциях графов / Е.О. Карманова // Проблемы теоретической кибернетики. Материалы XVI Международной конференции (Нижний Новгород, 20-25 июня 2011 г.). - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2011. - С. 195-197. ISBN 978-5-91326-161-8. А5. Карманова, Е.О. О конгруэнциях цепей / Е.О. Карманова // Прикладная дискретная математика. - 2011. - № 2 (12). - С. 96-100. ISSN 2071-0410. А6. Карманова, Е.О. О конгруэнциях цепей / Е.О. Карманова // Прикладная дискретная математика. Приложение: Тезисы докладов X Сибирской научной школы-семинара с международным участием «Компьютерная безопасность и криптография». - SYBECRYPT11 (Томск, ТГУ, 5-10 сентября 2011 г.). - № 4, сентябрь 2011.-С. 91-92.

А7. Karmanova, Е.О. On congruence relations of graphs [Электронный ресурс] / Е.О. Karmanova // 2011 Fall Central Section Meeting (University of NebraskaLincoln, Lincoln, NE October 14-16). - 2011. - Режим доступа: http://www.ams.Org/amsmtgs/2185_abstracts/l 074-00-14.pdf. A8. Карманова, Е.О. Две теоремы о конгруэнциях цепей / Е.О. Карманова // Материалы Международного молодежного научного форума «ЛОМОНОСОВ-

15

2012» / Отв. ред. А.И. Андреев, A.B. Андриянов, Е.А. Антипов, М.В. Чистякова. [Электронный ресурс] — М.: МАКС Пресс, 2011. — 1 электрон, опт. диск (DVD-ROM); 12 см. - Систем, требования: ПК с процессором 486+; Windows 95; дисковод DVD-ROM; Adobe Acrobat Reader. — ISBN 978-5-31704041-3.

A9. Карманова, Е.О. Конгруэнции цепей: некоторые комбинаторные свойства / Е.О. Карманова // Прикладная дискретная математика. - 2012. - № 2 (16). — С. 86-89.-ISSN 2071-0410.

А10. Карманова, Е.О. Упорядоченное множество конгруэнций цепи / Е.О. Карманова // Компьютерные науки и информационные технологии: Материалы междунар. науч. конф. — Саратов: Издат. центр "Наука", 2012. - С. 133-135.-ISBN 978-5-9999-1304-3.

AI 1. Карманова, Е.О. Конгруэнции цепей: некоторые комбинаторные свойства / Е.О. Карманова // Прикладная дискретная математика. Приложение: Тезисы докладов Всероссийской конференции "XI Сибирская научная школа-семинар с международным участием «Компьютерная безопасность и криптография» -SYBECRYPP12" (Иркутск, 3-8 сентября 2012 г.). - № 5, сентябрь 2012. - С. 93-94. - ISSN 2226-308Х.

А12. Карманова, Е.О. О решетках конгруэнций цепи / Е.О. Карманова // Труды 55-й научной конференции МФТИ: Всероссийской научной конференции «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе», Научной конференции «Современные проблемы фундаментальных и прикладных наук в области физики и астрономии», Всероссийской молодёжной научной конференции «Современные проблемы фундаментальных и прикладных наук». Инновации и высокие технологии. -М.: МФТИ, 2012. - С. 22-24. - ISBN 978-5-7417-0408-0. А13. Фомина, Е.О. Главные идеалы в полурешетке конгруэнций цепи / Е.О. Фомина // Известия СГУ. Серия Математика, механика, информатика. - 2013. -Т. 13, вып. 1.-С. 99-109.

Подписано в печать: 27.12.2014

Объем: 0,6 усл. п.л. Тираж: 100 экз. Заказ № 2062 Отпечатано в типографии «Реглет» 119526, г. Москва, Мясницкие Ворота д. 1, стр. 3 (495)971-22-77; www.reglet.ru