существенную помощь. Во-первых, если s(G)≠s(G'), то отсюда сразу следует неизоморфность графов G и G'. Во-вторых, если s(G)=s(G'), то для проверки графов G и G' на изоморфизм требуется перебор не всех n! соответствий между вершинами, а лишь тех, при которых сопоставляются вершины одинаковой степени.
Рис. 6.44
Однако имеются случаи, когда при выяснении изоморфизма графов их векторы степеней практически бесполезны: речь идет об регулярных (однородных) графах, в которых степень всех вершин одна и та же. Например, граф, степени всех вершин которого равны трем (рис. 6.45).
|
1 |
6 |
|
2 |
5 |
Рис. 6.45 |
3 |
4 |
|
|
Противоположный случай представляют графы, определяемые однозначно с точностью до изоморфизма своим вектором степеней (или, что равносильно, его обращением) и называемые униграфа-
ми.
6.8.3. Гомеоморфизм графов
Два графа гомеоморфны (или тождественны с точностью до вершин степени 2), если они оба могут быть получены из одного и того же графа «включением» в его ребра новых вершин степени 2. Если ребро графа изображено в виде линии, то можно на ней по-
199
ставить точку и считать ее новой вершиной степени 2. Формально эта операция определяется следующим образом.
Пусть G – любой граф и (a,b) – его ребро. Операцией подразделения ребра (a,b) называется удаление из графа G ребра (a,b), добавление новой вершины c и добавление двух новых ребер (a,c) и (c,b).
Граф G1 называется подразделением графа G, если G1 может быть получен из G несколькими подразделениями ребер.
Графы G1 и G2 называются гомеоморфными, если существуют их подразделения, которые изоморфны.
Изображенные на рис. 6.46 графы гомеомофны, и то же самое можно сказать о любых двух циклических графах.
Рис. 6.46
6.8.4. Автоморфизм графов
Автоморфизмом графа G называется изоморфизм графа G на себя, при этом всякий граф G имеет тождественный (или тривиальный) автоморфизм I, такой, что I(x)=x для каждого ребра x и каждой вершины x из G.
Автоморфизм графа есть отображение множества вершин на себя, сохраняющее смежность. Множество таких автоморфизмов, обозначаемое Γ(G), образует группу, называемую группой графа G, или группой автоморфизмов графа G. Таким образом, элементы группы Γ(G) являются подстановками, действующими на множестве вершин графа.
На рис. 6.47 представлен исходный граф и его автоморфизм.
200
v1 |
v4 |
v4 |
v1 |
v2 v3 v3 v2
Рис. 6.47 |
a |
б |
|
|
Для подстановки в теории графов принята запись
1 |
2 |
... |
n |
|
||
|
ϕ |
ϕ |
|
... ϕ |
|
, |
|
2 |
|
|
|||
|
1 |
|
|
n |
|
|
|
|
|
|
|
|
|
где φ1, φ2,..., φn – те же числа 1, 2,..., n, но записанные, возможно, в каком-либо ином порядке.
Таким образом, вторая строка подстановки образует перестановку φ1, φ2,..., φn из чисел 1, 2,..., n. Различных подстановок вообще из n элементов существует столько же, сколько и перестановок, т.е. n! = 1×2×3×...×n. Однако при построении автоморфизмов требуется сохранение степеней вершин и смежности между ними, что в большинстве случаев существенно сокращает их количество.
Наибольшее количество автоморфизмов в группе автоморфизмов существует у полных и пустых графов – их на n вершинах в обоих случаях будет n!.
Подстановка, оставляющая на месте все элементы, называется
начальной (единичной, тождественной).
1 |
2 |
... |
n |
|
|
I = |
|
|
|
|
, |
|
2 |
... |
n |
|
|
1 |
|
|
|||
|
|
|
|
|
|
Еe краткая запись α0=(1)(2)...(n).
Для каждой подстановки А существует обратная, т. е. такая, которая переводит φi в i, она обозначается через А-1. Например:
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
|
|
|
|
, |
A = |
3 |
2 |
5 |
1 |
4 |
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
201
|
|
3 2 5 1 4 |
1 2 3 4 5 |
|
||
A |
−1 |
|
|
|
|
|
|
= |
|
= |
4 2 1 5 3 |
. |
|
|
|
1 2 3 4 5 |
|
|
||
|
|
|
|
|
|
|
Результат последовательного применения двух подстановок А и
Вснова будет некоторой подстановкой С: если А переводит i в φi, а
Впереводит φi в ψi, то С переводит i в ψi. Подстановка С называется произведением подстановок А и В, что записывается так: С = АВ. Например, если
1 2 3 4 5 |
|
|
|
|
1 2 3 4 5 |
|
|
||||
|
|
|
, |
B = |
|
|
|
|
|
, |
|
A = |
3 2 5 1 4 |
|
|
2 5 4 1 3 |
|
||||||
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
то |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
|
4 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
C = AB = |
4 |
5 |
3 |
2 |
1 |
. |
|
|
||
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
При умножении подстановок не выполняется закон коммутативности, т.е., вообще говоря, АВ ≠ ВА, как в том же примере
1 2 3 4 5
BA = .
2 4 1 3 5
Легко видеть, что IA = AI = А, АА-1= А-1А = I, А(ВС) = (АВ)С (ассоциативный закон).
Подстановка, переставляющая местами только два элемента i и j, называется транспозицией:
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
|
|
= (2, 4) . |
|
4 |
3 |
2 |
5 |
|
|
1 |
|
|
||||
|
|
|
|
|
|
|
Подстановка, циклически переставляющая данную группу элементов, а остальные элементы оставляющая на месте, называется циклом. Число переставляемых элементов называют длиной цикла. Например, подстановка А есть цикл длины 4: она переводит 1 в
202
3, 3 в 5, 5 в 4, 4 в 1, при этом 2 остается на своем месте. Коротко это записывается так:
А = (1, 3, 5, 4)(2). |
|
|
Рассмотрим граф G, изображенный на рис. |
1 |
4 |
6.48. |
||
Его четыре вершины составляют множество |
|
|
X целых чисел 1, 2, 3, 4. Заметим, что следую- |
|
|
щий список подстановок: |
2 |
3 |
|
α0 = (1)(2)(3)(4), |
α1 = (1)(3)(2,4), |
||
α2 = (1,3)(2)(4), |
α3 = (1,3)(2,4) |
|
Рис. 6.48 |
включает все подстановки множества X, сохра- |
|
||
|
|
||
няющие отношение смежности в графе G. Например, вершины 1 и 4 смежны в G. Подстановка (1,3)(2)(4) преобразует вершины 1 и 4 в вершины 3 и 4, и эти образы 3 и 4, также являются смежными. Таким образом, подстановка (1,3)(2)(4) сохраняет смежность вершин
1 и 4.
В случае если в короткой записи присутствуют только циклы длиной 2, обратная подстановка строится всегда очень просто, так как совпадает с исходной, например, для α1 обратной является α1-1 = =(1)(3)(2,4), а для α3 = (1,3)(2,4) обратной является α3-1 = (1,3)(2,4).
На практике, если граф задан своим изображением, поиск всех автоморфизмов практически осуществляется путем поиска возможных поворотов графа или его «частей» вокруг осей симметрии.
Задача 6.15. Найти группу автоморфизмов данного графа (рис. 6.49) и для каждой подстановки привести обратную.
2 |
3 |
1 |
4 |
6 |
5 |
Рис. 6.49 |
|
Решение. В данном графе просматривается несколько условных осей симметрии, относительно которых можно поворачивать граф.
Начальная подстановка:
α0=(1)(2)(3)(4)(5)(6).
203
Если перевернуть граф относительно горизонтальной оси, получим подстановку (рис.6.50):
α1=(1)(2,6)(3,5)(4).
6 |
5 |
1 |
4 |
2 |
3 |
Рис. 6.50
Если перевернуть граф относительно вертикальной оси, получим подстановку (рис.6.51):
α2=(2,3)(6,5)(1,4).
3 |
2 |
4 |
1 |
5 |
6 |
Рис. 6.51
Если сделать эти повороты по очереди, то получим четвертую и последнюю в данном случае подстановку (рис.6.52):
α3=(1,4)(2,5)(3,6).
5 |
6 |
4 |
1 |
3 |
2 |
|
Рис. 6.52 |
204
Задача 6.16. Найти все графы, группа подстановок которых содержит подстановку (v1,v2,v3,v4,v5).
Решение. Такого рода задачи решаются переборным методом, причем перебор удобнее всего осуществлять по степеням вершин.
Поскольку, как видно из данной подстановки, в графе пять вершин, максимальная степень вершины равна 4, минимальная в случае пустого графа равна 0. Кроме того, поскольку в цикле участвуют все пять вершин, это значит, что у всех вершин степени одинаковые. Переберем все степени от 0 до 4.
Пусть степень всех вершин равна 0. Эта ситуация наблюдается в пустом графе на пяти вершинах, и он нам по своим свойствам подходит. Итак, первый найденный граф – P5 (отметим, что конкретная нумерация вершин в данном случае не важна).
Пусть степень всех вершин равна 1. Значит, суммарная степень вершин графа равна 5, это число нечетное, следовательно, такого графа не существует.
Пусть степень всех вершин равна 2. Эта ситуация наблюдается в простом цикле на пяти вершинах, по своим свойствам он нам подходит, только важно правильно пронумеровать вершины. Графически можно изобразить найденное решение в виде кольца (рис. 6.53, а) или звезды (рис. 6.53, б). Оба решения эквивалентны.
Обратите внимание на нумерацию вершин: она должна позволять осуществлять переход 1→2→3→4→5→1. Например, вершины в звезде можно было пронумеровать иначе (рис 6.53, в), но ни в коем случае нельзя нарушать циклический порядок (рис. 6.53, г). В последнем случае перестановка (1,2,3,4,5) нарушит смежность вершин (рис. 6.53, д): в исходном графе вершина v1 была смежна с v4 и v5, а после такой перестановки станет смежна с v2 и v3. Итак, второй найденный граф – простой цикл на 5 вершинах (с правильной нумерацией вершин).
Пусть степень всех вершин равна 3. Значит, суммарная степень вершин графа равна 15, следовательно, такого графа не существует.
Пусть степень всех вершин равна 4. Эта ситуация наблюдается в полном графе на пяти вершинах, и он нам по своим свойствам подходит (отметим, что нумерация вершин в данном случае не важна). Следовательно, найдено три возможных графа: P5, Ц5, K5.
205