Книги, научные публикации Pages:     | 1 | 2 | -- [ Страница 1 ] --

САНКТЦПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ В. Ф. ГОРЬКОВОЙ ЛЕКЦИИ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ САНКТ - ПЕТЕРБУРГ 2004 УДК 519.8 Р е ц е н з е н т ы: проф. Чернецкий В. И. (Петрозав.гос. ун-т) проф.

Романов М. Ф (С.-Петерб.гос.политехн. ун-т) Печатается по постановлению Редакционно-издательского совета факультета прикладной математики-процессов управле ния Санкт-Петербургского государственного университета Г о р ь к о в о й В. Ф.

ЦЛекции по дискретной математике. Ч СПб.:

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

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

Библиогр. 10 назв. Ил. й В.Ф.Горьковой, ISBN й МНОЖЕСТВА И ФУНКЦИИ.

1.1. Множества и подмножества.

О п р е д е д е л е н и е 1. Система, состоящая из множества элементов a1, a2,..., an,..., над которыми определены операции типа сложения или умножения, не выводящие за пре делы данного множества, называется алгебраической системой.

В дальнейшем мы будем употреблять следующие обозначения.

Z - все целые числа, включая нуль.

Q - все рациональные числа.

R - все вещественные числа.

C - все комплексные числа.

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

P - множество всех целых положительных чисел {1, 2, 3,...}.

N - множество всех неотрицательных целых чисел {0, 1, 2,...}.

Подмножеством S множества T называется любое множество, все элементы которого принадлежат T, т.е. из a S следует, что a T. Это отношение включения записывается так: S T. Оно обладает следующими свойствами:

S S для любого множества S, (1.1.1) из S T и T U следует, чтоS U. (1.1.2) Свойство (1.1.1) называется рефлексивным свойством, а(1.1.2) Ч транзитивным.

S = T тогда и только тогда, когда S T и T S. (1.1.3) Множество всех подмножеств ( частей) данного множества U обозначается через P(U).

Например, множество подмножеств U = {a, b, c} содержит шесть собственных подмножеств: {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, пустое множество и само множество U. Если U состоит из n раз личных элементов a1, a2,..., an, то P(U) состоит из 2n различных подмножеств.

1.2. Булевы алгебры.

О п р е д е л е н и е 2. Бинарной операцией на множес тве S называется правило, которое каждой упорядочной паре (a, b) элементов из S ставит в соответствие третий элемент s Ч значение этой операции на паре (a, b). Примерами таких опе раций являются сложение и умножение на множестве Z целых чисел.

О п р е д е л е н и е 3. Унарной операцией на множестве S называется правило f, которое любому элементу a S ста вит в соответствие однозначно определенный элемент f(a) S, значение операции f на a.

На множестве подмножеств данного множества U определе ны две бинарные операции и одна унарная. Это Ч операции теоретико-множественного пересечения, объединения и дополне ния;

они называются также булевыми.

Обозначим через n(S) число элементов множества S. Если R и S Ч конечные множества, не имеющие общих элементов, то n(R S) = n(R) + n(S). Для любых конечных множеств R и S справедливо соотношение n(R S) = n(R) + n(S) - n(R S).

В качестве примера рассмотрим подмножества M = {mk} и N = {nk} всех целых чисел кратных m, n Z. Тогда M N совпадает с множеством всех целых чисел кратных и m и n.

Пусть S Ч любое подмножество U. Множество тех элементов x U, которые не принадлежат S называется дополнением S и обозначается S.

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

L1. S S = S, S S = S (идемпотентность).

L2. S T = T S, S T = T S (коммутативность).

L3. R (S T ) = (R S) T, R (S T ) = (R S) T (ассоциативность).

L4. S (S T ) = S (S T ) = S (поглощение).

L5. Если R T, то R (S T ) = (R S) T (модулярный закон).

L6. R (S T ) = (R S) (R T ), R (S T ) = (R S) (R T ) (дистрибутивность).

L7. R =, R = R, R U = R, R U = U (универсальные границы, нижняя и верхняя).

L8. R R =, R R = U (дополняемость).

L9. (S) = S (инволютивный закон).

L10. (S T ) = S T и (S T ) = S T (законы де Моргана).

Докажем первый закон дистрибутивности. Если x R(S T ), то x R и либо x S, либо x T. В первом случае x R и x S, поэтому x R S. Аналогично, во втором случае x R T.

Следовательно, в любом случае либо x R S, либо x R T, так что x (R S) (R T ). Это показывает, что R (S T ) (R S) (R T ).

Обратно, пусть x (R S) (R T ), т.е. либо x R S, либо x R T. Значит, в любом случае x R, а также в любом случае либо x S, либо x T. Таким образом, x R и x S T, а поэтому x R (S T ), т.е.

(R S) (R T ) R (S T ).

Объединяя этот результат с последней формулой предыдущего аб заца и используя (1.1.3), получим первый из двух законов дистри бутивности L6.

П р и м е р 1. Пусть U = {a} Ч одноэлементное множество.

Переобозначив U через l, а через 0, получим простейшую нетри виальную булеву алгебру [P({a}),,, ], операции в которой задаются следующими таблицами:

0 l 0 l 0 0 0 0 0 l 0 l l 0 l l l l l П р и м е р 2. Пусть U = {a, b}, тогда P(U) = {, {a}, {b}, U}.

Введем обозначения: = 0, {a} = S, {b} = S, U = I. Тогда булева алгебра {0, S, S, I} определена следующими таблицами 0 S S l 0 S S l x x 0 0 0 0 0 0 0 S S l 0 l S 0 S 0 S S S S l l S SТ S 0 0 S S S S l S l SТ S l 0 S S l l l l l l l УПРАЖНЕНИЯ 1.Положим S + T = (S T ) (S T ).

Найти необходимые и достаточные условия для того, чтобы S+T = ST.

2. a) Доказать, что S S (S T ) и S S (S T ).

б) Доказать, что S = S (S T ).

3. Доказать, что S T в том и только в том случае, если S T = U.

4. a) Доказать, что любое из трех соотношений S T, S T = S и S T = T между подмножествами данного множества U влечет два других (закон согласованности).

б)Доказать, что для любых элементов S, T любой булевой алгебры свой ства S T = S и S T = T равносильны.

5. Используя непосредственно существование универсальных границ и закон согласованности, доказать, что S U = U, S =, S U = S, S = S.

В упражнениях 6 и 7 следует пользоваться только тождествами L Ч L10.

6. a) ПоложивR + S = (R S) (R S), доказать тождества R + S = S + R, R + (S + T ) = (R + S) + T и R + R =.

б) Положив S - T = S T, доказать, что S + T = (S T ) - (S T ).

7. Исходя из определения булевой алгебры, доказать тождества:

а)S + S =, S + I = S, S + = S, S + S = I, б) S + T = S + T, (R + S) T = (R T ) + (S T ), в) R (S - T ) = (R S) - (R T ).

1.3. Функции О п р е д е л е н и е 4. Пусть S и T Ч множества.

Функцией f из области S в кообласть T называется правило, которое сопоставляет каждому элементу s S единственный элемент из T, называемый значением f в s и обозначаемый через f(s).

Мы будем также говорить, что f является функцией (или ото бражением, преобразованием) из S в T, и писать f : S T. Обра зом Im f отображения f : S T называется множество f(S) всех значений f(s), которые оно принимает при всевозможных s S.

Образ f является подмножеством кообласти T.

Один из способов задания функции Ч перечисление значений, которые она принимает на элементах области. Например, функция с областью S = {a, b, c}, кообластью T = {a, b, c, d} и образом f(S) = {a, b} задается предписанием f : a a, b a, c b.

Другая функция g : S T с образом g(S) = {b, c, d} задается предписанием g : a d, b c, c b.

Очевидно, к образам этих функций можно применять булевы операции: в наших примерах f(S)g(S) = {a, b, c, d} и f(S)g(S) = {b}.

Определим функцию следования Пеано, для которой множес тво P всех положительных целых чисел является и областью, и кообластью. Каждому целому положительному числу n она ста вит в соответствие число n + 1 : (n) = n + 1, : P P Ч функция из P в P. Функцию также можно задать (бесконечным) списком предписаний:

: 1 2, 2 3, 3 4,..., n n + 1,...

Очевидно, образом Im функции : P P является множес тво (P) = {2, 3, 4,...}, которое мы обозначим символом P2.

Чтобы задать функцию, мы должны определить ее область, ко область и значения, которые она сопоставляет каждому элементу области. Если f : S T и g : S1 T1, то f = g в том и только том случае, когда f(x) = g(x) для всех x S, S = S1 и T = T1.

Согласно этому определению, функции могут быть строго оди наковыми, только если их области и кообласти совпадают. Напри мер, предписание n n + 1 определяет также функцию : P P2. Эта функция не совпадает с функцией следования : P P, поскольку кообласть у не совпадает с кообластью функции.

Для любого множества S тождественная функция 1S : S S отображает любой элемент S в себя: 1S(s) = s для всех s S. В силу сказанного выше тождественные функции разных множеств различны.

О п р е д е л е н и е 5. Левой композицией g f любых двух функций называется функция, полученная в результате их применения в порядке, обратном написанному при условии, что область g совпадает с кообластью f.

Пусть f : S T и g : T U.

Тогда левая композиция g f есть функция g f : S U, определяемая правилом (g f)(s) = g(f(s)) для всех s S.

О п р е д е л е н и е 6. Правой композицией fg называ ется функция, получаемая из левой композиции перестановкой символов: ff = g f.

Пусть, например, m : R R Чоперация возведения в степень m, m(x) = xm. Подобно показателю степени m, символ функ ции m можно записать справа от аргумента: xm = xm. Если условиться писать символы функций,,... справа, то естествен но записывать их композицию также в правой форме, ибо тогда выполнено правило (x) = x(). Так, в предыдущем примере x(mn) = (xm)n = xmn = xmn;

следовательно, mn = mn.

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

Лемма 1. Композиция функций подчиняется ассоциативно му закону:

(h g) f = h (g f) = f(gh) = (fg)h.

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

Д о к а з а т е л ь с т в о. Пусть f : S T, g : T U, h : U V.

Любому элементу x S обе композиции приписывают значения (hg)f hg h(gf) [(hg)f]x = (hg)(fx) = h((gf)x) = [h(gf)]x.

Из определения равенства функций следует ассоциативный закон:

(hg)f = h(gf) : S V. Для краткости записи символ здесь опущен.

Тождественные функции 1S и 1T в композиции с любой функ цией f : S T не меняют ее:

f 1S = 1T f = f, 1Sf = f1T = f.

Чтобы убедиться в этом, следует заметить, что (f1S)s = f(1Ss) = f(s) для всех s S в силу леммы 1 и определения равен ства функций.

О п р е д е л е н и е 7. Функция f : S T называется инъективной, или инъекцией, или вложением, или взаимно од нозначным отображением УвФ, если из s = s в S следует, что f(s) = f(s) в T.

О п р е д е л е н и е 8. Функция h : S T называется сюръективной, или сюръекцией, или отображением УнаФ, если ее образ совпадает со всей кообластью, т.е. для каждого t T существует хотя бы один элемент s S, такой, что h(s) = t.

О п р е д е л е н и е 9. Биекцией, или взаимно однозначным отображением УнаФ, называется функция, являющаяся одновре менно инъекцией и сюръекцией.

Например, среди функций из Z в Z отображение n -n би ективно, отображение n 2n инъективно, но не сюръективно, а отображение n n2 не инъективно и не сюръективно.

Пусть P Ч множество всех положительных целых чисел, :

P P Ч функция следования Пеано, (n) = n + 1 для всех n P.

Это инъекция, но не сюръекция.

Пусть n = {1, 2,..., n} Ч множество положительных целых чи сел k n. К числу основных функций на нем принадлежит цик лическая перестановка: n : n n. Она сопоставляет всем числам k n, кроме n, следующее k + 1, а n переводит в 1. Это биекция.

При n = 3 функция 3 задается предписанием 1 2, 2 3, 3 1.

В общем случае n : 1 2, 2 3,..., n - 1 n, n 1.

О п р е д е л е н и е 10. Характеристической функцией подмножества S данного множества U, eS : U {0, 1}, опреде ляется предписанием 1, если x S, eS(x) = 0, если x S.

/ Пусть, например, U = {1, 2, 3} Ч множество, которое мы обо значим также символом 3. Вот списки значений функций eS, от вечающих всевозможным подмножествам S U:

(0, 0, 0), {1} (1, 0, 0), {2} (0, 1, 0), {3} (0, 0, 1), {1, 2} (1, 1, 0), {1, 3} (1, 0, 1), {2, 3} (0, 1, 1), 3 = {1, 2, 3} (1, 1, 1).

Например, при U = 3 описанное отображение b : S eS яв ляется биекцией между P(3) и множеством всех последователь ностей из символов 0, 1 длины три. Для простоты мы можем обо значить любой элемент из P(3) одной из восьми двоичных троек:

000, 100, 010, 001, 110, 101, 011, 111.

1.4. Обратные функции О п р е д е л е н и е 11. Если левая композиция функций f : S T и g : T S совпадает с тождественной функцией 1S на S, мы будем говорить, что g Ч левая обратная к f, а f Ч правая обратная к g. Eсли, кром того, f g = 1T, мы будем говорить, что g Ч двусторонне обратна к f и, по симметрии, f двусторонне обратна к g. Функция, имеющая двусторонне об ратную, называется обратимой.

Теорема 1. Функция обратима слева тогда и только тогда, когда она инъективна. Функция обратима справа тогда и толь ко тогда, когда она сюръективна.

Д о к а з а т е л ь с т в о. Покажем сначала, что любая обратимая слева функция взаимно однозначна. Пусть g : T S Ч функция, обратная слева к f : S T. Предположим, что f(s) = f(s). Тогда, по определению, s = 1S(s) = g(f(s)) = g(f(s)) = 1S(s) = s.

Таким образом, из предположения, что f(s) = f(s), мы вывели, что s = s. Это доказывает инъективность f.

Проверим обратное утверждение. Пусть f инъективна. Выбе рем элемент s1 S и определим g1 : T S так:

s, если t = f(x) для некоторого s S, g1(t) = s1 в противном случае, т.е. если t Im f.

/ Тогда (g1 f)(s) = g1(f(s)) = s для всех s S, так что, по определению, g1 f = 1S и g1 является левой обратной к f.

Аналогично проверяется вторая часть теоремы. Если t T и fh = 1T, то t = 1T (t) = f(h(t)), так что любой элемент t T является образом f(s) подходящего элемента s = h(t) S, и f сюръективна. Обратно, если f : S T сюръективна, то каждый элемент t T является образом t = f(s) хотя бы одного элемента s S. Для каждого элемента t T выберем из множества всех s, переходящих в t, один представитель и обозначим его через h(t).

Тогда получим функцию h : T S, такую, что f(h(t)) = t для всех t T, т.е. fh = 1T, как утверждалось.

С л е д с т в и е. Функция f : S T является биекцией тогда и только тогда, когда она обратима слева и справа.

Теорема 2. Следующие свойства функции f : S T эквива лентны:

(i) f Ч биекция;

(ii) f обладает левой обратной g и правой обратной h. Если эти свойства выполняются, то (iii) все обратные к f функции (левые, правые и двусторон ние) совпадают. Эта единственная обратная к f функ ция f-1 биективна, и (f-1)-1 = f.

Д о к а з а т е л ь с т в о. Эквивалентность свойств (i) и (ii) является просто переформулировкой предыдущего следствия. Из условия (ii) вытекает, что g = g1T = g(fh) = (gf)h = 1Sh = h.

Это показывает, что все левые и правые обратные к f совпада ют, и доказывает (iii). Наконец, биективная функция f обратна к своей обратной функции g = h, ибо gf = 1S и fh = 1T. Следова тельно, обратная функция биективна и имеет f в качестве своей единственной обратной, т.е. (f-1)-1 = f.

1.5. Функции из S в S Рассмотрим множество SS всех функций с областью и кооблас тью S. Оно образует алгебраическую систему [SS, ] с бинарной операцией (левая композиция). Поскольку кообласть любой функ ции из SS совпадает с областью любой другой функции, компози ции f g и fg = gf всегда существует в SS. Кроме того, обе эти операции удовлетворяют следующему закону ассоциативности:

f (g h) = (f g) h, f(gh) = (fg)h для всех f, g, h SS. Далее, в этой алгебраической системе тож дественная функция 1S удовлетворяет соотношениям 1S f = f 1S = f, т.е. f1S = 1Sf = f, для всх f SS.

Приведенные соотношения имеют одинаковый вид для операций и Когда f2 = f f = f, функция f называется идемпотентом, или проектором. Например, ортогональный проектор (x, y)-плоскости на x-ось или y-ось является идемпотентом. Заметим также, что два эти проектора обладают свойством f g = gf (или, что то же самое, gf = fg), поскольку f g и gf отображают любую точку плоскости в начало координат (0, 0). Функции f, g со свойством fg = gf называются коммутирующими, или перестановочными.

П р и м е р 3. Пусть S = {a, b};

обозначим элементы SS бук вами: e = 1S, : a a, b a;

: a b, b b;

f : a b, b a.

Тогда системы [SS,, 1S] и [SS,, 1S] имеют следующие таблицы умножения:

e f e f e e f e e f f f e f f e Элементы 1,, идемпотенты, т.е. 12 = 1, 2 = и 2 =.

Функция f не идемпотентна, ибо f2 = e. Кроме того, =, так что операция (и противоположная к ней ) не коммутативна.

У функций и нет обратных, ни правой, ни левой, а f обратна сама к себе (т.е. f2 = 1).

УПРАЖНЕНИЯ 1. Рассмотрим функции f(n) = 3n, g(n) = 3n + 1, h(n) = 3n + 2 из Z в Z. Построить функцию, которая была бы обратной слева к f, g, и h одновременно.

2. а) Если fg определена и обе функции f, g имеют обратные, показать, что fg имеет левую обратную.

б) Показать на примере, что обратное утверждение верно не всегда: fg может иметь левую обратную функцию даже тогда, когда f ее не имеет.

