Конгруэнции цепей и циклов

• Автор: Фомина, Евгения Олеговна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Саратов
• Количество страниц: 100 с. : ил.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

Глава 1. ОСНОВНЫЕ СВОЙСТВА КОНГРУЭНЦИЙ

ЦЕПЕЙ И ЦИКЛОВ

§ 1. Основные определения

§ 2. Конгруэнции цепей

§ 3. Конгруэнции циклов

Глава 2. ПОЛУРЕШЕТКА КОНГРУЭНЦИЙ ДЛЯ ЦЕПИ

И ДЛЯ ЦИКЛА
§ 1. Основные определения
§ 2. Нолурешетка конгруэнций цепи
§ 3. Полу решетка конгруэнций цикла
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ 1. ВСЕ КОНГРУЭНЦИИ И ФАКТОРГРАФЫ ЦЕПЕЙ Р2, Ръ Р4 И Р5. ВСЕ НЕИЗОМОРФНЫЕ ФАКТОРГРАФЫ
ЦЕПЕЙР2,/’з,Р4ИР
ПРИЛОЖЕНИЕ 2. ВСЕ КОНГРУЭНЦИИ И ФАКТОРГРАФЫ ЦИКЛОВ С3, С4, С5 И С,;. ВСЕ НЕИЗОМОРФНЫЕ ФАКТОРГРАФЫ
ЦИКЛОВ С3,С4,С5 И Сб
ПРИЛОЖЕНИЕ 3. ПОЛУ РЕШЕТКИ КОНГРУЭНЦИЙ
ЦЕПЕЙ Р2, Р2, РА И Р
ПРИЛОЖЕНИЕ 4. ПОЛУРЕШЕТКИ КОНГРУЭНЦИЙ
ЦИКЛОВ С4,С5ИС

ВВЕДЕНИЕ
Нормальные подгруппы, введенные Галуа в начале XIX века, привели к определению факторгрупп и к доказательству теорем о гомоморфизмах, сыгравших основополагающую роль в развитии теории групп. Точно так же идеалы колец, введенные Дедекиндом во второй половине XIX века, позволили определить факторкольца и получить соответствующие теоремы о гомоморфизмах для колец. Эта аналогия не могла не навести на мысль о существовании некоторых общих конструкций, имеющих смысл для алгебр в самом широком понимании этого слова. Такой объединяющей идеей явило сь понятие конгруэнции и тесно связанные с ним понятия факторалгебры и гомоморфизма. Доказанные Нетер в 1920-х годах теоремы о гомоморфизмах для произвольных алгебр заложили основы теории алгебраических систем, в разработке которой важное место заняли методы универсальной алгебры и теории решеток (см [3], [4], [11], [13], [14]). Достижения в этой области математики вызвали интерес у исследователей, работавших с дискретными системами различной природы, и стимулировали развитие алгебраической теории для соответствующих объектов (см. [23], [25], [27], [31]), в первую очередь в теории автоматов (см. [18], [34]).
Понятие конгруэнции было перенесено и на случай графов.
Под ориентированным графом (далее орграфом) понимается пара О = (V, а), где V - конечное непустое множество, а а - отношение на V. Множество V называется множеством вершин, отношение а - отношением смежности, а пары, входящие в а, дугами орграфа О. Если (и, г) 6 а , то говорят, что вершина V смежна с вершиной и. Основные понятия приводятся в соответствии с [5].
Графовые модели широко используются по многих областях человеческой деятельности. Транспортные системы, информационные сети, компьютерные программы, отношение зависимости в социальных группах -все могут моделироваться графами.

Существуют различные методы преобразования графовых систем для приложений к проблемам оптимизации в вышеупомянутых ситуациях. В качестве допустимых реконструкций данного графа обычно рассматриваются следующие [19]:
1) ориентация ребер данного неориентированного графа (например, известная теорема Оре - критерий ориентируемости графа в сильно связный орграф [17]);
2) добавление новых дуг (ребер) (эта реконструкция используется, например, для построения отказоустойчивых реализаций по Хейзу -Абросимову [1], [32]);
3) удаление некоторых дуг (ребер) (здесь общеизвестными результатами являются, например, алгоритмы построения минимального остовного дерева для связной сети, так называемые минимальные расконтуривапия сетей в технической диагностике [6]);
4) отождествление некоторых вершин графа.
Последний вид реконструкций формализуется следующим образом.
Гомоморфизмом орграфа С = (Г,, а.) в орграф (А = (У2, а2) называется отображение <р V] —> У2 такое, что (и, у) е а —* ((р(и), (р(у)) е а2 для любых и, V е У. Отметим следующие работы, посвященные гомоморфизмам графов: [29], [33].
В алгебре конгруэнции тесно связаны с гомоморфизмами: каждая конгруэнция является ядром подходящего гомоморфизма. Для графов подобный подход представляется мало интересным: любая эквивалентность на множестве вершин графа может рассматриваться как ядро некоторого гомоморфизма. Например, если <р — произвольное отображение множества вершин У орграфа С = (Уи а,) в некоторое непустое множество У2, то существует орграф С2 = (У2, о.2) такой, что ф будет гомоморфизмом орграфа в орграф <72: нужно задать отношение а2 следующим образом: а2= {(», г) 6 У2 х У< (Эн, г е У{]{(р{и) = и & = V & (и, у) е он)}. Отсюда следует, что
если определить конгруэнцию орграфа как ядро Кег <р некоторого его

Используя один из алгоритмов, связанных с этой задачей [22], докажем следующую теорему.
Теорема 7. Пусть О - связный граф. Тогда р(С) = т+1-к, где т -количество ребер графа О, I — количество ребер в минимальном цепном паросочетании на множестве нечетных вершин графа С, к - максимальная из длин цепей в таких паросочетаниях.
Доказательство. Пусть дан произвольный связный граф (7 с т ребрами и п вершинами. Найдем длину наименьшей цепи Рп факторизующейся на Є. Так как, по теореме 2, связный граф тогда и только тогда является факторграфом /-реберной цепи, когда в нем есть обход длины г, то найдем длину /• минимального обхода Я.
Рассмотрим случай, когда граф Є не эйлеров и не имеет эйлерова пути, поскольку иначе этот граф имеет обход длины т. Таким образом, в связном графе С существуют ребра, проходимые в Я более чем один раз.
Так как граф Є — связный, то построим обход графа О, используя алгоритм решения задачи китайского почтальона.
Пусть V* - множество вершин графа Є, имеющих нечетную степень. Так как граф (7 не эйлеров, то количество вершин, имеющих нечетную степень, будет больше двух и число таких вершин будет четным.
Пусть М- множество цепей между концевыми вершинами V, И є
V'*, і фу, в графе (7 таких, что никакие две цепи не имеют одинаковых концевых вершин, и ребра, соединяющие различные пары вершин из V*, покрывают все вершины множества К*. Такое множество цепей М называется цепным паросочетанием. Так как количество нечетных вершин
четно, что количество таких цепей ~ У*.
Следуя [22], строим все минимальные цепные паросочетания па множестве нечетных вершин V* графа (7. В силу минимальности никакие две цепи в таком паросочетании не могут иметь общих рсбер.