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

УНИВЕРСИТЕТ Б. Н. ИВАНОВ дискретная математика АЛГОРИТМЫ И ПРОГРАММЫ Москва Лаборатория Базовых Знаний 2003 32.973.3 20 Рецензенты: ...

-- [ Страница 2 ] --

Определение. Граф U, Ф) называется связным, если для всех х, у е X существует путь из вершины в вершину у (вер шины х и у связаны маршрутом). Связный ориентированный называется сильно связным. Орграф называется слабо связ ным, если соответствующий ему неориентированный граф (иг норируется ориентация ребер) связный (рис. 6.8).

Рис. 6.8. Ч слабо связный, Ч сильно связный Х Определение. Связный неориентированный ациклический граф называется деревом, множество деревьев называется лесом.

Глава 6. Введение в теорию графов. Алгоритмы на графах Рис. 6.9. Ч дерево, Ч не дерево Большинство задач на графах касается определения компо нент связности, поиска маршрутов, расстояний и т.п. Далее будут рассмотрены решения подобных вопросов. Однако при решении реальных задач соответствующие им графы весьма велики, и ана лиз возможен лишь с привлечением современной вычислитель ной техники. Поэтому конечной целью рассмотрения каждой из задач будет являться описание и реализация практического алго ритма решения данной задачи на ЭВМ.

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

6.2.1. Матрица смежности графа Х Определение. Матрицей смежности ориентированного поме ченного графа с вершинами называется матрица 1, п, в которой _ если существует ребро если вершины,Xj не связаны ребром 6.2. Представления графов Матрица смежности однозначно определяет структуру графа.

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

3 Рис. 6.10. Ориентированный граф "0 1 1 0 0 0 0" 1 0 1 1 1 0 0 0 0 0 1 0 А = 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 Рис. 6.11. Матрица смежности ориентированного графа рис. 6. 6.2.2. Матрица инцидентности графа Х Определение. Матрицей инцидентности для неориентированно го графа с п вершинами и т ребрами называется матрица В [by], i = 1, j = 1, т, строки которой соответству ют вершинам, а столбцы Ч ребрам. Элементы _ если вершина инцидентна ребру если вершина не инцидентна ребру Х Определение. Матрицей инцидентности для ориентированного графа с п вершинами и т ребрами называется матрица 116 Глава 6. Введение в теорию графов. Алгоритмы на графах 1, 1, т, строки которой соответствуют вер шинам, а столбцы Ч ребрам. Элементы если ребро выходит из вершины -1, если ребро Uj входит в О, если вершина не инцидентна ребру Матрица инцидентности однозначно определяет структуру графа. На рис. 6.12 представлена такая матрица для орграфа на рис. 6.10.

0 О О О О О 3 0 0 0 0 О О О 0 0 О О 0 0 0 0 0 0 0 0 0 0 О 0 0 0 0 0 Рис. 6.12. Матрица инцидентности ориентированного графа 6.2.3. Матрица весов графа Х Определение. Граф называется взвешенным, если каждому его ребру сопоставлено число. Простой взвешенный граф может быть представлен своей матрицей весов W= где Ч вес ребра, соединяющего вершины 1, п. Веса несущест вующих ребер полагают равными или 0 в зависимости от приложений. Заметим, что матрица весов является простым обобщением матрицы смежности.

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

2, 2, 3, 4, 4, 4, 6, 6, 6, 7, 7), 6.3. Метод поиска в глубину Х Интересно, что данное представление позволяет легко петли и кратные ребра.

6.2.5. Структура смежности графа Ориентированный или неориентированный граф может быть однозначно представлен структурой смежности своих вершин.

Структура смежности состоит из списков вершин графа, смежных с вершиной х. Списки составляются для каждой вершины графа. В качестве примера опишем смежно сти графа, представленного на рис. 6.10.

X, 1 2, 3 5 Ч Структуры смежности могут быть удобно реализованы масси вом из п (число вершин в графе) линейно связанных списков.

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

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