3. а) Показать, что композиция gf для двух любых инъекций f : S T и g : T U является инъекцией.

б) Доказать то же утверждение для сюръекций.

4. а) Сколько имеется сюръекций из трехэлементного множества на двух элементное?

б) Сколько имеется инъекций из трехэлементного множества в четырех элементное?

5. а) Рассмотрим отображение x x2 каждого из следующих множеств в себя:

P, Z, Q, R, C.

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

б) Тот же вопрос для x x3.

6. а) Какие подмножества множества 4 = {1, 2, 3, 4} представляются следу ющими двоичными последовательностями: 1001, 0110, 1101, 0010.

б) Показать, что если двоичная последовательность n = n1n2n3n4 пред ставляет множество S, то последовательность n = (1 - n1) (1 - n2)(1 n3)(1-n4) представляет его дополнение. Проиллюстрировать это на при мерах из п. а).

7. Пусть n(X) Ч число элементов множества X. Тогда следующие тождества верны для любых трех конечных множеств:

а) n(A) + n(B) = n(A B) + n(A B);

б) n(A B C) + n(A B) + n(B C) + n(C A) = = n(A B C) + n(A B) + n(B C) + n(C A).

8. В кровопролитном бою не менее 70% воинов потеряли глаз, не менее 75% Ч ухо, не менее 80% Ч руку и не менее 85% Ч ногу. Оценить снизу число воинов, потерявших одновременно глаз, ухо, руку, и ногу (Льюис Кэрролл).

1.6. Суммы, произведения и степени О п р е д е л е н и е 12. Будем говорить, что конеч ное множество S состоит из m элементов, или что его карди нальное число равно m, если существует биекция b : S m = {1, 2,..., m}. Будем считать, что пустое множество имеет элементов.

О п р е д е л е н и е 13. Пусть даны два множества S и T.

Их раздельным объединением, или суммой, называется множест во D = S T вместе с фиксированными биекциями i : S S D и j : T T D, такими, что S и T Ч взаимно дополнитель ные подмножества D.

Если S U, T U и S T =, тогда S T = S T, i = 1S, j = 1T и n(S T ) = n(S) + n(T ) Имеют место следующие очевидные биекции:

: S T T S, : S (T U) (S T ) U.

О п р е д е л е н и е 14. Декартовым, или прямым, произ ведением S T множеств S и T называется множество упоря доченных пар вида (s, t), где s принадлежит S, а t принадлежит T.

Так, если R Ч множество всех вещественных чисел, то R R Ч множество всех упорядоченных пар (x, y) вещественных чисел.

Как и выше, имеются естественные биекции:

S T T S, S (T U) (S T ) U.

Наконец, вместо естественных инъекций f : S S T и g :

T S T определены естественные сюръекции:

p : S T S, p(s, t) = s, q : S T T, q(s, t) = t.

Эти сюрьекции называются проекторами на сомножители произ ведения S T по аналогии с проекторами плоскости на оси декар товой координатной системы.

Множество всех функций из множества S в множество T обо S значается через T. Если S и T конечны и состоят из n(S) и n(T ) элементов соответственно, то имеет место формула S n(T ) = n(T )n(S).

Действительно, для каждого si S значение f(si) T можно вы брать ровно n(T ) способами. Все эти способы независимы, поэтому f выбирается одним из n(T )... n(T ) (n(S) раз) способов.

Пусть 2 = {0, 1}. Формула 1, если x S, eS(x) = 0, если x S.

/ определяет естественную биекцию b : P(U) 2U, которая ставит в соответствие каждому подмножеству S U его характеристи ческую функцию eS 2U. Эта же биекция отождествляет под множества из n = {1, 2,..., n} с двоичными последовательностями длины n.

В общем случае имеются естественные биекции:

RS R S S SR T T T, (T U)S T US, (S)R T.

1.7. Аксиомы Пеано Итальянский математик Дж. Пеано систему [P, +, ], где P множество положительных целых чисел, определил как алгебра ическую систему [P, ] с одной унарной операцией счета.

Функция PP называется функцией следования Пеано и ха рактеризуется следующими аксиомами:

S1. Если (m) = (n), то m = n ( взаимно однозначна).

S2. Не существует такого n P, что (n) = 1.

S3. Пусть подмножество S P удовлетворяет двум услови ям: a)1 S и б) из того, что n S следует (n) S.

Тогда S = P.

В терминах бинарной операции операции сложения и умно жения в множестве P определяются следующими рекурсивными описаниями.

П р и м е р 4. Для любого m P функция m : n m + n определяется простой рекурсией:

m + 1 = m(1) = (m), (1.7.1) m + (n + 1) = m(n) = (m(n)). (1.7.2) Для фиксированного m P рассмотрим множество Sm всех n P для которых m(n) определена. В силу (1.7.1), 1 Sm, а согласно (1.7.2), из того, что n Sm, следует, что (n) Sm.

Значит, в силу аксиомы S3, функция m(n) = m + n определена для всех n P.

Если теперь m будет пробегать все множество P, то мы полу чим бинарную операцию сложения + : P P P.

П р и м е р 5. Для фиксированного m P определим функцию pm : n nm следующей простой рекурсией:

pm(1) = m, (1.7.3) pm((n)) = m + pm(n) = m(pm(n)). (1.7.4) Как и в предыдущем примере, проверяется, что множество Sm всех n P, для которых pm(n) определена, совпадает со всем P.

Поэтому, если m и n пробегают все P, мы получаем бинарную операцию умножения на P.

1.8. Финитная индукция Предположим, что задана последовательность высказываний P (1), P (2), P (3),..., каждое из которых может быть либо истин ным, либо ложным. Принцип финитной (конечной) индукции утверждает, что для доказательства истинности высказываний P (n) для всех n P достаточно установить, во-первых, истин ность P (1) и, во-вторых, истинность бесконечной последователь ности импликаций P (1) P (2) P (3)... P (n) P (n + 1)....

Второе условие можно записать как утверждение, что (для всех n) из истинности P (n) следует истинность P ((n)). Здесь (n) = n = n + 1 Ч функция следования.

Принцип финитной индукции немедленно следует из аксиомы Пеано S3. Действительно, пусть T P Ч множество всех поло жительных целых чисел n, для которых P (n) истинно. Если 1 T и если из того, что n T, следует, что (n) T, то, в силу акси омы S3, T = P.

Докажем индуктивным методом коммутативность и ассоциа тивность сложения целых чисел.

Теорема 3. Определим сложение в [P, ] формулой m + n = m(n). Тогда для всех m, n P m + (n + r) = (m + n) + r (ассоциативность), (1.8.1) m + n = n + m (коммутативность). (1.8.2) Докажем ассоциативность. Обозначим через P (r) высказывание об истинности (1.8.1) для этого r и всех m, n P. Тогда P (1) утверждает [если r = 1 в (1.8.1)], что m + (n) = (m + n);

это верно в силу (1.7.2).

Пусть теперь истинно высказывание P (r):

m + (n + r) = (m + n) + r, для всех m, n. Снова, замечая, что m + (n) = (m + n) согласно (1.7.2), находим (1.7.2) (1.7.2) P (r) m + (n + (r)) = m + (n + r) = (m + (n + r)) = P (r) = ((m + n) + r), где над каждым знаком равенства отмечено, на основании чего это равенство справедливо (для всех m, n P). Снова применяя (1.7.2) к m + n и r, получаем (1.7.2) ((m + n) + r) = (m + n) + (r).

Отсюда окончательно m + (n + (r)) = (m + n) + (r) для всех m, n P.

Но это высказывание совпадает с P ((r)). Это завершает доказа тельство (1.8.1).

Чтобы установить (1.8.2), начнем с n = 1. Обозначим через P (m) высказывание m + 1 = 1 + m и снова проведем индукцию.

Поскольку 1 + 1 = 1 + 1, утверждение P (1) истино. Считая P (m) истинным, с помощью (1.7.1) и (1.8.1) доказываем истинность вы сказывания (m + 1) + 1 = (1 + m) + 1 = 1 + (m + 1), т.е. P (m + 1). Это завершает индукцию и доказывает истинность P (m) для всех m.

Теперь обозначим через Q(n) высказывание m + n = n + m для всех m. Мы доказали Q(1). Считая Q(n) истинным, мы затем можем последовательно доказать, что m + (n + 1) = (m + n) + 1 = (n + m) + 1 = n + (m + 1) = = n + (1 + m) = (n + 1) + m, применяя (1.8.1), Q(n), (1.8.1), P (m) и (1.8.1) (в указанном поряд ке). Это означает, что Q(n + 1) истинно, и завершает индукцию.

Но истинность Q(n) для всех n, очевидно, и означает (1.8.2).

Аналогичные доказательства можно провести для законов ас социативности и коммутативности умножения целых положитель ных чисел:

m(nr) = (mn)r для всех m, n, r P, mn = nm для всех m, n P.

Пользуясь индукцией, нетрудно вывести из аксиом Пеано также и дистрибутивные законы. Обозначим через P (r) высказывание, что m(n + r) = mn + mr для всех m, n P. Тогда P (1) следует из (1.7.4) и (1.8.2). Затем, приняв P (r), получаем m(n + (r)) = m(n + (r + 1)) = m((n + r) + 1) = = m(n + r) + m = mn + mr + m = (в силу P (r))= = mn + (mr + m) = mn + mr.

УПРАЖНЕНИЯ 1. Определив подходящим образом xn, доказать по индукции следующие тож дества в P:

1n = 1, xmxn = xm+n, (xy)n = xnyn, (rs)n = rsn.

2. Определим xn рекурсией: x1 = x и xn = xnx. Доказать по индукции, что если a2 = a, то an = a для всех n P.

n 3. а) Доказать по индукции, что k = n(n + 1)/2.

k= n б) Доказать по индукции, что k2 = n(n + 1)(2n + 1)/6.

k= n 4. Доказать, что k3 = [n(n + 1)/2]2.

k= r 5. Полагая по определению = r!/s!(r - s)!, доказать по индукции, что s r r r + + = s s - 1 s для всех r P и s = 0,..., r. Затем, используя этот факт, доказать по n n индукции формулу бинома Ньютона (x + y)n = xn-kyk.

k k= n n 2 2n 6. Доказать, что =.

k n k= 7. Доказать по индукции, что из m + r = m + s в P следует, что r = s.

8. а) Доказать по индукции, что композиция инъекций fm fm-1... f является инъекцией.

б) Доказать аналогичное утверждение для сюръекций.

9. Доказать, что в P справедливы следующие факты:

а)m < n тогда и только тогда, когда m + r = n для некоторого r P.

б) m n тогда и только тогда, когда m + r = n для некоторого r N.

БИНАРНЫЕ ОТНОШЕНИЯ И ГРАФЫ 2.1. Введение Бинарным отношением между множествами X и Y, а также графиком этого отношения, называется любое множество упоря доченных пар (x, y), где x X, y Y. Если (x, y), мы говорим, что x находится в отношении к y, и пишем xy. Если x не на ходится в отношении к y, то мы пишем x y.

Бинарное отношение может задаваться правилом, которое поз воляет для каждой пары (x, y) решить, находится ли x в отноше нии к y.

Понятие бинарного отношения между X и Y служит обобщени ем понятия функции f : X Y. Действительно, каждая функция f : X Y определяет бинарное отношение f между X и Y :

xy означает, что y = f(x). (2.1.1) Обратно, пусть дано бинарное отношение между множества ми X и Y. Рассмотрим для каждого x X множество всех y Y со свойством xy. Это соответствие определяет функцию f : X Y тогда и только тогда, когда для каждого x X существует ровно один элемент y Y со свойством xy. Таким образом, понятие бинарного отношения включает понятие функции как (очень важ ный) частный случай.

Следуюший пример из аналитической геометрии показывает, каким образом многозначную функцию (так же, как и однознач ную) можно рассматривать как бинарное отношение между ее об ластью и кообластью [1].

П р и м е р 5. Пусть X = Y = R (множество вещественных чисел). Пусть xy означает, что x2 + y2 = 25. Итак, xy тогда и только тогда, когда y = 25 - x2 : графиком является окруж ность радиусом 5 с центром в начале координат. В этом примере 34 и 4(-3), но, например, 2 3.

Слово лграфик в применении к окружности, состоящей из точек, координаты которых (x, y) в отношении x2 + y2 = 25 (или в функциональном обозначении y = 25 - x2), как уже говори лось, употребляется и для произвольного бинарного отношения.

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

О п р е д е л е н и е 15. Графиком бинарного отношения между множествами X и Y называется множество S() всех пар (x, y) X Y, таких, что xy.

Символически: S() = {(x, y) : xy}.

П р и м е р 6. Пусть X = {a, b}, Y = {c, d, e}. Зададим отно шение списком ac, ad, a e, b c, b d, be.

Тогда график S() имеет вид S() = {(a, c), (a, d), (b, e)}.

Заметим, что отрицание отношения является бинарным отношением между X и Y. Переобозначив через, мы получим, что задается списком a c, a d, ae, bc, bd, b e.

Двойное отрицание совпадает с. Это верно и в общем слу чае: если x y означает не xy, (2.1.2) то ( ) =.

Любое бинарное отношение между конечными множествами X = {x1,..., xm} и Y = {y1,..., yn} можно задать таблицей, стро ки которой отвечают элементам X, столбцы Ч элементам Y, а на пересечении xi-й строки и yj-го столбца записана единица, если xiyj, и ноль, если xi yj. Таблицы для отношений и из при мера 2 имеют вид c d e c d e a 1 1 0 a 0 0 b 0 0 1 b 1 1 Табличная запись любого отношения позволяет отождествить (например, или = ) с характеристической функцией гра фика этого отношения: значение этой функции на элементе (xi, xj) стоит на пересечении i-й строки и j-го столбца таблицы:

1, если xiyj, eS()(xi, yj) = (2.1.3) 0, в противном случае 2.2. Матрицы отношений Пусть заданы пронумерованные конечные множества X = {x1,..., xm} и Y = {y1,..., yn}.

Тогда таблица из нулей и единиц, задающая любое отношение, представляет собой m n-матрицу A = aij :

1, если xiyj, aij = (2.2.1) 0, в противном случае.

В примере 6 матрицы A, B, отвечающие соотношениям,, имеют вид 1 1 0 0 0 A = B =.

0 0 1 1 1 Обратно, любая m n-матрица A = aij из нулей и единиц определяет отношение (A) по формуле (2.2.1). Поэтому всякую (прямоугольную) матрицу из нулей и единиц мы будем называть матрицей отношения.

На пересечении i-й строки и j-го столбца матрицы M() = A любого бинарного отношения между множествами X и Y стоит элемент aij, значение характеристической фукции e = eS() : X Y {0, 1} графика S() X Y отношения. Иными словами, 1, если (xi, yj) S(), e(xi, yj) = aij = (2.2.2) 0 в противном случае.

В примере 6 характеристическая функция e = eS() задается следующими предписаниями:

(a, c) 1, (a, d) 1, (a, e) 0, eS() :

(b, c) 0, (b, d) 0, (b, e) 1.

Каждое бинарное отношение между X и Y определено его гра фиком S() и каждое подмножество T X Y является графи ком единственного бинарного отношения T между X и Y, которое определяется условием xT y тогда и только тогда, когда (x, y) T.

Поэтому соответствия S() и T T определяет взаимно об ратные биекции множества всех бинарных отношений между X и Y и множества всех подмножеств P (X Y ) произведения X Y :

S() =, S(T ) = T для всех, T. (2.2.3) Кроме того, S( ) = [S()] : отрицание отношения в этой биек ции отвечает взятию дополнения к графику. По этой причине также называется дополнением к отношению.

Б у л е в ы о п е р а ц и и. Описанные биекции приводят к рассмотрению булевой алгебры, элементами которой являются бинарные отношения между X и Y. Введем операции и следу ющим образом:

x( )y означает xy и xy, (2.2.4) x( )y означает xy или xy. (2.2.4) Тогда, по определению операций и на множествах:

S( ) = S() S() и TV = T V, (2.2.5) S( ) = S() S() и TV = T V (2.2.5) для любых двух отношений между X и Y и любых двух подмно жеств T, V XY. В частности, для любых двух дополнительных отношений, таких как и = в примере 6, S( ) = (пустое множество) и S( ) = X Y. Мы будем называть пере сечением бинарных отношений,, а Ч их объединением.

Наконец, будем писать, если S() S(). Иными словами, означает, что из xy следует xy. (2.2.6) 2.3. Алгебра отношений Бинарные отношения между множествами, кроме общих свойств булевых алгебр, обладают многими алгебраическими свойствами. Например, по любому отношению между множес твами X и Y можно определить обратное отношение между X и Y следующим образом:

yx означает, что xy. (2.3.1) Очевидно, что матрица ij отношения получается транспо нированием матрицы aij отношения, т. е. заменой строк столб цами и наоборот (отражением относительно главной диагонали в случае m = n). Иными словами, ij = aji.

Только в исключительном случае и отношение и обратоное к нему могут одновременно соответствовать функциям. Тогда, по лагая = f и = g, имеем: каждый элемент y Y (поскольку g Ч функция) должен отвечать некоторому элементу x X, и при том единственному (поскольку f Ч функция). Поэтому функции f и g, отвечающие и, должны быть взаимно обратными би екциями. Их матрицы отношений (если они существуют) должны быть квадратными матрицами перестановок, у которых в любой строке и в любом столбце имеется ровно одна единица.

Понятие композиции двух функций можно обобщить на отно шения. Пусть, Ч отношения между X, Y и Y, Z соответствен но. Тогда композицией называется отношение x()z тогда и только тогда, когда существует такой y Y, что xy и yz. (2.3.2) Если = f и = g отвечает функциям, то = gf, т. е.

композиция отношений отвечает композиции функций.

Читая (2.3.2) справа налево, мы убеждаемся, что z()x озна чает существование такого y Y, что zy и yx. Отсюда следует тождество =, (2.3.3) которое обобщает соотношение (fg)-1 = g-1f-1.

Б и н а р н ы е о т н о ш е н и я на S. Бинарное отношение между множеством S и им самим (т. е. X = Y = S ) называется отношением на множестве S. Важным частным случаем этого по нятия является отношение равенства e на S : xey означает x = y.

