Упорядоченное множество конгруэнций цепи



Скачать 148.99 Kb.
Дата04.07.2013
Размер148.99 Kb.
ТипДокументы
УПОРЯДОЧЕННОЕ МНОЖЕСТВО КОНГРУЭНЦИЙ ЦЕПИУПОРЯДОЧЕННОЕ МНОЖЕСТВО КОНГРУЭНЦИЙ ЦЕПИ

Е. О. Карманова

Саратовский государственный университет им. Н. Г. Чернышевского, Саратов, Россия

Пусть Pm – неориентированная m-реберная цепь, и пусть в цепи Pm вершины пронумерованы обозначены натуральными числами 0,1,2,…, m. Под конгруэнцией цепи Pm понимается отношение эквивалентности на множестве ее вершин, всекаждый классы которого еявляется независимыми

Совокупность подмножестваоми, т.е. состоит из попарно несмежных вершин (см.[1]). Совокупность всех конгруэнций цепи Pm обозначим через Con Pm. Пусть θ – конгруэнция цепи Pm. Так как Con Pm – непустое множество, упорядоченное теоретико-множественным включением, то пПара (Con Pm, ) будет упорядоченным множеством. Так как для любых двух элементов θ1 и θ2 в упорядоченном множестве (Con Pm, ) существует inf(θ1,θ2) = θ1θ2, то (Con Pm, ) – нижняя полурешетка. Наименьшим элементом ееупорядоченного множества (Con Pm, ) является его тождественная конгруэнция ∆.

Пусть u и v – любые две несмежные вершины цепи Pm. Главной конгруэнцией, порожденной парой u, v, называется наименьшая конгруэнция θ(u,v), отождествляющая вершины u и v. Очевидно, что такие конгруэнции являются атомами в полурешетке (Con Pm, ), так как не существует такой конгруэнции θ*, что ∆θ*θ(u,v). Количество главных конгруэнций цепи Pm, т.е. атомов в (Con Pm, ), равно .
Наибольшего элемента в (Con  Pm, ), при m3 нет. Покажем это на простом примере. Возьмем, например, главные конгруэнции θθ(0,2) θ и θθ((0,3)θ, которые есть практически у любой цепи Pm ,при m3. У этих конгруэнций нет общей верхней грани: если θ содержит θθ(0,2) и θθ(0,3), то = в силу транзитивности пара (2,3) θθ(0,2,3)θ, что невозможно, так как но вершины 2 и 3 смежные, поэтому это невозможно.

Конгруэнция θmin упорядоченного множества (Con Pm, ) будет минимальной, если в (Con Pm, ) нет конгруэнции θ, такой что θ θmin. Аналогично, кКонгруэнция θmax будет максимальной в (Con Pm, ), если в этом упорядоченном множестве нет конгруэнции θ*, такой, что θ* θmax.

Так как для любых двух элементов θ1 и θ2 в упорядоченном множестве (Con Pm, ) существует inf(θ1,θ2) = θ1θ2, то (Con Pm, ) – нижняя полурешетка.

Пусть u и v – любые две несмежные вершины цепи Pm. Главной конгруэнцией, порожденной парой u, v, называется наименьшая конгруэнция θ(u,v), отождествляющая вершины u и v. Очевидно, что такие конгруэнции являются атомами в полурешетке (Con Pm, ), так как не существует такой конгруэнции θ*, что ∆ θ* θ(u,v). Количество главных конгруэнций цепи Pm будет .

Длиной конечной убывающей цепи a1>a2>…>an естьназывается уменьшенное на единицу число элементов в ней.

Высотой элемента в конечном упорядоченном множестве называется наибольшая из длин убывающих цепей, начинающихся с этого элемента. Высота элемента a обозначается через h(a). Например, любой минимальный элемент имеет высоту 0.

ТЕОРЕМА 1. В полурешетке (Con Pm, ) высота конгруэнции θi,iI равна h(θi) = m+1-c(θ)i|k, где |θi| kc(θ) –- число классов конгруэнции θi,iI.

Доказательство.

Докажем теорему с помощью математической индукции по m.

Базис индукции. Для случаев m =1 и m =2 утверждение очевидным образом выполняется.

Базис индукции:Пусть m=3. Полурешетка (Con P3, ) имеет три уровня: на нулевом уровне находится тождественная конгруэнция θ1=Δ, на первом – дветри конгруэнции: θ2={0,2}{1}{3}, и θ3={0,3}{1}{2}{0}{1,3}{2}, θ4={0}{1,3}{2}, на втором – конгруэнция θ54={0,2}{1,3}, то естьоткуда

h(θ1) = 3+1- c(θ1) 1|=3+1-4=0;

h(θ2) = 3+1- c(θ2) 2|=3+1-3=1;

h(θ3) = 3+1-|θ c(θ3) 3|=3+1-3=1;

h(θ4) = 3+1- c(θ4) =3+1-3=1;

h(θ54) = 3+12- c(θ5) |θ4|==3+1-2=2.

ОчевидноТаким образом, что утверждение теоремы выполняется.

Шаг индукции. Предположим, доказываемое утверждение верно для m=k, т.е. h(θ) = k+1-c(θ) для любой конгруэнции θ Con PkCon Pm-1. Докажем, что оно верно и для m=k+1, т.е. что h(θ*) = k+2-c(θ*) для любой конгруэнции θ*Con Pk+1 Con Pm.

полуКаждая конгруэнция θ*Con Pk+1 получается из некоторой конгруэнции θCon Pk одним из двумях способамиов: 1) присоединением нового класса {k+1}; 2) добавлением в один из θ-классов вершщины k+1, кроме класса, содержащего вершину m-k1. В первом случае h(θ*)=h(θ*) в полурешетках (Con Pk+1Pk, ) и (Con  Pk+1, ) соответственно и c(θ*)= c(θ)+1, т.еоткуда. h(θ*)= h(θ)= k+1-c(θ*)= k+1-(c(θ*)-+1)= k+2-c(θ*), а во втором h(θ*)=h(θ*)+1 и c(θ*)=c(θ), откуда h(θ*)=h(θ)+1== k+1-c(θ)+1= k+2-c(θ*). Исходя из этого, получаем, что для любой конгруэнции θ*Con Pk+1 верно равенство h(θ*)= (k+1)+1-c(θ*) = k+2-c(θ*)|k. □

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

