О конгруэнциях цепей | ПДМ. 2011. № 2(12).

О конгруэнциях цепей

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

On congruences of paths.pdf Под ориентированным графом (далее орграфом) понимается пара G = (V, а), гдеV - конечное непустое множество вершин, а а - отношение на V, задающее множестводуг. Основные понятия приводятся в соответствии с [1].Графовые модели широко используются во многих областях человеческой дея-тельности. Транспортные системы, информационные сети, компьютерные программы,отношение зависимости в социальных группах - все могут моделироваться графами.Существуют различные методы преобразования графовых систем для приложенийк проблемам оптимизации в вышеупомянутых ситуациях. В качестве допустимых ре-конструкций данного графа обычно рассматриваются следующие [2]:1) ориентация ребер данного неориентированного графа (например, известная тео-рема Оре - критерий ориентируемости графа в сильно связный орграф [3]);2) добавление новых дуг (ребер) (эта реконструкция используется, например,для построения отказоустойчивых реализаций компьютерных сетей по Хейзу -Абросимову [4, 5]);3) удаление некоторых дуг (ребер) (здесь общеизвестными результатами являют-ся, например, алгоритмы построения минимального остовного дерева для связ-ной сети, так называемые минимальные расконтуривания сетей в техническойдиагностике [6]);4) отождествление некоторых вершин графа.Последний вид реконструкций формализуется следующим образом.Пусть е - некоторое отношение эквивалентности на множестве вершин V оргра-фа G. Фактор-графом орграфа G по эквивалентности е называется орграф G/е == (V/e,a.), где V/е - множество классов эквивалентности е; а. = |(e(vi),e(v2)) :3ui е e(vi),u2 е e(v2) ((ui,u2) e а)}.Пусть K - некоторый класс орграфов. Конгруэнцией K-графа G называется такоеотношение эквивалентности 9 на V, что фактор-граф G/9 является K-графом.Известны результаты М. Р. Мирзаянова [7], который рассматривал случай, когдаK - класс сильносвязных орграфов, и предложил способ построения сильносвязнойконгруэнции произвольного орграфа, наибольшей по числу вершин в фактор-графе.Им установлено также [8], что n-элементная ориентированная цепь имеет 2n - 3 мини-мальных сильносвязных конгруэнций.Возьмём в качестве класса K класс неориентированных графов.Путем в графе G = (V, а) называется последовательность ребер, в которой каждыедва соседних ребра имеют общую вершину и никакое ребро не встречается более одногораза. Если начальная и конечная вершины пути совпадают, путь называется цикли-ческим. Путь, каждая вершина которого принадлежит не более чем двум его ребрам,является простым. Простой циклический путь называется циклом, нециклический -цепью. Цепь с m ребрами будем обозначать Pm.Звезда - это граф, все ребра которого инцидентны одной и той же вершине. Звездус m ребрами будем обозначать Sm.Показано, что любой связный граф является фактор-графом подходящей цепи, иполучены оценки для минимальной длины цепи, факторизующейся на данный граф.Множество вершин называется независимым, если любые две вершины из этогомножества несмежны.Очевидно, что отношение эквивалентности 9 на множестве вершин графа G тогдаи только тогда будет конгруэнцией этого графа, когда каждый 9-класс образует в Gнезависимое подмножество.Известна следующая задача о факторизации: можно ли для заданного графа ска-зать, является ли он фактор-графом другого заданного графа? Эта задача являетсяNP-полной.Например, возьмем пятиреберную цепь P5. Пятивершинный цикл C5 будет её фак-тор-графом, а четырехреберная звезда S4 нет.К числу нерешенных проблем комбинаторной теории графов относится следующаязадача: сколько фактор-графов имеет n-элементная цепь? Сколько среди них неизо-морфных?В [9] доказана следующая теорема.Теорема 1. i(Pn - 1 ) = F(n + 2), где i(G) -число независимых множеств в гра-фе G, F(n) -числа Фибоначчи.Отсюда следует, что для цепи Pn - 1 количество всех конгруэнций с одним нетри-виальным классом равно F(n + 2) - 2, так как в число всех независимых множествв графе включается пустое множество и все одноэлементные подмножества множестваего вершин.В [10] представлена программа, генерирующая все конгруэнции заданной цепи ивыделяющая среди них цепные конгруэнции, т. е. такие, фактор-графы по которымявляются цепями. При этом выдается общее число конгруэнций данной цепи и ко-личество её цепных конгруэнций. Например, у трехреберной цепи P3 имеется четыреразличных конгруэнции, которые дают три неизоморфных фактор-графа.У четырех-реберной цепи P4 всего имеется 14 фактор-графов, из них 7 попарно неизоморфных.На основании результатов, полученных в [10], можно выдвинуть следующее пред-положение.ГИПОТЕЗА. Количество конгруэнций n-элементной цепи равно B(n - 1), гдеB (n) -число Белла.Число Белла B(n) -это число всевозможных эквивалентностей на n-элементноммножестве.Маршрут в связном графе называется обходом, если он содержит все ребра графа.Следующий известный результат Тарри [3] показывает, что любой связный графс m ребрами имеет обход длины 2m.Лемма 1. Если граф связный, то можно построить циклический маршрут, со-держащий все ребра графа в точности два раза, по одному в каждом направлении.Пусть дана m-реберная цепь. Какие графы являются ее фактор-графами?Теорема 2. Связный граф тогда и только тогда является фактор-графом m-ре-берной цепи, когда в нем есть обход длины m.Доказательство. Необходимость. Пусть связный граф G является фактор-графом цепи Pm по конгруэнции 9. Покажем, что в нем есть обход длины m.Пусть в цепи Pm вершины пронумерованы натуральными числами 1, 2,...,m,m+1.Каждая вершина графа G является 9-классом. При этом 9(i) и 9(j) смежны в Gтогда и только тогда, когда существуют i' е 9(i) и j' е 9(j), такие, что |i' - j'| = 1.Рассмотрим в G маршрут M = 9(1), 9(2),... , 9(m + 1). Покажем, что это обход, т. е.любое ребро графа G входит в состав маршрута. В самом деле, пусть {9(k),9(/)} -ребро в G. Так как 9(k) и 9(/) смежны в G, то найдутся k' е 9(k) и /' е 9(/), такие,что k' и /' смежны в цепи Pm, т. е. |k' - Z'| = 1. Пусть l' = k' + 1. Тогда в M встретитсяфрагмент . . . , 9(k' - 1), 9(k'), 9(/'),..., и значит, ребро {9(k), 9(/)} входит в состав M.Таким образом, M - обход, и его длина равна m.Достаточность. Пусть G - произвольный связный граф и в нем есть обход длины m.Построим цепь, фактор-графом которой является граф G.Так как в графе G есть обход длины m, то каждая вершина при нумерации вершинвдоль обхода получит одну или более меток из натуральных чисел 1, 2 , . . . , m ,m +1.Наибольшая метка равна m + 1. В цепи Pm, вершины которой пронумерованы нату-ральными числами 1, 2, . . . , m, m + 1, рассмотрим отношение(i, j) е 9 ^ i и j -метки одной и той же вершины графа G.Очевидно, что отношение 9 - эквивалентность на множестве вершин цепи.Пусть (i, j) е 9 и i < j, т. е. при прохождении обхода некоторая вершина графа Gвстретилась на шаге i, а затем на шаге j. Понятно, что j ^ i + 2. Следовательно,вершины i и j не являются смежными в цепи Pm. Это означает, что все 9-классыявляются независимыми подмножествами, и значит, 9 - конгруэнция цепи Pm.Покажем, что граф G изоморфен фактор-графу Pm/9.Каждой вершине графа G сопоставим множество всех её меток. Тем самым устанав-ливается взаимно однозначное соответствие между вершинами графа G и 9-классами.Покажем, что это соответствие сохраняет отношение смежности.Пусть вершины u и v смежны в графе G. Это означает, что при обходе они былипройдены последовательно, например вершина v после u. Тогда существуют такиеметки i у вершины u и j у вершины v, что j = i + 1. Отсюда следует, что классы 9(i)и 9(j) смежны в фактор-графе Pm/9.С другой стороны, если классы 9(i) и 9(j) смежны в фактор-графе Pm/9, то в Pmсуществуют вершины i' е 9(i) и j' е 9(j), такие, что |i' - j'| = 1. Это означает, чтов графе G вершины, соответствующие классам 9(i) и 9(j), являются смежными.Таким образом, граф G изоморфен фактор-графу Pm/9. Следствие 1. Любой связный граф с m ребрами является фактор-графом це-пи P2m-1.Одной из открытых проблем является следующая: для данного связного графа Gнайти цепь с минимальным числом ребер p(G), фактор-графом которой является дан-ный граф.Напомним, что диаметром дерева называется максимальное расстояние между еговершинами.Теорема 3. Если T - дерево с m ребрами, имеющее диаметр d, то p(T) = 2m - d.Доказательство. Согласно лемме, любой граф с m ребрами имеет обход дли-ны 2m. Пусть R - минимальный обход дерева T, и пусть его длина r < 2m. Значит,в R есть ребро, проходимое один раз. Пусть таких ребер k штук. Пронумеруем ихв порядке обхода R. Покажем, что ребра, проходимые один раз, образуют в T цепь.Предположим, что это не так. Пусть ребра 1 = {u°,u} и 2 c началом v не инци-дентны. Рассмотрим в составе R маршрут R(u, v). Он содержит цепь P(u, v). Пусть еепервым ребром будет {u,u'}.Ребро {u,u'} в обходе R проходится больше одного раза.Представим обход R в виде R = Rinu°uRUMU'R^/u'uRUuu'RU/.. .uu/Rfin, где Rin -подмаршрут, соединяющий начальную вершину обхода R с вершиной u°; R f i n - под-маршрут, соединяющий вершину u/ с конечной вершиной обхода R; RU - подмаршрутыобхода R с началом и концом в u; RU/ - с началом и концом в u/.Заметим, что второй раз ребро {u,u/ } не может быть пройдено от u к u/, так какиначе после его прохождения нужно попасть из u/ в u по некоторому подмаршру-ту R(u/,u), а тогда в составе маршрута uu/R(u/,u) появляется цикл, что невозможнодля дерева. Таким образом, в составе R ребро {u, u/ } второй раз проходится от u/ к u.Теперь построим маршрут Rinu°uRURU ... RUuu/RU/ RU R U R f i n . Этот маршрутявляется обходом, так как он содержит все ребра, пройденные в составе R, а значит,все ребра дерева T. Его длина меньше, чем у R, что невозможно, ибо R минимален.Следовательно, предположение о том, что ребра, проходимые один раз, не образуютв T цепь, неверно, и в составе обхода R есть цепь P, состоящая из ребер, проходимыходин раз.Длина цепи P равна k. Но k ^ d, так как d - наибольшая длина цепи в дереве T.Пусть - длина части обхода R, проходимая по ребрам кратности ^ 2 в R.Тогда 2m > r = sm_k + k ^ 2(m - k) + k = 2m - k ^ 2m - d. Итак, каждый обходдерева T имеет длину не меньше чем 2m-d. Следовательно, 2m - d - это минимальнаявозможная длина обхода дерева T. Покажем, что обход длины 2m - d существует.Изобразим дерево T следующим образом. Пусть Pd - цепь длины d в дереве T,vi е Pd, i = 0, d - 1.Выберем висячую вершину v° е Pd в качестве корневой и припишем уровень i каж-дой вершине vi цепи Pd. Эти вершины могут быть смежны с некоторыми вершинами,не входящими в цепь Pd, они, в свою очередь, с другими вершинами и т.д. Такимобразом, каждая вершина vi е Pd, i = 1,d - 2, является корнем некоторого дерева Ti(среди этих деревьев могут быть пустые).Построим обход v°v1T1v1v2T2 ... vd-3vd_2Td_2vd_2vd-1. Согласно лемме 1, каждое де-рево Ti имеет обход длины, равной удвоенному числу его ребер, причем начинается изаканчивается он в вершине vi е Pd графа T.Отсюда и из теоремы 2 следует доказываемое утверждение, поскольку длина по-строенного обхода равна 2m - d, и этот обход минимален. Следствие 2. Для звезды Sm имеем p(Sm) = 2m - 2.Докажем теорему о верхней и нижней оценках p(G) для произвольного связногографа G с m ребрами.Теорема 4. Для связного графа G с m ребрами m ^ p(G) ^ 2m - 2.Доказательство. Первое неравенство следует из того, что количество реберв фактор-графе не может превышать количества ребер в исходном графе.Покажем, что в каждом связном графе G с m ребрами существует обход длины2m - 2. Рассмотрим два случая.1) Граф G имеет висячие вершины.Возьмем произвольную висячую вершину u, пройдем исходящее из неё ребро.Граф G* = G \ {u} связный и имеет m* = m - 1 ребер. По следствию 1, существуетобход графа G* длины 2m* - 1 = 2m - 3 и, следовательно, обход графа G длины 2m - 2.2) Граф не имеет висячих вершин.Отметим произвольную вершину u, не являющуюся точкой сочленения. Возьмемнекоторое исходящее из неё ребро, пусть другим его концом будет вершина v.Граф G* = G \ {u} связный и имеет m* = m - d ребер, где d - степень вершины u.По лемме 1 существует обход графа G* из вершины v длины 2(m - d). Вершина uс непройденными ребрами образует d-реберную звезду. Обойдем эту звезду, отправ-ляясь из вершины v. Согласно следствию 2, этот обход имеет длину 2d - 2. Такимобразом, получаем обход графа G длины 2(m - d) + 2d - 2 = 2m - 2. Заметим, чтоесли в m-реберном графе есть эйлеров путь, то этот граф является фактор-графом це-пи длины m (наименьшая возможная длина для цепи, факторизуемой на m-реберныйграф). С другой стороны, звезда Sm, имеющая m ребер, не может быть получена какфактор-граф цепи с длиной меньше чем 2m - 2. Следовательно, обе оценки являютсяточными.