6.3. Метод поиска в глубину Один из наиболее естественных способов систематического исследования всех вершин графа исходит из процедуры прохож дения графа методом поиска с возвращением, который исследует граф в глубину (см. На неориентированном графе (X, U, Ф) поиск в глубину осуществляется следующим обра зом. Когда посещаем вершину X, то далее идем по одному из ребер (х, у), инцидентному вершине у е X. Если вершина у уже пройдена (посещалась ранее), то возвращаемся в х и выбираем 118 Глава 6. в теорию графов. Алгоритмы на графах другое ребро. Если вершина у не пройдена, то заходим в нее и применяем процесс прохождения рекурсивно уже с вершиной у.

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

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

Метод поиска в глубину на простом неориентированном гра фе представлен в алгоритме Рекурсивная процедура Depth(x, w) осуществляет поиск в глубину на графе (X, U, содержащем е X, и строит для графа дерево Т поиска, которое является ориентированным деревом = (X, Т, Ф) (если исходный граф не связен, то будет w отцом х е строящемся дереве, где х Ч исследуемая вершина.

Граф задан смежности где означает мно жество вершин, смежных с х е X. Элементы это ребра строя щегося дерева поиска, а элементы В Ч это обратные ребра, кото рые не могут принадлежать так как они ведут назад в пройден ные ранее вершины. Заметим, что обратное ребро должно идти от потомка к предку по дереву поиска. Чтобы отличить уже прой денные вершины от непройденных, вводится вектор ме ток вершин, которые постепенно нумеруются от 1 до по мере как попадаем в них. Сначала полагается = 0 для всех х X в знак того, что ни одна вершина не пройдена, и когда попа даем в вершину х первый раз, получает ненулевое значе ние. Ребро (х, v) е Т, если метка вершины = Если же О, то условием того, что (х, v) & В будет обратным реб ром, являются соотношения Mark[v] < и v w. Условие < Mark[x] означает, что вершина v была пройдена раньше вершины х. Поэтому ребро (х, v) е В будет обратным, если оно не является ребром дерева Т, пройденным от отца w к х, т. е. v w.

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

Алгоритм 6.1. Поиск в глубину на простом неориентированном графе for v X do = 0;

0;

for v e = 0 then 0);

procedure Depth(x, Mark[x] = for v e do begin = 0 then {(x, { ребро дерева } Depth(v, x);

else < and v w then = { Включить обратное ребро } end;

end.

Программная реализация алгоритма представлена алгорит мом 6.2. Реализация близко соответствует основному алгоритму Программа представлена тремя процедурами Depth, Way Depth, где WayDepth Ч основная программа поиска в глубину;

Depth Ч рекурсивная процедура поиска, один к одному соответст вующая аналогичной процедуре в алгоритме процедура контроля исходных данных и изменения меток вершин. Измене ние нумерации меток вершин является существенным для алго ритма. Новые метки вершин Ч это натуральные числа от 1 до Данная нумерация позволяет обращаться к элементам массивов, содержащих информацию о вершинах, по номерам соответству ющих вершин. Такой прием позволяет очень близко подойти в программной реализацией структуры смежности Adj[x] к ее мно жественному описанию. В этом случае множественное описание выражения for v e do... в программной реализации пред 120 Глава 6. Введение в теорию графов. Алгоритмы на графах for Nbr[x] = Adj[Fst[x] + где Ч количество вершин в структуре смежности для вершины х X;

Adj[x] Ч вектор, содержащий все вершины структуры смежности по строкам;

Fst[x] + 1 Ч номер первой вершины структуре смеж ности для соответствующей вершины х е X, тогда Fst[x] + i Ч но мер вершины в структуре смежности для х X.

Например, для следующей структуры смежности X 1 2, 2 1, 3 1, 4 2, 5 1, 7 5, соответствующие массивы в программной реализации принима ют вид О 3 6 10 12 16 235 134 1245 23 1367 57 Исходные данные для расчета по программе алгоритма 6. представляются в текстовом файле со следующей структурой смежности Х в первой строке файла содержится количество строк в структу ре смежности, которое равно числу вершин в графе;

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

Рассмотрим пример расчета по программе алгоритма 6.2 обхо да графа, представленного на рис. Сплошными линиями от мечены ребра, которые были пройдены во время обхода графа в глубину, пунктирными Ч обратные ребра.

Рис. 6.13. Пример обхода графа в глубину 6.3. Метод поиска в глубину Исходные данные структуры смежности графа рис. зада ются в текстовом файле in:

Результаты расчетов сохраняются в выходном файле Depth.out со следующей структурой:

2 3 1 4 2 5 1 1 1 0 1 0 1 0 Каждая колонка таблицы выходного файла соответствует реб ру прохода графа, где последнее значение является призна ком 1 или 0, что отвечает при проходе либо основному ребру, либо обратному.

Алгоритм 6.2. Программа поиска в глубину на простом неориентированном графе Program графа в uses Const количество длина списка Туре of Integer;

of Integer;

Var f { Текстовый файл } n { Количество вершин } nT { Количество ребер прохода в Adj { Список смежности графа } Fst :TypeVertex;

вершин списка смежности } Nbr { Количество вершин в списке Vtx { Список вершин графа } Mark { Номера компонент для вершин Т { Последовательность ребер прохода в глубину } Глава 6. Введение в теорию графов. Алгоритмы на графах В { Признаки основных и обратных ребер прохода в глубину } Procedure Var yes { Переназначение меток вершин } { их порядковыми номерами в списке смежности } { yes - признак правильной структуры списка смежности } Var i, begin for i:=l to n do for to Nbr[i] do begin for to n do if then begin break;

if not yes then exit;

end;

Procedure var count Var i,v begin for i:=l to do begin if then begin div end else if and (v<>u) then begin B[nT div end;

6.3. Метод поиска в глубину Procedure в begin nT:=0;

- пустое for v:=l to n do for v:=l to n do if then Var yes begin открыт для ( Ввод списка смежности } Read(f,n);

строк в начала первой строки for to n do begin Read вершин в for j:=l to Nbr[i] do смежных начала следующей строки в Close открыт для if not yes then begin структура смежности Close exit;

for i:=l to nT div 2 do for i:=l to nT div 2 do for i:=l to nT div 2 do Глава Введение в теорию графов. Алгоритмы на графах 6.4. Отношение эквивалентности Бинарное отношение ~, определенное на множестве S, назы вается отношением эквивалентности, если оно удовлетворяет свойствам рефлексивности, симметричности и транзитивности:

1. S 2. S ~ ~ 3. 53 S ~ л ~ ~ Все элементы из множества S, эквивалентные данному эле менту образуют множество которое называется классом эк вивалентности. Два различных класса эквивалентности не могут иметь какого-либо общего элемента, в противном случае такие классы совпадают, что следует из свойств Таким образом, определенное на множестве S отношение эквивалентности вы полняет разложение его на непересекающиеся классы эквива лентности, т.е. S где = 0, i Пример. Пусть множество треугольников. Определим на S бинарное ~ отношение. Будем считать, что для треугольников S выполняется отношение Да ~ если они подобные.

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

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

Пример. Пусть множество векторов. Определим на S бинарное ~ отношение. Будем полагать, что для e S вы полняется отношение а ~ если они Данное отно шение является отношением эквивалентности, так как свойства выполняются для векторов. Множество векто ров под действием введенного отношения разбивается на классы эквивалентности колинеарных векторов.

Пример. Пусть Определим на бинарное ~ от ношение. Будем полагать, что для р, q e S выполняется отноше ние р ~ q, если они имеют одинаковые остатки от деления на це лое положительное число т. Данное отношение является отно шением эквивалентности. Множество S действием введенно го отношения разбивается на классы эквивалентности чисел с одинаковыми остатками от деления на т.

6.5. Связные компоненты Пример. Пусть множество треугольников. Определим на S бинарное ~ отношение. Будем считать, что для треугольников Да, отношение Да ~ если их площади рав ны. Данное отношение является отношением эквивалентности.

6.5. Связные компоненты Пусть псевдограф Г = (X, U, является неориентированным.

Две вершины связанными, если существует маршрут из в Определим на множестве вершин ~ отношение. Для е отношение ~ будет выполняться, т.е.

~ если эти вершины связанные. Введенное отношение яв ляется отношением эквивалентности. Действительно, если вер шина связана с а вершина связана с то очевидно, что вершина связана с Следовательно, существует такое разло жение множества вершин на попарно непересекающиеся подмножества, что все вершины в каждом связаны, а вершины из различных не связаны. Тогда можно записать разложение графа (X, U, Ф) на непересекающиеся связные подграфы Ф). Вследствие попарного непересечения подграфов, разложение называется прямым, а сами подграфы называются компонентами связности графа Г. Таким образом, справедливо следующее утверждение.

Х Утверждение 6.5.1. Каждый неориентированный граф распа дается единственным образом в прямую сумму своих компо нент связности.

Количество компонент связности находится в определенном отношении с основными параметрами графа Ч числом его вер шин и ребер.

Х Утверждение 6.5.2. Пусть (X, U, Ф) является простым гра фом с п вершинами и k компонентами связности. Число ребер в таком графе не может превосходить величины = Доказательство. Рассмотрим прямое разложение k Г =,Ф) исходного графа на компоненты связности.

Глава 6. Введение в теорию графов. Алгоритмы на графах Если положить, что число вершин в компоненте связности рав но то число ребер в таком графе не превосходит Данная величина достигается в том случае, когда каждая из компонент связности является полным подграфом. Допустим, что среди компонент связности Ф) найдутся хотя бы две, которые имеют более одной вершины, например Перенесем одну вершину из в Легко видеть, что это увеличивает число ребер в модифицируемом полном с k компонентами связ ности. Отсюда следует, что максимальное число ребер должен иметь граф, состоящий из k Ч 1 изолированной вершины и одно го полного подграфа с п Ч k + 1 вершинами.

Х Следствие. Граф с п вершинами и числом ребер, большим чем связен.

6.6. Выделение компонент связности Рассмотрим алгоритм нахождения числа компонент связно сти, а также выделения этих компонент на неориентированном графе. Подобным образом решается задача и для ориентирован ного графа. В основу рассматриваемого алгоритма 6.3 выделения компонент связности положена описанная ранее техника поиска в глубину на графе U, Ф). Структура алгоритма является модификацией в сторону упрощения основного алгоритма поиска в глубину. Работа алгоритма 6.3 направлена на формиро вание вектора меток вершин х е X графа. Элементу Mark[x] присваивается общий номер той компоненты, которой принадлежит вершина х е Сложность алгоритма как и ал горитма 6.1, составляет + Алгоритм 6.3. Выделение связных компонент неориентированного графа for v = 0;

count = 0;

числа for v e = 0 then begin count + 1;

count);

end;

6.6. Выделение компонент связности Procedure Mark[x] = for v do = 0 then count);

end;

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

Х4 Т Рис. 6.14. Пример выделения компонент связности графа Для программы алгоритма 6.4 исходные данные структуры смежности графа на рис. задаются в текстовом файле Структура (правило) заполнения файла одинакова с той, которая описана в рассмотренном примере поиска в глубину при расчете по программе алгоритма 6.2.

Данные файла Connect.in для примера на рис.

1 3 2 3 2 2 3 9 1 8 1 12 3 14 15 14 2 12 3 3 2 1 4 2 1 7 2 9 15 2 14 21 1 Результаты расчетов сохраняются в выходном файле Соп nect.out со следующей структурой:

1 2 9 8 12 14 з 4 7 15 21 Ч номера графа;

номера компонент связности.

128 Глава 6. Введение в теорию графов. Алгоритмы на графах Алгоритм 6.4. Программа выделения связных компонент неориентированного графа Program компонент uses Const количество длина списка of Integer;

of Integer;

Var f { Текстовый файл } n { Количество вершин } { Список смежности графа } Fst { Указатели вершин списка Nbr { Количество вершин в списке Vtx { Список вершин графа } Mark { Номера компонент для вершин Procedure Var yes { Переназначение меток вершин } { их порядковыми номерами в списке смежности } { yes - признак правильной структуры списка смежности } Var begin for i:=l to n do for j:=l to Nbr[i] do begin for to n do if then begin Adj [Fst :=m;

break;

end;

if not yes then end;

Procedure Var i,v begin 6.6. Выделение компонент связности for i:=l to Nbr[x] do begin if then end Procedure Connect;

Var begin for v:=l to n do компоненты for v:=l to n do begin if then begin end;

end;

Var i, j yes begin ) Reset открыт для { Ввод списка смежности } строк в первой строки for i: =1 to n do begin { Метка { Количество вершин в for j:=l to Nbr[i] do { Список смежных Fst [i + Указатель начала следующей строки в Rewrite(f);

открыт для if not yes then begin структура смежности 130 Глава 6. Введение в теорию графов. Алгоритмы на графах for i:=l to n do for i:=l to n do Close 6.7. Эйлеровы графы Классической в теории графов является следующая задача.

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

Рис. 6.15. План расположения мостов и соответствующий ему Х Определение. Пусть (X, Ф) Ч неориентированный псев дограф. Цепь в Г называется эйлеровой, если она проходит по одному разу через каждое ребро псевдографа Г. Такой граф на зывается эйлеровым. Замкнутая эйлерова цепь называется эйлеровым циклом.

Поставим в соответствие плану расположения суши и мостов, приведенному на рис. мультиграф на рис. в котором каждой части суши соответствует вершина, а каждому мосту Ч ребро, соединяющее соответствующие вершины. Теперь задача звучит так: найти эйлерову цепь (цикл) в Решение этой задачи было дано Л. Эйлером.

Х Теорема Л. Эйлера. Эйлерова цепь в псевдографе (X, U, Ф) существует тогда и только тогда, когда выполняются следую щие условия:

1. Граф связный;

2. Степени внутренних вершин четные (внутренние вершины не являются началом и концом 6.7. Эйлеровы графы 3. Если вершины а и Ъ являются началом и концом цепи и а Ь, то степени их нечетные;

4. Если вершины а и b являются началом и концом цепи и a = степени их четные.

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

2) каждая тройка цепи привносит вершине степень два, а так как все ребра в цепи различные, то степени внутренних вершин четные;

3) и 4) доказа тельства повторяют доказательство пункта 2.

Даны условия Построим эйлерову цепь. Предварите льно приведем условие 3 к условию 4 включением в граф фиктив ного ребра которым свяжем вершины а и Теперь и в случае все вершины будут иметь четную степень. А XЧ произво льная вершина (рис. 6.16). Из нее будем строить цепь, выбирая в качестве продолжения пути ребро, которое еще не пройдено. Эта цепь (цикл может закончиться только в вершине А, как, при входе в любую другую вершину, всегда существует ребро, по кото рому можно выйти из нее (степени вершин Возможны два случая: 1) построенный цикл содержит все ребра графа, тогда теорема доказана;

2) содержит не все ребра графа. Во втором случае рассмотрим граф полученный уда лением из всех ребер, входящих в Граф Г \ вновь содержит вершины только с четными степенями (у каждой вершины удали ли по четному числу Так как ГЧ связный граф, то сущест вует вершина в инцидентная ребру из Г \ Пусть это верши на В X. Построим из нее цикл так же, как строили цикл Построим общий цикл из и так, как это сделано на рис. Для вновь проверяем рассмотренные выше два слу чая, как для Рис. 6.16. двух циклов в один цикл Глава 6. Введение в теорию графов. Алгоритмы на графах Процесс расширения продолжаем до тех пор, пока не будут включены все ребра графа в один цикл: Разры вая данный цикл по ребру получим эйлерову цепь flw1/2.,./nwn, где X, U.

характер доказательства теоремы позволяет на формальном уровне в алгоритме 6.5 записать рассмотренный по иск эйлеровой цепи. Исходный граф представлен своей структурой где Ч множество вершин, смежных X.

Результирующая эйлерова цепь формируется в множестве Z.

Алгоритм 6.5. Алгоритм поиска эйлеровой цепи графа 3v начала эйлеровой Z- строящейся эйлеровой R = 0;

расширяющийся цикл эйлеровой repeat R);

Z= R, циклов в один until Not e Z > Procedure Cycle(v, R) R= отдельного цикла эйлеровой repeat R = \ пройденное ребро (v, w) } then = \ (v, w) } v = w;

until Not > 0;

все ребра не end;

Частные же циклы, расширяющие Z, представляются множе ством R. Ребра, включенные в частный цикл R (а значит, и в удаляются как пройденные из структуры смежности Adj[x] (из графа). Формирование расширяющих циклов R осуществляется до тех пор, пока структура смежности графа содержит хотя бы одно ребро.

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

Сложность суммарной работы процедуры Cycle пропорциона 6.7. Эйлеровы графы льна количеству ребер Поэтому сложность выделе ния эйлеровой цепи составляет + Программная реализация поиска эйлеровой цепи представле на в алгоритме который соответствует множественному опи санию соответствующего алгоритма 6.5.

6.6. поиска цепи графа цепь в uses Const количество длина списка Туре of Integer;

of Integer;

Var f { Текстовый файл } ks { Начальная вершина эйлеровой цепи } n { Количество вершин } Adj Список смежности графа } Fst { Указатели вершин списка Nbr { Количество вершин в списке смежности } Vtx { Список вершин графа } Deg { Степени вершин графа } kz { Количество вершин в эйлеровой z Последовательность вершин эйлеровой цепи } Отдельный расширяющийся цикл } Procedure Var yes Var begin { Переназначение меток вершин } { их порядковыми номерами в списке смежности } { yes - признак правильной структуры списка смежности } for i:=l to n do for to do begin for to n do if then begin Глава 6. Введение в теорию графов. Алгоритмы на графах end;

if not yes then exit;

{ Разместить петли в начале списка смежности } for i:=l to n do begin k:=l;

for j:=l to do if then begin end;

{ Степени вершин графа ) for i:=l to n do begin for to do begin if then ( Поиск начальной вершины ks цепи } k:=0;

for i:=l to n do if ( Deg[i] mod 2 ) > 0 then begin if ( k<>2 ) and ( k<>0 ) then { Граф не эйлеровый } Procedure v var count { Построение частной эйлеровой цепи } Var w begin repeat { Следующая вершина цепи } { Удалить ребро (v,w) из списка смежности для вершины v } 6.7. Эйлеровы графы { Если ребро (w,v) не петля, то удалить и его из списка для вершины w } if vow then for i:=l to Nbr[w] do if then for to Nbr[w] do until end;

Procedure { Построение эйлеровой цепи } i,j,kt count yes begin Write for i:=l to kz do repeat for i:=l to count do for i:=l to do begin Write for i:=l to kz do for i:=kz downto 1 do if then begin ;

break;

until Not end;

136 Глава 6. Введение в теорию графов. Алгоритмы на графах Var yes begin Reset открыт для { Ввод списка смежности } (Количество строк в начала первой строки for i:=l to n do begin вершин в for to Nbr[i] do смежных начала следующей строки в end;

открыт для if not yes then begin структура смежности или граф не end;

) for i:=l to kz do end.

Рассмотрим пример расчета по программе алгоритма поис ка эйлеровой цепи в изображенного на рис.

Рис. 6.17. Пример расчета эйлеровой цепи графа 6.8. деревья Для программы алгоритма 6.6 исходные данные структуры смежности графа на рис. 6.17 задаются в текстовом файле Структура (правило) заполнения файла совпадает с той, которая описана в рассмотренном примере поиска в глубину при расчете по программе алгоритма 6.2.

Данные файла Eiler.in для примера на рис.

1 4 2 2 4 1 3 4 1 4 4 1 5 4 1 6 2 2 7 2 2 8 2 3 9 2 4 Результаты расчетов сохраняются в выходном файле Eiler.out со следующей структурой:

Z= R = 1 2 3 1 4 5 Z = 1 2 3 1 4 5 5 6 2 7 3 8 4 9 Z = 1 2 3 1 4 5 6 2 7 3 8 4 9 5 0 = 1 2 3 1 4 5 6 2 7 3 8 4 9 5 1.

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

6.8. Остовные деревья Х деревом связного неориентированно го графа (X, U, Ф) называется дерево = (X, явля ющееся подграфом графа Г и содержащее все его вершины (рис. 6.18).

Рис. 6.18. Связный граф и два дерева Глава 6. Введение в теорию графов. Алгоритмы на графах Х Утверждение Дерево с и вершинами содержит - 1 ребро.

Доказательство. Доказательство проведем по индукции числа вершин. Заметим, что в дереве найдется степень которой равна единице (висячая вершина). Действительно, в противном случае, если степени вершин 2, можно построить цикл, что про тиворечило бы определению дерева. Цикл строится следующим образом. Выполним проход по ребрам графа, начиная с произво льной вершины. Так как степени 2, то, попав в вершину первый раз, можно всегда из нее выйти. Исходный граф Ч конечный и связный. наступит момент, когда вновь попадем в пройденную уже вершину, что доказывает существование цикла.

Условие индукции для п = 2 выполняется, дерево с двумя вер шинами содержит одно ребро. Предположим теперь, что утверж дение выполняется для деревьев, число вершин у которых меньше п. Рассмотрим дерево с п вершинами. Удалим из этого дерева ви сячую вершину и инцидентное ей ребро. Очевидно, что остав шийся граф будет связным и без циклов, т.е. будет деревом с п Ч вершиной. Тогда по предположению индукции оставшаяся часть графа содержит п Ч 2 ребра, а значит, исходное дерево должно иметь их п Ч 1.

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

В терминах теории графов задачу можно сформулировать сле дующим образом. Рассмотрим граф Г= (X, U, где XЧ города, дороги. Каждому ребру и & вес Ч стоимость строительства дороги и. Задача состоит в том, чтобы построить связный граф = (X, содержащий все вершины, с мини мальным весом, что Ч дерево, в противном случае можно было бы удалить одно ребро, не нару шая связности и уменьшая сумму весов его ребер.

Х Определение. Минимальным деревом (лесом) назы вается остовное дерево (лес) с минимальным общим весом его ребер.

6.8. деревья 6.8.1. Жадный алгоритм построения минимального остовного дерева Минимум деревьев графа Г = (X, U, можно применяя процедуру исследования ребер в порядке возрастания их весов. Другими словами, на каждом шаге выбирается новое ребро с наименьшим весом, не образующее циклов с уже выбран ными ребрами. Процесс продолжается до тех пор, пока не будет выбрано Ч 1 ребро. Рассмотренная процедура называется жадным Реализация данной схемы может быть выполнена следующим образом. Для каждой вершины Х= графа Г= (X, U, Ф) формируются начальные тривиальные компоненты связности = Ф), = Компоненты деревьями, объединение Т которых дает начальное приближение строящегося остовного де рева (Х, Включение в строящееся остовное дерево выбранного ребра на очередном шаге жадного алгоритма выполняется слиянием 7} = 7} u = и - = двух компонент 7) и которым принадлежит по вершине нового ребра, и включением самого ребра в объединенное множество ребер. Процесс роста объе динения Т компонент к дереву (X, Ф) i продолжаем до тех пор, пока не будет включено Ч 1ребро.

Справедливость жадного алгоритма является следствием сле дующих двух лемм.

Х Лемма 6.8.1. Пусть (X, U, Ф) Ч связный неориентирован ный граф и = (X, Ф) Ч произвольное остовное дерево для него. Тогда:

V единственная между ними цепь в 2) если к добавить ребро из U \ то возникнет ровно один цикл.

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

6. Введение в теорию графов. Алгоритмы на графах Х Лемма 6.8.2. Пусть (X, U, Ф) Ч связный неориентирован ный граф, для каждого ребра и U определен вес и = Ф) Ч компоненты связности жадного алгоритма, объединение которых Т = согласно алгоритму, растет к дереву = (X, где = k и k > Пусть следующим найденным для включения ребром является ребро Е = (х, у) наименьшего веса из оставшихся U \ у и пусть х i Тогда найдется остовное дерево (X, U, Ф), со держащее ребра вес которого не больше любого другого остовного дерева, содержащего ребра у Доказательство. Допустим противное. Пусть существует ос товное дерево = Г, содержащее и не содер i жащее ребра Е, вес которого меньше веса любого остовного дерева для Г, содержащего у По 1 при добавлении Е к образуется цикл. Этот цикл должен содержать такое ребро от личное от Е, что и т.к. цикл вхо дит в по ребру (х, у) и у то он должен и выйти из (рис. Из условия следует, что Рис. 6.19 с с и ребро Е выбиралось минимальным весом из оставшихся ребер У Uj без образования циклов, в противном же случае выбор должен был бы пасть на Е ', т.к. оно тоже не образует циклов у Рассмотрим граф (X, Ф), образованный добавлением Е к и удалением Е В нет циклов, так как единственный цикл разорван удалением ребра Е '. остался так как осталась цепь Таким образом, Ч остовное дерево.

Учитывая, что (Б) ), то вес дерева не больше веса Ос товное дерево содержит и Е, а это противоречит предпо ложению минимальности что доказывает справедливость жадного алгоритма.

6.8. деревья Реализация лжадной схемы формирования остовного дерева представлена в алгоритме 6.7. Используемые при его описании обозначения соответствуют тому, что вводилось при обоснова нии жадной схемы. Вектор меток вершин х е X графа поддерживает их принадлежность компонентам связности из которых формируется реберный список остовного дерева. Нача льные величины устанавливаются равными порядковым номерам соответствующих вершин X. Далее значения корректируются по мере слияния компонент сохра няя соответствие принадлежности им вершин. Исходный граф задается реберным списком U, выходное остовное дерево также формируется реберным списком Алгоритм Жадный алгоритм минимального остовного дерева for = списка ребер по их do begin (х, у) е с весом из then begin u в остовное Z for v 6 = z then Mark[v] = end;

U= ребро с весом из end;

Х Сложность жадного алгоритма. Жадный алгоритм требует предварительной сортировки ребер по их весам. Стандартные методы сортировки имеют сложность Сложность ал горитма 6.7 помимо сложности сортировки зависит от слож ности реализации слияния подмножеств и Сложность данной операции при полном переборе вершин данных под множеств (как представлено в алгоритме 6.7) составляет Значит, сложность го алгоритма + | Программная реализация жадного алгоритма представлена в алгоритме 6.8, который близко соответствует множественному описанию соответствующего алгоритма 6.7.

142 Глава 6. Введение в теорию графов. Алгоритмы на графах Алгоритм 6.8. Программа жадного алгоритма Program Жадный uses Const количество количество Туре of Integer;

of Integer;

Var f ( Текстовый файл } nX { Количество вершин в графе } { Количество ребер в графе } Mark { Метки принадлежности вершин } X { Список вершин графа } { Реберный список графа } { Количество ребер в { Ребра остовного дерева } We { Веса ребер графа } { Вес минимального остовного Procedure { меток вершин } Var begin for i:=l to 2*nU do for i:=l to 2*nU do for j:=i+l to do if Uo[j ]=l then if then for i:=l to 2*nU do if then begin for to do for to nX do if then begin break;

end;

Procedure Sort;

{ Сортировка списка ребер по их весам } w begin for i:=l to nU do for to do if then begin 6.8. Остовные деревья end;

Procedure { Строим минимальное остовное дерево } Var Integer;

begin for to nX do Sort;

ребер по Uo} ребро в сортированном while do begin нового ребра из if Mark [x] [у] then begin ребро в остовное Ux и Uy} for i:=l to nX do if then ребро из end;

Var i,j begin ' открыт для ребер списке for to do { Первые } for i:=l to nU do { Вторые вершины for i:=l to nU do { Веса ребер } открыт для Sort =',nU:3);

144 Глава 6. Введение в теорию графов. Алгоритмы на графах i:=l to nX do for i:=l to nU do for i:=l to nU do Write for i:=l to nU do Write [i] 3) (f) for i:=l to do for i:=l to nUo do for i:=l to nUo do for i:=l to nUo do Рассмотрим пример построения минимального дере ва графа, изображенного рис. по программе алгоритма х5 х Рис. 6. 20. Пример расчета остовного дерева Для программы этого алгоритма исходные данные графа на рис. 6.20 задаются реберным списком в текстовом файле Hung со следующей структурой:

Х в первой строке файла содержится количество ребер в списке (12);

Х во второй и третьей строках указываются своими верши нами: одна вершина во второй строке, другая вершина ребра в третьей строке;

6.8. деревья Х в четвертой строке располагаются значения весов соответству ющих ребер.

7 7 7 7 7 7 1 2 3 4 5 б 1 2 3 4 5 6 2 3 4 5 6 1 4 9 16 25 36 20 15 3 17 28 Результаты расчетов сохраняются в выходном файле со следующей структурой:

nU = пХ = Х = 7 1 2 3 4 5 = 7 3 7 7 2 7 4 1 6 7 5 u 2 = 1 4 2 3 3 4 5 2 1 5 6 We = 1 3 4 9 15 16 17 20 23 25 28 uol= 1 3 4 9 17 Bec= 57.

Обозначения данных в файле nU Ч число ребер в графе;

пХ Ч число вершин в графе;

X Ч список вершин графа;

u2) Ч сортированный список ребер графа;

We Ч веса ребер согласно их сортировке;

uo2) Ч ребра остовного дерева;

Woe Ч веса ребер остовного дерева;

Вес Ч сумма весов ребер остовного дерева.

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

1. Построение остовного дерева начинается с произвольной вершины 2. Затем среди ребер, инцидентных выбираем ребро с наименьшим весом и включаем его в дерево 3. Повторяя процесс, выполняем поиск наименьшего весу реб ра, соединяющего вершины и с некоторой другой верши ной графа 146 Глава 6. Введение в теорию графов. Алгоритмы на графах 4. Процесс включения ребер продолжаем до тех пор, пока все вер шины исходного графа Г не будут включены в дерево По строенное дерево будет минимальным того, что последовательность шагов при водит к построению минимального остовного дерева, аналогично доказательству для жадного алгоритма. Реализация схемы бли жайшего соседа формирования остовного дерева выполнена в ал горитме 6.9, где исходный граф Г= (X, U, Ф) представляется мат рицей весов веса несуществующих ребер полагаются равными Под весами ребер понимаются их длины. Остовное дерево Г = Ф) формируется посредством реберного спи ска и списка вершин В качестве меток вершин устанавли ваются их порядковые номера Х= Для каждой верши ны х е еще не включенной в остовное дерево, поддержи вается минимальное расстояние до множества ранее включенных вершин в Это осуществляется с помощью двух векторов dist[x] где равно минимальному расстоянию е вершины prev[x] е Обновление значений векторов и prev[x] выполняется на каждом шаге алгоритма при пополнении новой вершиной.

Х алгоритма ближайшего соседа. Сложность алгорит ма определяется двумя вложенными циклами по числу вер шин. В каждом из циклов выполняется константное число операций. Следовательно, сложность составляет Алгоритм 6.9. Алгоритм ближайшего соседа для остовного дерева вершин вершин в v = вершина v е - Mi остовного v = 0;

остовного остовного for x begin = от х до v е prev[x] = v;

(v, х), длина которого while begin dist[v] = { v е ХЧ вершина для 6.8. деревья = {v};

вес дерева] Ч вектор расстояний] e > x] then begin = prev[x] = v;