Ясно, что на множестве n ему отвечает единичная матрица. Это квадратная матрица n n с единицами на главной диагонали и нулями на остальных местах:

1, если i = j, I = ij, где ij = 0, если i = j.

Из (2.3.2) следует, что композиция любых двух отношений на множестве S существует. Отношение равенства e удовлетворяет условиям e = e = для всех. Наконец, справедлив ассоциа тивный закон () = () для любых отношений,, на S. (2.3.4) Действительно, оба утверждения x[()]y и x[()]y означа ют, что для подходящих элементов z1, z2 S имеют место утверж дения xz1, z1z2 и z2y.

Резюмируем сказанное:

Теорема 5. Бинарные отношения на множестве S относи тельно композиции образуют алгебраическую систему, которая ассоциативна и в качестве единицы имеет отношение равенст ва.

Существует много важных типов бинарных отношений на S.

Если xx для всех x S, отношение называется рефлексивным.

Если из xy следует, что yx, отношение называется симмет ричным, а в противном случае Ч асимметричным. Если x = y, то из xy, очевидно, следует, что yx;

обратно, если из xy и yx следует, что y = x, отношение называется антисимметричным.

Мы видели, что отношение включения между множествами рефлексивно и антисимметрично. Поэтому таково же отношение включения между отношениями.

Бинарное оотношение на множестве S называется транзитив ным, если из xy и yz (x, y, z S) вместе следует, что xz. В частности, отношение включения между множествами транзи тивно.

Пусть, например, T = {1, 2, 3}, и Ч отношение на T с графи ком S() = {(1, 1)(1, 2)(2, 1)(2, 2)(2, 3)(3, 2)(3, 3)}.

Это отношение рефлексивно и симметрично, но не транзитивно, ибо 12 и 23, но 1 3. Заметим, что график S(2) отношения совпадает с T T. Таким образом, 2 Ч отношение, выполняю щееся на всем T : x2y для всех x, y T.

Данные выше определения можно переформулировать следую щим образом. Бинарное отношение на S рефлексивно тогда и только тогда, когда оно содержит отношение равенства e (e ) или, что то же самое, когда e = e и e =. Оно симметрич но в том и только том случае, когда =. Оно антисимметрично тогда и только тогда, когда e. Оно транзитивно тогда и только тогда, когда 2 (где 2, конечно, есть ).

Если S = n, рефлексивность отношения на S означает, очевид но, что все диагональные элементы матрицы этого отношения рав ны единице. Отношение симметрично в том и только том случае, когда матрица aij симметрична (т. е. aij = aji для всех i, j).

Наконец, понятие декартова произведения функций обобщается на отношения следующим образом. Пусть Ч бинарное отноше ние между множествами A и Y, а Ч между множествами B и Y. Определим декартово (или прямое) произведение = как отношение между множествами A B и Y вида (a, b)y означает, что ay и by. (2.3.5) Аналогично, пусть Ч бинарное отношение между множества ми A и X, а Ч бинарное отношение между множествами A и Y.

Определим отношение = следующим образом:

a(x, y) означает, что ax и ay. (2.3.5) 2.4. Частичное упорядочение.

Бинарное отношение на множестве S называется частичным упорядочением этого множества (или частичным поядком на нем), если оно рефлексивно, антисимметрично и транзитивно. Такие от ношения часто обозначаются символом. Аксиомы частичного порядка могут быть записаны тогда привычным способом:

P1. x x для всех x S.

P2. Если x y и y x, то x = y.

P3. Если x y и y z, то x z.

П р и м е р 7. Отношение m|n (m делит n) является частичным упорядочением на множестве всех положительных целых чисел.

П р и м е р 8. Обычное отношение является частичным упорядочением множества всех положительных целых чисел.

П р и м е р 9. Для любого множества U отношение S T явля ется частичным порядком на множестве P (U) всех подмножеств множества U.

О п р е д е л е н и е 16. Частично упорядоченным множес твом называется любая пара [S, ], где частичный порядок намножестве S.

Имеется много полезных примеров частичных упорядочений.

Рассмотрим некотоpые из простейших свойств частично упоря доченных множеств. Во-первых, отношение, обратное к частич ному порядку, снова является частичным порядком, который называется двойственным к первому и обозначается символом.

Таким образом, по определению, X Y тогда и только тогда, когда Y X. Во-вторых, частично упорядоченные множества, со стоящие из небольшого числа элементов, удобно описывать диа граммами. Маленькие кружочки на них означают элементы;

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

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

В частично упорядоченном множестве [P (3), ] элементы и являются универсальными границами потому, что x 3 для любого элемента x P (3). Это понятие можно определить в обшем случае: элементы O и I называются универсальными границами частично упорядоченного множества S (соответственно верхней и нижней), если O x и x I для любого x S. (2.4.1) Иными словами, O наименьший, а I наибольший элемент мно жества S.

Лемма 2. В любом частично упорядоченном множествые [S, ] может существовать не более одного наименьшего эле мента и не более одного наибольшего элемента.

Д о к а з а т е л ь с т в о. Пусть O, O два наименьших элемента [S, ]. Тогда O O (ибо O наименьший элемент) и O O (ибо O наименьший элемент). Согласно P2 отсюда следует, что O = O. Доказательство для I аналогично.

Cуществуют частично упорядоченные множества без универ сальных границ. Таково множество вещественных чисел [R, ] с обычным отношением порядка (если оно не расширено формаль ным присоединением Ц, ).

Кроме того, [R, ] является линейно упорядоченным множест вом или цепью: кроме свойств P1ЦP3, оно обладает свойством P4.

Для любых x, y либо x y, либо y x.

Всякое подмножество упорядоченного множества, очевидно, са мо упорядочено индуцированным на нем бинарным отношением.

Если множество линейно упорядочено, то его подмножества также линейно упорядочены. Все это следует из того, что свойства P1, P2, P3, P4 наследственны, т. е. сохраняются при ограничении на любое подмножество своей области, если они выполнялись на всей области.

Д о м и н и р о в а н и е. С любым отношением частичного по рядка свзан ряд других бинарных отношений. К ним относятся:

отношение x < y, означающее, что x y, но x = y;

отношение x > y, означающее, что y < x, а так же отношение x y (ллx и y не сравнимы), означающее, что ни одно из двух утверждений x y и y x неверно. Ясно, что если x, y [S, ], то справед лива только одна из следующих альтернатив: x = y, x > y, x < y или x y. Менее очевидно отношение, связанное с, а именно доминирование.

О п р е д е л е н и е 17. Пусть P = [S, ] частично упорядо ченное множество, а a и b его элементы. Будем говорить, что a доминирует над b, если a > b, но ни для какого x S неверно, что a > x > b.

Покажем, что отношение однозначно восстанавливается по отношению доминирования в любом конечном частично упорядо ченном множестве.

Теорема 6. Пусть a < b в конечном частично упоядоченном множестве P. Тогда P содержит по крайней мере одну цепь xo = a < x1 <... < xl = b, в которой каждый из элементов xi (i = 1,..., l) доминирует над xi-1.

Д о к а з а т е л ь с т в о. используем индукцию по количеству n элементов y со свойством a < y < b. Если n = 0, то b доминирует над a, и утверждение очевидно. Пусть n > 0, и a < c < b. Тогда количество элементов y, удовлетворяющих условию a < y < c, и элементов z, удовлетворяющих условию c < z < b, не превосходит n - 1, ибо c мы исключили. Значит, по предположению индукции существуют конечные цепи, связывающие a с c и c с b, соседние элементы которых находятся в отношении доминирования. Соеди няя эти две цепи, получим требуемый результат.

Удобно представить себе, что если a доминирует над b, то b находится в прямом подчинении к a относительно некоторой ие рархии. Тогда x y означает отношение подчинения.

О п р е д е л е н и е 18. Элемент m частично упорядоченно го множества [S, ] называется минимальным, если не существует такого элемента x S, что x < m. Элемент m называется макси мальным, если не существует такого элемента x S, что x > m.

Напомним, что x < m означает, x m, но x = m;

x > m означает, что m x, но m = x.

Очевидно, что если частично упорядоченное множество облада ет универсальной нижней границей, или наименьшим элементом O, то O является единственным минимальным элементом. В неупо рядоченном множестве (где x y означает x = y) любой элемент минимален, а так же максимален. В цепи минимальный элемент должен быть наименьшим, и поэтому он единствен.

Следующий принцип, относящийся к конечным частично упо рядоченным множествам, играет важную роль. Он утверждает су ществование согласованной (с порядком) нумерации.

Теорема 7. Пусть [S, ], S = {s1,..., sn} конечное частично упорядоченное множество. Тогда элементы S можно занумеро вать таким образом: S = {x1,..., xn}, что из xi < xj будет следовать i < j.

Д о к а з а т е л ь с т в о. Положим Xm = {s1,..., sn}, где первоначальная нумерация S = {s1,..., sn} выбрана каким угодно способом. Мы построим последовательность биекций m множеств m = {1,..., m} в себя, такую, что каждое подмножество Xm, пе ренумерованное посредством m:

Xm = {xm,..., xm}, xm = s, 1 m i m(i) будет удовлетворять сформулированному в теореме утверждению:

из xm < xm сдедует, что i < j.

i j При m = 1 биекция 1 строится однозначно. Предположим, что биекция n-1 : n - 1 n - 1 с требуемым свойством уже по строена. Обозначим через k наименьшее из чисел i, обладающих свойством sn < xn-1. Построим биекцию n-1 : n n следующим i образом:

n(i) = i, если i < k, n(i) = n, если i = k, n(i) = i + 1, если i > k.

Иными словами, вставим sn между xn-1 и xk-1. Проверим, что n k-1 k обладает тебуемыми свойствами. Если xn < xn и {xn, xn} Xn-1, i j i j то i < j по предположению индукции. Если sn = xn < xn, то k < j k j по построению. Наконец, если xn < xn = sn, то xn < xn < xn, i k i k k+ откуда xn < xn в силу транзитивности P3 и, наконец, i < k + i k+ по предположению индукции, так как {xn, xn } Xn-1. Следова i k+ тельно, и здесь i < k (случай i = k невозможен);

доказательство завершено.

Следствие. В любом конечном частично упорядоченном мно жестве P есть минимальный элемент m: не существует x P, такого, что x < m.

В е р х н я я и н и ж н я я г р а н и. Пусть S некоторое подмножество частично упорядоченного множества P. Назовем a P нижней границей, или минорантой, множества S, если a x для всех x S. Назовем a верхней границей, или мажорантой, множества S, если a x для всех x S. Назовем элемент b P нижней гранью S, если (i) он является нижней границей для S и (ii) b b для любой другой нижней границы b множества S.

В этом случае мы будем писать b = inf S. Аналогично, назовем c P верхней гранью множества S, если (i) c является верхней границей для S, (ii) c c для любой другой верхней границы c.

В этом случае мы будем писать c = sup S.

Лемма 3. Любое подмножество частично упорядоченного множества имеет не более одной верхней и не более одной ниж ней грани.

Д о к а з а т е л ь с т в о. Пусть b1, b2 нижние грани множества S. Тогда b1 b2, потому что b1 нижняя граница, а b2 наибольшая нижняя граница. Аналогично, b2 b1. Из свойства P2 следует, что b1 = b2. Двойственное рассуждение доказывает единственность верхней грани.

2.5. Графы О п р е д е л е н и е 19. Kонечным графом G = (X, ) назы вается пара, где X конечное множество вершин, а Ч бинарное отношение на X.

Если Ч симметричное отношение, то G называется неориен тированным графом. В противном случае Ч ориентированным.

Если вершины x и y из X находятся в отношении, то пишут xy и говорят, что они смежны, а связь между x и y осуществля ется с помощью ребра, ориентированного от x к y. Ребро, соответ ствующее соотношению xx, называется петлей.

П р и м е р 7. Пусть X = {1, 2, 3, 4, 5}, задается с помощью графика следующим образом:

G() = {(1, 1)(1, 2)(1, 4)(4, 1)(2, 3)(2, 5)(5, 2)(3, 4)(3, 5)(5, 5)}.

Графическое изображение этого графа имеет вид, указанный на рисунке.

Каждому бинарному отношению на X отвечает матрица отно шений. Следовательно, с каждым графом можно связать матрицу из нулей и единиц ||aij||, называемую матрицей смежности, такую, что 1 если xixj, aij = 0 если xi xj.

О п р е д е л е н и е 20. Два графа G = (X, ) и H = (Y, ) называются изомофными, если существует биекция : X Y, такая, что для всех x, y X и z, t Y, для которых (x) = z, (y) = t, из того, что xy в G, следует zt в H.

П р и м е р 8. Пусть G = (X, ) и H = (Y, P ), такие, что X = {1, 2, 3}, Y = {a, b, c} и G() = {(1, 2)(2, 3)(3, 1)}, G() = {(a, c)(c, b)(b, a)}.

Тогда биекция : X Y, задаваемая перечислением :

1 a, 2 c, 3 b, является изоморфизмом, так как (12) (ac), (23) (cb), (31) (ba) при отображении. Однако, биекция : 1 a, 2 b, 3 c не является изоморфизмом, так как из того, что 12 и (1) = a, (2) = b, следует, что (1, 2) (a, b), а это не удовлетворяет определению изоморфизма, так как a и b не находятся в отношении, т. е. ab.

Каждому бинарному отношению на X можно сопоставить функцию F : X X следующим образом: y F (x) xy.

Тогда граф можно определить как пару G = (X, F ), где F : X X есть отображение, которое каждому x X ставит в соответствие подмножество F x X.

Так, для графа из примера 7 таблица, задающая F, имеет вид F 1 2 3 4 1 3 4 1 2 5 5 Для такого способа задания графа определение изоморфизма фор мулируется следующим образом.

О п р е д е л е н и е 21. Два графа G = (X, F ) и H = (Y, P ) называются изоморфными, если существует биекция : X Y, такая, что для любых x X и y Y, для которых (x) = y, имеем (F x) = P y. (2.5.1) Соотношение (2.5.1) эквивалентно коммутативности следующей диаграммы:

x - y - P F F x - P y - где коммутативность означает, что проход по верхней части диа граммы совпадает с проходом по нижней ее части.

Граф, о котором здесь идет речь, называется графом Бержа.

Приведем некоторые сведения из теории конeчных групп [5].

О п р е д е л е н и е 22. Группой G называется некоторое множество элементов G = {a, b, c,...} вместе с одной бинарной операцией, называемой произведением, такой что выполняются:

G0. Закон замкнутости: для каждой упорядоченной пары эле ментов a, b из G произведение a b = c существует и является однозначно определенным элементом из G.

G1. Ассоциативный закон: (a b) c = a (b c).

G2. Существование единицы: в G существует такой элемент 1, что 1 a = a 1 = a для любого элемента a G.

G3. Существование обратного элемента: для всякого элемен та a G существует такой элемент a-1 G, что a-1 a = a a-1 = 1.

Опpеделяя гpуппу через опеpацию умножения, мы на самом де ле имеем в виду не обязательно обычное умножение. Под этой опе рацией подразумевается любая бинарная операция, в том числе и двуместная функция f(a, b), которая состоит в соответствии лю бым двум элементам a, b G однозначно определенного третьего элемента c G. В частности, имеет место следующая теорема Теорема 8. Множество всех взаимно однозначных отобра жений S на себя относительно операции умножения отображе ний образует группу.

Д о к а з а т е л ь с т в о. Под умножением отображений, как обычно, понимается их суперпозиция относительно элементов из G. Выполнимость условий G0, G1 очевидна. Проверим выполнение условий G2, G3.

Так как тождественное отображение e является взаимно одно значным, то e S и ef = fe = f для любого отображения f S.

Таким образом, тождественное отображение e S играет роль единицы.

Так как всякое отображение f S;

f : G G является взаим но однозначным, то по определению для каждого элемента y G существует единственный x G, такой, что f (x) = y. Cопостав ляя элемент x элементу y, мы определяем взаимно однозначное отображение g(y) = x множества G на себя. Из определения ото бражения g видно, что (g f )(x) = g(f (x)) = x. Следовательно, f g = g f = e и g является отображением, обратным для f.

Взаимно однозначное отображение некоторого конечного мно жества на себя называется перестановкой. Перестановка традици онно задается следующим образом.

Пусть G = {1, 2, 3}, тогда 1 2 3 1 2 f =, g = 2 3 1 1 3 две перестановки, у которых верхняя строка есть множество G, а нижняя образы элементов из G. Согласно определению, их произ ведением является перестановка 1 2 f g =.

3 2 Перестановки можно задавать с помощью перечисления всех их неодноэлементных циклов: f = (1, 2, 3), g = (2, 3), f g = (1, 3).

Подмножество H группы G, само являющееся группой относи тельно операции, определенной в G, называется подгруппой.

О п р е д е л е н и е 23. Взаимно однозначное отображение : G H группы G на группу H называется изоморфизмом, если из того, что (g1) = h1, (g2) = h2, следует, что (g1 g2) = h1 h2.

П р и м е р 9. Рассмотрим следующие две подгруппы: G и H соответствующих групп перестановок:

1 2 3 1 2 3 4 5 g1 = h1 =, 1 2 3 1 2 3 4 5 1 2 3 1 2 3 4 5 g2 = h2 =, 2 3 1 2 3 1 6 4 1 2 3 1 2 3 4 5 g3 = h3 =, 3 1 2 3 1 2 5 6 1 2 3 1 2 3 4 5 g4 = h4 =, 1 3 2 4 5 6 1 2 1 2 3 1 2 3 4 5 g5 = h5 =, 3 2 1 5 6 4 3 1 1 2 3 1 2 3 4 5 g6 = h6 =.

2 1 3 6 4 5 2 3 Тогда отображение (gi) = hi является изоморфизмом, а подгруп пы G и H изоморфны.

Действительно, если (g2) = h2, (g3) = h3 и Ч изоморфизм, то должно быть (g2 g3) = h2 h3. Непосредственной проверкой убедимся, что 1 2 3 1 2 3 4 5 g2 g3 =, h2 h3 =, 1 2 3 1 2 3 4 5 т. е. g2 g3 = g1 и h2 h3 = h1. Согласно определению отображения имеем (g1) = h1.

