XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 56
Текст из файла (страница 56)
Очевидно, что группа автоморфизмов графа есть подгруппа группы перестановок множества его вершин. Поэтому, согласно теореме 2.13 Лагранжа, порядок еруппы автоморфизмов графа есть делитель факториала числа его вершин. В частности, для графа на рис. 5.35, а группа автоморфизмов имеет порядок 4 и состоит из тождественной подстановки с и подстановок (1 4), (2 3), (1 4)(2 3). Очевидно, что 4! делится на 4. Можно доказать, что автоморфизмы неориентированного графа сохраняют сшепеии, а ориентированого графа— полустепени исхода и захода всех его вершин. Это свойство позволяет упростить описание автоморфизмов графа. 348 б.
ТЕОРИЯ ГРАФОВ Итак, для любого автоморфизма Ь этого графа Це~) = е~. Поскольку е~ ~-~ею то Це~) «-~Ь(еэ), и, следовательно, поскольку еэ — единственная вершина, смежная с ем всегда Ь(ез) = ею т.е. вершина ез переходит в себя. Таким образом, единственным нетривиальным автоморфизмом данного графа будет транс- позиция (3 5) — „отражение" квадрата езезе4ез относительно диагонали эзе4. ф Иногда группу автоморфизмов графа легко найти именно из чисто геометрических соображений при удачном изображении графа.
Автоморфизм есть не что иное, как преобразование графа (геометрической фигуры), при котором граф совмещается с самим собой. Поэтому группу автоморфизмов графа можно изучать, анализируя его как геометрическую фигуру. Пример 5.14. Дая графа, изображенного на рис. 5.37, из геометрических соображений вытекает, что автоморфизм ~р сводится к повороту графа на 60' по часовой стрелке вокруг центра тяжести треугольника е~езез.
Рис. Ь.ЗТ Следовательно, группа автоморфизмов порождаетсл подстановкой ~р, являющейся композицией трех циклов: у = (1 2 3)(4 6 8)(5 7 9). Заметим, что ни один цикл, входящий в ~р, сам по себе не будет автоморфизмом данного графа. Так, если мы рассмотрим цикл Ь = (1 2 3), то Ь(3) = 1, Ь(4) = 4, и ЦЗ) ~ Ь(4), но ез ~д и4. Ф 349 5.8. лопологическал сортировка В заключение сформулируем без доказательства теорему, доказанную Фрухтом в 1938 г. и характеризующую все конечные группы в терминах групп автоморфизмов конечных неориентированных графов. Теорема 5.5 (теорема Фрукта).
Каждая конечная группа изоморфна группе автоморфиэмов конечного неориентированного графа. 5.8. 'Гопологическаи сортировка Определение 5.1 т. Ориентпиров анной ветвью (иди просто сетпью) называют беснонтурный ориентированный граф '. Поскольку сеть является бесконтурным графом, можно показать, что существуют вертаины (узлы) сети с нулевой полусптепенью исхода, а также вершины (узяы) с нулевой полустпепенью захода. Первые называют спьонами или выходами сепзи, а вторые — истпочниками или входами сепьи.
Определение 5.18. уровень верилины сети — это натуральное число, определяемое следующим образом: 1) если полустепень захода вершины равна О, то ее уровень равен О и наоборот (т.е. нулевой уровень )то — это множество всех входов); 2) если множества т у; вершин уровня т определены дяя всех т ( Й, то уровень 5)а+1 содержит те и только те вершины, предшесшввнники которых принадлежат любому из уровней с номером от О до к, причем существует хотя бы один предшественник уровня Й, т.е.
Же+1 = (е: Г ~(и) С Фт 0... т.) йта, Г ~ (и) П )та ф а), 'В некоторых задачах встречаютсл бесконтурные ориентированные графы, вмеющне бескокечвые множества вершин и дуг. 'Хакие графы называют бесконечными сетлмк. Мы рассматриваем только конечные сети. Кроме того, в литературе по теории графов терман „сеть" иногда используетсл в вном смысле — дла обьекта, более сложного, чем граф (смл Яблонский С.В.). 350 б. ТЕОРИЯ ГРАФОВ где Г 1(п) = 1я: я -+ е) — множество предшественников верши- ны 9. Уровень вершины сети можно интерпретировать как длину максимального пугни от входов сети до этой вершины. Определение 5.19. ллорядковой функцией сети С = = (У, Е) называют отображение огй: К вЂ” ~ М, сопоставляющее каждой вершине сети номер ее уровня.
Во многих прикладных задачах возникает проблема такого упорядочения вершин сети, при котором вершины, принадлежащие одному уровню, располагаются друг под другом, а дуги ориентированного графа ведут в его иэображении на плоскости от вершин с меньшим уровнем к вершинам с большим уровням слева направо. Подобного рода проблема называется проблемой тпонолоеинеской сортировки, поскольку необходимо расположить вершины графа на плоскости так, чтобы отчетливо было видно распределение вершин по уровням. Само расположение при этом может быть разным, лишь бы оно имело „слоистую" структуру, в которой каждый слой составляют вершины одного уровня.
На рис. 5.38 показаны сеть и результат применения топологической сортировки сети. Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Формально топологическую сортировку можно реализовать по-разному. Мы опишем один вз возможных методов'.
Этот метод состоит в вычислении порядковой функции сети и известен как алеоритпле Делеукроно. Предполагается, что вершины сети пронумерованы от 1 до н. 'Другие методы топологической сортировки смс Кнуте Д.; Верта Я. Зб1 о.В. 'Ховологичесаав сортировиа Он ов в10 Рис. 5.38 Наглядно процесс определения уровней вершин можно представить следующим образом.
Нулевой уровень образуют входы сети — вершины с полусшепенью захода, равной О. Удалив из сети все вершины нулевого уровня и исходящие из них дуги, вновь получим сеть, входами которой будут вершины первого уровня исходной сети. Указанный процесс „послойного" удале- 352 5. ТЕОРИЯ ГРАФОВ ния вершин следует продолжать до т~с пор, пока все вершины исходной сети не будут распределены по уровням. Алгоритм Демукрона использует матрицу смежкосщи вершин В типа п х п в качестве средства представления сети и основан непосредственно на определении уровня вершины и свойствах матрицы В. Можно увидеть, что сумма элементов й-го столбца матрицы В равна полустепени захода вершины еь. Поэтому, просуммировав элементы матрицы по всем столбцам и выбрав вершины, соответствующие столбцам с нулевой суммой, получим множество вершин нулевого уровня — входы сети. Безусловно, „физически" удалять вершины и дуги из сети и вычеркивать из матрицы В строки, соответствующие удаляемым вершинам, нет необходимости.
Процесс вычисления порядковой функции можно организовать следующим образом. Запишем суммы элементов столбцов матрицы В в вектор М длины и. При этом элемент оЫ, вектора М будет содержать полустепень захода вершины еь. Пусть из сети удалены вершина еч и все исходящие из нее дуги. Заметим, что элемент Ьл, равен 1, если из вершины е; идет дуга в вершину еь, и равен О в противном случае. Поэтому, чтобы получить новую полустепень захода вершины еь, необходимо из элемента тпь вектора М вычесть элемент 61и матрицы В. Чтобы пересчитать полустепени захода всех вершин сети, оставшихся в ней после удаления вершины е;, надо из вектора М вычесть 1-ю строку матрицы В.
Если на очередном шаге входами сети являются вершины е;„..., е;„, то для определения следующего „слоя" вершин нужно из вектора М вычесть строки матрицы В с номерами 11, ..., 1„и зафиксировать новые нулевые элементы вектора М, появившиеся после вычитания. Фиксировать следует именно новые нулевые элементы, поскольку элементы вектора М, соответствующие вершинам, лежащим на предыдущих уровнях, стали равными О на предыдущих шагах алгоритма.
353 5.В. Топологическал сортировка Заметим, что порядковую функцию сети можно задать, указав множества вершин, принадлежащих каждому уровню, или сопоставив каждой вершине ее номер уровня. Первый способ более удобен при теоретических рассуждениях, второй — при вычислениях. Алгоритм Демукрона вычисления порядковой функции сети Алгоритм обрабатывает матрицу В смежности вершин графа порядка и. В результате работы алгоритма получаем массив Огй длины п, 1-й элемент которого равен номеру уровня вершины е;. О. Сформировать множество У~ вершин сети. Значение счетчика уровней й положить равным О.
Найти суммы элементов по всем столбцам матрицы В (полустепени захода вершин) и заполнить ими массив М. 1. Если множество У~ не пусто, перейти на шаг 2, если иначе, то перейти на шаг 3. 2. Определить множество 1 номеров всех новых нулевых элементов массива М, т.е. таких, что соответствующие этим номерам вершины принадлежат множеству Уг Присвоить элементам массива Оп1 с номерами из множества 1 номер уровня Й и удалить вершины с этими номерами нз множества У~ („замаскировать" вершины). Вычесть из массива М строки матрицы В, соответствующие вершинам с номерами из множества 1 (т.е. вершинам последнего вычисленного уровня). Увеличить счетчик уровней на 1 (й = й+ 1). Вернуться на шаг 1.
3. Закончить работу. Пример 5.15. Применим алгоритм Демукрона к сети, представленной на рис. 5.38. Матрица смежности вершин сети 5. ТЕОРИЯ ГРАФОВ имеет следующий вид: Приведем последовательность значений массива М, соответствующую итерациям алгоритма и множества Ф; вершин 1-го уровня. Прочерки соответствуют вершинам, не принадлежащим множеству У1 („ замаскированные" вершины) на соответствующем этапе алгоритма. Алгоритм Демукрона может быть модифицирован так, чтобы он останавливался, если ориентированный граф, поданный на вход, не является сетью, и сообщал об этом.
Можно увидеть, 5.8. 'Толологвчееввя сортировка что анализируемый граф не будет сетью тогда и только тогда, когда при очередном перевычислении массива М не появятся новые нули. В заключение рассмотрим вопрос о связи понятий ориентированной сети и упорядоченного множестпеа. Так как сеть есть бесконтурный граф, то ошкошение досшижимосшк в нем будет отношением порядка. Действительно, пусть для двух отличных друг от друга вершин к, о сети вершина к достижима из вершины о (о ~' к) и вершина о достижима из вершины и (и =«' о).
Тогда существует путь ненулевой длины из о в к (о =«+ к) и нз и в е (и=«+ о). Отсюда вытекает, что существует путь ненулевой длины из к в к (и =«+ к) и из о в о (и =«+ о). Следовательно, существует кокшур, связывающий вершины и и о, что невозможно. Обратно, пусть (А, <) — конечное упорядоченное множество. Сопоставим ему ориентированный граф 6' = (Р; Е) так, что множество вершин У находится с А во взаимно однозначном соответствии, а множество дуг определяется следующим образом: и -+ о тогда и только тогда, когда о домикируеш над и в смысле порядка <.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