end, end.

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

6.10. Программа алгоритма ближайшего соседа Program {Остовное Метод ближайшего uses Const количество nRib=1000;

количество of Integer;

of Integer;

of Integer;

Var f { Текстовый файл } nX { Количество вершин в графе } nXo { Количество вершин в { Количество ребер в остовном дереве } X { Список вершин графа } Хо { Список вершин остовного дерева } Uo :TypeRib;

{ Ребра остовного дерева } Prev { Список ближайших вершин } Dist { Расстояния до ближайших вершин } We { Матрица весов ребер графа } { Вес минимального остовного дерева } Procedure Var v v - ближайшего Var i,d begin Глава 6. Введение в теорию графов. Алгоритмы на графах for to nX do if then begin Procedure v минимальные Var i begin for i:=l to nX do if,v] then begin Procedure Var i,nStop,v begin for i:=l to nX do for to nX do begin end;

{ Xo - пустое множество } { - пустое множество } - добавить вершину v к { X=X\v - удалить v из X } while do begin - добавить вершину v к for to nX do { X=X\v - удалить v из X } if X[i]=v then begin break;

end;

добавить ребро к 6.8. Остовные деревья { Обновить вес дерева } end;

Var открыт для чтения) вершин в for to nX do begin for j : =i to nX do begin { Ввод матрицы весов } if then end;

открыт для реберного списка графа для for i:=l to nX do for to nX do begin if then continue;

i:=l to nX do Write Write(f,'ul for i:=l to nUo do for i:=l to nUo do for i:=l to nUo do for to nUo do for i:=l to nUo do Глава 6. Введение в теорию графов. Алгоритмы на графах Write for i:=l to nUo do for i:=l to nUo do Рассмотрим пример расчета по программе алгоритма по строения минимального остовного дерева графа, изображенного на рис. 6.20. Исходные данные графа представляются матрицей весов его ребер в текстовом файле in со следующей структу рой:

Х в первой строке содержится количество вершин в графе;

Х в следующих п строках задаются верхние диагональные элемен ты (нулевые диагональные элементы включаются) строк мат рицы весов.

0 20 0 0 0 23 0 15 0 0 0 0 3 0 0 0 17 0 0 28 0 Результаты расчетов сохраняются в выходном файле out со следующей структурой:

= = Х = 1 2 3 4 5 6 = 1 1 1 2 2 3 3 4 4 5 5 u 2 = 2 6 7 3 7 4 7 5 7 6 7 We = 20 23 1 15 4 3 9 17 16 28 25 uol= uo2= Woe= 1 4 9 3 17 Bec= 57.

Обозначения данных в файле out соответствуют приня тым обозначениям в файле при контрольном расчете остовного дерева по жадному алгоритму 6.8 (см.

6.9. Кратчайшие пути на графе 6.9. Кратчайшие пути на графе Рассматриваемый алгоритм определяет расстояния между вер шинами в простом орграфе с неотрицательными весами. К таким орграфам сводятся многие типы графов. Если граф не является его можно сделать таковым, отбрасывая все петли и за меняя каждое множество параллельных ребер кратчайшим реб ром (ребром с наименьшим весом) из этого множества;

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

Пусть (X, U, Ф) Ч простой орграф, для каждого ребра и е определен вес 0. Найдем кратчайший путь между выделен ными вершинами и z (рис. 6.21). Несуществующие ребра будем считать ребрами с бесконечными весами. Сумму весов ребер в пути будем называть весом или длиной пути. Обозначим = Ч вес ребра = Алгоритм поиска кратчайшего пути, начиная из вершины просматривает граф в ширину, по мечая вершины Xj их расстояний от Мет ки могут быть временные и окончательные. Временная метка вер шины Ч это минимальное расстояние от до когда в опреде лении пути на графе учитываются не все маршруты Окон чательная Xj Ч это минимальное расстояние на графе до Xj. Таким образом, в каждый момент времени работы алгоритма некоторые вершины будут иметь окончательные метки, а осталь ная их часть Ч временные. Алгоритм заканчивается, когда верши на z получает окончательную метку, т.е. расстояние от до z.

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

1. Каждой не имеющей окончательной метки, присва ивается новая временная метка Ч наименьшая из ее временной и числа + окончательная метка где Ч вершина, которой присвоена окончательная метка на предыдущем шаге.

2. Определяется наименьшая из всех временных меток, которая и становится окончательной меткой своей вершины. В случае равенства меток выбирается любая из них.

152 Глава 6. Введение в теорию графов. Алгоритмы на графах Циклический процесс продолжается до тех пор, пока вершина z не получит окончательной метки. Легко видеть, что окончательная метка каждой вершины Ч это рассто яние от этой вершины до начала Рассмотрим пример поиска кратчайшего пути на графе, пред ставленном на рис.

2 х2 5 хЗ 7 х Рис. 6.21. Простой взвешенный орграф Процесс назначения меток вершинам графа на каждом шаге удобно представить в виде следующей таблицы.

х2 хЗ х4 х 10 13 Квадратами выделены окончательные метки, т.е. расстояния от них до По такой таблице легко восстановить путь перемеще ния от z к который отмечен ломаной кривой.

Реализация рассмотренной схемы поиска кратчайшего пути представлена в алгоритме где граф (X, U, Ф) представля ется матрицей весов We веса несуществующих ребер пола гаются равными Вектор Mark[x] меток вершин устанавливает принадлежность вершины х Е (TRUE) или времен ной (FALSE) метке. Вектор Dist[x] в алгоритме фиксирует теку щие значения меток вершин. Вектор Prev[x] позволяет восстано вить в обратной последовательности вершины кратчайшего пути.

6.9. Кратчайшие пути на графе Алгоритм 6.11. Алгоритм кратчайшего пути на орграфе for x X do begin FALSE;

Dist[xJ = end;

У TRUE;

0;

while not do begin for x X do if not Mark[x] and > + z] then begin dist[x] + end;

новой вершины у X с минимальной временной = = TRUE;

end.

Prev[x] указывает на вершину с окончательной меткой, бли жайшую к вершине х. Последовательность вершин кратчайшего пути будет имеет следующий вид:

z,..., а значение Dist[z] составит длину пути из в Очередная новая вершина, претендующая на постоянную метку, обозначается че рез у.

Х Сложность алгоритма, Алгоритм обращается телу цикла whi le не более Ч 1 раз, и число операций, требующихся при каждом таком обращении, равно |). Тогда сложность алго ритма составит ).

Интересно заметить, что если требуется найти длины кратчай ших путей от до всех вершин графа, то в алгоритме условие цикла while not do begin надо заменить на условие while v not Mark[x] do begin. При этом сложность алгоритма останется прежней.

Программная реализация алгоритма поиска кратчайшего пути представлена в алгоритме на Pascal'e, который близко соот ветствует множественному описанию алгоритма Глава 6. Введение в теорию графов. Алгоритмы на графах Алгоритм 6.12. Программа кратчайшего пути на орграфе Short;

пути на uses Const количество Type of Boolean;

of Longlnt;

of Integer;

of Integer;