Группа перестановок является представлением любой группы G в том смысле, что любая группа изоморфна некоторой группе перестановок. Таким образом, будучи вполне конкретным мате матическим объектом, она позволяет сводить решение достаточно общих математических вопросов к непосредственным вычислени ям над перестановками.

Теорема 9 (Кэли). Произвольная группа G изоморфна неко торой группе перестановок своих элементов.

Д о к а з а т е л ь с т в о. Для каждого g G определим отображение Rg(x) = gx для всех x G. При фиксированном g получаем отображение множества G на себя, так как для данного y G Rg(g-1y) = gg-1y = y.

Это отображение взаимно однозначно, так как в силу существова ния в G для любого элемента обратного из соотношения gx1 = gx следует x1 = x2. Таким образом, Rg Ч перестановка для каждого g G. Отображение Rg Rg таково, что 1 Rg Rg (x) = g1(g2x) = (g1g2)x = Rg g2(x).

1 2 Поэтому Rg Rg = Rg g2. Далее, Rg (1) = g1 и Rg (1) = g2, следова 1 2 1 1 тельно, если g1 = g2, то Rg = Rg. Значит, отображение g Rg 1 является изоморфизмом. Очевидно, что R1 = 1 тождественная пе рестановка и Rg-1 Rg = 1, так что Rg-1 = (Rg)-1.

Пусть G Ч группа, а H Ч ее подгруппа. Множество элемен тов вида hx, где h Ч любой элемент из H, а x Ч фиксированный элемент из G, называется левым смежным классом по H и обо значается Hx. Аналогично определяется правый смежный класс xH.

Теорема 10. Два левых (правых) смежных класса группы G по H или не пересекаются, или совпадают. Смежные классы по H и подгруппа H совпадают по мощности.

Д о к а з а т е л ь с т в о. Предположим, что z HxHy. Тогда z = h1x = h2y. Отсюда x = h-1h2y и hx = hh-1h2y. Поэтому 1 Hx Hy. Аналогично hy = hh-1h1x, следовательно, Hy Hx, откуда Hx = Hy. Аналогичное доказательство проводится и для правых классов.

Равномощность H, Hx и xH доказывается так же, как утверж дение в теореме Кэли.

Из этой теоремы следует, что существуют такие x2,..., xr из G, что смежные классы H, Hx2,..., Hxr не пересекаются и исчерпы вают всю группу G, в этом случае пишут G = H Hx2 Hxr.

Если G Ч конечная группа, то число r называется индексом под группы H в G, а число элементов группы G Ч порядком группы.

Теорема 11. ( Лагранжа). Порядок группы G равен произве дению порядка подгруппы на индекс H в G.

Д о к а з а т е л ь с т в о. Число элементов в каждом из r смежных классов G по H равно числу элементов в H, т. е. ее порядку. Если таких классов r, то количество элементов в G есть произведение r на порядок H.

О п р е д е л е н и е 24. Группа G называется цикличес кой, если каждый ее элемент является степенью gi некоторого фиксированного элемента g.

Если все степени элемента g различны, то циклическая группа имеет бесконечный порядок и изоморфна группе по сложению всех целых чисел. Если же не все степени различны, то существует такое m > 0, что gm = 1.

Пусть n > 0 Ч наименьшее положительное число, для котоpого gn = 1. Тогда легко видеть, что элементы 1, g,..., gn-1 составляют всю группу. Число n называется порядком элемента g и при r 0, s < n имеем grgs = gr+s, если r + s < n, если же r + s n, то grgs = gr+s-n. Элемент g называется образующей циклической группы 1, g,..., gn-1.

Для любой перестановки g как для элемента группы переста новок также существует понятие порядка пеpестановки.

Теорема 12. Порядок перестановки равен наименьшему об щему кратному длин ее циклов.

Д о к а з а т е л ь с т в о. Для цикла (x1,..., xn) имеем j(xi) = xi+j, где i+j берется по модулю n. Следовательно, t(xi) = xi тогда и только тогда, когда m кратно n. В этом случае m(xi) = xi для всех xi G тогда и только тогда, когда m кратно длинам всех циклов перестановки. Следовательно, при таком m m = e, где e Ч тождественная перестановка.

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

Если задана некоторая система A, состоящая из некоторого мно жества X и некоторой совокупности операций fk, то взаимно одно значное отображение множества X на себя называется автомор физмом системы A, если из соотношения fk(x1,..., xn) = y следует fk((x1),..., (xk )) = (y). Под fk могут подразумеваться как од нозначные отображения, так и многозначные.

Из определения автоморфизма следует, что произведение двух автоморфизмов есть снова автоморфизм, поэтому все автоморфиз мы относительно умножения образуют группу.

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

2.6. Теорема об изоморфизме графов Общее число шагов, которое необходимо сделать для выяснения изоморфности графов с n вершинами, равно n!. Если удачно про вести классификацию вершин гафов и наделить полученные клас сы сравнительными характеристиками, то общий перебор можно сократить по крайней мере до ini!, где ni Ч число вершин в i-м классе.

Пусть G = (X, F ) и H = (Y, P ) Ч два конечных графа Бержа, таких, что |X| = |Y |;

здесь X и Y Ч множества вершин, F :

X X, P : Y Y Ч отображения, ставящие в соответствие каждой вершине x X (y Y ) множество вершин, в которые из x X (y Y ) идут дуги.

О п р е д е л е н и е 25. Представлением графа G = (X, F ) называется пара G = (TX, AF ), где TX{(, )x}xX ;

= - |F x|, = |F x|, а AF : TX TX Ч соответствие, порождаемое соответствием F при замене элементов x X и F x X в G парами (, )x TX, такое, что AF (, )x = {(, )x }x F x.

Таким образом, в терминах графического способа задания гра фа представление графа отличается от него самого тем, что вер шина графа с номером i у представления помечена (, )i.

Пусть 1 и 2 Ч два множества из TX. Будем писать 2, если отображение 1 2 с точностью до индексов x из X элементов из i, i = 1, 2, является тождественным.

П р и м е р 10. Пусть 1 и 2 из TX имеют следующий вид:

1 = {(0, 1)i, (1, 0)i, (1, 0)i }, 1 2 2 = {(1, 0)j, (0, 1)j, (1, 0)j }.

1 2 Тогда 1 2. Если же, например, 2 = {(1, 0)j, (0, 1)j, (0, 1)j }, 1 2 то 1 2.

Обозначим через X/ множество классов, полученных с помо щью разбиения множества X, а через F Ч сужение отображения F на X/, относящее каждому классу из X/ некоторое множество классов из X/.

Определим на классах из X/ некоторые порядки. Если X/, то через будем обозначать t копий упорядоченного мно t жества, а через s Ч результат применения перестановки s к.

Выражение s следует понимать как (s).

t t Теорема 13. Два графа G = (X, F ) и H = (Y, P ), |X| = |Y |, изоморфны тогда и только тогда, когда существует разбиение и биекция : X/ X/, такие, что для любых X/ и Y/, удовлетворяющих соотношениям || = ||, () =, коммутативна следующая диаграмма:

- - P F (2.6.1) s sr r (t 1,...,t r ) - - (t s,...,t s ) 1 r 1 1 r r Здесь P и F Ч сужения отображений P и F на Y/ и X/ соответственно.

З а м е ч а н и е. Если графы G и H изоморфны, вопрос о су ществовании разбиения и биекции, вообще говоря, очевиден, так как всегда в качестве можно взять тривиальное разбиение, при котором в каждом классе содержится по одной вершине. Тогда в качестве будет выступать. Интересно выяснить, существу ют ли какие-то другие разбиения, отличные от тривиальных, и как их найти. Один из ответов на этот вопрос дается в данной теореме, где искомое разбиение формулируется исходя из некото рых качественных и количественных характеристик вершин и их совокупностей.

Д о к а з а т е л ь с т в о. Н е о б х о д и м о с т ь. Пусть графы G и H изоморфны и Ч биекция, осуществляющая изоморфизм.

Разобьем множество X (соответственно Y ) на непересекающиеся подмножества последовательно следующим образом:

1 этап. Разбиение 1 = {0, 1}:

0 = {x X : x F x};

1 = {x X : x F x}.

/ II этап. По разбиению 1 строим разбиение 2, при котором классы 0 и 1 разбиваются на подмножества kp, k = 0, 1, следу ющим образом:

kp = {x, y k : (, )x (, )y&AF(, )x AF (, )y &AF -1 (, )x AF -1 (, )y}.

Здесь p можно положить равным (, ), но в общем случае пред ставляет собой, кроме того, перечисление всех пар вида (,, ) t как из AF (, )x, так и из AF -1 (, )x.

III этап. По разбиению 2 строим разбиение 3 множеств kp на подмножества kp, относя к одному подмножеству kp те и только те вершины x, y из kp, для которых выполняется равенство |F x -1 -1 - F x| = |F y F y|, при этом полагается равным |F x F x|.

IV этап. По разбиению 3 построим разбиение 4 классов kp на подмножества kp, каждое из которых характеризуется следу ющим свойством:

{( x kp)( y kp : = |F x F y| не зависит от x и y)} Положим =. Обозначим через (x) след класса на F x и - F x соответственно.

V этап. Разбиение 5, построенное по разбиению 4, есть раз биение классов kp на подклассы kpl, такие, что {( x, y kpl)( 5)(|(x)| = |(y)|)}.

Упорядочим элементы F x для всех x из каждого таким образом, чтобы в строке с номером m содержались вершины, принадлежа щие одному классу. В силу свойства разбиения 5 это возможно сделать. Множество вершин с номером m из F будем обозначать (F )m.

VI этап. По ризбиению 5 строим более мелкое разбиение клас сов kM, M = (pl) на подмножества kMq, такие, что:

1) для любого x из kMq (F kMq)m = kMq, t {1, 2,...}, (2.6.2) t если |kMq| > 1;

2) если |kMq| = 1, то непустой след любого класса в F kMq совпадает с самим классом.

Очевидно, что построенное таким образом разбиение таково, что G/ = (X/, F) есть не обязательно граф Бержа.

Покажем, что все свойства, указанные в разбиении 1 - 5, графа G, переносятся на соответствующие классы графа H.

Пусть () =, X/, Ч некоторое подмножество вер шин из Y. Так как Ч биекция, то || = || для всех X/.

Пусть x F x, т. е. при x имеется петля и (x) = y. Тогда y = (x) (F x) = P (x) = P y т. е. y P y. Аналогично, из того, что x F x, следует, что и y = (x) P y. Таким образом, при изо / / морфизме вершинам с петлями в графе G соответствуют вершины с петлями в графе H, а вершинам без петль в G соответствуют вершины без петель в H.

Пусть вершине x в G соответствует пара (, )x в G, а вер шине y = (x) H Ч пара (, )y H. Тогда в силу изо -1 - морфности имеем (F x) = P y, (F x) = P y, следовательно, -1 -1 - |F x| = |P y|, |F x| = |P y| и = |F x| = |P y| =, = |F x| = - |P y| =. Таким образом, (, )x (, )y.

Каждой вершине xi F x, в силу изоморфности, соответ ствует yi P y, где y = (x), (xi) = yi. Так как |F x| = |P y| 1 и (, )x (, )y, то AF (, )x AP (, )y. А так как для i i 1 любых x, z kp выполняется AF (, )x AF (, )z, то и для y = (x) и t = (z) из соответствующего kp выполняется 1 AP (, )y AP (r, s)t. Следовательно, |kp| = |kp| и p = p.

- Из того, что Ч изоморфизм, следует, что (F x F x) = -1 -1 - (F x) (F x) = P (x) P (x) = P y P y. А тогда |F x -1 - F x| = |P y P y|, где x, y, () =.

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

Аналогично проверяется для свойство, указанное в разбиении 4.

Пусть классы, из разбиения 5 графа G, классы, из графа H таковы, что () =, () =, и пусть класс из F такой, что |(x)| = k для всех x. Тогда в силу биективности имеем |(x)| = |(y)| = k для всех x и y, таких, что (x) = y. Наконец, в силу того, что Ч изоморфизм и () =, имеем s1 sr 1 r (t 1,...,t r ) = (F ) = P () = P = (t s,...,i s ).

1 r 1 i1 r ir Д о с т а т о ч н о с т ь. Пусть существует разбиение и биекция, такая, что для любых X/ и Y /, удовле творяющих соотношениям || = || и () =, коммутативна диаграмма (2.6.1). Зафиксируем некоторые порядки на элементах разбиения из X/ и Y /. Построим по биекции биекцию сле дующим образом. Если () =, то элементу x, имеющему номер i, поставим в соответствие элемент y c тем же номером.

Из диаграммы (2.6.1) видно, что si = si, и, следовательно, si i (t i ) =t (i)s.

i i Пусть xi из и yi из таковы, что (xi) = yi, и пусть s1 sr 1 r F xi = (xj (1 ),..., xj (r )), P yi = (yk (s ),..., yk (s )).

1 r 1 1 r r si Здесь i = kp + jt, k {0, 1,...}, p = |t|, t = 1, r, а xj (i ) есть i si вершина из i с номером ji. Тогда в силу перестановочности и si имеем kt = jt, t = 1, r, и, следовательно, диаграмма xi - yi - P F s sr r (xj (1 ),..., xj (r )) - (yj (s ),..., yj (s )).

- 1 r 1 1 r r коммутативна, а, построенный по указанному правилу, есть изо морфизм.

П р и м е р 11. Пусть графы G = (X, F ) и H = (Y, P ) заданы следующим образом:

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 5 3 2 3 1 1 1 4 4 6 4 1 3 2 1 G H 6 6 4 5 4 2 2 5 7 7 5 3 6 3 2 7 7 6 8 8 3 8 7 8 8 6 7 8 5 4 Так как графы G и H являются однородными графами степени три без петель [4], то первые три разбиения 1, 2, 3 будут триви альными и состоят из одного элемента, т. е. 1 = 2 = 3 = {X} (соответственно {Y } для графа H). Поиск разбиения и биекции, удовлетворяющих теореме об изоморфизме, будем проводить од новременно для графов G и H.

Построим разбиение 4 для графа G. Как видно из определения разбиения 4, каждый его класс характеризуется тем, что для любой вершины x существует y, такой, что = |F x F y| одно и то же для всех таких пар.

Анализируя таблицу графа G, устанавливаем, что наибольшим таким является = 2. Этим характеризуется класс 02 = (1, 2, 6, 7), так как |F 1 F 2| = |F 6 F 7| = 2.

Аналогично 02 = (1, 2, 7, 8) для графа H.

Так как |02| = |02| и они характеризуются одним, то в слу чае, если G и H изоморфны, существует биекция между элемен тами 02 и 02. Будем обозначать этот факт так 4(02) = 02.

Заметим, что в силу того, что |X| = |Y |, i(X) = Y i = 1, 2, 3, очевидно следующее 01 = (3, 5, 8), так как F 3 F 5 F 8 = 4, 01 = (4, 5, 6), так как P 4 P 5 P 6 = 3.

Оставшиеся вершины в G и H образуют одноэлементные клас сы 00 = (4), 00 = (3).

Таким образом, если G и H изоморфны, то 4(01) = 01, 4(4) = (3).

Построим разбиение 5. С этой целью упорядочим для каждого x (соответственно y ) вершины в F x (соответственно в P y) таким образом, чтобы в каждой строке F (соответственно P ) находились вершины одного и того же класса разбиения (если это возможно).

Так, частичная таблица для 02 (соответственно для 02) будет иметь вид 02 1 7 2 6 02 1 2 7 5 8 3 3 4 6 4 6 2 6 2 7 7 1 7 1 7 1 8 8 2 Но для класса (3, 5, 8) сделать это можно лишь в том случае, если разбить его на два: 011 = (5, 8), 012 = (3). Действительно, 012 3 011 5 2 1 4 4 6 8 Соответственно 011 = (5, 6), 012 = (4). Но тогда и классы (1, 7, 2, 6) (соответственно (1, 2, 7, 8) в H) распадутся на два класса:

(1, 7) = 021 и 022 = (2, 6) (соответственно 021 = (1, 7), 022 = (2, 8)). Так как |011| = |011| и |012| = |012|, то в случае изо морфности G и H 5(021, 022) = (021, 022), 5(011) = 011, 5(012) = 012, 5(4) = (3).

Из анализа F (021), F (022), P (021), P (022) ясно, что 5(021) = 022, 5(022) = 021.

Зафиксируем на всех элементах разбиений в G и H некоторые порядки, например те, которые указаны выше при их записи, и проверим, яиляется ли диаграмма (2.6.1) в этом случае коммута тивной.

Если обозначить для двухэлементного класса через инвер сию ее элементов, то диагpамма (2.6.1) для 011 и соответствую щего ему при отображении 5 класса 011 будет иметь вид 011 - - P F (021,2 00, 011) - (,2 00, ) - 022 и не являться коммутативной в силу того, что 5(021) = С, т.

е. из-за несогласованности правых верхних индексов.

Попробуем поменять порядок на 011, заменив его на (6, 5), тогда P (011) С, а С превратится в 022 и P (011) = 011 (022,2 00, С ).

Аналогичным образом можно проверить и другие соответствия элементов разбиения из X/ и Y /. Такая проверка показывает, что 5{(1, 7), (2, 6), (5, 8), (3), (4)} = {(2, 8), (1, 7), (6, 5), (4), (3)} и, следовательно, 5 = и 5 =, а перестановка имеет вид 1 2 3 4 5 6 7 =.

2 1 4 3 6 7 8 2.7. Теорема об автоморфизмах автомата О п р е д е л е н и е 26. Конечным автоматом без вы ходов называется тройка A = (Q, X, F ), где Q и X Ч конечные непустые множества состояний и выходных символов соответ ственно, а F : X Q Q Ч функция переходов.

Если задано разбиение множества Q на подмножества Qk, то будем считать, что подмножества Qk наделены циклическим по рядком, и называть их циклами. Именно в этом смысле будем далее отождествлять множество Q с перестановкой, а о подмножествах Qk говорить как о циклах.

