Конгруэнции цепей: некоторые комбинаторные свойства | ПДМ. 2012. № 2(16).

Конгруэнции цепей: некоторые комбинаторные свойства

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

Congruence relations of paths: some combinatorial properties.pdf Ориентированным графом (орграфом) называется пара G = (V, а), где V - конеч-ное непустое множество вершин; а - отношение (смежности) на V. Пары в а называ-ются дугами орграфа G. Основные понятия приводятся в соответствии с [1].Пусть е - некоторое отношение эквивалентности на множестве вершин V оргра-фа G. Фактор-графом орграфа G по эквивалентности е называется орграф G/е == (V/e,a. ) , где V/е - множество классов эквивалентности е; а. = {(e(v1 ),e(v2)) :3^1 е e(v1) 3u2 e e(v2) ( ( u b u2) e а ) }.Пусть K - некоторый класс орграфов. Конгруэнцией K-графа G называется такоеотношение эквивалентности 9 на V, что фактор-граф G/9 является K-графом. В [2]рассмотрен случай, когда K - класс сильно связных орграфов, и предложен способпостроения сильно связной конгруэнции произвольного орграфа, наибольшей по числувершин в фактор-графе. В [3] установлено, что n-элементная ориентированная цепьимеет 2n - 3 минимальных сильно связных конгруэнций.В качестве класса K возьмём класс неориентированных графов.Под неориентированным графом (или, для краткости, графом) понимается параG = (V, а) , где а - симметричное и антирефлексивное отношение на множестве вер-шин V. В графе пара встречных дуг (u,v), (v,u) рассматривается как один элемент,называемый ребром { u , v } . Вершины u и v по определению инцидентны ребру { u , v }.Множество вершин графа называется независимым, если любые две вершины изэтого множества несмежны. Очевидно, что отношение эквивалентности 9 на множествевершин графа G = (V, а) тогда и только тогда будет конгруэнцией этого графа, когдакаждый 9-класс образует в G независимое подмножество.Пусть Pm - неориентированная m-рёберная цепь, и пусть её вершины пронумерова-ны натуральными числами 0,1, 2 , . . . , m. Через ConPm обозначим множество всех кон-груэнций цепи Pm, а через E (m) -множество всех эквивалентностей на m-элементноммножестве. Количество элементов в E(m) называется числом Белла B(m). В работе [4]высказана гипотеза о том, что |Con(Pm)| = B(m), то есть что |Con(Pm)| = |E(m)|. Ни-же приводится доказательство этого факта.Напомним, что числом Стирлинга второго рода s2(m, k) называется количествовсех эквивалентностей с k классами на m-элементном множестве. Очевидно, чтоm. s2(m,n) = B(m). Известно, что s2(m,k) = s2 (m - 1,k - 1) + ks2(m - 1,k) дляn=10 < k < m (рекуррентная формула для чисел Стирлинга второго рода). Числа Беллаи Стирлинга для графов рассматривались, например, в работе [5].Пусть c(Pm, k) - количество всех конгруэнций цепи Pm с k классами. Очевидно, чтоm+1если Con(Pm) -множество всех конгруэнций цепи Pm, то |Con(Pm)| = . c(Pm, k).k=2Теорема 1. |Con(Pm)| = | E (m)|.Доказательство. Методом математической индукции докажем равенствоc(Pm, k + 1) = s2(m, k) для 1 ^ k ^ m.Базис индукции: m = 2. Цепь P2 имеет две конгруэнции: одна с двумя класса-ми {0, 2}, { 1 } , вторая с тремя классами { 0 } , { 1 } , { 2 } , таким образом, c(P2, 2) = 1 иc(P2, 3) = 1. Так как двухэлементное множество { 0 , 1 } имеет два разбиения - однос одним блоком { 0 , 1 } , второе с двумя блоками { 0 } , { 1 } , то s2(2,1) = 1, s2(2, 2) = 1.Шаг индукции. Предположим, что c(Pm,k + 1) = s2(m,k), 1 ^ k ^ m, верно дляцепи Pm и цепей длины меньше m, и покажем, что c(Pm+1,k + 1) = s2(m + 1,k),1 ^ k ^ m + 1.Заметим, что из каждой конгруэнции в с k +1 классами цепи Pm можно получитьконгруэнции с k + 1 классами цепи Pm+1 двумя способами. Первый способ: добавивв один из k в-классов (кроме класса в(ш)) вершину m + 1, получаем разбиение мно-жества вершин цепи Pm+1 , все k +1 классов которого будут независимыми, и, следо-вательно, разбиение является конгруэнцией цепи Pm+1. Таких возможностей имеетсяkc(Pm, k + 1). Второй способ: создаём новый класс {m + 1}, который вместе с классамиконгруэнции в образует разбиение множества вершин цепи Pm+1 . У этого разбиения всеклассы образуют независимые подмножества, т.е. получаем конгруэнцию цепи Pm+1.Этим способом может быть получено c(Pm, k) конгруэнций цепи Pm+1 . Таким образом,c(Pm+1, k + 1) = c(Pm, k) + kc(Pm, k + 1).Ввиду предположения индукции и рекуррентной формулы для чисел Стирлингавторого рода запишем c(Pm+1,k + 1 ) = c(Pm,k) + kc(Pm,k+1) = s2(m,k - 1)+ks2(m, k) == s2 (m + 1, k). Тем самым доказано равенство c(Pm, k + 1) = s2(m, k), 1 ^ k ^ m.m+1Докажем теперь, что |Con(Pm)| = |E (m)|. В самом деле, |Con(Pm)| = . c(Pm ,k) =k=2m m= . c(Pm,k) = . s2(m,k) = |E(m)|. k=1 k=1В [4] обсуждалась также задача нахождения для данного связного графа G цепис минимально возможным числом ребер p(G), фактор-графом которой является G.Задача китайского почтальона для произвольного связного графа [6] состоит в на-хождении кратчайшего обхода, начинающегося и заканчивающегося в одной и тойже вершине и содержащего все рёбра графа (рёбра в этом обходе могут повторятьсяв случае необходимости). Используя один из алгоритмов, связанных с этой задачей [7],докажем следующую теорему.Т е о р е м а 2. Пусть G - связный граф. Тогда p(G) = m +1 - k, где m - количестворёбер графа G; l - количество рёбер в минимальном цепном паросочетании на мно-жестве вершин нечётной степени (нечётных вершин) графа G; k - максимальная издлин цепей в таких паросочетаниях.Доказательство. Пусть дан произвольный связный граф G c m рёбрами и n вер-шинами. Найдем длину наименьшей цепи Pr, факторизующейся на G. Так как связныйграф тогда и только тогда является фактор-графом r-рёберной цепи, когда в нем естьобход длины r [4, теорема 1], то найдем длину r минимального обхода R.Рассмотрим случай, когда граф G не имеет эйлерова пути, поскольку иначе этотграф имеет обход длины m. Тогда в графе G существуют ребра, проходимые в R болеечем один раз.Построим обход графа G, используя алгоритм решения задачи китайского поч-тальона.Пусть V* - множество нечётных вершин графа G. Так как G не содержит эйлеро-вых цепей, то число таких вершин больше двух и чётное.Пусть M - множество цепей между концевыми вершинами v и vj, v, vj е V*,i = j, в графе G, таких, что никакие две цепи не имеют одинаковых концевых вершини каждая вершина из V* является концом какой-нибудь цепи. Такое множество цепейназывается цепным паросочетанием; количество цепей в M равно |V*|/2.Следуя [7], строим все минимальные (по числу рёбер) цепные паросочетания намножестве нечётных вершин V* графа G. В силу минимальности никакие две цепив таком паросочетании не имеют общих рёбер. Выберем цепь наибольшей длины извсех минимальных цепных паросочетаний. Пусть это будет цепь длины k из цепногопаросочетания M* , соединяющая вершины u и v. Далее удвоим все ребра, входящиев M*, кроме рёбер, входящих в цепь максимальной длины.Таким образом, получим мультиграф G* с двумя нечётными вершинами u и v.Мультиграф G* имеет эйлеров путь из u в v (или из v в u). Следовательно, граф Gимеет минимальный обход R длины m + / - k, где / - количество рёбер в минимальномцепном паросочетании M* на множестве нечётных вершин V* графа G. Значит, p(G) == m + / - k. Полный граф с n вершинами обозначается Kn . Каждая его вершина имеет степеньn - 1. Число рёбер в графе Kn равно n(n - 1)/2.С л е д с т в и е 1. Для полного графа Kn имеем:1) p(Kn ) = n(n - 1)/2, если n нечётно;2) p(Kn ) = n 2 / 2 - 1, если n чётно.Доказательство. Первый случай очевиден, так как полный граф с нечётнымколичеством вершин эйлеров.Во втором случае используем результат теоремы 2: p(G) = m + / - k. Так как всевершины полного графа Kn при чётном n являются нечётными, то / = n/2. Используятот факт, что в полном графе каждая вершина соединена со всеми другими, получаемk = 1. В итоге имеем p(G) = n(n - 1)/2 + n / 2 - 1 = n 2 / 2 - 1. Звезда - это граф, все ребра которого инцидентны одной и той же вершине. Звездус m рёбрами будем обозначать Sm.С л е д с т в и е 2 (см. также [4]). Для звезды Sm имеем p ( Sm) = 2m - 2.Доказательство. Так как у звезды Sm нечётными будут либо все вершины,либо m вершин, то все ребра звезды Sm входят в минимальное цепное паросочетаниена множестве её нечётных вершин, то есть / = m. Наибольшая длина цепи в паросо-четании равна 2. Таким образом, p(G) = m + / - k = m + m - 2 = 2m - 2.

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