Var f { Текстовый файл } nX { Количество вершин в графе } Mark временных и постоянных Dist { Значения текущих меток вершин Prev { Указатель на ближайшую вершину } We { Матрица весов ребер графа } хО { Вершина начала пути } z { Вершина конца пути } у вершина с постоянной Var weight begin открыт для вершина вершина вершин в (* - множество вершин *) for to nX do begin for to nX do begin { Ввод матрицы весов } if then end;

end;

открыт для for х:=0 to nX do begin end;

6.9. Кратчайшие пути на графе вершина с постоянной while not do временные for x:=0 to nX do if not and ( ) then begin вершины с минимальной временной for x:=0 to nX do if not then if then begin x:=z;

while do begin end;

' Длина пути= Рассмотрим пример расчета по программе алгоритма по иска кратчайшего пути на графе, показанном на рис. Исход ные данные графа представляются матрицей весов его ребер в текстовом файле со следующей структурой:

Х в первой строке определяется номер начальной вершины Х во второй строке определяется номер конечной вершины пути z', Х в третьей строке указывается количество пХ вершин в графе;

Х в следующих определяются строки матрицы весов графа.

о б 156 Глава 6. Введение в теорию графов. Алгоритмы на графах 0 7 2 0 0 0 0 0 0 1 5 0 0 3 0 5 0 0 0 0 0 0 3 7 0 0 8 0 0 5 0 0 0 0 1 0 0 0 0 0 0 0 Результаты расчетов сохраняются в выходном файле со структурой:

Вершины пути= Длина пути= 6.10. Потоки в сетях Х Определение. Транспортной сетью называется связный ориен тированный граф без петель (X, U, с выделенной парой вершин и z (рис. Вершина Ч начало транспортной сети, из которой дуги только выходят. Вершина z Ч конец транспортной сети, в которую дуги только входят. На множе стве дуг и U задана целочисленная функция О, где Ч пропускная способность дуги.

Рис. 6.22. Транспортная сеть Определение. Потоком по транспортной сети называется цело численная функция 0, заданная на множестве дуг и и обладающая следующими свойствами:

и (6.10.1) где х Ч внутренняя вершина графа, т.е. х х Ч множество дуг, заходящих в вершину х;

Ч множество дуг, выходящих из вершины х (рис. 6.22).

6.10. Потоки в сетях _ На рис. 6.22 напротив каждой дуги стоит дробь, числитель ко торой Ч пропускная способность дуги, знаменатель Ч поток по дуге. Свойство утверждает, что поток, входящий в верши ну, равен выходящему потоку (поток в вершинах не скапливает ся). Обозначим где поток, входящий в вершину Ч поток, выходящий из вершины Х Утверждение 6.10.1. = Действительно, сумма так как U величина суммируется дважды Ч со знаками + и -. Здесь где первая часть выражения равна нулю вследствие Х Определение разреза. Пусть А с множество вершин транс портной сети: A, Обозначим через множество дуг, входящих в А. Это множество дуг будем называть разрезом транспортной сети.

с(и Рис. 6.23. Разрез транспортной сети = Ч называется мощностью разреза. Это максимально возможный поток, входящий в А по дугам разреза.

= Ч поток, входящий в А по дугам разреза. Ясно, что так как U Х Утверждение 6.10.2. С(А).

Действительно, из рис. 6.23 видно, что не весь поток, входя щий в А, скатывается в z. Часть потока может выходить из А. Зна чит, но тогда и 158 Глава 6. Введение в теорию графов. Алгоритмы на графах Теорема 6.10.1 Форда и Максимальный поток по транспортной сети равен мощности минимального т.е.

max = Доказательство теоремы Ч это алгоритм определения макси мального потока по сети. Алгоритм состоит из двух частей.

Насыщение потока. Поток называется насыщенным, если лю бой путь из в z содержит дугу и s для которой = Задача первой части алгоритм состоит в насыщении потока.

Зададим произвольный начальный поток. Например, нуле вой на всех дугах: e = 1.2. Поиск пути из в г. Если путь найден, то переход к пункту 1.3. Если путь не найден, то переход к пункту 1.5.

Увеличиваем поток по найденному пути таким образом, что бы одна из стала насыщенной.

1.4. Условно разрываем насыщенную дугу и переходим к пункту 1.2, на поиск пути из в z.

1.5. Сеть насыщена и 2. Перераспределение потока. Итак, поток насыщен, как в приме ре на рис. 6.24. Пометим рекурсивным образом все возмож ные вершины сети.

- х2 х Рис. 6.24. Насыщенная транспортная сеть и пометка вершин Вершину пометим 2.2. Пусть Ч любая из уже вершин;

у Ч произволь ная непомеченная вершина, смежная Вершину у помечаем если данные вершины соединены ненасыщенным ребром и помечаем /', если соединены непустым ребром После пометки вершин возможны два случая: вер шина z оказалась либо помеченной, либо непомеченной.

6:10. Потоки в сетях 2.3. Вершина z оказалась помеченной. Значит, существует после довательность помеченных вершин от к z. В этой последо вательности каждая последующая вершина помечена номе ром предыдущей, на рис. 6.25. Определим на дугах новый поток, увеличивая на единицу поток на дугах, ориентирован ных по направлению движения z, и уменьшая поток на единицу на дугах, направленных против этого движения, как на рис. 6.25.

+ -О 1 +0 1 -2 1 +1 2 0 хО х2 хО х Рис. 6.25. Перераспределение потока на основе пометки вершин Заметим, что поток можно увеличивать (уменьшать) на пря мых (обратных) дугах пока одна из дуг не станет насыщенной (пустой). Далее вновь переходим к пометке вер шин (пункт Выполненное перераспределение потока со храняет все его свойства и увеличивает на единицу поток в вершину z. Таким образом, пометка вершины z позволяет увеличить поток как минимум на единицу, а значит, алго ритм конечен, т.е. наступит момент, когда вершина z оста нется непомеченной.

2.4. Вершина z осталась непомеченной. В рассматриваемом при мере это показано на рис. 6.26. Пусть А* Ч множество всех не помеченных вершин. Тогда дуги, входящие в эти вершины, насыщенные, а выходящие Ч пустые. В примере А* = Множество А* определяет разрез, так как z А*. Та ким образом, мы нашли поток и разрез для которых вы полняется = Учитывая, что выходящие дуги из пустые, то весь поток скатывается в z, т.е. = xl Рис. 6.26. Максимальный поток 162 Глава 6. Введение в теорию графов. Алгоритмы на графах Х Определение независимого множества вершин. Пусть граф (X, Ф) Ч неориентированный и без петель. Множество / называется независимым, если между любыми его вершинами нет соединяющих ребер. В зависимом множе стве хотя бы две вершины соединены ребром. Множество полностью зависимое, если каждая пара его вершин соединена.

Вершины графа, составляющие Q, образуют полный подграф.

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

Х Определение независимого множества ребер. Подобно незави симым множествам вершин рассматриваются независимые множества ребер, состоящие из ребер, не имеющих общих вер шин. Каждое независимое множество ребер содержится в не котором максимальном независимом множестве. Число ребер в максимальном независимом множестве называется числом реберной независимости При представлении игр графами независимые множества вер шин являются такими множествами позиций, что никакая из них не может быть достигнута из другой за один ход. Примером явля ется задача о расположении максимального числа ферзей на шах матной доске так, чтобы ни один них не мог побить другого. Это максимальное число равно = 8.

Х Утверждение 6.11.1. Независимое множество максимально тогда и только тогда, когда оно доминирующее, а значит, число (вершинной) независимости не может быть меньше числа доминирования.

Доказательство. Если 7с UЧ максимальное независимое множество, то не может быть вершин k 7, не соединенных с ребром, так как в противном случае множество k /также было бы независимым, но максимальное по условию. Отсюда 7 Ч доминирующее. Пусть 7Ч независимое доминирующее мно жество. Тогда никакое k нельзя перевести из 7 в чтобы k I осталось независимым, а значит, 7 Ч максимальное.

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

Клики графа представляют лестественные группировки вер шин в максимальные полные подграфы. Определение клик графа полезно в кластерном анализе в таких областях, как ин формационный в социологии и др. В качестве примера на рис. 6.31 показан граф и его клики.

7 Рис. 6.31. Граф и его клики Х Замечание. Если предположить, что граф (X, U, про стой, то полностью зависимые множества (клики) в Г стано вятся максимально независимыми множествами в дополните льном графе Г, верно и обратное.

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

Вершины (множества) дерева поиска определим рекурсивно. Ко рень дерева поиска Ч пустое начальное множество S = 0. Пусть теперь S Ч произвольная вершина дерева поиска какого-либо уровня. Тогда вершиной следующего уровня дерева поиска будет вершина S u {х}, если х х смежна с каждой вершиной из S. В дереве поиска такие вершины S и S соединяются ребром, которое соответствует вершине х. На рис. 6.32 показаны некото рый граф дерево поиска Т, которое исследуется в процессе по иска с возвращениями клик графа полным перебором.

Заметим, что каждая клика порождается много раз: клика порождается 3! раз, клики порождаются 2! раз. В общем случае клика размера порождается раз. Все тонкие реб ра на рис. 6.32 исследования дерева поиска можно оборвать, они не приводят к новым кликам. Следующие два утверждения по зволяют обрывать такие лтонкие ребра (не исследовать обес печивая целенаправленный проход по дереву поиска клик графа.

Глава 6. Введение в теорию графов. Алгоритмы на графах 3} (31} Рис. 6.32. Граф полный перебор дерева Т поиска клик Х Утверждение 6.11.2. Пусть (X, U, Ф) Ч исходный граф, S узел в дереве поиска XЧ подмножество вершин графа).

Вершина поиска уже обработана и первой вершиной, которую надо исследовать, является множество {х}, как на рис. 6.33, вершина х смежна с каждой вершиной из S. Пусть все поддеревья узла в дереве Гуже исследованы и по рождены все клики, включающие Тогда необходимо исследовать только те из вершин для которых v (рис. 6.33).

Рис. 6. Поддеревья с корнями (эти вершины смежны с 5) Х Утверждение 6.11.3. Пусть S Ч узел в дереве поиска Т, и пусть S с S Ч предок Т. Если все поддеревья узла ис следованы, что порождены все клики, включающие S то все неисследованные поддеревья с корнями можно игнорировать.

Алгоритм порождения клик графа представляет собой про цедуру поиска с возвращением и является наиболее сложным из всех ранее рассмотренных алгоритмов. Рекурсивная процедура CLIQUE два параметра: D. Для рассматриваемого узла S Клики, независимые множества поиска объединение N представляет множество вершин, смежных с каждой вершиной из S, т.е. Ч множество вершин, которые могут выступать в качестве продолжения поиска клик из вершины S. Множество только из новых вершин, кото рые могут быть добавлены к S в процессе поиска клик, т.е.

e с S ни одно из поддеревьев S {x} не Алгоритм 6.13. Порождение клик графа вершина дерева поиска D CLIQUE(N, D, Z);

проход по дереву поиска Procedure CL1QUE(N, D, Z) D = 0 then вывести S, которое является кликой else then begin x e первое оставшиеся while do begin Z e end;

end;

Procedure N= D end;

Процедура CLIQUE выбирает произвольную вершину x e N, удаляет ее из N и исследует поддерево обращаясь к процедуре View. согласно и при помощи процедуры исследуются только поддеревья где v е v что соответствует условию v e Z. Множество 166 Глава 6. Введение в теорию графов. Алгоритмы на графах из вершин одного уровня дерева, которые должны быть исследованы при рекурсивном проходе по дереву поиска, чтобы не потерять ни одной клики графа.

Второй параметр D процедуры CLIQUE представляет собой множество вершин, смежных со всеми вершинами из S, но таких, которые не надо добавлять к S на предмет продолжения форми рования клик.

исследовалось для некоторых S По алгоритму множество S с X является полным подграфом гра фа Г = (X, U, и D Ч множество всех вершин, смежных с каждой вершиной в S.

Х Множество S будет кликой тогда и только тогда, когда Х Условие N= 0 и 0 обозначает, что все клики, включающие S, уже ранее порождались.

Х При 0 могут оставаться клики, включающие S, которые еще не порождались. Исследование таких поддеревьев S {х}, х N необходимо продолжить.

Основные усилия алгоритма 6.13, порождения клик графа, на правлены на поддержание множеств N к D, текущее состояние которых, согласно перечисленным выше условиям, предопреде ляет исследования по дереву поиска.

Программная реализация алгоритма порождения клик графа представлена в алгоритме на Pascal'e, который близко соот ветствует множественному описанию алгоритма 6.13. Отметим, что в программной реализации передача множеств N, D, ZB каче стве параметров процедур выполнена посредством указателей kN, kD, nD, kZ, где kN, kD, указатели начала вершин в множествах, соответственно N, D, Z, a nN, nD, nZ Ч количество вершин в каждом из этих множеств.

Алгоритм 6.14. Программа порождения клик графа клик uses Const количество длина списка Туре of Integer;

Клики, независимые множества of Integer;

Var f { Текстовый файл } { Количество вершин в графе } Список смежности графа } Fst { Указатели списка Nbr { Количество вершин в списке смежности } Vtx { Список вершин графа } S ( Список вершин формируемых клик } nS { Количество вершин в списке S } N { Список включаемых вершин при поиске - указатель начала и количества вершин в списке D вершин с ранее найденными - указатель начала и количества вершин в списке Z { Список не исследованных вершин } - указатель начала и количества вершин в списке Procedure FORWARD;

Procedure Var FOR Procedure Var teger;

Var FORWARD;

Procedure Var kN,nN, kD,nD, ger FORWARD;

Procedure FORWARD;

Procedure Var yes { Переназначение меток вершин их порядковыми номерами по списку смежности вершин графа } ( yes - признак правильной структуры списка смежности Var begin for i:=l to m do for to do begin for k:=l to m do if then begin break;

end;

168 Глава 6. Введение в теорию графов. Алгоритмы на графах if not yes then end;

Procedure ( Печать вершин найденной клики } Var i begin for i:=l to nS do Write Procedure Var Var ) { Формирование пересечения множеств М и } Var yes begin - указатель начала вершин в множестве - вершин в множестве for i:=l to nM do for j:=l to Nbr[v] do if then begin break;

end;

Var (* Формирование разности множеств и *) Var yes begin (* Формирование *) for i:=l to nZ do if Z[kZ+i]=x then begin for k:=i to nZ do break;

(* Формирование *) 6.11. Клики, независимые множества for to do for i:=l to do if then begin for k:=i to nZ do break;

Procedure { Процедура рекурсивного поиска клик графа } i,j,x begin if (nN=0) and (nD=0) then else if nN<>0 then begin исследование с конца вершин множества первое поддерево (* и *) while nZ<>0 do begin следующие поддеревья (* *) Procedure Var { Исследование поддеревьев следующего уровня } Var kNw,nNw kDw,nDw kZw,nZw begin (* Формирование *) for i:=l to nN do if then begin for k:=i to nN do break;

end;

Глава 6. Введение в теорию графов. Алгоритмы на графах (* Формирование *) (* Формирование пересечения множеств *) и {D и (* Формирование начального Z=N нового уровня *) for i:=l to nNw do (* Исследование поддеревьев нового уровня *) (* Формирование *) Формирование end;

Var kN,nN, kD,nD, kZ,nZ yes begin Assign открыт для списка строк в начала первой строки for i:=l to m do begin вершин в for j:=l to Nbr[i] do смежных начала следующей строки в end;

открыт для if not yes then begin структура смежности Close exit;

end;

Клики, независимые начальных множеств: S, D, N, - пустое - все вершины for i:=l to do - для исследования доступны все for i:=l to m do выделение клик Close Воспользуемся данной программой в качестве примера для шения следующей задачи.

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

Симпатичный граф генерала представлен на рис. 6.34.

Рис. 6.34 Д Пример порождения клик графа Для программы алгоритма 6.14 исходные данные структуры смежности этого графа задаются в текстовом файле Структура (правило) заполнения файла совпадает с той, которая описана в примере поиска в глубину при расчете по про грамме алгоритма 6.2.

Данные файла для примера на рис. 6.34:

172 Глава 6. Введение в теорию графов. Алгоритмы на графах Результаты расчетов сохраняются в выходном файле Clique.out со следующей структурой:

6 3 Строки файла Clique.out это номера вершин соответствую клик лсимпатичного графа на Отсюда видно, что в данном случае на вечер могут быть приглашены лишь четыре близких друга генерала.

6.12. Циклы, фундаментальные множества циклов В данном разделе рассматриваются алгоритмы решения задач, имеющих отношение к структуре циклов графа. Подобного рода задачи возникают при изучении вычислительных программ, в стемах контроля при размыкании обратных связей и т. п. Рас смотрим остовное дерево = (X, Ф) графа (X, U, Ф). Лю бое ребро, не принадлежащее т. е. любое ребро из по рождает в точности один цикл при добавлении его к Такой цикл является элементом фундаментального множества циклов графа дерева Так как каждое остовное дерево графа Ч 1 ребро, в фундаментальном множестве циклов относительно любого дерева графа / имеется \U\ Ч + 1 циклов.

Полезность фундаментального множества циклов вытекает из того факта, что это множество полностью определяет цикличе скую структуру графа: каждый в графе может быть представ лен комбинацией циклов из фундаментального множества. Пусть F= Ч фундаментальное множество циклов, где каждый цикл является подмножеством ребер с U. любой цикл графа / можно записать в виде Ф Ф ), где символ Ф обозначает операцию симметрической разности, Ф = и 6.12. Циклы, фундаментальные множества циклов Например, на рис. 6.35 показан граф и фундаментальное мно жество циклов, получающихся из выделенного жирной линией остовного дерева графа. Цикл графа есть й о или цикл есть Отметим, что в общем случае не каждая сумма циклов будет являться циклом графа.

\2 хЗ х Рис. 6.35. Граф, его остовное дерево и фундаментальное множество циклов При порождении фундаментального множества циклов удобно использовать метод поиска в глубину;

он строит остовное дерево и каждое обратное ребро порождает цикл относительно этого дере ва. Для того чтобы следить за ребрами дерева, используется поиск в глубину со стеком, в котором хранятся все текущие вершины пройденного пути в данный момент. Когда попадаем на обратное ребро, обнаруженный цикл будет состоять из этого ребра и ребер, соединяющих вершины из верха стека. Реализация рассмотренно го подхода представлена в алгоритме 6.15, который строит фунда ментальное множество циклов графа Г= (X, U, Ф).

Программная реализация поиска фундаментального множест ва циклов представлена в алгоритме 6.16.

Алгоритм 6.15. циклы графа for v X do = 0;

метки count - 0;

0;

числа 0;

стека for v 6 X do if Mark[v] = 0 then begin _ Глава 6. Введение в теорию графов. Алгоритмы на графах Cycle(v, 0);

= 1;

Procedure Cycle(x, у) 1;

= count;

for v s Adj[x] do begin 1;

C[n = v;

в = 0 then Cycle(v, x) else < Mark[x] л v у then begin 1;

(х, v), найден С, end;

- 1;

исследованную вершину из end;

end;

Procedure С, print номера repeat print вершины из пС пС- 1;

until end.

Алгоритм Программа поиска циклов графа Program циклы uses Const количество длина списка смежности) Туре of Integer;

of Integer;

Var f Текстовый файл ) n { Количество вершин } nC { Количество вершин в стеке Циклы, фундаментальные множества циклов { Список смежности графа } Fst { Указатели вершин списка Nbr { Количество вершин в списке смежности } Vtx { Список вершин графа } Mark { Номера компонент для вершин С { Стек выделения циклов графа } В { Признаки основных и обратных ребер прохода в глубину } jC { Счетчик числа циклов } { Счетчик меток вершин } var yes { Переназначение меток вершин } { их порядковыми номерами в списке смежности } { yes - признак правильной структуры списка смежности } Var begin for to n do for j:=l to Nbr[i] do begin for to n do if then begin break;

end;

if not yes then end;

Procedure var цикла из begin repeat ] :3) until end;

Procedure Var i,v begin 178 Глава 6. Введение в теорию графов. Алгоритмы на графах Листы Х Определение. Пусть Г= (X, U, Ф) Ч неориентированный граф.

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

Х Определение. Ребро и = (х, у) s разделяющим реб ром (или мостом, разрезающим ребром) в Г, если в графе Т, получающемся после удаления ребра и, вершины х и у не свя заны. Тогда граф Г можно представить как объединение гра фов = (6.13,1) где = 0, и содержит х, содержит у.

Х Утверждение 6.13.1. Ребро и = (х, у) е тогда и только тогда, когда оно не является Доказательство. Допустим, что разделяющее ребро ется циклическим. Тогда после его удаления вершины х и у оста нутся связанными, а значит, разложение невозможно, что противоречит условию: и Ч разделяющее ребро. Теперь и = (х, у) Ч не циклическое ребро, т.е. не существует цепей, соединяющих х и у и не содержащих и. Отсюда и Ч разделяющее ребро.

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

Условно взаимное расположение вершин и циклов можно представлять так, как показано на рис. 6.36.

Рис. 6.36. Вершины циклически-реберно связаны Утверждение 6.13.2. Циклически-реберная связность опреде ляет отношение эквивалентности (см. на множестве вер шин графа (X, U, Ф). На рис 6.37 показано разбиение на компоненты связности.

6.13. Листы и блоки Рис. 6.37. Компоненты циклически-реберной связности графа.

Компоненты связности графа.

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

Х Определение. Подграф определяемый листовым множе ством L, называется листом.

Х Утверждение 6.13.3. Отметим следующие очевидные свойства листа 1. Граф циклически замкнут, т.е. если простой цикл в /имеет общую вершину с L, то весь про стой цикл С содержится в 2. Не может быть более одного ребра, связывающего два раз личных листовых множества и так как иначе эти ребра оказались бы циклическими и множества и должны были бы совпадать. Связывающие одиночные ребра различ ные листовые множества и являются мостами для гра фа. Ниже показано, что они будут являться и блоками, со стоящими из одного ребра.

3. Все ребра в являются циклическими. Пусть ребро (х, у) лежит Покажем, что оно циклическое. Действитель но, если, например, вершины х и у в L соединены ребром, тогда (х, у) циклическое по построению L. Если же х и у в L не соединены ребром, то, добавив данное ребро у) к L, Глава 6. Введение в теорию графов. Алгоритмы на графах получим цикл, так как вершины х, у связаны в L по построе нию. Отсюда следует, что ребро (х, у) циклическое.

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

6.13.2. Блоки Х Определение. Пусть (X, U, Ф) Ч неориентированный граф.

Два ребра и, v e U называются сильно циклически связанными, если существует такая последовательность простых циклов что и e v e и любая пара соседних циклов имеет, по крайней мере, одно общее ребро. Условно вза имное расположение ребер и циклов можно представлять так, как показано на рис. 6.38.

Рис. 6.38. Сильно циклически связанные ребра v Х Определение. Множество всех ребер, сильно циклически свя занных с ребром и U, образует некоторую часть графа Г называемую блоком, определяемым ребром и. Множество вер шин L этого графа называется блоковым множеством, опреде ляемым ребром и. Блок является связным графом и может со стоять из единственного ребра.

Х Лемма 6.13.1. Два ребра сильно циклически связаны тогда и только тогда, когда существует простой цикл, содержащий оба эти ребра. Справедливость данного утверждения следует непо средственно из структуры сильно циклической связанности ребер (рис. 6.38).

Х Лемма 6.13.2. Если Р(х, у) Ч простая цепь, связывающая две различные вершины х, у e блокового множества, то все ра цепи Р(х, у) принадлежат блоку Доказательство. Если предположить, что утверждение леммы не выполняется, то существует участок цепи Р(х, ребра кото рого не принадлежат данному блоку Не уменьшая общнос 6.13. Листы и блоки ти, будем считать, что этим участком является исходная цепь Р(х, у). как х, у Е то в блоке существует простая цепь у), связывающая х, у. Тогда объединение простых цепей Р(х, у) Q(x, у) составит простой цикл. Согласно лемме ребра этого цикла будут сильно циклически связаны, а значит, все ребра простой цепи Р(х, у) должны лежать в Г что проти воречит предположению.

Х Утверждение 6.13.4. Из леммы 6.13.2 следует, что блок является подграфом. Он циклически сильно замкнут, в том что если простой цикл С имеет хотя бы две вершины, общие с то все ребра цепи С принадлежат Поэтому два различных блока могут не более одной общей вершины (рис. 6.39). В противном слу чае блоки должны совпадать.

Х Утверждение 6.13.5. Из определения блокового множества следует, что все его вершины являются циклически-реберно свя занными при условии, что число ребер в блоке Г (L ) более од Отсюда заключаем, что с L, где L Ч листовое множе ство вершин и каждый лист Г (L) имеет непересекающееся по ребрам разложение (6.13.2) I на семейство блоков.

Х Определение. В графе (X, U, Ф) вершину х вершиной (разрезающей или точкой сочленения), если имеет место прямое по ребрам разложение (рис. 6.40) x. (6.13.3) Рис. 6. Прямое по ребрам разложение графа Х Утверждение 6.13.6. Блок не имеет разделяющих вер так как все его вершины циклически-реберно связаны.

На основании разложения любого листа Г на непе ресекающееся по ребрам разложение на блоки и последне го утверждения, составление листа Г (L) из блоков может быть представлено фигурой, как на рис. 6.41, 182 Глава 6. Введение в теорию графов. Алгоритмы на графах в которой различные блоки соприкасаются в своих соединяющих вершинах. Соединяющие вершины блоков являются разделяющими вершинами графа. Разложение (6.13.2) листов на блоки позволяет теперь А уточнить структуру графа (рис. 6.37): каждый лист можно представить в виде (рис. 6.41) составляющих его Рис. 6. блоков 6.13.3. Поиск блоков в глубину Разложение графа на блоки и выделение их имеет важное прак тическое значение. Иногда недостаточно знать, что граф связен;

может интересовать насколько лсильно связен связный граф.

k Ь) с) Рис. 6.42. Исходный граф (а);

блоки графа (Ь);

листы (с), (е) и один мост (d);

точки сочленения: b, f, j, Например, удаляя вершину сочленения двух блоков (рис. 6.40) и инцидентных ей ребер, нарушим связность графа. Связность графа не нарушится, если удалить внутреннюю вершину блока и инцидентные ей ребра. Про такие компоненты графа говорят, что они Отыскание точек сочленения и блоков графа важ но при изучении надежности коммуникационных и транспорт 6.13. Листы и блоки сетей. Это важно также и при изучении других свойств таких, например, как планарность, так как часто полезно разло жить граф на его компоненты (блоки) и изучать каж дую из них в отдельности.

На рис. 6.42 в качестве примера изображен связный граф и его блоки (двусвязные Здесь же показано разложение графа на листы.

Для нахождения блоков и точек сочленения применим извест ный метод поиска в глубину на неориентированном графе (X, U, Ф). Основу алгоритма выделения блоков и точек их со членения легче понять, рассмотрев пример на рис. 6.43, где схе матически изображен связный граф, состоящий из шести блоков i = 1,6, и четырех точек сочленения Xj, j = 1,4.

Рис. 6.43. Схематическое изображение графа с шестью блоками и четырьмя точками сочленения Если начать поиск в глубину, скажем, из вершины s e то мо жем перейти из в проходя через вершину Из свойства по иска в глубину, все ребра в должны быть пройдены до того, как вернемся в Поэтому состоит в точности из ребер, которые проходятся между входом и выходом из вершины Для других блоков дело обстоит несколько иначе. Так, например, если уйти из в а оттуда Ч в через то окажемся в пройдя ребра из и Если хранить ребра в то во время прохождения назад из в через вершину все ребра будут на верху стека.

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

Реализация рассмотренного подхода выделения блоков графа представлена в алгоритме В векторе Mark[x] меток вершин х фиксируются порядковые номера обхода соответст Глава 6. Введение в теорию графов. Алгоритмы на графах вершин. В этом случае метка вершины сочленения при входе в блок получит наименьший номер из всех остальных вер шин блока. Таким образом, для определения точки сочленения выхода из блока достаточно найти вершину этого блока с мини мальной меткой. Свойство циклической замкнутости блока по зволяет это сделать лишь на основе вектора меток не привлекая дополнительной информации. На рис. 6.44 схематич но представлен блок, где вершина Ч точка входа в блок и точка сочленения. Вершина х Ч следующая обследованная вершина блока после w. Свойство циклической замкнутости блока позволяет утверждать, что существует по край Рис. 6. мере еще одна вершина у, смежная w. Рекур сивный характер алгоритма поиска в глубину на графе позволяет утверждать, что в этом случае ребро блока (у, w) будет пройдено как обратное, и, значит, метка точки со членения блока будет доступна до выхода из блока по ребру входа (z, x). Поэтому, сохраняя минимальное значение меток обследо ванных вершин (включая и по обратным ребрам поиска в глуби будем проверять при рекурсивном выходе из поиска в глуби ну совпадает ли это минимальное значение с меткой вершины выхода. Если ответ положительный, то найдена точка сочлене ния. В алгоритме значения минимальных меток фиксируются в векторе для каждой вершины х е X, как наименьшее значение из у Ч вершины графа, которые достижимы из при проходе графа в глубину.

Алгоритм 6.17. Выделение блоков графа count = 0;

for v Mark[v] = 0;

метки for = 0 then Block(v, 0);

Procedure Block(x, w) 1;

= count;

= count;

минимальная for v do = 0 then begin Stack = Stack (x, 6.14. Двудольные графы if then begin В этой х Ч либо корень дерева, либо точка сочленения. Образовать новый блок.

состоящий из всех ребер стека, включая (х, v).

end, else if < Mark[x] and then begin { (x, v) Ч обратное Stack = Stack (х, end;

end.

6.14. Двудольные графы Х Определение. Граф (X, U, называется двудольным, если множество его вершин можно разбить на два независимых подмножества таких, что и = Такой граф будем обозначать как U, Ф).

На рис. 6.45 изображен типичный двудольный граф. Двудольные графы играют заметную роль в различных приложениях.

6.14.1. Условия существования двудольных графов Х Теорема Граф Г = (X, U, Ф) является двудольным тогда и только тогда, когда любой его простой цикл четной длины.

Ясно, что данное условие для двудольно го графа всегда выполняется. Разобьем граф компоненты = Ф) одна из них и а Ч произвольная вершина. Разобьем множество вершин на непе ресекающиеся и где Ч вершины, расстояние до кото рых от а нечетно;

Ч вершины, расстояние до которых от а чет но, а е Множества и являются независимыми. Дейст вительно, если предположить, что вершины b и с смежные и 186 Глава 6. Введение в теорию графов. Алгоритмы на графах с или с то существовал бы цикл нечетной длины, соответственно ла длина Ь длина единица с нечетная длина а или ла четная длина единица с длина а, что противоречит усло вию. Рассмотренное разбиение вершин вы полним для компоненты связности. На рис. 6.46 показано объедине ние независимых компонент и в не- Рис. 6. зависимые компоненты и k 6.14.2. Паросочетания.Х Определение. в двудольном графе U, Ф) называется независимое подмножество ре бер л с ребра л не имеют общих вершин. _ Для графа, изображенного на рис. 6.47, в качест ве паросочетания можно взять множество ребер = 1), и т.п. 6. Х Определение максимального паросочетания. Па росочетание называется максимальным, если любое другое паросочетание содержит меньшее число ребер.

6.14.3. Алгоритм определения максимального паросочетания Пусть U, Ф) Ч двудольный граф и Ч произволь ное паросочетание. Множество вершин с и с (рис.

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

Заметим, что ребра в цепи не повторя ются. Пусть Ч произвольная вершина и = Ч ребро, инци дентное вершинам из и Постро им чередующуюся цепь и допустим, что по такой цепи можно достичь вершины 6.14. Двудольные графы Такую цепь С можно использовать для получения нового паросо я, которое содержит на одно ребро больше, чем исходное паросочетание я. в я можно включить все ребра я, идобавив Полученное таким образом п содержит несмежные ребра, а значит, я Ч паросочета ние. Говорят, что получено из я чередующимся расширением.

Пример. Дан двудольный граф где = и = Соединение вершин и задано соот ношениями: 5, Найти максимальное паросочетание.

Выберем начальное паросочетание я таким образом, что вер шину e соединяем с вершиной j первой незанятой ра нее из списка соединений для На рис. 6.49 изображено исход ное паросочетание я = 4), 5), 3), |я| = 5.

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

Переходы следует закончить, если вершина 6 достиг нута или подмножество вершин доступных из повторилось в чередующейся цепи. В последнем случае вершина 6 не доступна из и, значит, исходное паросочетание л максимальное. В нашем случае вершина 6 оказалась доступной. Для выделения исходной чередующейся цепи из всего множества расширяющихся цепей выполним обратный ход: Теперь новое па росочетание строим из старого, исключая из него ребро 1) и включая ребра Процесс включения также показан на рис. 6.49. Максимальное паросочетание содержит ребра 4), 5), 3), 2), 6), 1) и |я| = 6.