Через F будем обозначать распространение отображения F на множество подмножеств Qk множества Q.

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

Всюду в дальнейшем соотношение F (Qk, {x}) = Qi, n 1, n означает, что F (Qk, {x}) есть совокупность из n тождественных циклов Qi.

О п р е д е л е н и е 27. Автоморфизмом автомата A = (Q, X, F ) называется любая перестановка g на Q, такая, что {( q Q)( x X)(g(F (q, x)) = F (g(q), x))}.

О п р е д е л е н и е 28. Конгруенцией автомата A бу дем называть разбиение множества Q на непересекающиеся подмножества Qk, такие, что {( Qk )( x X)( Qi )(F (Qk, {x}) Qi)}, где i, k > 0 Ч целые числа.

Теорема 14. Конгруенция порождает автоморфизм тогда и только тогда, когда ( Qk )( x X)( Qi )(F (Qk, {x}) = Qi.

p Д о к а з а т е л ь с т в о. Н е о б х о д и м о с т ь. Пусть g Ч автоморфизм, а Q1, Q2,..., Qm Ч элементы разбиения. Тогда формулировка теоремы равносильна эквивалентности следующих двух соотношений:

{( g)( q Q)( x X)(g(F (q, x)) = F (gq, x))}, (2.7.1) {( )( Qk )( x X)( Qi )(F (Qk, {x}) = Qi)}, (2.7.2) p т. е. (1.3.1) (1.3.2) (1.3.1).

Если Qk Ч произвольный цикл автоморфизма g, то (2.7.1) эк вивалентно соотношению {( x X)(g(F (Qk, {x})) = F (gQk, {x}))}. (2.7.1) Зафиксируем на Qk начальный элемент относительно некоторой его записи. Разобьем Qk на классы эквивалентности Qki, относя к одному классу Qki те элементы q Qk, которые при отображении F имеют один и тот же образ при некотором фиксированном, но произвольном x.

Так как g Ч автоморфизм, то ij {( qi Qki)( qj Qkj)( x X)( rij > 0)(gr qi = qj& ij ij &F (gr qi, x) = gr (F (qi, x)))}.

Покажем, что любой паре классов Qki, Qkj из Qk может быть поставлено в соответствие одно rij.

Действительно, если существуют r и R, такие, что grqi = qj, gRqi = qj, где qi, q Qki, а qj, qj Qkj, то gr(F (qi, x)) = F (grqi, x) = F (qj, x), gR(F (q, x)) = F (gRq, x) = F (qj, x). Анало гично F (qi, x) = F (q, x). Так как gr и gR Ч автоморфизмы, то R r(mod ). Здесь такое, что g+1 = g.

Таким образом, для любой пары классов Qki и Qkj найдено та ij ij кое rij, что gr (Qki) = Qkj. Так как gr Ч биекция, то Qki и Qkj равномощны.

Покажем, что в случае, когда F : Qk {x} Qk, F действует на Qk как циклическая перестановка.

Пусть q1, q2 Qk. Существует r > 0, такое, что grq1 = q2. Пусть F (q1, x) = q и F (q2, x) = q. Тогда, если grq = q, то F действует на Qk как циклическая перестановка. В самом деле, grq = gr(F (q1, x)) = F (grq1, x) = F (q2, x) = q.

Рассмотрим случай F : Qk {x} Qi. Возмем q и q из Qk, 1 2 1 такие, что F (q, x) Qi, F (q, x) Qi, и пусть Qi = Qi. Тогда найдется r > 0, такое, что grq = q, а gr(F (q, x)) = F (grq, x), 1 так как gr(F (q, x)) Qi и F (grq, x) Qi. А это противоречит 1 автоморфности g. Таким образом, Qi = Qi.

В силу равномощности классов эквивалентности из Qk найдется p > 0 целое, такое, что F (Qk, {x}) = Qi.

p Покажем, что все Qi упорядочены одним и тем же образом и этот порядок с точностью до циклического сдвига совпадает с ис ходным порядком на Qi, т. е. F (Qk, {x}) = Qi.

p Пусть это не так и n = |Qk|, m = |Qi|, n = pm. Возьмем q и q из Qk, такие, что q = q и F (q, x) = F ( x). Пусть F (q, x) Qi, q, 2 1 а F ( x) Qi, Qi = Qi, но порядок на них неодинаков. Если q, 1 F (q, x) имеет номер k1 в Qi, а F ( x) Ч k2 в Qi и |k1 - k2| < m, q, то r = lm + k2 - k1 таково, что grq = q, и в силу автоморфности gr 2-k имеем F ( x) = F (grq, x) = grF (q, x) = gk (F (q, x)) = F (q, x), q, так как |k2 - k1| < m, что противоречит выбору q и q.

Таким образом, F (Qk, {x}) = Qi и (1.3.2) доказано.

p Д о с т а т о ч н о с т ь. Пусть имеет место соотношение (2.7.2).

Доопределим порядки на Qk до циклических и положим g = {Qk}k.

В случае i = k соотношение (2.7.1), очевидно, выполняется для всех q Qk и x X, так как F действует на Qk как циклическая перестановка, по определению равенства =. В случае i = k обозна чим через R отношение элвивалентности на Qk по mod F, тогда имеет место соотношение F (Qk/R, {x}) = Qi. Классы Qki из Qk/R равномощны, а F Ч биекция и, следовательно, F g = gF, так как g- биекция. Таким образом, и в этом случае F (gq, x) = g(F (q, x)) для любого q Qk, т. е. g Ч автоморфизм.

П р и м е р 12. Пусть автомат А задан таблицей x\Q| 0 1 2 3 4 5 6 7 8 x1 | 1 3 7 1 5 4 9 2 1 x2 | 3 1 5 1 2 7 0 4 3 x3 | 8 1 8 1 0 0 3 8 0 Как следует из теоремы, разбиение множества Q на классы (0, 8), (1), (3), (4, 2, 5, 7), (6, 9) порождает автомоpфизм, если на каждом классе определить циклические порядки. Действительно, F ((0, 8), x1) = (1), F ((0, 8), x2) = (3), 2 F ((0, 8), x3)) = (8, 0), F ((2, 4, 7, 5), x1) = (7, 5, 2, 4), (2.7.3) F ((2, 4, 7, 5), x2) = (5, 2, 4, 7), F ((2, 4, 7, 5), x3) = (8, 0),...

Таким образом, перестановка 0 1 2 3 4 5 6 7 8 g = 8 1 5 3 2 7 9 4 0 является автомоpфизмом.

2.8. Теорема об автоморфизмах гафов Пусть G = (X, F ) Ч граф Бержа, у которого X Ч множество вершин, а F : X X Ч отображение, ставящее в соответствие каждому x X множество вершин, в которые из x идут дуги.

Пусть Ч разбиение множества X на попарно не пересекаю щиеся классы, а X/ Ч множество полученных в результате раз биения классов.

О п р е д е л е н и е 29. Автоморфизмом графа G = (X, F ) называется биекция : X X, такая, что для всех x X и y X, для которых (x) = y, выполняется соотношение (F x) = F ((x)). (2.8.1) Как уже указывалось, всю группу автомофизмов графа G мож но вычислить, зная свойство циклов автоморфизма графа относи тельно графовского отображения.

Каждый вычисленный автоморфизм порождает циклическую подгруппу группы автоморфизмов графа, и в силу его конечнос ти вся группа графа [5] исчерпывается конечным числом таких циклических подгрупп.

Пусть Ч разбиение множества X на непересекающиеся клас сы k, такое, что F k, где F Ч распространение F на множество классов X/, представляет собой множество классов из X/.

Зафиксируем некоторые порядки на каждом классе из X/. Упо рядочим элементы из F k для каждого x k таким образом, чтобы все элементы, имеющие после упорядочения один и тот же номер, принадлежали одному и тому же классу из X/. Множество элементов из F k, имеющие один и тот же номер после упорядо чения, будем обозначать F(m)k или (F k)m. Как и ранее, через p обозначим p копий упорядоченного множества, а соотношение (F (k))m = i(m), i, k X/ p (p > 0 Ч целое число), означает, что правая часть его представля ет собой совокупность из p упорядоченных одним и тем же образом копий множества i, причем порядок на i совпадает с исходным порядком на нем с точностью до циклического сдвига.

Теорема 15. Разбиение множества X графа G = (X, F ) порождает автоморфизм g тогда и только тогда, когда для лю бого класса k и любого m > 0 найдется k, такой, i(m) что (F (k))m = k (2.8.2) pi(m) i(m) при |k| > 1 и F k = {k }i (2.8.3) i при |k| = 1.

Д о к а з а т е л ь с т в о. Н е о б х о д и м о с т ь. Пусть Ч разбиение множества X на классы {k}, каждый из которых упорядочен циклическим образом, составляет автоморфизм g.

Пусть x k, y k, |k | |k | > 1, таковы, что F(m)x = y.

1 2 2 Для произвольного, но фиксированного m > 0 разобьем множес тво k на классы k i, относя в один класс те и только те элементы 1 z и z k, которые удовлетворяют соотношению F(m)z = F(m)z.

Так как g Ч автоморфизм, то ij ( xi k i)( xj k j)( rij > 0)(gr xi = 1 ij ij = xj&gr (F(m)xi) = F(m)(gr (xi))).

Покажем, что любой паре k i и k j из k можно поставить в 1 1 соответствие одно rij.

Пусть xi, xi k i, xj, xj k j, а r и R таковы, что grxi = 1 xj, gRxi = xj. Тогда в силу того, что gr gR Ч автоморфизмы, gr(F(m)xi) = F(m)(gr(xi)) = F(m)xj, gR(F(m)xi) = F(m)(gR(xi)) = F(m)xj, но так как xi, xi k i, xj, xj k j, то F(m)xi = F(m)xi, F(m)xj = 1 F(m)xj и, следовательно, r R( mod ), где > 0 такое, что g+1 = g.

Итак, для любой пары классов k i и k j существует rij, для 1 ij ij которого gr (k i) = k j. Так как gr Ч биекция, то |k i| = |k j| 1 1 1 и, следовательно, существует такое p > 0, что F(m)k = k.

p 1 Покажем, что все копии k в F(m)k упорядочены одинаковым 2 образом и порядок на них совпадает с исходным с точностью до циклического сдвига.

Доказательство будем вести от противного.

Пусть |k | = n, |k | = l, n = pl. Рассмотрим такие x, x k, 1 2 что x = x, F(m)x = F(m)x и F(m)x k, F(m)x k, причем k = 2 2 k, но поpядки на них, как на подмножествах из F(m)k, разные.

2 Пусть F(m)x имеет номер i1 в k, а F(m)x Ч номер i2 в k и 2 |i2 - i1| < l, тогда r = sl + i2 - i1 таково, что grx = x и в силу того, что gr Ч автоморфизм, 2-i F(m)x = F(m)(gr(x)) = gr(F(m)x) = gi (F(m)x) = F(m)x, что противоречит выбору x и x.

Следовательно, F(m)k = k. (2.8.4) p 1 Так как m выбиралось произвольно, то соотношение (2.8.4), а следовательно, и (2.8.2), выполняется для всех m.

В силу произвольности выбора класса k из разбиения соот ношение (2.8.2) выполняется для всех k, таких, что |k| > 1. А так как r Ч вычет по модулю , то порядки на i отличаются на циклический сдвиг.

Пусть |k| = 1 и k = {x}. Тогда, в силу соотношения g(x) = x и того, что g Ч автоморфизм, g(F x) = F g(x) = F x. Но для любого k X/, g(k) = k, поэтому любой непустой след класса k на F x совпадает с самим классом k.

Таким образом, F k = {k }i при |k| = 1.

i Д о с т а т о ч н о с т ь. Пусть разбиение таково, что соотно шение (2.8.2) выполняется для всех m и любых k из. Покажем, что разбиение порождает автоморфизм g.

Доопределим порядки на классах k до циклических. В качестве перестановки g возмем совокупность циклов {k}. Очевидно, что для каждого класса k разбиения g(k) = k. А так как для s любого m > 0 имеем (F k)m = k, то g((F k)m) = (g(k )), где p p i i s Ч циклический сдвиг на некоторое количество разрядов.

s Так как g и s Ч биекции, то g(k ) = (g(k ))s.

i i Рассмотрим элементы x, x k, такие, что F(m)x = F(m)x = y k. Тогда существут r > 0, такое, что gr(x) = x. Так как i F(m)k = k, то номера у F(m)x и F(m)x совпадают в соответ p i ствующих копиях k. Тогда r = sl и gr(y) = y при некотором s, i где l = |k |, n = |k| и n = pl, p s. Так как F(m)x = F(m)x, то i gr(F(m)x) = gr(F(m)x) = gry, F(m)grx = F(m)x = y.

Таким образом, gr(F(m)x) = F(m)grx = F(m)x для x и x связанных между собой автоморфизмом = gr, т. е. таких, что (x) = x.

П р и м е р 13. Пусть граф G задан с помощью следующей таблицы:

1 2 3 4 5 6 7 5 3 2 3 1 1 1 6 6 4 5 4 2 2 7 7 6 8 8 3 8 Здесь X = {1, 2, 3, 4, 5, 6, 7, 8}. Покажем, что разбиение = {(1, 7), (2, 6), (3), (4), (5, 8)} (2.8.5) порождает автоморфизм 1 2 3 4 5 6 7 g =.

7 6 3 4 8 2 1 Зафиксируем на элементах разбиения те порядки, которые определились в результате записи в (2.8.5). Тогда частичные таблицы, после соответствующего упорядочения элементов обра зов, соответствующие элементам разбиения будут иметь вид 1 7 2 6 3 4 5 5 8 3 3 2 3 4 6 2 6 2 6 5 1 7 1 7 1 4 8 8 Нетрудно заметить, что каждый элемент разбиения удовлетво ряет соотношению (2.8.2).

В соответствии с доказательством достаточности теоремы об автоморфизмах графов коммутативны следующие диаграммы:

1 - 7 2 - -- - 5, 6, 7 - 8, 2, 1 3, 6, 7 - 3, 2, -- - 5 - - 4, 1, 8 - 4, 7, - что эквивалентно автоморфности g.

АВТОМАТЫ 3.1. Полностью определенные автоматы Расмотрим автомат, у которого кроме функции переходов зада на также функция выходов.

О п р е д е л е н и е 30. Конечным автоматом называется набор из пяти объектов M = [X, Q, Y, F, ]. Здесь X = {x0, x1,..., xn} Ч выходные символы (входной алфавит), Q = {q0, q1,..., qr} Ч множество внутренних состояний, Y = {y0, y1,..., ym} Ч множество выходных символов (выход ной алфавит), F : Q X Q Ч функция перехода (в следующее состояние), : Q X Y Ч функция выхода.

Автоматы мы будем задавать в виде таблицы. Например, если X = Y = {0, 1}, Q = {q0, q1, q2}, то автомат M может быть задан следующим образом с помощью функций перехода и выхода F : (q0, 0) q1 : (q0, 0) (q0, 1) q0 (q0, 1) (q1, 0) q2 (q1, 0) (q1, 1) q1 (q1, 1) (q2, 0) q0 (q2, 0) (q2, 1) q2 (q2, 1) Или в виде таблицы Q F 0 1 0 q0 q1 q0 0 q1 q2 q1 1 q2 q0 q2 1 которую следует понимать таким образом. В первой колонке пе речисляются элементы множества Q. В первой строке перечисля ются элементы входного алфавита X. Во второй колонке таблицы задается функция перехода F. А в третьей колонке Ч функция выхода.

Так, если на вход автомата подается последовательность вход ных символов x = 01, то автомат, начинающий свою работу из состояния q0, под действием входного символа 0 переходит в состо яние q1 и на выходе появляется символ 0. Под действием входного символа 1 из состояния q1 автомат переходит в состояние q1 и на выходе появляется 0.

Пусть M = [X, Q, Y, F, ] некоторый автомат. Тогда по любой входной строке x = x0, x1,..., xr-1 длины r и по любому началь ному состоянию q0 Q однозначно определяется строка длины r внутренних состояний q = q0, q1,..., qr-1, которая получается по следовательным применением отображения F, точнее qj+1 = F (qj, xj);

j = 0, 1,..., r - 2. (3.1.1) Аналогично, yj = (qj, xj);

j = 0, 1,..., r - 1. (3.1.2) Поэтому, рассматривая автомат как устройство, преобразующее пары (q0, x = x0,..., xr-1) в строки q = q0, q1,..., qr-1 и y = y0, y1,...yr-1 мы можем с помощью (1) и (2) определить функции r Fr : Q Xr Qr;

r : Q Xr Y. (3.1.3) r Здесь Xr, Y, Qr множество строк длины r символов из X, Y, Q со ответственно.

Далее будет решаться следующая задача.

Пусть входной и выходной алфавит фиксированы. По даннаому автомату M = [X, Q, Y, F, ] найти автомат M = [X, Q, Y, F, ] с меньшим числом состояний, но с той же функцией, переводящей входы в выходы.

О п р е д е л е н и е 31. Автомат M покрывает автомат M, и пишут M M, если входной и выходной алфавиты у этих автоматов общие и существует функция : Q Q, такая, что для любого положительного числа r r(q, x) = r((q), x) при всех x Xr. (3.1.4) О п р е д е л е н и е 32. Автоматы M и M эквивалентны, и в этом случае пишут M M, если M покрывает M и M по крывает M, т.е. кроме функции : Q Q со свойством (3.1.4), существует функция : Q Q, такая, что r(q, x) = r((q), x) при всех q и x Xr. (3.1.5) О п р е д е л е н и е 33. Морфизмом называется такое отображение : Q Q, что F ((q), x) = (F (q, x)) и ((q), x) = (q, x), (3.1.6) для всех q Q и x X.

Если сюръективно, то оно эпиморфизм, если биективно, то Ч изоморфизм.

Лемма 4. Пусть эпиморфизм автомата M на M, тогда для любой входной строки x = x0, x1,..., xn-1 и начального состояния q0 Q выходная строка y = y0, y1,..., yn-1 автомата M совпада ет с выходной строкой автомата M, если начальное состояние автомата M равно q0 = (q0).