цепь, конгруэнция, отношение эквивалентности, фактор- граф, число Белла, path, congruence relation, equivalence relation, quotient-graph, Bell number

Авторы

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

Ссылки

Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997. 367 с.
Мирзаянов М. Р. Сильно связные конгруэнции ориентированных графов // Теоретические проблемы информатики и ее приложений. Вып. 7. Саратов: Изд-во Сарат. ун-та, 2006. С.104-114.
Мирзаянов М. Р. О минимальных сильно связных конгруэнциях ориентированных цепей // Изв. Сарат. ун-та. Сер. Математика. Механика. Информатика. 2006. Т. 6. Вып. 1/2. С.91-95.
Карманова Е. О. О конгруэнциях цепей // Прикладная дискретная математика. 2011. № 2(12). С. 96-100.
Duncan B. and Peele R. Bell and Stirling numbers for Graphs // J. Integ. Sequenc. 2009. V. 12. Article 09.7.1.
Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. С. 227-239.
Bellman R. and Cooke K. L. The Konigsberg bridges problem generalized // J. Math. Anal. Appl. 1969. No. 25. P. 1-7.
 Конгруэнции цепей: некоторые комбинаторные свойства | ПДМ. 2012. № 2(16).

Конгруэнции цепей: некоторые комбинаторные свойства | ПДМ. 2012. № 2(16).

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