ТЕОРЕМА 2. Полурешетка (Con Pm, ) имеет длину m-1.

Доказательство.

ойМаксимальной ейконгруэнцией θ с наименьшим количеством классов будет конгруэнция θ, состоящая из двух θ-классов, в одном классе – все четные четные номера вершины цепи Pm, в другом – все нечетные,. тТаким образом, высота данной конгруэнции по теореме 1 будет h(θ) = m+1- |θ|kc(θ) = m+1-2 = m-1. □

Пусть θ — некоторая конгруэнция цепи Pmграфа G. Факторграфом цепи Pmорграфа G по конгруэнции θ называется граф = (, αθ), где — множество классов конгруэнции θ, а αθ = {(θ(v1), θ(v2)): (u1θ(v1), u2θ(v2)) ((u1,  u2)  α)}, где α – отношение смежности в цепи Pm.

Понятие факторграфа по конгруэнции

ТеоремаЕОРЕМА 3. Конгруэнция θmax будет максимальной в (Con Pm, ), тогда и только тогда, когда факторграф будет полным графом.

Доказательство.

Необходимость. Пусть конгруэнция θmax будет максимальной в (Con Pm, ), то есть в (Con Pm, ) нет конгруэнции θ*, такой что θ*θmax. У всякой конгруэнции θ цепи Pm классы являются независимыми подмножествами, то. есть. (i, j)θ: (i и j – несмежные вершины цепи Pm).

Предположим противное, что не будет полным графом. Тогда существуют классы θmax(u) и θmax(v) не смежные в , то есть никакие uθmax(u) и vθmax(v) не будут смежными в цепи Pm.

Так как θmax(u) и θmax(v) не смежны в , то, оОбъединив классы θmax(u) и θmax(v), получим новую конгруэнцию θ*(u,v) вцепи (Con Pm, ).

Таким образом,При этом получается, что θ*θmax в (Con Pm, ), то.  есть. конгруэнция θmax не будет максимальной, а это противоречит условию теоремы.

Достаточность. Пусть будет полныйм графом. Покажем, что конгруэнция θ будет максимальной в (Con Pm, ).

Так как – полный граф, то каждая его вершина соединенмежна со всеми другими, то есть любые классы θ(u) и θ(v) соединены ребром {θ(u), θ(v)} в , а значит, найдутся такие uθ(u) и vθ(v), что u′ и v′ смежны в цепи Pm.

Предположим, что конгруэнция θ не будет максимальной в (Con Pm, ), то. есть. θ*θ* в (Con Pm, ) что для некоторой θ* Con Pm..