Д о к а з а т е л ь с т в о. Доказательство проводится индукцией по n.

qk+1 = F (qk, xk) = F ((qk), xk) = (F (qk, xk)) = (qk+1), k = (qk, xk) = ((qk, xk) = (qk, xk) = yk.

О п р е д е л е н и е 34. Состояния qi и qj называются r-эквивалентными, если для всякой входной строки x Xr r(qi, x) = r(qj, x) В этом случае пишут qiErqj или (qi, qj) G(Er), где G(Er) Ч график бинаоного отношения Er. Если qiErqj для всех r, будем писать qiEqj и говорить, что qi и qj эквивалентны. Бинарные отношения E и Er Ч отношения эквивалентности.

Вместо (qi, qj) G(Er) мы пишем qiErqj. Например, для авто / мата (A) Q F 0 1 0 q0 q2 q1 0 q1 q0 q2 1 q2 q0 q1 0 графики 1-эквивалентных и 1-неэквивалентных состояний име ют вид G(E1) = {(q0, q2), (q2, q0), (q0, q0), (q1, q1), (q2, q2)} G(E1) = {(q0, q1), (q1, q0), (q1, q2), (q2, q1)} Решение задачи минимизации оказывается лучше всего начать с выявления неэквивалентных состояний.

О п р е д е л е н и е 35. Положим F : Q Xr Q :

F (q0, x) = qr-1 = F (...(F (F (q0, x0), x1),...), xr-2).

Это означает. что F (q0, x) есть последнее состояние авто мата, начавшего работу в состоянии q0 и считавшего входную строку x длины r.

Положим далее : Q Xr Y :

(q0, x) = yr-1 = (...F (F (q0, x0), x1),..., xr-1).

Это означает, что (q0, x0) есть последний символ выходной стро ки автомата, начавшего работу в состоянии q0 и считавшего вход ную строку x.

Так, для автомата (A) при r = 3 имеем F (q0, 101) = q1, F (q1, 101) = q1, (q0, 101) = 1, (q1, 101) = 1.

Две теоремы о неэквивалентных состояниях.

Теорема 16. Если qiEqj, то либо qiE1qj, либо для подходя щей строки x = (x0,..., xr-1) имеем F (qi, x)E1F (qj, x)).

Д о к а з а т е л ь с т в о. Утверждение qiEqj означает, что (qi, x) = (qj, x) для подходящей строки x = (x0,..., xr-1). При необходимости мы можем укоротить входную строку x так, чтобы выходные строки, отвечающие qi и qj, отличались только послед ними символами. Пусть это уже сделано. Если после этого r = 1, то, очевидно, qiE1qj. Если же r > 1, то qiErqj, но qiEkqj при k < r.

Таким образом, последние выходные символы автомата, считав шего x, различны, если он исходил из начальных состояний qi и qj соответственно. Чтобы выходы отличались, (qi, x) = (qj, x), должно быть F (qi, x)E1F (qj, x). Иначе последний входной сим вол xr-1 даст один и тот же выходной символ.

Имеет место более сильная теорема.

Теорема 17. Если qiErqj, но qiEkqj для всех k < r, то F (qi, xl)Er-1F (qj, xl) для подходящего xl X.

Д о к а з а т е л ь с т в о. Переформулировка этого утверждения такова: если (qi, qj) G(Er) - G(Er-1), то для подходящего xl X имеем (F (qi, xk), F (qj, xk)) G(Er-1) - G(Er-2).

Эта теорема утверждает, что состояния qi, qj, эквивалентные относительно всех входных последовательностей длины r - 1, мо гут оказаться неэквивалентными относительно последовательнос тей длины r только в том случае, когда имеется символ xk, пе реводящий qi, qj соответственно в состояния ql, qm, неэквивалент ные относительно подходящей входной последовательности длины r-1. Это означает, что на r-м шаге достаточно исследовать состо яния в G(Er-1) и установить, найдется ли пара qi, qj, переходящая в пару ql, qm со свойством qlEr-1qm. В этом случае qiErqj.

Если мы уже определили G(E1), то G(E2) состоит из G(E1) и таких упорядоченных пар (qi, qj), что для некоторого xp имеем (F (qi, xp), F (qj, xp)) G(E1). В общем случае нужно исследовать каждый раз только G(Er-1)-G(Er-2). Таким способом мы сумеем рекурсивно определить G(E) и, наконец, G(E) Ч дополнение к G(E) в булевой алгебре подмножеств S S.

Доказательство теоремы проводится непосредственно. Если па ра (qk, ql) лежит в G(Er-1), то она не лежит в G(Er) - G(Er-1).

Значит, нужно рассматривать лишь такие пары (qk, ql), что для некоторой строки x Xr имеем (qk, x) = (ql, x), а для всех строк x Xr-1 имеем (qk, x) = (ql, x). Но это в точности те пары, которые переводятся в G(E1) (r - 1)-м входным символом xr-2 и, стало быть, в G(Er-1) - G(Er-2) некоторым символом x0 X.

Лемма 5. Если G(Er) - G(Er-1) =, то G(Er) = G(Er+k) для всех k 0.

Действительно, дальнейшие шаги не добавят новых пар состо яний, ибо, согласно теореме 2, дополнение G(Er+1)-G(Er) состоит из тех пар, которые переводятся подходящим символом xi X в дополнение G(Er) - G(Er-1).

П р и м е р 14. Пусть автомат M задан следующей таблицей:

Q F 0 1 0 q1 q1 q2 1 q2 q1 q3 1 q3 q5 q1 1 q4 q4 q2 1 q5 q4 q3 1 При формировании графиков неэквивалентных состояний мы в дальнейшем не бедем включать в перечень неэквивалентных со стояний симметричные к данным пары, а в графики эквивалент ных состояний не включать еще и пары типа (qi, qi).

График 1-неэквивалентных состояний для данного автомата имеет вид:

G(E1) = {(q1, q5), (q2, q5), (q3, q5), (q4, q5)}.

Согласно теореме 17, график 2-неэквивалентных состояний состо ит из 1-неэквивалентных состояний и тех пар состояний, кото рые под действием некоторого входного символа переходят в 1 неэквивалентные состояния, т.е.

G(E2) = G(E1) {(q1, q3), (q2, q3), (q3, q4)}.

Аналогично, G(E3) = G(E2) {(q1, q2), (q2, q4)}.

Дальнейший перебор показывает, что G(E3) = G(E4). Таким обра зом, G(E4) = G(E3), E = E3 и q1Eq4, а остальные пары состояний неэквивалентны.

3.2. Неполностью определенные автоматы Так как системы обычно проектируются по частям, то некото рые входные последовательности либо вообще не встречаются для данного подавтомата, либо реакция на некторые последователль ности нас не интересует. Это приводит к тому, что некоторые позиции в таблицах состояний и выходов подавтоматов отсуст вуют. Такие позиции называются неопределенными и в таблицах обозначаются прочерком. Например, Q F 0 1 0 q0 q2 q1 0 q1 Ч q2 1 q2 q0 q1 Ч Для описания способа минимизации неполностью определенных автоматов нам потребуются следующие определения.

О п р е д е л е н и е 36. Входная последовательность x = x0, x1,..., xr-1 называется допустимой для автомата в на чальном состоянии qj, если функция F перехода в следующее состояние определена для всех элементов последовательности, кроме, возможно, последнего.

Таким образом, начальное состояние qj и допустимая входная последовательность x однозначно определяют строку внутренних состояний, за исключением того, что последнее состояние может быть неопределенным.

О п р е д е л е н и е 37. Выходная строка y покрывает выход ную строку y ( в которой могут быть неопределенные символы), если всякий определенный символ yj в y равен соответствующе му символу yj в y.

Например, строка y = 0, 1, 1 покрывает строку y =Ч,1,1. Стро ка 0,1,0 покрывает Ч,1,0. Если y покрывает y, то пишем y y.

О п р е д е л е н и е 38. Если r(qk, x) r(qj, x) для всех x допустимых для qj, мы пишем qk qj и говорим, что qk покры вает qj.

О п р е д е л е н и е 39. Автомат M покрывает автомат M, если для каждого состояния qj автомата M существует такое состояние qk автомата M, что r(qk, x) r(qj, x) для всех x, допустимых для qj.

В этом случае мы пишем M M. Очевидно, в случае M = M состояние qk покрывает qj, если r(qk, x) r(qj, x) для всех x, допустимых для qk, и мы пишем qk qj.

Рассмотрим следующие автоматы Q 0 1 0 1 Q 0 1 0 q0 q0 q1 0 1 q0 q0 q0 0 q1 q1 q0 - 1 q1 q0 q1 1 q2 q0 q2 1 Автомат M покрывает автомат M, так как состояние q0 покры вает состояния q0 и q1, а состояние q1 покрывает q2.

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

О п р е д е л е н и е 40. Выходная строка y совместима с выходной строкой y, если в каждой позиции, где символы обе их строк определены, они совпадают. В этом случае мы будем писать yy.

Например, строка 0,1,Ч,1 совместима с 0,Ч,1,Ч, или с Ч,0,Ч,1. Заметим, что не является отношением эквивалентности. Оно рефлексивно, симметрично, но не транзитивно.

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

О п р е д е л е н и е 41. Состояние qi называется сов местимым по выходу с состоянием qj, если (qi, x)(qj, x) для всех x X. В этом случае мы пишем qi qi. Если состояния не совместимы по выходу, мы пишем qk qi.

Иначе говоря, два состояния совместимы по выходу, или 1 совместимы, если для каждого входного символа их выходы сов падают, когда они определены.

О п р е д е л е н и е 42. Состояния qi и qj называются совместимыми, если для всех x Xr, допустимых как для qi, так и для qj, имеем r(qi, x)r(qj, x).

В этом случае мы пишем qiqj. Если qk и ql совместимы не для всех x, мы пишем qkql. Если состояния qi и qj совместимы для всех строк фиксированной длины k, то состояния qi и qj называем k k-совместимыми и пишем qi qj.

Рассмотрим автомат M, заданный следующей таблицей:

Q F x1 x2 x3 x4 x1 x2 x3 x q1 q2 - q3 q2 0 - - - q2 q3 q5 q2 - 0 1 0 - q3 q3 q4 - q5 0 1 - q4 - q1 q2 - - 1 - - q5 - - q1 - - - 1 - Для упрощения записи состояние qi будем обозначать через i.

Тогда график 1-совместимых состояний будет иметь вид:

G( ) = (1, 2)(1, 3)(1, 4)(1, 5)(2, 3)(2, 4)(3, 4)(3, 5)(4, 5) Вычислим графики несовместимых состояний. Для чего по ав томату M вычислим следующую таблицу совместимости для 1 совместимых состояний и воспользуемся Теоремой 17 о несовмес тимых состояниях:

x1 x2 x3 x (1,2) (2,3) - (2,3) - (1,3) (2,3) - - (2,5) (1,4) - - (2,3) - (1,5) - - (1,3) - (2,3) - (4,5) - - (2,4) - (1,5) - - (3,4) - (1,4) - - (3,5) - - - - (4,5) - - (1,2) - Те пары 1-совместимых состояний, которые переходят под дей ствием некоторого входного символа в пару 1-несовместимых со стояний, согласно теореме 2 оказываются 2-несовместимыми и т.д.

Последовательное вычисление несовместимых состояний дает:

1 G() = (2, 5), G() = (2, 5)(1, 3), 3 G() = (2, 5)(1, 3)(1, 5), G() = (2, 5)(1, 3)(1, 5)(2, 4) Таким образом, график совместимых состояний будет иметь вид:

G() = (1, 2)(1, 4)(2, 3)(3, 4)(3, 5)(4, 5) Расширим теперь понятие совместимости, учитывая, что склеи ваться могут не только пары состояний.

О п р е д е л е н и е 43. Совместимым классом Ck называ ется такое множество внутренних состояний q1, q2,..., qm, что qiqj для всех qi, qj Ck.

Для выше приведенного автомата совместимые классы таковы:

(1,2),(1,4),(2,3), (3,4),(3,5),(4,5).

О п р е д е л е н и е 44. Некоторое множество совмести мых классов называется согласованным, если для любого класса Ck из этого множества и любых его элементов qi, qj внутренние состояния F (qi, xk), F (qj, xk) принадлежат подходящему совмес тимому классу Ci для любого входного символа xk.

О п р е д е л е н и е 45. Некоторое множество совместимых классов называется замкнутым, если всякое внутреннее состо яние автомата принадлежит хотя бы одному из этих классов.

Теорема 18. Пусть задано замкнутое согласованное мно жество совместимых классов для автомата M. Тогда сущест вует автомат M, состояния которого получаются склеиванием всех состояний M, содержащихся в одном совместимом классе из данного множества.

Д о к а з а т е л ь с т в о. Пусть задано замкнутое согласованное множество совместимых классов. Склеим все состояния класса Ci в одно новое состояние qj. Определим (qj, xk) как (qi, xk), если эти значения определены для всех qi Ci. Определим F (qj, xk) как qm, если F (qj, xk) Cm для всех qi Ci. Каждое новое состояние покрывает все состояния соответствующего класса.

Очевидно, для получения минимального автомата M, необ ходимо выбрать замкнутое согласованное множество совмести мых классов, состояшее из наименьшего числа согласованных классов. Вт предыдущем примере таким множеством является (1,2),(2,3),(4,5), а соответствующий минимальный автомат имеет вид Q F x1 x2 x3 x4 x1 x2 x3 x q1 q2 q3 q2 q1 0 1 0 - q2 q2 q3 q1 q3 0 1 0 q3 - q1 q1 - - 1 1 - ДЕКОМПОЗИЦИЯ ГРАФОВ Здесь мы рассмотрим операции умножения, суммирования и композиции над множеством графов Бержа.

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

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

Как сам граф, так и его разложение по данной операции восста навливаются с точностью до изоморфизма по их представлениям.

4.1. Умножение, сумма и композиция графов Пусть G = (X, F ) Ч граф Бержа, X Ч множество вершин, а F : X X Ч соответствие, при котором каждому x X отвечает некоторое подмножество x из X вершин, в которые исходят дуги из x.

О п р е д е л е н и е 43. Представлением графа G называет - ся пара G = (TX, AF ), где TX = {(, )x}xX, = |F x|, = |F x| и AF : TX TX ставит в соответствие каждой паре (, )x из TX некоторое подмножество пар из TX по следующему правилу:

AF (, )x = {(, )x }x F x. (4.1.1) О п р е д е л е н и е 44. Граф Q = (Z, U) называется произведением графов G = (X, F ) и H = (Y, P ) и обозначается Q = G H, если Z = X Y и для каждого z из Z Uz = F x P y, x X, y Y, z = (x, y). (4.1.2) П р и м е р 15. Пусть даны графы G = (X, F ) и H = (Y, P ), где X = {x1, x2}, Y = {y1, y2, y3}, а F и P задаются следующими таблицами:

y1 y2 y x1 x F x2 x1 P y1 y2 y x y3 y Найдем произведение графов G и H. Согласно определению Q = G H = (Z, U) и Z = {(x1, y1)(x1, y2)(x1, y3)(x2, y1)(x2, y2)(x2, y3)}, Введем обозначения:

(x1, y1) = z1, (x1, y2) = z2, (x1, y3) = z3, (x2, y1) = z4, (x2, y2) = z5, (x2, y3) = z6, тогда Z = {z1, z2, z3, z4, z5, z6}. Согласно (4.1.2) Uz1 = F x1 P y1 = {z4, z6}, Uz2 = F x1 P y2 = {z5}, Uz3 = F x1 P y3 = {z4, z5}, Uz4 = F x2 P y1 = {z1, z3, z4, z6}, Uz5 = F x2 P y2 = {z2, z5}, Uz6 = F x2 P y3 = {z1, z2, z4, z5}.

Таким образом, таблица, задающая соответствие U, имеет вид U z1 z2 z3 z4 z5 z z4 z5 z4 z1 z2 z z6 z5 z3 z5 z z4 z z6 z Найдем представление графа Q, для чего построим таблицу, задающую соответствие U-1 графа Q = (Z, U-1), которое опре деляется как отображение, при котором каждому z из Z отвечает множество вершин из Z, из которых в z имеются дуги.

Из таблицы для U имеем U-1z1 z2 z3 z4 z5 z z4 z5 z4 z1 z2 z z6 z6 z3 z5 z z4 z z6 z Таким образом, TZ = {(2.2)1, (1.2)2, (2.1)3, (4.4)4, (2.4)5, (4.2)6}, где для краткости положено zi = i, i = 1, 6, а соответствие AU задается таблицей AU (2.2)1 (1.2)2 (2.1)3 (4.4)4 (2.4)5 (4.2) (4.4)4 (2.4)5 (4.4)4 (2.2)1 (1.2)2 (2.2) (4.2)6 (2.4)5 (2.1)3 (2.4)5 (4.4) (4.4)4 (1.2) (4.2)6 (2.4) Теорема 19. Пусть G = (X, F ) и H = (Y, P ) Ч два графа Бержа. Тогда вершина z = (x, y) графа Q = (Z, R) = G H обладает петлей тогда и только тогда, когда вершины x X и y Y обладают петлями.

Д о к а з а т е л ь с т в о. Теорему можно переформулировать следующим образом:

z Rz x F x & y P y.

Если (z = (x, y) Z) Rz = F xP y, то из определения декартова произведения следует, что x F x & y P y. И наоборот, если x F x & y P y, то z = (x, y) F x P y = Rz.

О п р е д е л е н и е 45. Граф N = (Z, L) называется суммой графов G и H и обозначается N = G + H, если Z = X Y и Lz = (F x {y}) ({x} P y), (4.1.3) где z = (x, y) Z;

x X;

y Y.

П р и м е р 16. Пусть даны графы G и H, из примерa 1. Очевид но, Z = (z1, z2, z3, z4, z5, z6), а отображение L : Z Z определяется следующим образом:

Lz1 = (F x1 {y1}) ({x1} P y1) = {z1, z3, z4}, Lz2 = (F x1 {y2}) ({x1} P y2) = {z2, z5}, Lz3 = (F x1 {y3}) ({x1} P y3) = {z1, z2, z6}, Lz4 = (F x2 {y1}) ({x2} P y1) = {z1, z4, z6}, Lz5 = (F x2 {y2}) ({x2} P y2) = {z2, z5}, Lz6 = (F x2 {y3}) ({x2} P y3) = {z3, z4, z5, z6}, или в табличной форме z1 z2 z3 z4 z5 z z1 z2 z1 z1 z2 z L z3 z5 z2 z4 z5 z z4 z6 z6 z z Теорема 20. Пусть N = (Z, L) = G + H и G = (X, F ), H = (Y, P ). Тогда (z = (x, y) Z) Lz x F x y P y.

Д о к а з а т е л ь с т в о. Если z = (x, y) Lz = F x{y}{x} P y, то (x, y) F x {y} и тогда x F x, либо (x, y) {x} P y, и тогда y P y.

И наоборот, если x F x, либо y P y, то (x, y) F x{y}, либо (x, y) {x}P y. Следовательно, z = (x, y) F x{y}{x}P y = Lz.

О п р е д е л е н и е 40. Граф K = (Z, R) называется композицией графов G и H и обозначается K = G H, если Z = X Y и Rz = (F x Y ) (X P y), (4.1.4) где z = (x, y) Z, x X, y Y.

Рассмотрим графы G и H из первого примера и вычислим их композицию. Как и ранее, Z = (z1, z2, z3, z4, z5, z6), а отображение R : Z Z задается системой равенств Rz1 = (F x1 Y ) (X P y1) = (z1, z3, z4, z5, z6), Rz2 = (F x1 Y ) (X P y2) = (z2, z4, z5, z6), Rz3 = (F x1 Y ) (X P y3) = (z1, z2, z4, z5, z6), Rz4 = Rz5 = Rz6 = (F x2 Y ) (X P y1) = (z1, z2, z3, z4z5, z6), или в табличной форме z1 z2 z3 z4 z5 z z1 z2 z1 TZ TZ TZ z3 z4 z R z4 z5 z z5 z6 z z6 z Теорема 21. Пусть T = (Z, M) = G H и G = (X, F ), H = (Y, P ). Тогда (z = (x, y) Mz) (x F x y Y ) (y P y x X).

Д о к а з а т е л ь с т в о. Из того, что z = (x, y) Mz = F x Y X P y, следует, что (x, y) F x Y и, значит x F x y Y, либо (x, y) X P y, и тогда y P y x X.

И наоборот, если x F x y Y, то (x, y) F x Y. А если y P y x X, то x, y X P y. Следовательно, z = (x, y) F x Y X P y = Mz.

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

Пусть G = (X, F ) и H = (Y, P ) Ч два графа Бержа. Обозначим через A множество операций {, +, }, а произвольную операцию из A Ч через.

О п р е д е л е н и е 46. Граф = G H = (Z, B) тогдa и только тогда, когда Z = X Y и Bz = (F x Y ) (X P y). (4.1.5) Здесь z = (x, y) Z, x X, y Y, X X, Y Y.

Из соотношени (4.1.5) следует, что различные алгебраические операции из A отличаются друг от друга выбором элементов из X и Y.

Если X = {x}, Y = {y}, то (4.1.5) определяет операции сум мирования Bz = (F x {y}) ({x} P y).

В том случае, когда X = F x, а Y = P y, (4.1.5) определяет операцию умножения Bz = F x P y.

Наконец, если X = X, а Y = Y, получаем операцию компози ции графов G и H : Bz = (F x Y ) (X P y).

Очевидно, операция ассоциативна и вместе с операцией объ единения подчиняется дистрибутивному закону.

Можно определить множество алгебраических операций, двой ственных операциям из A.

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

Граф, порождаемый отображением B, является дополнени ем по отображению до соответствующего насыщенного графа, у которого для любого z Z, Bz = Z.

В дальнейшем черта над множеством будет означать дополне ние до соответствующего множества вершин графа.

В силу соотношения (X Y ) \ (X Y ) = ((X - X) Y ) (X (Y - Y )), где X X, Y Y, Bz = (F x Y ) (X P y) = (F x Y ) (X P y) = ((X Y ) \ (F x Y )) ((X Y ) \ (X P y)) = (((X \ F x) Y ) (X (Y \ Y ))) (((X \ X) Y ) (X (Y \ P y))) = ((F x Y ) (X Y )) ((X Y ) (X P y)).

Если X = X \X и Y = Y \Y, то можно построить операцию, двойственную к операции, которая графам G и H сопоставляет граф S = GH, причем S = (Z, B), где Z = X Y, а Bz = ((F x Y ) (X Y )) ((X Y ) (X P y)). (4.1.6) Оказывается, операция композиции является двойственной к операции умножения. Подставляя в (4.1.6) F x и P y, получаем Uz = ((F x Y ) (X P y)) ((F x Y ) (X P y)) = = (F x Y ) (X P y), что является композицией дополнений по отображению исходных графов.

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

Из (4.1.5) и (4.1.6) вытекает G H = GH, GH = GH, и если учесть, что G = G, то получим G H = GH, GH = GH. (4.1.7) Оказывается, что графы G H и G H представляются в виде разложения по операциям, и, соответственно:

G H = (G H) (G H) (G H), G H = (G H) (G H) (G H).

4.2. Бинарные отношения и операции над графами Пусть G = (X, F ) Ч граф Бержа, где X Ч конечное множество, а F : X X такое, что F x X.

Функции F : X X можно сопоставить бинарное отношение на X следующим образом: yx y F x, x, y X. Тогда определение графа Бержа можно сформулировать так:

Графом Бержа называется пара G = (X, ), где X Ч конечное множество, а Ч бинарное отношение на X.

Пусть Ч бинарное отношение на X, а Ч на Y, тогдa = есть бинарное отношение на X Y, такое, что (x, y)(z, t) xz & yt, x, z X, y, t Y.

Определим бинарное отношение = + на X Y следующим образом:

(x, y)(z, t) (x = z & yt) (xz & y = t).

Здесь x, z X, y, t Y.

Бинарным отношением = на X Y называется отноше ние, определяемое следующим образом:

(x, y)(z, t) (xz yt).

Пусть G = (X, F ) и H = (Y, P ) Ч два графа Бержа и Q = G H, N = G + H, M = G H Ч произведение, сумма и композиция графов.

Теорема 22. Пусть G = (X, ) и H = (Y, ). Тогда Q = GH = (Z, ) тогда и только тогда, кoгда Z = XY и =.

Д о к а з а т е л ь с т в о. Пусть G = (X, F ), H = (Y, P ) Q = (Z, R) = G H, где Z = X Y. Тогда по функциям F : X X, P : Y Y R : Z Z построим бинарные отношения,, над множествами X, Y Z соответственно:

xx x F x, yy y P y zz z Rz, где z = (x, y), x X, y Y.

Имеет место следующая последовательность импликаций:

z = (x, y) R(x, y) = Rz = F x P y x F x & &y P y xx & yy (x, y)(x, y), откуда =.

И наоборот, если =, то по бинарным отношениям, и построим функции F : X X, P : Y Y и R : Z Z, где Z = X Y, следующим образом F x = {x X : xx}, P y = {y Y : yy} и Rz = {z Z : zz}.

Тогда (x, y)(x, y) (xx & yy) (x F x & y P y) (x, y) F x P y, и, следовательно, Rz = F x P y.

Если положить G = (X, F ), H = (Y, P ) и Q = (Z, R), то граф Q будет иметь вид Q = G H.

Теорема 23. Пусть G = (X, ) и H = (Y, ).Тогда N = G+H = (Z, ) тогда и только тогда, когда Z = XY и = +.

Д о к а з а т е л ь с т в о. Пусть G = (X, F ), H = (Y, P ) и N = (Z, L) = G + H. По функциям F,P и L, как и в теореме 22, построим бинарные отношения,. Тогда имеем z = (x, y) L(x, y) = Lz = F x {y} {x} P y (x, y) F x {y} (x, y) {x} P y (x F x & y = y) (x = = x & y P y) (xx & y = y ) (x = x & yy) (x, y)(x, y) и, следовательно, = +.

И наоборот, если = +, то по бинарным отношениям, и построим, как в теореме 22, функции F : X X, P : Y Y, L : Z Z, где Z = X Y. Тогда (x, y)(x, y) (xx & y = y) (x = x & yy) (x F x & y = y) (x = x & y P y) (x, y) F x {y} (x, y) {x} P y (x, y) F x {y} {x} P y Lz = L(x, y) = F x {y} {x} P y.

Если положить G = (X, F ), H = (Y, P ) и N = (Z, L), то N = G + H.

Теорема 24. Пусть G = (X, ) и H = (Y, ). Тогда M = (Z, ) = GH тогда и только тогда, когда Z = XY и =.

Д о к а з а т е л ь с т в о. Пусть G = (X, F ), H = (Y, P ) и M = (Z, T ) = G H, где Z = X Y. Как и ранее, по функциям F, P и T построим бинарные отношения, и. Тогда (x, y) T (x, y) = T z = F x Y X P y (x, y) F x Y (x, y) X P y (x F x y P y) (xx yy) (x, y)(x, y) и, следовательно, =.

И наоборот, если =, то по бинарным отношениям,, можно, как и ранее, построить функции F, P и T. В результате получим (x, y)(x, y) (xx y Y yy x X) (x F x y Y y P y x X) (x, y) F x Y (x, y) X P y (x, y) F x Y X P y T z = T (x, y) = = F x Y X P y.

Если положить G = (X, F ), H = (Y, P ) и M = (Z, T ), где Z = X Y, то M = G H.

4.3. Операции над представлениями Пусть G = (TX, AF ) и H = (TY, AP ) Ч представления графов G и H [2], где TX = {(, )x}xX, TY = {(, )y}yY.