Ключевые слова

дерево, звезда, фактор-граф, конгруэнция, цепь, обход, path, congruence, quotient-graph, tree, star

Авторы

ФИООрганизацияДополнительноE-mail
Карманова Евгения ОлеговнаСаратовский государственный университет им. Н. Г. Чернышевскогоаспиранткаlkb@info.sgu.ru
Всего: 1

Ссылки

Карманова Е. О. О конгруэнциях цепей и циклов // Компьютерные науки и информационные технологии. Саратов: Изд-во Сарат. ун-та, 2009. С. 238.
Prodinger H. and Tichy R. F. Fibonacci numbers of graphs // Fibon. Quart. 1982. V. 20. No. 1. P. 16-21.
Мирзаянов М. Р. О минимальных сильно связных конгруэнциях ориентированных цепей // Изв. Сарат. ун-та. Сер. Математика. Механика. Информатика. 2006. Т. 6. Вып. 1/2. С.91-95.
Мирзаянов М. Р. Сильно связные конгруэнции ориентированных графов // Теоретические проблемы информатики и ее приложений. Саратов: Изд-во Сарат. ун-та, 2006. Вып. 7. С.104-114.
Верзаков Г. Ф., Киншт Н. В., Рабинович В. И., Тимонен Л. С. Введение в техническую диагностику. М.: Энергия, 1968.
Абросимов М. Б. Некоторые вопросы о минимальных расширениях графов // Изв. Сарат. ун-та. Сер. Математика. Механика. Информатика. 2005. Т. 5. Вып. 1. С. 86-91.
Оре О. Теория графов. 2-е изд. М.: Наука, 1980. 336 с.
Hayes J. P. A graph model for fault-tolerant computing systems // IEEE Trans. Comput. 1976. No. 9. P. 25.
Салий В. Н. Оптимальные реконструкции графов // Современные проблемы дифференциальной геометрии и общей алгебры. Саратов: Изд-во Сарат. ун-та, 2008. С. 59-65.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, Физматлит, 1997. 367 с.
 О конгруэнциях цепей | ПДМ. 2011. № 2(12).

О конгруэнциях цепей | ПДМ. 2011. № 2(12).

Полнотекстовая версия