Пусть u и v – вершины цепи Pm, такие что (u,v)θ, то. есть. θ(u)θ(v) в , и. По предположению, θ* θ*, тогда пусть (u,v)θ*. Таким образомТогда, (uθ(u),vθ(v))((u′,v′)α), где α – отношение смежности в цепи Pm. и Следовательно, (u′,v′) θ*, что невозможно, так как вершины u′ и v′ смежны в цепи Pm.

Таким образом, показано, что не существует такой конгруэнции θ* в (Con Pm, ), что θ*θ*, то. есть. конгруэнция θ будет максимальной в (Con Pm, ), то есть θ= θmax. □

Согласно теореме 3, число максимальных конгруэнций в полурешетке (Con Pm, ) будет равно числу полных графов, на которые факторизуется цепь Pm. Найдем среди них полный граф Kn с наибольшим количеством вершин n., Заметим, чтотак как если цепь Pm будет факторизоваться на полный граф Kn, то также она будет факторизоваться на любой полный граф Kl, l=2,…,n-1. Можно показать, что длина кратчайшей цепи, факторизующейся на Kn, Согласно [1],есть , p(Kn) = , еслипри n – нечетном и p(Kn) = , еслипри n – четном, где p(KnG) – это цепь с минимальным возможным числом ребер, факторграфом которой является граф KnG.

Определим Таким образом, для полполногоныйого графа Kn с наибольшим четным количеством вершин n, если n – четно, являющийегося факторграфом цепи Pm. , Очевиднополучаем, что n = .

Далее Ппроверяемим, является ли граф Kn, факторграфом цепи Pm, имеющийм с наибольшимеенаибольшее количеством вершин, или цепь Pmсуществуе факторизуется нат граф Kn+1, на который факторизуется цепь Pm. Так как n+1 – нечетное число, то должно быть проверим условие: m. Если m удовлетворяет данному условию, то полный граф Kn+1 является факторграфом цепи Pm и наибольшим по числу вершин.

Конгруэнция θпр Conпр Pm цепи Pm будет называется правильной, тогда и только тогда, когдаесли (i, j)θ: (i и j – номера вершины цепи Pm одной четности). Обозначим множество правильных конгруэнций через Conпр Pm . Определим четную конгруэнцию θ цепи Pm, как такую конгруэнцию θ, что (i, j)θ: (i и j – четные номера вершины цепи Pm), а нечетную конгруэнцию θ, как (i, j)θ: (i и j – нечетные номера вершины цепи Pm). Обозначим множество четных конгруэнций через Conч Pm. Аналогично определим множество нечетных конгруэнций Conн Pm.Будет различать четные и нечетные конгруэнции, то есть θч Conч Pm и θн Conн Pm соответственно.

Так как (Conпр Pm, ) является нижней полурешеткойтеоретико-множественное пересечение двух конгруэнций снова является конгруэнцией и в (Conпр Pm, )ней есть наибольший элемент, который также является конгруэнцией, то упорядоченное множество (Conпр Pm, ) – решетка. (Ннаибольшим элементом в (Conпр Pm, ), очевидно, будет конгруэнция с двумя классами, в одном классе которой будут все четные вершины цепи Pm, в другом – все нечетные).

Прямым произведением X Y двух упорядоченных множеств X и Y называется множество всех пар (x,y), где x X и y Y, причем (x1,y1) (x2,y2) тогда и только тогда, когда x1 x2 в X и y1 y2 в Y.

ТЕОРЕМА 4.: Conпр Pm Conч Pm Conн Pm = Conпр Pm.

Доказательство.

Согласно определению, прямым произведением Conч Pm Conн Pm будет множество всех (θч, θн), где θч Conч Pm и θн  Conн Pm, причем (,) (,) тогда и только тогда, когда в Conч Pm и в Conн Pm.

Требуемый изоморфизм получается, если каждой конгруэнции θConпр  Pm сопоставить пару (θ1, θ2), где θ1 – эквивалентность, нетривиальными классами которой являются в точности θ-классы, состоящие из четных вершин цепи, а θ2 имеет нетривиальными классами в точности θ-классы, состоящие из нечетных вершин. Очевидно, что что θ1 Conч  Pm и θ2 Conн  Pmвсе такие конгруэнции будут правильными, так как (i, j) θч i и j – четные номера вершины цепи Pm и(i, j) θн i и j – нечетные номера вершины цепи Pm. Это удовлетворяет определению правильной конгруэнции. □