Очевидно, представление графа = (Z, B) = G H есть пара = (TZ, AB), где AB : TZ TZ и для любой пары (, )z TZ имеют место равенства = |Y | + |X| - |(F x Y ) (X P y|, -1 - = |Y | + |X| - |(F x Y ) (X P y|.

Для каждой операции из A определим представление соответ ствующего графа = G H.

Теорема 25. Представление графа Q = (Z, U) = G H есть пара Q = (TZ, AU), где TZ = TX ХTY - множество всевозможных произведений пар из TX и TY, таких, что (, )x Х (, )y = (, )z = (, )z, (, )x TX, (, )y TY, а AU : TZ TZ таково, что AU(, )z = AF (, )x Х AP (, )y, x X, y Y, z = (x, y) Z.

Д о к а з а т е л ь с т в о. Действительно, -1 - (, )x = (|Uz|, |U-1z|) = (|F x P y|, |F x P y|) = -1 - = (|F x||P y|, |F x||P y|).

-1 - Если = |F x|, = |F x|, = |P y|, = |P y|, то (, )z = (, )z.

Положим по определению, (, )z = (, )x Х (, )y.

Так как Z Ч множество всевозможных упорядоченных пар эле ментов из X и Y, то TZ есть множество всевозможных произведе ний пар (, )x из TX и (, )y из TY и, следовательно, TZ = TX ХTY.

Определим отображение AU через AF и AP. Очевидно, AU(, )z = {(, )zС}z Uz=F xP y.

Так как прямому произведения X Y соответствует в представ лении произведения графов произведение TX Х TY, то F x P y будет соответствовать TF x Х TP y, где TF x = {(, )x }x F x, а TP y = {(, )y }y P y. Но {(, С)x }x F x = AF (, )x, аналогич но, {(, )y }yСP y = AP (, )y. Таким образом, AU(, )z = AF (, )x Х AP (, )y.

П р и м е р 17. Пусть даны графы G = (X, F ) и H = (Y, P ), где X = {x1, x2}, Y = {y1, y2, y3}, а F и P задаются следующими таблицами:

y1 y2 y x1 x F x2 x1 P y1 y2 y x y3 y Согласно определению Q = G H = (Z, U) и Z = {(x1, y1)(x1, y2)(x1, y3)(x2, y1)(x2, y2)(x2, y3)}, Введем обозначения:

(x1, y1) = 1, (x1, y2) = 2, (x1, y3) = 3, (x2, y1) = 4, (x2, y2) = 5, (x2, y3) = 6, тогда Z = {1, 2, 3, 4, 5, 6}.

Для вычисления представлений для графов G и H необходимо вычислить графы G и H. В нашем случае они имеют вид G x1 x2 H y1 y2 y x2 x1 y1 y2 y x2 y3 y Очевидно, TZ = TX Х TY = {(2, 2)1, (1, 2)2, (2, 1)3, (4, 4)4, (2, 4)5, (4, 2)6}. Тогда AU(2, 2)1 = AF (1, 1)x Х AP (2, 2)y = (2, 2)x Х {(2, 2)y, (2, 1)y } = 1 1 2 1 {(4, 4)4, (4, 2)6}, AU(1, 2)2 = AF (1, 1)x Х AP (1, 2)y = (2, 2)x Х (1, 2)y = (2, 4) 1 2 2 AU(2, 1)3 = AF (1, 1)x Х AP (2, 1)y = (2, 2)x Х {(2, 2)y, (1, 2)y } = 1 3 2 1 {(4, 4)4, (2, 4)5}, AU(4, 4)4 = AF (2, 2)x Х AP (2, 2)y = {(1, 1)x, (2, 2)x } Х 2 1 1 {(2, 2)y, (2, 1)y } = {(2, 2)1, (2, 1)3, (4, 4)4, (4, 2)6}, 1 AU(2, 4)5 = AF (2, 2)x Х AP (1, 2)y = {(1, 1)x, (2, 2)x } Х (1, 2)y = 2 2 1 2 {(1, 2)2, (2, 4)5}, AU(4, 2)6 = AF (2, 2)x Х AP (2, 1)y = {(1, 1)x, (2, 2)x } Х 2 3 1 {(22, )y, (1, 2)y } = {(2, 2)1, (1, 2)2, (4, 4)4, (2, 4)5}.

1 Таким образом, представление Q графа G имеет вид Q (2, 2)1 (1, 2)2 (2, 1)3 (4, 4)4 (2, 4)5 (4, 2) (4, 4)4 (2, 4)5 (4, 4)4 (2, 2)1 (1, 2)2 (2, 2) (4, 2)6 (2, 4)5 (2, 1)3 (2, 4)5 (1, 2) (4, 4)4 (4, 4) (4, 2)6 (2, 4) Теорема 26. Представление графа N = (Z, L) = G + H есть пара N = (TZ, AL), такая, что TZ = TX + TY, где TZ есть мно жество всевозможных сумм пар из TX и TY, определенных сле дующим образом:

( + - 1, + - 1)z, x F x, y P y, (, )x + (, )y = ( +, + )z, x F x y P y, / / а AL : TZ TZ таково,что AL(, )z = {AF (, )x + (, )y} {(, )x + AP (, )y}, где (, )z = (, )x + (, )y, z = (x, y) Z, x X, y Y.

Д о к а з а т е л ь с т в о. Действительно, если x F x или / y P y, то / = |F x {y}| + |{x} P y| = |F x| + |P y|, -1 -1 -1 - = |F x {y}| + |{x} P y| = |F x| + |P y|, -1 - и если |F x| =, |F x| =, |P y| =, |P y| =, то = +, = +.

Пусть x F x и y P y, тогда = |F x {y}| + |{x} P y| - |(F x {y}) ({x} P y)| = = |F x| + |P y| - 1 = + - 1.

Аналогично = + - 1.

Пусть (, )z = (, )x + (, )y = ( + - t, + - t)z, где t = при x F x, y P y и t = 0 во всех остальных случаях.

Из определения представления следует, что AL(, )z = {(, )z }z Nz=F x{y}{x}P y = = {(, )z }z F x{y} {(, )zС}z {x}P y.

Так как прямому произведению X Y в представлении для сум мы графов соответствует TX+TY, то из того, что F x X, {y} Y следует, что прямому произведению F x {y} будет отвечать TF x + T{y}. Аналогично прямому произведению {x} P y отвечает T{x} + TP y. Таким образом:

{(, )z }z F x{y} = TF x + T{y} = {(, )x }x F x + (, )y = = AF (, )x + (, )y, а {(, )z }z {x}P y = T{x} + TP y = (, )x + {(, )y }y P y = = (, )x + AP (, )y. З а м е ч а н и е. Следует отметить, что в случае, когда F x = - F x =, очевидно, должно быть (0, 0)x + (, )y = (, )z, если положить || = 0.

П р и м е р 18. Для графов G = (X, F ) и H = (Y, P ) из примера 17 построим представление N = (TZ, AL) графа N = (Z, L) = G + H. В данном случае имеем TZ = TX + TY = {(3, 3)1, (2, 3)2, (3, 2)3, (3, 3)4, (2, 3)5, (4, 3)6}.

Вычислим образы каждого элемента из TZ.

AL(3, 3)1 = AF (1, 1)x + (2, 2)y (1, 1)x + AP (2, 2)y = (2, 2)x + 1 1 1 1 (2, 2)y (1, 1)x + {(2, 2)y, (2, 1)y } = {(3, 3)4, (3, 3)1, (3, 2)3}, 1 1 1 AL(2, 3)2 = AF (1, 1)x + (1, 2)y (1, 1)x + AP (1, 2)y = (2, 2)x + 1 2 1 2 (1, 2)y (1, 1)x + (1, 2)y = {(2, 3)5, (2, 3)2}, 2 1 AL(3, 2)3 = AF (1, 1)x + (2, 1)y (1, 1)x1 + AP (2, 1)y = (2, 2)x + 1 3 3 (2, 1)y (1, 1)x + {(2, 2)y, (1, 2)y } = {(4, 3)6, (3, 3)1, (2, 3)2}, 3 1 1 AL(3, 3)4 = AF (2, 2)x + (2, 2)y (2, 2)x + {(2, 2)y, (2, 1)y } = 2 1 2 1 {(1, 1)x, (2, 2)x } + (2, 2)y (2, 2)x + {(2, 2)y, (2, 1)y } = 1 2 1 2 1 = {(3, 3)1, (3, 3)4, (4, 3)6}, AL(2, 3)5 = AF (2, 2)x + (1, 2)y (2, 2)x + AP (1, 2)y = 2 2 1 {(1, 1)x, (2, 2)x } + (1, 2)y (2, 2)x + (1, 2)y = {(2, 3)2, (2, 3)5}, 1 2 2 2 AL(4, 3)6 = AF (2, 2)x + (2, 1)y (2, 2)x + AP (2, 1)y = 2 3 2 {(1, 1)x, (2, 2)x } + (2, 1)y (2, 2)x + {(2, 2)y, (1, 2)y } = 1 2 3 2 1 = {(3, 2)3, (4, 3)6, (3, 3)4, (2, 3)5}, Таким образом, таблица для представления N будет иметь вид N (3, 3)1 (2, 3)2 (3, 2)3 (3, 3)4 (2, 3)5 (4, 3) 2,7 (3, 3)4 (2, 3)5 (4, 3)6 (3, 3)1 (2, 3)2 (3, 2) (3, 3)1 (2, 3)2 (3, 3)1 (3, 3)4 (2, 3)5 (4, 3) (3, 2)3 (2, 3)2 (4, 3)6 (3, 3) (2, 3) Теорема 27. Представление графа K = (Z, R) = G H есть пара K = (TZ, AR), такая, что TZ = TX TY, где TZ Ч мно жество всевозможных композиций пар из TX и TY, определенных следующим образом: если (, )x TX, (, )y TY, то (, )x (, )y = (l+k-, l+k-)z, k = |X|, l = |Y |, а AR : TZ TZ таково, что AR(, )z = {(AF (, )x TY ) (TX AR(, )y)}, где (, )z = (, )x (, )y, z = (x, y) Z, x X, y Y.

Д о к а з а т е л ь с т в о. Действительно, по определению = |(F x Y ) (X P y)| = |F x||Y | + |X||P y|- |(F x Y ) (X P y)|.

Очевидно, что X = F x F x, Y = P y P y, где F x и P y Ч дополнения F x до X и P y до Y соответственно.

Используя эти равенства, вычислим следующую величину:

t1 = |(F x Y ) (X P y)| = |(F x P y F x P y) (F x P y F x P y)| = |(F x P y F x P y) (F x P y F x P y) (F x P y F x P y) (F x P y F x P y)|.

Так как A A =, F x P y F x P y =, F x P y F x P y =, F x P y F x P y =, то t1 = |F x P y F x P y| = |F x P y| =.

Аналогично вычисляется величина t2:

-1 - t2 = |F x Y X P y| =.

Таким образом, = l + k -, = l + k -.

Пусть (, )z = (, )x (, )y = (l + k -, l + k - )z. Тогда AR(, )z = {(, )z }z F xY XP y = = {(, )z }z F xY {(, )z }z XP y Так как декартову произведению X Y в прдставлении компо зиции графов G и H соответствует TX TY, то декартову про изведению F x Y будет соответствовать TF x TY, а декартову произведению X P y Ч TX TP y.

Но TX = {(, )x}xX;

TY = {(, )y}yY, TF x = {(, )x }x F x, TP y = {(, )y }y P y.

Следовательно, AP (, )z = TF x TY TX TP y = AF (, )x TY TX AP (, )y, где (, )z = (, )x (, )y, z = (x, y) Z, x X, y Y.

П р и м е р 19. Для графов G = (X, F ) и H = (Y, P ) из примера 17 вычислим представление M = (TZ, AS) графа M = (Z, S).

Из теоремы о представлении композиции представлений следу ет, что TZ = TX TY = {(5, 5)1, (4, 5)2, (5, 4)3, (6, 6)4, (6, 6)5, (6, 6)6} AS(5, 5)1 = AF (1, 1)x {(2, 2)y, (1, 2)y, (2, 1)y }{(1, 1)x, (2, 2)x } 1 1 2 3 1 AP (2, 2)y = (2, 2)x {(2, 2)y, (1, 2)y, (2, 1)y } {(1, 1)x, (2, 2)x } 1 2 1 2 3 1 {(2, 2)y, (2, 1)y } = {(6, 6)4, (6, 6)5, (6, 6)6, (5, 5)1, (5, 4)3}, 1 AS(4, 5)2 = AF (1, 1)x {(2, 2)y, (1, 2)y, (2, 1)y }{(1, 1)x, (2, 2)x } 1 1 2 3 1 AP (1, 2)y = (2, 2)x {(2, 2)y, (1, 2)y, (2, 1)y } {(1, 1)x, (2, 2)x } 2 2 1 2 3 1 (1, 2)y = {(6, 6)4, (6, 6)5, (6, 6)6, (4, 5)2}, AS(5, 4)3 = AF (1, 1)x {(2, 2)y, (1, 2)y, (2, 1)y }{(1, 1)x, (2, 2)x } 1 1 2 3 1 AP (2, 1)y = (2, 2)x {(2, 2)y, (1, 2)y, (2, 1)y } {(1, 1)x, (2, 2)x } 3 2 1 2 3 1 {(2, 2)y, (1, 2)y } = {(6, 6)4, (6, 6)5, (6, 6)6, (5, 5)1, (4, 5)2}, 1 AS(6, 6)4 = AF (2, 2)x {(2, 2)y, (1, 2)y, (2, 1)y }{(1, 1)x, (2, 2)x } 2 1 2 3 1 AP (2, 2)y = TX TY = TZ, AS(6, 6)5 = AS(6, 6)6 = TZ.

Таким образом, представление M = (TZ, AS) для композиции M = (Z, S) имеет вид M (5, 5)1 (4, 5)2 (5, 4)3 (6, 6)4 (6, 6)5 (6, 6) (6, 6)4 (6, 6)4 (6, 6)4 TZ TZ TZ (6, 6)5 (6, 6)5 (6, 6) (6, 6)6 (6, 6)6 (6, 6) (5, 5)1 (4, 5)2 (5, 5) (5, 4)3 (4, 5) Пусть N Ч некоторое подмножество из X, а M Ч из Y и пусть заданы два графа Бержа G = (X, F ), H = (Y, P ).

Пусть (F x, N) #(M, P y) = (F x M) (N P y), x X, y Y.

Очевидно, при различных N и M операция # является одной из рассмотренных ранее операций из A= {, +, }. Действительно, при N =, M = P y операция # есть ;

при N = {x}, M = {y} # есть +, а при N = X, M = Y # есть.

Таким образом, рассмотренные операции на графах можно об общить, заменив их операцией #.

Будем говорить, что граф V = (Z, B) получается из графов G и H с помощью операции #, и писать V = G# H, если Z = X Y и Bz = (F x, N)#(M, P y).

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

Теорема 28. Представление графа V = (Z, B) = G#H есть пара V = (TZ, AB), такая, что TZ = TXTY, где операция такова, что для любой пары (, )x из TX и любой пары (, )y из TY (, )z = (, )x(, )y = (n + m - p1, n + m - p2)z, а AB : TZ TZ на элементах из TZ определяется следующим образом AB(, )z = (AF (, )x, TN)(TM, AP (, )y) = = (AF (, )xTM) (TNAP (, )y).

В этом случае будем писать V = GH;

G = (TX, AF );

H = (TY, AP ).

Д о к а з а т е л ь с т в о. Действительно, если n = m = 0, -p1 =, -p2 =, то мы имеем дело с теоремой 25;

при n = l, m = k, p1 =, p2 = Ч это есть теорема 27;

при m = n = 1, p1 = p2 = 0 1 мы имеем дело с теоремой 26.

МИНИМАЛЬНЫЕ РАСКРАСКИ И КРИТИЧЕСКИЕ ГРАФЫ 5.1. Основные понятия и определения Здесь мы будем иметь дело с так называемыми обык новенными графами, т. е. неориенированными графами без петель и кратных ребер.

Вершинной раскраской графа [4] называется такое приписывание цветов его вершинам, что никакие две смежные вершины не окрашиваются в один цвет.

Дадим другое определение раскраски, более фор мальное.

О п р е д е л е н и е 47. Раскраской графа G = (X, F ) в m цветов, или m-раскраской, называ ется разбиение его вершин X на классы C1, C2,..., Cm попарно несмежных вершин.

Классы Ci называются одноцветными классами.

Хроматическое число (G) графа G определяется как наименьшее m, для которого граф G имеет m раскраску.

Граф G называется m-раскрашиваемым, если (G) m, и m-хpоматическим, если (G) = m.

Хроматическое число для некоторых простых гра фов легко вычисляется. Если Fm Ч полный m вершинный граф, то (Fm) = m, (Ck) = 3, где Ck Ч простой цикл нечетной длины k, (C2n) = 2 [4].

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

Среди n-хроматических графов выделяются мини мальные по числу вершин.

О п р е д е л е н и е 48. Граф G называется критическим, если (G-x) < (G) для любой вершины x;

если при этом (G) = m, то граф G называется m критическим.

Очевидно, что если G Ч критический граф, то (G) - 1 = (G - x) для каждой его вершины x.

Единственный 2-критический граф Ч это F2. Все 3 критические графы исчерпываются простыми циклами нечетной длины.

Каждый m-хроматический граф содержит m-критический подграф. Действительно, если H Ч такой наименьший порожденный [5] подграф графа G, что (H) = (G), то H Ч критический граф.

Очевидно, каждый критический граф связен.

Если Fp = (X, F ) Ч полный граф, то для любого Y X справедливо равенство (Fp - Y ) = p - |Y | и, следовательно, граф Fp критический.

Для любого другого m-критического графа, m > 2, нельзя удалить не менее двух вершин, не уменьшая при этом хроматическое число больше, чем на единицу.

Действительно, если C Ч произвольное подмножес тво любого одноцветного класса, то (G - C) = m - 1.

Но, если x и y Ч любые две вершины m-критического неполного графа, то не всегда их удаление уменьшает хроматическое число на единицу. Следующий пример служит тому подтверждением.

Критический граф может обладать еще одним свой ством: (G - u) = (G) - 1 для любого ребра u графа G. В этом случае граф G называется реберно критическим. При (G) = n граф G называется n реберно-критическим.

Каждый реберно-критический граф является крити ческим, обратное неверно. Например, граф G, мини мальная раскраска которого представлена на рис. 5.1, является 4-критическим, но не реберно-критическим, поскольку (G - u) = 4.

Таким образом, реберно-критические графы облада ют всеми свойствами критических графов.

Пусть G = (X, F ) Ч m-критический граф, X Ч мно жество вершин, а F : X X Ч отображение, ставящее в соответствие вершине x X множество смежных с ней вершин F x. Пусть (m) = (C1, C2,..., Cm) Ч его ми нимальная вершинная раскраска, где Ci, i = 1, m, Ч классы одноцветных вершин.

О п р е д е л е н и е 49. Будем говорить, что фактор-степень вершины x из Ci относительно рас краски (m) равна r m - 1, если имеется ровно r классов (Ci, Ci,..., Ci ), таких, что F x Ci =, j = 1 2 r j 1, r, i = ij.

Соотношение ASB будет означать в дальнейшем, что A и B из X содержат по крайней мере одну пару смежных вершин.

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

1. Перемещение вершин {xk} Ci (m) фактор степени меньше m-1 из одного класса Ci в другой Cj, с вершинами которого они не смежны.

Например, раскраска (3) = {(1), (2, 3), (4, 5)} графа G, задаваемого таблицей 1 2 3 4 G 2 1 4 2 5 4 5 3 такова, что перемещение вершины 3 из C2, или верши ны 4 из C3 в C1, есть элементарное преобразование Ч перемещение, изменяющее фактор-степень вершин 4, или 2, 3 соответственно.

2. Пусть x Ci и y Cj пара смежных вершин.

И пусть ((C1, C2), F ) максимальный по числу вершин связный двудольный подграф над Ci, Cj, такой что x C1, y C2. Тогда одновременное перемещение C1 в Cj и C2 в Ci называется инверсией.

Здесь F Ч сужение отображения F на подмножества из X, в данном случае на C1 C2.

Так, в предыдущем примере инверсия двудольного связного подграфа, состоящего из пары смежных вер шин 1 и 2, изменяет фактор-степень вершин 4 и 5.

О п р е д е л е н и е 50. Минимальную раскрас ку (m) будем называть 1-приведенной относитель но Ci и обозначать (m), если вершины из Ci име ют фактоp-степень m - 1 и никакие преобразования на (C1,..., Ci-1, Ci+1,..., Cm) не изменяют их фактор степеней.

В частности, минимальная раскраска графа G на рис. 5.1 является приведенной относительно C4, так как никакие преобразования над (C1, C2, C3) не изменяют фактор-степеней вершин из C4.

Если минимальная раскраска (m) приведена относи тельно Ci и никакие преобразования на (m) - {Ci, Cj} не изменяют фактор-степеней вершин из Cj, равных m - 2 относительно раскраски (m) - Ci, то раскрас ка (m) называется 2-приведенной и обозначается (m).

Если уже определена (r - 1)-приведенная последова тельно относительно классов Ci, Ci,..., Ci раскрас 1 2 r- r- r ка (m), то r-приведенная раскраска (m) опеделяется как раскраска, для которой никакие преобразования над (m)-(Ci, Ci,..., Ci ) не изменяют фактор-степеней 1 2 r вершин из Ci, равных m - r относительно раскраски r (m) - (Ci, Ci,..., Ci ).

1 2 r- Таким образом, процесс приведения раскраски (m) относительно некоторого класса, например C1, сво дится к проведению различных преобразований над (C2, C3,..., Cm) и перемещения после каждого такого преобразования вершин, фактор-степени которых ока зались меньше m - 1, из класса C1 в классы, с верши нами которых они не смежны.

О п р е д е л е н и е 51. Подмножества Xi и Xj соответственно из классов Ci и Cj раскраски (m) графа G будем называть R-связным (рис. 5.2) и обозначать XiRXj, если в Ci и Cj существуют под множества Xi Xi и Xj Xj, такие, что подграф ((XiXj), F ) является связным двудольным подграфом над Ci Cj.

О п р е д е л е н и е 52. Два подмножества вер шин Ci и Ck из классов Ci и Ck раскраски (m) будем называть Z-связными и обозначать CiZCk (рис. 5.3), если CiRCk и для некоторых Ci и Ck из Ci и Ck соот ветственно подграф ((Ci Ck), F ) графа G является максимальным по числу вершин связным двудольным графом над Ci Ck.

Если Ci = Ci, Ck = Ck, то будем писать CiZCk, а соответствующий максимальный связный двудольный подграф графа G, содержащий ((Ci Ck), F ) будем на зывать Z-й и обозначать r, где r Ч номер Z-ки над ik классами Ci и Ck.

Очевидно, из Z-связности следует R-связность, но не наоборот.

Пусть (m) = (C1, C2,..., Cm) Ч минимальная рас краска графа G, тогда любой подграф ((Ci Cj), F ), i = j, с точностью до вершин, образующих пустой подграф, представляется объединением Z-ок.

Так, минимальная раскраска графа G на рис. 5. обладает указанным свойством. Действительно, напри мер, подграф, порожденный парой классов (C1, C2), есть объединение следующих Z-ок: 1Z6, 2Z5. Подграф над (C2, C3) Ч объединение Z-ок 5Z3, 6Z4.

kl В дальнейшем через Crj будем обозначать подкласс класса Ck, k = r j, порожденный разбиением пары jl rl классов (Cr, Cj) на q Z-связных пар (Crj, Crj) = l, rj l q.

На рис. 5.1 множество вершин {3,4} есть C31, {1, 2} = 11 21 21 22 22 C13, {5} = C21 = C23, {6} = C21 = C23, {1} = C12 и т. д.

Пусть (m) Ч минимальная раскраска, приведенная относительно, например, Cm, m 3. Тогда:

Z1. Для любой вершины x из Cm в силу инвариант ности фактор-степени x относительно инверсий Z-ок l, r, j 1, m - 1, для некоторого l выполняется со rj jl rl отношение CrjSxSCrj для всех r и j. Будем говорить в этом случае, что x опирается на l, а саму Z-ку l rj rj будем называть опорной для x.

12 22 11 31 21 Как следует из рис. 5.1, C12S7SC12, C13 S7SC13, C23S7SC и, следовательно, вершина 7 опирается на Z-ки 2, 1, 1.

12 13 Z2. Так как фактор-степень x инвариантна и отно kl сительно перемещений некоторых Crj, k = r j, то при r m > 3 для любого класса Ci раскраски (m), приведен ной относительно Cm, i = m, найдется по крайней мере один набор из m - 2 Z-к 1, 2,..., m-2, ij = m, j = 1, m - 2, ii1 ii2 iim- i(m-2) i1 i таких что Cii Cii... Cii yiSx.

1 2 m- m- st Положим xst = Csi, t > 0. Из примера на рис.

j j= 5.1 видно, что {6} = x22, {5} = x21, {4} = x32, {3} = x31, {1} = x12, {2} = x11.

Пусть m = 3 и (3) = (C1, C2, C3) Ч минимальная раскраска графа G, приведенная относительно C3. Тог да в силу Z1 для любой вершины x из C3 при некотором 1i 2i i > 0 выполняется соотношение (рис. 5.4) C12SxSC12.

Подграф (x, i ) с указанными связями обозначим че 1i 2i рез G(3)(x). Если xS(y C12), xS(z C12), то в i существует простая цепь из z в y, содержащая четное число вершин, которые вместе с x образуют простой не четный цикл. Так как минимальная раскраска нечетно го цикла состоит из трех классов, то все 3-критические графы исчерпываются циклами нечетной длины.

5.2. О 5-критических графах Как отмечал Харари, если гипотеза четырех кра сок не верна, то должен существовать 5-хроматический планарный граф и, следовательно, проблему четырех красок можно сформулировать следующим образом:

всякий 5-критический граф содержит подграф, стя гиваемый к полному 5-вершинному графу F5. А так как в силу теоремы, являющейся двойственной фор мой теоремы Понтрягина - Куратовского [4], всякий 5-хроматический граф, стягиваемый к F5, непланарен, то указанная формулировка эквивалентна формулиров ке гипотезы четырех красок.

Pages:     | 1 | 2 |    Книги, научные публикации