188 Глава 6. Введение в теорию графов. Алгоритмы на графах Х Теорема 6.14.2 о максимальном паросочетании.

Пусть U, Ч двудольный граф. Тогда количест во ребер в максимальном паросочетании равно (*) где = е л (х, у) е с Доказательство. Пусть л Ч максима льное паросочетание в исходном двудо льном графе (рис. 6.50). Паросочетание я позволяет рассматривать его как ото бражение я: вершин множест ва в вершины множества по ребрам я.

Аналогично, под Д будем понимать ото бражение Д:

вершин МНОЖе паросочетание л ства в вершины множества рам U графа. Вершины множеств и Z (рис. 6.50) несмежные, так как паросочетание я является макси мальным.

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

Для множества А выполняется условие = \АА\, в противном случае множество А можно было бы еще расширить. Следствием расширения множества в процессе его отображения является включение Дсо с ДА Обозначим множество со A = В. Покажем, что найденное множество В удовлетворяет условию (*) теоремы, т.е. = Ч - | - Имеем | = и А)\ = =, следова тельно, - - = - | - = | - | = 6.14. графы Покажем теперь, что с условие (*) теоремы записывается в следующем виде: Ч Ч Тогда ранее найденное множество В, для которого данное неравенство обращается в равен ство, будет доказательством условия (*) теоремы. Пусть А = Отметим, что выполняется неравенство так как вершины множества составляют паросочетание. Тогда верно, что = + | + | + + или Ч АА\ Теперь количество ребер в максимальном паросочетании можно оценить: = Ч Ч Ч Теорема доказана.