ТЕОРЕМА 5. Всякая решетка эквивалентностей конечного множества изоморфна решетке четных конгруэнций подходящей цепи.

Доказательство.

Рассмотрим решетку (E(m), ) – всех ээквивалентностей на множестве {0, 1, 2, … m}{0, 1, 2, …, m}с. Возьмем произвольную эквивалентность на множестве {0, 1, 2, …, m}. Построим решетку (E*(m), ) следующим образом: кКаждый элемент i, i=, в каждойм -классе эквивалентности ε(E(m),) заменим на 2i. Получим эквивалентность θ() на решетку эквивалентностей множества {0,2,4, …. , 2m}, то есть все возможные разбиения множестваемножестве четных чисел 2m, все классы которой будут независимыми подмножествами цепи P2m., т.е. получим четную конгруэнцию цепи P2m

. С другой стороны, если θ Conч P2m , то заменим в каждом θ-классе элемент i {0, 2, 4, …, 2m} на i/2, получим эквивалентность (θ) на множестве {0,  1, 2, …, m}. При этом если 1 2 в E(m), то θ(1) θ(2), и обратно если θ 1 θ 2, то (θ 1) (θ 2). Значит, решетки (E(m), ) и (Conч P2m, ) изоморфны. Возьмем для рассмотрения решетку (Conч P2m, ) и пусть m – четно. По определению, Conч P2m - это решетка таких конгруэнций θч Conч P2m, что (i, j)θ: (i и j – четные номера вершины цепи P2m),. тТаким образом, получается, что (Conч P2m, ) - множество всевозможных разбиений на множестве {0,2,4, …. , 2m}. Очевидно, что (Conч P2m, ) (E(m), ), если m – четно. Аналогично доказывается, если m – нечетно. □

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

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

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

  1. Карманова Е.О. О конгруэнциях цепей // Прикладная дискретная математика. – 2011. – № 2 (12). – С. 96–100. ISSN 2071-0410.

  2. P. Pudlák, J. Tuma: Every finite lattice can be embedded in a finite partition lattice, Algebra Universalis, Vol.10, 1980, pp.74-95.

Похожие:

Упорядоченное множество конгруэнций цепи iconЗакон Ома для участка цепи Электрическим током называется
Б. упорядоченное движение заряженных частиц. B. упорядоченное движение электронов
Упорядоченное множество конгруэнций цепи iconКомплексная методика создания логистической сбытовой цепи (лсц)
Таким образом, логистическая сбытовая цепь (лсц) это упорядоченное (оптимизированное) множество субъектов, осуществляющих доведение...
Упорядоченное множество конгруэнций цепи icon7-8 классы Модуль 1: Основы теории множеств
С математической точки зрения вместо разных слов можно использовать одно «множество»: множество учеников, множество берез, множество...
Упорядоченное множество конгруэнций цепи iconОпределение числовой последовательности и её предела
Если каждому натуральному числу n=1,2,3,… по некоторому правилу поставлено в соответствие единственное число хn, то полученное упорядоченное...
Упорядоченное множество конгруэнций цепи iconАдрес: Россия. 188760. Ленинградская область
По этим формулам можно находить пифагоровы тройки, однако представить эти тройки как упорядоченное множество достаточно затруднительно,...
Упорядоченное множество конгруэнций цепи iconБинарные отношения. Отношение эквивалентности и разбиение на классы, фактор-множество
Поле. Простейшие свойства поля. Поле рациональных чисел. Примеры полей. Упорядоченное поле. Система действительных чисел
Упорядоченное множество конгруэнций цепи iconИсследование цепи постоянного тока
Цель работы: опытным путем определить потери напряжения и мощности в цепи в зависимости от тока в цепи. Определить внутреннее сопротивление...
Упорядоченное множество конгруэнций цепи iconМетодические указания и контрольные задания по дисциплине: «Электротехника и электроника» для студентов заочного отделения
Охватывают весь основной курс «Электротехника и электроника» по разделам: электрическое поле, электрические цепи постоянного тока,...
Упорядоченное множество конгруэнций цепи iconУрок 46 Тема урока: Параллельное соединение проводников
В, лампочки от карманного фонаря сопротивлением 13,5Ом, двух спиралей сопротивлением 3 и 2 Ом, ключа и соединительных проводов. Все...
Упорядоченное множество конгруэнций цепи iconТема магнитные цепи и их расчет
При­мером простой магнитной цепи может служить сердечник коль­цевой катушки (см рис. 3, а). Магнитные цепи трансформато­ров, электрических...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org