6.14.4. Системы различных представителей Рассмотрим пять множеств: = = 2, = 2, = 4, = Требуется выбрать такие различные чис i = 5. данного = 2, = 1, = 5, = 3, = 4. Однако если взять множества = = = = = 4, то такой выбор ока зывается невозможным.

Рассмотрим данную задачу в общем случае. Пусть Ч система подмножеств множества S. Будем го ворить, что имеет систему различных представителей, если для всех /' = п существуют различные 6.14.5. Связь системы различных представителей и двудольных графов Определим двудольный граф соответствующий системе подмножеств. Пусть = Ч сис тема подмножеств множества S. По ложим вершинами графа, которые соединены ребрами со своими элементами Ч смежными им вершинами из (рис. 6.51).

Х Лемма 6.14.1. Двудольный граф отвечаю щий системе подмножеств = имеет макси мальное паросочетание из п ребер тогда и только тогда, когда имеет систему различных представителей. (Доказатель ство вытекает из определения построения двудольного графа, отвечающего системе представителей).

Глава 6. Введение в теорию графов. Алгоритмы на графах Х Теорема 6.14.3 Ф. Холла о существовании системы различных представителей. Система = имеет систему различных представителей тогда и только тогда, когда для лю бой } с неравен k ство т.е. количество элементов в объединении лю k подмножеств должно быть не менее k.

Необходимое условие теоремы следует из определения системы различных представителей. Каждое под множество содержит элемент отличный от К элементов других подмножеств, а значит Ф) соответству ющий системе подмножеств = Покажем, что в данном графе существует максимальное паросочетание, количе ство ребер в котором равно п. Тогда из леммы будет следо вать достаточное условие теоремы. Из теоремы имеем, что число ребер в максимальном паросочетании равно = Ч где = \ л (х, у) с В рам ках принятой интерпретации A = }, \A\ = k и k = По условию теоремы k. Таким образом, с 7= \А\ - а значит, Однако следовательно, = = л до казано).

6.14.6. Задача о назначениях Существует множество задач, постановки которых укладыва ются в рамки задачи о назначениях. Рассмотрим две такие поста новки.

Задача. Предположим, что вычислительная сеть объединяет специализированных ЭВМ. На вход сети поступают задачи.

стно, что наибольшая производительность конкретной ЭВМ сети достигается на определенном классе задач. Это выражается коэф фициентом использования ЭВМ при класса за 6.14. Двудольные графы дач. Найти оптимальное распределение задач по сети таким обра зом, чтобы эффективность ее использования была наибольшей.

Задача. Группа лиц может выполнить п видов работ. Эффек тивность использования лица работе определяется ме рой ценности Найти оптимальную расстановку людей по ви дам работ.

Х Теорема 6.14.4 Ч алгоритм поиска перестановки я.

Пусть А \,n Ч матрица целых чисел. Тогда макси мум (6.14.1) по всем перестановкам я равен минимуму (6.14.2) ) по всем числам и таким, что + (6.14.3) Минимум суммы достигается на перестановке я такой, что Доказательство. Пусть я Ч произвольная перестановка. При изменении от 1 до л величины принимают все значения множе ства По условию + 1, п, а значит, и для j = верно Установим связь сумм (6.14.1) и (6.14.2).

;

=1 /= Таким образом, сумма для любой перестановки я не боль ше суммы Отсюда следует, что теорема будет верна, если мы найдем такие и и перестановку я, что (6.14.1) и (6.14.2) совпадают.

Шаг 0. Поиск начальных и удовлетворяющих ограничени ям + V/, j = 1, п. Положим = 0 и максима льный элемент в строке;

условие (6.14.3) +Vj выполняется. Для матрицы ценностей на рис. 6.52 и снизу указаны начальные значения, соответственно и 192 Глава 6. Введение в теорию графов. Алгоритмы на графах V2 V 3 4 2 1 1 4 3 3 6 5 2 5 л 6 4 5 5 0 0 0 Рис. 6.52. Начальная матрица Шаг 1. Фиксируем все и уменьшаем значения = до тех пор, пока одно из неравенств + не обратится в равенство + = Эту процедуру выполняем для каждой строки В рассматриваемом примере на рис. 6.53 звездоч ками отмечены совпадения.

V2 V3 V * * л * 0 0 0 Рис. 6.53. Матрица совпадений Шаг 2. Для каждого определим множества совпаде ний Если обратиться к = = = Система множеств l,n может иметь систему различных Ч все раз личные. Тогда на перестановке я ХХХ выполняется 72 ХХХ отношение а значит, найденная переста новка л является оптимальной.

Шаг 3. Предположим, что не имеют системы различ ных представителей, как в рассматриваемом примере. Тогда нару шается условие теоремы Ф. Холла, т. е. существуют что

тогда -l) + (Vj 2. j, а значит, v* и + > или + 1. Отсюда -l) + Обозначим =t

Глава 6. Введение в теорию графов. Алгоритмы на графах Х Замечание. При решении практических задач изменение пере менных и на 1 может затянуть получение ответа. Заметим, что алгоритм допускает изменение переменных и на лю бую величину, нарушая при этом основного условия:

В рассматриваемом примере сумма уменьшилась на 2, так как u u u = = 2 и k = 4. Необходимо вернуться на шаг 2.

Матрица совпадений примет вид на рис. 6.54, 6.55. Составим для нее систему множеств совпадений = = = Проверим наличие системы различных представите лей для данных множеств. Обращаясь к интерпретации системы различных представителей в терминах двудольного графа, надо проверить, что максимальное паросочетание равно 4 для графа Г= ( U, Ф), где = = 2, 3, и связь вершин 3, Решая, можно установить, что существуют три таких = 2), 3), 1), = 2), 3), 4), = 2), 4), 1), Таким образом, существуют три оптимальных назначения:

2 3 2 3 1 4/ 3 4 1/ 4 Ценность назначения составляет + + 6.15. Хроматические графы Пусть Г= (X, U, Ф) Ч простой граф. Граф k-pac если существует такое разложение множества его вершин Хна k непересекающихся подмножеств (компонент) таких, что С, =0 (6.15.1) и вершины в каждой компоненте независимы, т.е. ребра в /со единяют вершины только из разных компонент (рис. 6.56). Пред ставление (6.15.1) называется k-раскраской графа Г. Вершины этого графа можно раскрасить k красками так, чтобы смежные вершины всегда были окрашены в разные цвета. Для этого доста точно вершины каждой компоненты покрасить своей краской.

6.15. Хроматические графы Наименьшее возможное число компонент в разложении (6.15.1) называется хроматическим чис лом графа Г.

Рассмотрим несколько примеров хроматического разложения графов.

Х Утверждение 15.1. Полный граф (X, на = вершинах имеет хроматическое число = Здесь каждая компонента разложения состоит из одной вершины, = 1, /' = Х Утверждение 15.2. Граф (X, U, Ф) содержит максимальный подграф (клику) из k вершин тогда и только когда, когда его хроматическое число равно k.

Доказательство. Пусть макси мального подграфа. Для разложения максимального под графа требуется компонент е Пока жем, что этого числа компонент достаточно для разложения (6.15.1) всего графа Г. е произвольная вершина и у существует такая е которая несмежна у, в противном случае существовал бы макси мальный подграф из k + 1 вершины. Вершину у включаем в ком поненту Cj. Следовательно, = k.

= k. Предположим, что максимальный под граф в т вершин и т k. Необходимое условие теоре мы в этом случае утверждает: = т, что противоречит условию.

Х Утверждение 15.3. Граф (X, U, Ф) является двудольным тогда и только тогда, когда = 2.

Х Утверждение 15.4. Хроматическое число дерева равно 2, так как дерево является двудольным графом.

Х Теорема 6.15.1. Для числа вершинной независимости и хроматического числа графа U, Ф), = п выпол няется соотношение (6.15.2) Доказательство. В разложении все компоненты ляются независимыми. Из определения числа следует, что 196 Глава 6. Введение в теорию графов. Алгоритмы на графах Суммируя по всем компонентам, получим Задача. Для графа на рис.

найти разложение (6.15.1) и установить, что хроматиче Рис. 6. ское число = 3.

Задача. Пусть / Ч длина самой длинной простой цепи в графе Г. Показать, что 1.

Решение. Предположим, что + 2. Тогда утверждение позволяет сделать заключение, что граф максима льный подграф (клику) из / + 2 вершин или более. Такой подграф содержит простой цикл из + 2 ребер и простую цепь длиной / + 1.

Это противоречит условию задачи, так как любая простая цепь графа не может превосходить длины /. Отсюда следует, что 6.16. Диаметр, радиус и центры графа I. Пусть (X, U, Ч конечный связный псевдограф. Обо значим через d(x, у) длину минимального маршрута между вер шинами х, у X. Величина = называется ром графа.

П. Пусть х X Ч произвольная вершина графа. Величина r(x) называется максимальным удалением в графе Г от вершины х.

III. Радиусом графа Г называется величина ТУ. Любая вершина z е X, для которой называется центром графа.

Задача. Для графа на рис. 6. ти диаметр, радиус и все центры.

Решение. Диаметр = = 3. 3, = 2, 3, = 2, = 3, = 2. Следовате льно, радиус графа (Г) = 2.

Центры графа:

Введение в теорию групп.

Приложения Определение группы Х Определение. Группой называется непустое множество G с би нарной алгебраической операцией Х (будем умноже нием) такой, что выполняются следующие аксиомы:

1. =с Ч замкнутость относительно операции 2. Ч ассоциативность операции Х.

3. Ч существование единичного эле мента е.

4. Ч существование обратного элемента а.

Х Определение. Группа называется коммутативной, если выпол няется аксиома коммутативности:

5. коммутативность операции Х.

Примеры = | е Ч группа с операцией сложения чисел, где Z Ч множество целых чисел. Действительно, 0 Ч единица группы;

= Ч обратный элемент к л е 2. = | п е Ч группа с операцией сложения чисел.

3. = | л е группа с операцией умножения чисел.

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

5. Ч множество ортогональных матриц порядка п является группой с операцией умножения матриц.

6. = 1} Ч группа с операцией умножения чисел.

7. Ч множество рациональных чисел является группой отно сительно операций сложения и умножения (без Ч множество вещественных чисел является группой отно сительно операций сложения и умножения (без нуля).

Глава 7. Введение в теорию групп. Приложения = Ч множество подстановок (перестановок) является группой с операцией умножения подстановок (симметриче ская группа см.

Х Определение. называется подгруппой группы G, если группа относительно бинарной операции, определенной в G, т.е. для элементов аксиомы Так, на пример, являются подгруппами: с с с Х Утверждение 7.1.1. Пусть Ч подмножество группы G и е М выполняется М. Показать, что М Ч подгруп па. Данное условие можно рассматривать как характеристиче ское свойство группы.

Проверим выполнение аксиом группы.

1. Существование единичного элемента. Пусть а е М, тогда е М или е е М.

2. Существование обратного Пусть а е М и так как е М, то е Х е М или а~ е М.

3. Замкнутость. Пусть a, b е М, тогда и е М. Значит, и а Х е М или ab е М.

7.2. Гомоморфизм групп Х Определение. Гомоморфизмом группы в называется ото бражение сохраняющее операции:

где о Ч операция в группе Х Ч операция в группе взаимно однозначное отображение, то/ называется изоморфизмом.

Свойства гомоморфизма Свойство 1. Единичный элемент переходит в единичный. Пусть Ч единица е Ч единица Действи тельно, и В группе е Значит, = Свойство 2. Обратный элемент переходит в обратный. Пусть а е тогда = = = так как где М) = В группе = = довательно, 7.3. Смежные классы _ Х Определение. Образом гомоморфизма/называется подмножество Im/= \ с Х Определение. гомоморфизма /называется подмножество е = с Х Утверждение 7.2.1. Ч подгруппа.

Доказательство. Проверим все свойства (аксиомы) группы.

1. Замкнутость. е Im/ е = = Тогда е Im/ 2. Существование элемента. Так как е Im/ 3. Существование обратного элемента. е Im/ = Тогда и Х Утверждение 7.2.2. Ч подгруппа.

Доказательство. Проверим все свойства (аксиомы) группы.

1. Замкнутость. е Кег/ = = Сле fljij е Кег/ 2. Существование единичного элемента. Так = значит, 3. Существование обратного элемента.

Кег/ = 7.3. Смежные классы Х Определение. Пусть Н= Ч подгруппа группы G. Множество {ge, полученное умноже нием элементов Н слева на элемент g G, называется левым смежным классом группы G по подгруппе Н.

Х Лемма 7.3.1. Пусть Я Ч подгруппа группы G, тогда е Н Доказательство. Пусть Н- е Н е Н - замкнутость подгруппы, значит ЛЯ с Я. С другой стороны, е Н = = = е ЛЯ, откуда ЛЯ. Таким образом, е Я Я.

Х Лемма 7.3.2. Пусть Я Ч подгруппа группы G. Если 0, то ft-ff, где G.

200 _ Глава 7. Введение в теорию групп. Приложения Доказательство. Пусть тогда Я такие, что t = = Рассмотрим левый смежный класс = = откуда Х Лемма 7.3.3. Пусть Я Ч подгруппа группы G, тогда e G Доказательство. Для доказательства достаточно показать, что все элементы в различные. Пусть Я такие, что = Тогда g =g или = откуда = что противоречит предположению.

Х Лемма 7.3.4. Группа распадается на непересекающиеся ле вые смежные классы по подгруппе Я, т.е. G и где все Ч различные;

= 0, если ft ft.

Доказательство. Пусть }Х Ясно, что H.

лив совпадающие левые смежные классы из последнего разложе ния, получим искомое разложение группы Х Теорема 7.3.1 Порядок конечной группы G кратен порядку любой из ее подгрупп Яи \G \ = |Я| Х Я|, где Н\ Ч целое число, называется индексом подгруппы Яв группе G.

Доказательство. Лемма 7.3.4 позволяет записать разложение группы G = при ft*ft. Из леммы = \Н\, тогда = = = + +... + = s Х Следовательно, = |Я| Х Определение. Пусть G Ч группа. Порядком элемента g e G (g e) называется наименьшее целое k такое, что = e.

Утверждение 7.3. Пусть G Ч группа и g e G Ч произвольный элемент порядка k. Тогда множество = назы вается циклической подгруппой, a g есть образующий ее эле мент.

Утверждение 7.3.2. Порядок группы | G \ кратен порядку любо го G. (Следствие теоремы Лагранжа и утвер ждения Утверждение 7.3.3. Всякая циклическая группа коммутативна (абелева).

Теорема 7.3.2. Всякая подгруппа циклической группы сама яв ляется циклической.

7.3. Смежные классы Доказательство. Пусть G Ч циклическая группа с образую щим элементом е G и G Ч подгруппа. Предположим, что наименьшая положительная степень элемента g, содержащаяся в Н, есть что элемент Ч образующий элемент под группы Н. Допустим, что в содержится где О и делится на k. Пусть k)Ч наибольший общий делитель, тогда существуют такие целые числа и и v, что k Х и + Х v = d (см. п.

Следовательно, подгруппа Яв этом случае должна содержать эле мент = = Так как d < k, то приходим к противоре чию относительно выбора элемента Таким образом, Ч обра зующий элемент подгруппы с (Я Х Утверждение 7.3.4. Число образующих циклической группы равно значению функции Эйлера Ч ко личество чисел из множества взаимно простых с п.

Пусть е и п) = 1 Ч НОД (см.

т.е. Ч взаимно простые. Если предположить, что на ступит е некоторого = некото рого t, так как п Ч порядок элемента g. Из Х k = п Х t следует, что п делит k, так как и) = 1. Это противоречит предположению k < п. Следовательно, порядок элемента = п.

Пусть теперь п) s и s > 1, т.е. s Х р и п = s Х q, где q) = 1. = = = tf9? = = е, а значит порядок элемента | = q < п. Действительно, порядок | не ме ньше q, в противном случае имеем = = е, где k < q, и = так как п Ч порядок Как и в первом случае, = следует, что q делит k, т.к. (р, q) - 1. Это противоречит предположению k < q.

Х Определение. Подгруппа Я группы G называется делителем, если правые смежные классы совпадают с левыми:

е G Hg.

Х Утверждение 7.3.5. Множество смежных классов группы G по нормальному делителю Яявляется группой с операцией умно жения смежных классов. Такая группа называется фактор группой и обозначается Элементами этой группы являют ся смежные классы разложения группы G = непересекающиеся левые смежные классы, т.е.

202 _ Глава 7. Введение в теорию групп. Приложения Доказательство. Проверим выполнение аксиом группы.

1. Замкнутость. G/H = 6 G/H. Произведение двух классов Ч это умножение каждого с каждым элементов указанных классов.

2. Существование единичного элемента. Так как = = = то НЧ единица факторгруппы G/H.

3. Существование обратного элемента. Так как = = Н, то е обратный элемент к элементу gH е Х Теорема 7.3.3. Для любого нормального делителя Н группы G отображение где = gH, является гомоморфизмом, ядро которого Н, фактор группа.

Доказательство. Проверим свойство гомоморфизма сохране ния операций:

Единицей факторгруппы G/H является Н, тогда = Имеем s = Я, откуда Я с Кег/ С другой стороны, Я = Я. В противном случае, если H, то суще ствует такое Л е Я, что e или Я, что противоречит предположению Я. Таким образом, только Я с Кег/ а зна чит, Кег/= Я.

Х Теорема 7.3.4. Ядро произвольного гомоморфизма есть норма льный делитель.

Доказательство. G где G, гомо морфизм. e = е Обозначим Я= подгруппа. Покажем, что e G Eg, т.е. ЯЧ нормальный де литель.

Рассмотрим множество e G = k e где k Ч фиксиро ванный элемент. Покажем, что где Ч произвольный фиксированный элемент. Пусть тогда f = = e и = = e. Отсюда или и Таким образом, другой стороны, = fc.

Отсюда gh или S. Так же проверяется, что Получили, что Hg, т.е. нормальный делитель.

7.4. Строение коммутативных групп 7.4. Строение коммутативных (абелевых) групп Х Определение. Группа является прямым произведением своих подгрупп и G = x если выполнены следующие условия:

1. Пересечение подгрупп = e.

2. Любой элемент g е G однозначно представим в виде произ ведения элементов g = где 3. то Коммутативность указанных элементов позволяет записать представление в и Лемма 7.4.1 утверждает, что это представление од нозначное.

Х Лемма 7.4.1. Пусть G Ч группа и Ч ее подгруппы, для которых пересечение = е. Тогда, если то gl где Доказательство. Действительно, если = = e. Следовательно, и Х Теорема 7.4.1. Группа G является прямым произведением сво их подгрупп и тогда и только тогда, когда выполняются условия:

Пересечение подгрупп = е.

2. Любой е G однозначно представим в виде произ ведения элементов g = где e 3. Подгруппы и являются нормальными делителями.

Доказательство. Очевидно, что если группа G является прямым произведением своих подгрупп и то условия выполняются.

Достаточно показать, что если e и то = = Имеем e и = тогда e откуда Также e и = тогда e и, значит, Итак, а так как n = e, то из леммы 7.4.1 следует, что и Следовательно, S\S2 = 204 _ Глава 7. Введение в теорию групп. Приложения Х Утверждение Пусть G Ч конечная абелева группа поряд ка = > простые различные чис ла. Множество = {х е G \ где а принимает произ вольные целые значения, является подгруппой и называется примарной подгруппой группы G, соответствующей простому числу р.

Х Теорема 7.4.2. Всякая конечная абелева группа G разлагается в прямое произведение своих подгрупп где \G\ = Доказательство Ч индукция по числу простых в разложении порядка \G\ = Х Очевидно, что для \G \ справедли во, т.к. в этом случае = G. Пусть теперь где = 1.

Покажем, что G представимо в виде G = х Проверим свойства разложения.

1. = е. Если предположить, что Зх е х и х е, то | | = и | х \ = тогда и = что противоречит усло вию q) = 1.

2. Покажем, что любой элемент х G можно представить в виде х = у Х z, где у е z е A(q). Поскольку порядок | х \ делит | Ч взаимно простые, то существует представление =1 (см.

алгоритм Евклида), где т, Ч целые. Тогда =х х у Х и z для которых =е и z = е. Проверить, если = е, то порядок | у \ де лит N. Отсюда у е A(q).

Пусть разложение верно для т.е. для Рассмотрим группу порядка \G\ = тогда возможно пря мое разложение = = е G | Ч это доказывается как и для случая Имеем: группа Ч примарная, группа предположению индукции разлагается в прямое про изведение своих примарных подгрупп;

теорема доказана.

7.4. Строение коммутативных групп Х Утверждение 7.4.2. Порядок конечной примарной группы (подгруппы) = {х\ \ х \ равен | \ = р", где Ч неко торое положительное целое;

а принимает произвольные це лые значения.

Рассмотрим следующее разложение примар ной группы. Пусть Ч циклическая подгруппа максимального порядка По теореме жа (см. теорему 7.3.1) = Х где = Ч факторгруппа по подгруппе Ясно, что =е и, значит, = Ч примарная группа, которая вновь допускает разложение на смежные классы по циклической с максимального порядка, т.е.

= Х Х = примарная груп конечного порядка следовательно, за конечное число т шагов получим разложение = Х Х...Х или | = Х Лемма 7.4.2. Пусть Ч примарная группа (подгруппа), А с Ч циклическая подгруппа максимального порядка | А \ с образующим элементом а, Ч факторгруппа, у е Ч класс смежности порядка | у \ т.е.

тогда существует элемент у е у того же порядка | у \ Доказательство. Так то для любого у е у выполня ется А, где А Ч единица факторгруппы Следователь, где = 1 и р п. Положим зующий элемент группы тогда = ] ) = =e или =е. Так как z Ч образующий элемент А, то _ Вследствие максимального порядка подгруп пы | А \ порядок | у \ Отсюда или а р. Теперь fl = можно в = = е. образом, элемент е у, порядок которого | \ 206 _ Глава 7. Введение в теорию групп. Приложения Х Теорема 7.4.3. Всякая конечная примарная группа (подгруппа) разложима в прямое произведение своих циклических под групп. = {х )х ), где Ч циклическая подгруппа поряд ка ) = и + +...

Доказательство Ч индукция по числу л. Для п = 1 теорема вер на, т.к. Ч ляется циклической и не содержит подгрупп. Предположим, что те орема верна для всех групп меньшего Пусть с Ч циклическая подгруппа максимального порядка Рассмот рим факторгруппу = Данная группа являет ся примарной порядка | \ т.к. \ \.

Предположение индукции позволяет записать для нее разложение = Обозначим через образующие циклических подгрупп. Лемма 7.4.2 утверждает, что существует е и | \ = \ | и можно положить = Из пря мого разложения факторгруппы что любой класс смеж ности х е можно представить в виде х = или х где 0 то произвольный элемент х е представим как х Х Таким образом, искомое прямое разложение на циклические подгруппы найдено.

Покажем, что представление ) единственно. Доказательство единственности Ч индукция по числу п. Для п = 1 имеем = Ч свойство выполняется.

Пусть оно верно для всех k < п. Покажем, что верно и для групп порядка Предположим существование другого разложения )х где.... Ясно, ЧТО Запишем разложение группы в уточненном виде и 7.5. Строение некоммутативных групп Рассмотрим группу (подгруппу) = \ х е Для этой группы справедливы разложения:

и (*) (**) Порядок | | < | | и, следовательно, по предположе нию индукции разложения (*) и (**) совпадают, т.е. = = = = а значит, = или т = /. Единст венность разложения доказана.

Пример. Пусть G Ч коммутативная группа порядка | G \ = 42.

Так как 42 = 2 Х 3 Х 7, то группа разложима в произведение следу ющих своих циклических подгрупп С(2) х С(3) х С(7).

Пример. Пусть коммутативная группа порядка | G \ = 4. Так как 4 = то группа разложима в произведение следующих своих циклических подгрупп G = С(4) или G = С(2) х С(2) и в явном виде G = = Ч циклическая или G = у, = = = = 7.5. Строение некоммутативных групп Х Пусть G Ч конечная группа. Подгруппа называется если порядок ее Х называется если порядок ее имеет максимальную степень в разложении порядка групп G.

Х Теоремы 7,5.1 Пусть G Ч конечная группа порядка = Ч простые числа.

Для каждого существует подгруппа группы G.

2. Всякая группы G содержится в некоторой си ловской подгруппе.

3. Все подгруппы сопряжены, т.е. если подгруппы, то существует такое t е G, что 4. Количество р Х где которое целое.

Пример. Пусть G Ч группа порядка \G \ = 28 = Х тогда су ществуют силовские подгруппы \ \ = 4 и 208 Глава 7. Введение в теорию групп. Приложения 7.6. Симметрическая группа подстановок Пусть S Ч конечное множество из т элементов. Множество всех взаимно однозначных отображений множества S на себя на зывается симметрической группой степени т. Без ограничения общности можно что множество S состоит из элементов Каждое такое отображение л : S называется под 1 или перестановкой и записывается л \ где Х-Х = Ч образ элемента = Произведением подстановок яв ляется композиция отображений (операция группы) = ст(я(/)).

имеем Например, для подстановок =( ] и стл =( Данный пример показывает, что сим метрическая группа не является абелевой (некоммутативная) при т 3. Порядок данной группы = Ч количество всех пе рестановок из т элементов. Единичная (тождественная) (\ новка обозначается е > которая удовлетворяет е = я. Обратной к i... т подстановка ХХХ I... -1 - л = которой верно, что ля я я е.

ХХХ Х Утверждение 7.6.1. Симметрическая группа степени 2 Ч абелева.

Х Определение. Подстановка я, перемещающая элементы что = = = и оставляющая на месте остальные элементы, называется циклом длины и обознача ется Х Равносильное определение. Подстановка называется цикличе ской, если каждый из ее действительно перемещаемых элемен тов можно перевести в любой другой (из действительно перемещаемых если подстановку применить доста точное число раз. Например, = = = = rc^Oi) = = Теперь цикл можно записать:

7.6. Симметрическая группа подстановок Пример. I 7 3 семь.

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

Например, (1, 2, 3, 5, 9) и (7, 8) Ч независимые циклы.

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

Пусть я е и i,j e S. Элементы назовем эквивалентными i~j, = для некоторого целого числа k.

Введенное отношение есть отношение эквивалентности на мно жестве S. Оно разбивает множество непересекающиеся клас сы по этому отношению Каждый элемент принадлежит одному и только одному клас су причем множество состоит из образов элемента при дей ствии степеней подстановки л: S, = где Ч количество элементов в Множества еще называют л-орбита ми. Выберем в каждом классе по одному представителю и по ставим ему в соответствие цикл Так как любой элемент, не принадлежащий остается на месте при действии степеней то перестановка л есть произведение независимых циклов л = Х Замечание 1. Если цикл = имеет длину то он действует как тождественная подстановка. Такие циклы в записи л = можно опускать.

Х Замечание 2. Независимые циклы в записи л = произвольным образом переставлять между собой. Так, л Определение. Декрементом подстановки называется раз ность между числом действительно перемещаемых элементов и числом независимых циклов, на которые она раскладывает ся. Подстановка называется четной, если d Ч четное число и подстановка нечетная, если d Ч нечетное. Введем функцию 210 Глава 7. Введение в теорию групп. Приложения +1, если я - четная подстановка, = если л -нечетная подстановка, где я е тогда = для подстановки I 5 4 6 ] (45) декремент равен 5 - 2 = 3, следовательно, подстановка нечетная.

Х Определение. Цикл длины 2 называется транспозицией т = Для транспозиции декремент = 1 = 1 Ч нечетное число.

Х Теорема При умножении подстановки л е на транспо зицию т = (ар) она меняет свою четность.

Пусть л = Ч разло жение подстановки в произведение независимых циклов. Умно жим ее на транспозицию т = Рассмотрим все возможные случаи:

1. a л, р л.

2. а е л, Р 3. а л, р е л.

4. а е л, р е л, а и р принадлежат одному и тому же циклу.

5. а Е л, р е л, а и р принадлежат разным циклам.

Пусть k Ч число действительно перемещаемых элементов л;

/ Ч число независимых циклов в разложении л. Декремент подста новки = k 1. Пусть а л, р тогда = Дек ремент = + 2) - (/+ 1) = /+ 1.

2. Пусть а е л, р я. Будем считать, что = а. В этом случае лт = = Декремент = Случай a р е л рассматривается подобно а е я, р г л.

4. Пусть аир принадлежат одному и тому же циклу.

Тогда лт = = Декремент = 5. Пусть принадлежат разным циклам. Тогда лт = = Декремент = 7.6. Симметрическая группа подстановок Таким образом, во всех случаях = = = четность подстановки меняется.

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

Доказательство. = разложение под становки в произведение независимых циклов. Каждый цикл разла гается в произведение транспозиций = Та ким способом можно разложить в произведение транспозиций все циклы подстановки = где Ч транспозиции. Теорема 7.6.2 позволяет записать = = = = Таким образом, четность подстановки - совпадает с четностью числа транспозиций в разложении л = Х Следствие 1. = т Ч произвольные под становки.

Пусть = и т = Ч разложения в произведение транспозиций tj. Тогда от = ложение в произведение транспозиций. Из теоремы = = = = Х Следствие 2. = ст"1 Ч обратная подстановка.

Доказательство. Пусть тогда = так как стст"1 = = = = е Ч тож дественная подстановка, где Ч транспозиции. Первое следст вие позволяет записать = С другой сто роны, ста'1 = е Ч тождественная подстановка и = 1. Тогда = 1 и, следовательно, = Х Теорема Число четных подстановок с равно числу нечетных.

Доказательство. Достаточно показать, что = так как = ml. Для этого установим взаимно однозначное соответствие между четными и нечетными подстановками.

Пусть т Ч произвольная фиксированная транспозиция. Рас смотрим отображение : где Пусть а е Ч произвольная четная подстановка, тогда = at Ч не четная подстановка.

212 _ Глава 7. Введение в теорию групп. Приложения Свойство 1. Для верно, что в про тивном случае = Отсюда, умножая справа последнее ра венство на т, получим = а так как тт = е, то = что противоречит выбору Свойство 2. Для любой нечетной подстановки b существует прообраз е четной подстановки, так как = = = Свойства 1, 2 позволяют утверждать, что отображение ф явля ется взаимно однозначным.

Х Утверждение Ч подгруппа симметрической группы Х Теорема Всякая конечная группа т изо морфна некоторой подгруппе симметрической группы Для любого элемента а е G рассмотрим ото бражение G G, состоящее в умножении всех элементов на а: = Свойство группы aG= G позволяет утверждать, что Ч взаимно однозначное отображе ние (подстановка). Обратным к будет отображение единичным отображением является Вследствие ассоциатив ности умножения в группе G имеем замкнутость: = = = = = т.е. = Отсюда следует, что множество Н = } образует подгруппу в множе стве всех взаимно однозначных себя, т.е. в сим метрической группе Тогда отображение ф : G такое, что = есть изоморфизм, поскольку ф Ч взаимно од нозначное и выполняется свойство = = = сохранения операций.

7.7. Действие на множестве Х Определение. Говорят, что задано действие группы множе стве если определен гомоморфизм Г группы G в симметрическую группу подстановок: G Свойст во сохранения операций для гомоморфизма: е G 1 2...

( \ Л Далее полагаем, что \ ХХХ 7.7. Действие групп на множестве Х Замечание. Чаще всего бывает так, что действие кает естественным образом, как группа симметрии структуры, определенной на S.

Пример. Пусть S = 2, 3, 4, 5} Ч вершины графа на рис. 7.1. Найти G Ч группу самосовмещений дан ного графа.

Решение. Исходное множество элементов ся связанным или структурой. Группа G, действую щая на S, Ч группа самосовмещений: G a, b, где 9 4 Ч тождественное преобразование;

={\ ? 11 = - поворот Таблица 7. 3 5 ab вокруг горизонтальной оси;

ab 3 2 4 поворот ab вертикальной оси;

ab = (23)(45) - поворот 1 3 2 вокруг горизонтальной оси и вертикальной. В табл. содержат ся все возможные произведения элементов рассматриваемой группы. Из табл. видно, что G Ч коммутативная группа и Х Определение. Элементы e S называются ми и записывают ~ если 3g e G, который, действуя на S, g или ХХХ ХХХ более короткая запись этого = Х Утверждение Определенная на мно жестве S является отношением эквивалентности.

Проверим свойства отношения эквивалент ности.

1. S ~ Действительно, = где e e G Ч единичный элемент.

2, G О Имеем ~ тогда s G = = а значит, ~ A 214 _ Глава 7. Введение в теорию групп. Приложения Имеем, что g e G = л откуда = = = = Следовательно, ~ Х Утверждение Группа действуя на мно жестве S, порождает его разбиение на непересекающиеся под множества Ч классы эквивалентности (рис. 7.2):

, где e Ч количество классов эквивалентности.

Пусть тогда класс эквивалентности Рис. 7. составят все различные элементы множества = Определение. Множество = e G \ e называ ется стабилизатором e S. Элементы стабилизатора оставля ют на месте.

Пример. Продолжим рассмотрение примера на рис. 7.1.

2, 3, 4, 5} Ч вершины графа на рис. 7.3. На действует группа самосовмещений a, b, где 2 3 4 5/ ~l 2 3 5 3 2 4 5 " 3 2 5 Найдем все классы эквивалентности.

Ml), = 1, 1, 1} = b(2), 2, 3, 3} = = 5, 4, 5} S = всего три класса эквивалентности.

Определим стабилизаторы для вершин 2, 3, Z(l) = а, Ъ, = ДЗ) = Д4) = Д5) = Х Утверждение с G Ч подгруппа группы G.

Доказательство. Проверим свойства группы.

1. Замкнутость. e = = тогда и fag^ = = = fe^i = следовательно, 2. Единичный элемент e так как = 3. Обратный элемент. Пусть e тогда = откуда следовательно, e 7.7. Действие групп на множестве _ Х Утверждение 7.7.4. e = = = Ч в этом случае говорят, что подгруппы сопряжены.

Имеем следовательно, = e = = или = Отсю да = = = = т.е. e ад. Полу чили, что e tgt Заметим, что значит, = или Подобным образом доказывается в обратную сторону:

следовательно, = Показали, что e e и = = отсюда Х Утверждение 7.7.5. \, где e Доказательство. Пусть G Из утверждения 7.7. следует, что однако среди выписанных эле ментов множества могут встречаться одинаковые. Назовем e G эквивалентными ~ если они действуют на эле мент одинаковым образом, т.е. Данное отношение является отношением эквивалентности. Введенная эквивалент ность разбивает группу G на классы, количество которых равно числу различных элементов среди выписанных т.е. равно Пусть или fe1^ )*i=?r21fe1^i) = fe2^: 1)5i следовательно, или Верно и обратное, если то Таким образом, ~ тогда и только тогда, когда, лежат в одном правом классе смежности по стабилизатору e а значит, и число элементов в равно количест ву правых смежных классов в подгруппе Согласно тео реме \ = - Z(s 216 Глава 7. Введение в теорию групп. Приложения Х Лемма Бернсайда. Число классов эквивалентности, на которые распадается множество S = под дей G, = = Подсчитаем двумя различными способами множество всех таких пар элементов, что е G е S Это можно выполнить следующим образом:

Первая сумма Так как, то Таким образом, = Получили, что откуда Пример. Продолжим рассмотрение примера на рис. 7.3. S = 2, 3, 4, 5} Ч вершины графа. На действует группа самосовмеще fl ний a, b, ab}, =[i V X J 2 3 2 5 4/ Полным перебором установили, под действием множест во распадается на три класса эквивалентности: S где Установим данный факт, Бернсайда: Ч число классов валентности.

= = 2, 3, 4, = = {l, 7.8. Цикловой индекс группы _ Отсюда следует, что число классов эквивалентности = =3.

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

7.8. Цикловой индекс группы Пусть группа G действует на множестве и G Ч гомоморфизм в симметрическую группу Рас смотрим разложение g e G на независимые циклы где Ч количество циклов длины Ч количество циклов длины 2;

Ч количество циклов длины т.

Набор называется характеристикой элемента g G, где fcj + 2 Х +... + т Х - т.

Х Определение. Цикловым индексом Z(G, группы G, действующей на множестве S, называется полином от пере менных определяемый формулой где Ч характеристика элемента g Пример. Продолжим рассмотрение примера на рис. 7.3. S 2, 4, 5} Ч вершины графа. На группа самосовмеще ний а, Ъ, (\ 2 3 4 тт, аЪ = 5 4 Цикловой индекс группы l 32 G, для этого выполним разложение на независимые циклы под становок элементов G и установим их характеристики:

Глава 7. Введение в теорию групп. Приложения е = (1)(2)(3)(4)(5), (5, О, О, О, О);

а = = (3, О, О);

Ъ = (1)(23)(4)(5), О, О, О);

= (1)(23)(45), = (1, 2, О).

+ 7.9. Теория перечисления Введем следующие обозначения.

Ч конечное множество.

ftj--} Ч конечная группа, действующая на D.

R = Ч конечное множество качественных признаков (цвета).

D Ч множество функций;

каждая функция/опре деляет качественные признаки элементов D.

= Ч множество весов.

: R Ч весовая функция, назначает веса признакам = Ч сумма весов элементов или где Ч число элементов с весом е множество Ч перечень относительно весовой функции Рассмотрим введенные понятия на следующем примере, к ко торому ниже не раз будем возвращаться.

Пусть Ч вершины ного треугольника (рис. 7.4). Треугольник нанизан на вертикальную ось, вокруг кото рой он свободно вращается. = Ч мно жество из двух красок. Найти количество различных раскрасок вершин треугольни Рис. 7. 7.9. Теория перечисления На D действует группа самосовмещений {e, а, где тождественное совмещение, а поворот во круг оси на 120, = Ч поворот на 240.

= {х, у, и их множество весов.

= D Ч множество раскрасок. В треугольнике три вер шины и каждую допускается в любой из двух цветов = следовательно, всего функций Такое количество рас красок будет, если треугольник сделать неподвижным (рис. 7.4).

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

что для решаемой задачи совпада ют.

Назначим краскам R = {Х, веса:

-х и =у.

Х Замечание. Отметим, что назначенные веса элементов =х и =у позволяют сравнивать признаки количественно, за бывая, в степени, о качественном их содержании.

Х Определение. Для каждой функции определим вес В нашем примере = у, Определение. Группа G, действуя на D, индуцирует (наводит, создает, определяет) свое действие на множество функций S.

Положим это рассматривается 220 _ Глава 7. Введение в теорию групп. Приложения В нашем примере рассмотрим действие элемента а G на S.

= и /) , Таким образом, элемент группы а или, в при нятых обозначениях, Х Определение. если Такие и определяют одинаковые раскраски элементов Введенная эквивалентность функций есть от ношение эквивалентности, которое порождает разбиение множества элементов/е непере секающиеся классы эквивалентности (рис. 7.5):

Рис. 7. количество классов эквивалентности. Каждый класс эквивалентности определяет отдельную рас краску элементов e D. Таким образом, количество различных раскрасок равно Для определения воспользуемся леммой 7.7.1 N в данном случае Вернемся к нашему примеру на рис. 7.4 и найдем для него чис ло = S\ удовлетворяют S, откуда = = 8. = Ч это такие раскраски/вершин, ко торые допускают совмещение с эквивалентной из раскрасок вра щением треугольника на 120. Это возможно, если все вершины либо белые, либо черные. Итак, = 2. Подобным образом устанавливается, что и = 2. Следовательно, Х Утверждение 7.9.1. то = т.е. эквива лентные функции имеют одинаковые веса.

D = и D - Ч вер но e G, так как G действует на D и g j Ч это 7.9. Теория перечисления Теперь = Имеем тогда G Отсюда Определение. Последнее утверждение позволяет определить вес каждого класса эквивалентности в разложении S, как = где / e Определение кор ректно, так как каждый класс состоит из эквивалентных веса которых совпадают.

Теорема Пойа. Х = где число классов эквивалентности S = с ве сом e ) Ч цикловой индекс группы G, действующей на множестве Отметим, что гаеП Доказательство. Пусть разбиение множества D на непе ресекающиеся подмножества:

где | = \D | = m, 1 Х + 2 Х +... + т Х = Х Определение. Говорят, разбиению мно жества D и Д, на каждом под множестве Dy из разбиения: yd e = где e R.

Функция/, подчиненная разбиению Д, взаимно однозначно определяется набором ), где Все такие наборы составляют множество:

где - R, i = j = Полагая веса элементов e равны ми = ) 6 S 2 2 2 Г л а в а 7. Введение в теорию групп. Приложения равным произведению весов имеем = А подчинена разбиению.

Для множества выполнены все условия правила обобщенно го произведения, тогда сумма весов элементов данного множест ва, а значит, и сумма весов всех А составит ' т = вследствие ) = Следовательно, s или g = разложение на независимые циклы, где Ч 1 Х + 2 Х +... + т Х = т. Запишем разложение на независимые циклы в виде g где Ч цикл длины /', = Обозначим разбиение множества D на Dy через Элементы d e Dy одного цикла при умножении на g переходят последовате льно по циклу в элементы того же цикла. Указанное свойство по зволяет заключить, что e Dy 3k = Пример. Пусть g = (12345)(678), тогда (13524)(687).

Х Определение. называется неподвижной относи тельно g если e D Х Утверждение 7.9.2. Функция неподвижна относительно g e и только тогда, подчинена разбиению Доказательство. Пусть Dy Ч принадлежат одному циклу. Следовательно, = = = ХХХ > где каждый переход 7.10. Цикловая структура групп подстановок _ обусловлен Таким обра e Пусть тогда и gd e Ч свойство циклов. Имеем /e или e следовательно, тогда /есть неподвижная относительно e G.

Запишем сумму весов/ подчиненных разбиению в следую щем виде = количество функций, fflsQ подчиненных разбиению с весом Составим множество всех функций, неподвижных относите e с весом ш = = Утверждение 7.9.2 позволяет записать - Величина Ч число классов эквивалентности с весом на которые распадается множество функций S под дейст вием группы G. По лемме = = = Умножив последнее равенство на со и вав по всем весам из получим, что = Сумма Ч сумма весов функций, подчи разбиению Так как, то 7.10. Цикловая структура групп подстановок Рассмотрим несколько общих примеров, которые в какой-то степени дают представление о возможностях изложенной выше техники подсчета классов эквивалентности с использованием те ории перечисления Пойа.

224 Глава 7. Введение в теорию групп. Приложения Цикловой индекс группы, действующей на себе Пусть группа G действует на множестве G следующим об разом : е G е S = gs. Если порядок элемента | g | = то все элементы s различны. Группа G распадается под действием g на циклы одинаковой длины. Количество циклов равно где = Ч порядок группы. Цикловой индекс груп пы примет вид (7.10.1) где Ч количество элементов g е G с порядком | g | = d. Сумми рование выполняется по всем делителям d числа п.

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