Книги по разным темам Pages:     | 1 |   ...   | 6 | 7 | 8 | 9 | 10 |   ...   | 49 |

Д о к а з а т е л ь с т в о. Если p1 = p2 p, то образ отображения (p1) содержится в образе отображения (p2), т. е. H1 H2. Предположим те перь, что H1 H2. Пусть 1 X1 - произвольная точка, 1 - путь из x - - в y, = p11 - проекция пути 1. Положим p(1) = 2, где 2 - конец - - поднятия пути с началом x. Отображение p корректно определено тогда и только тогда, когда выполняется следующее условие: если путь 1 замкнут, то путь 2 тоже замкнут. Это означает, что если класс пет 54 Глава I. Графы ли лежит в H1, то он лежит и в H2. Это условие выполнено, поэтому отображение p определено корректно.

С л е д с т в и е. Если H1 = H2, то 1-мерные комплексы X1 и Xгомеоморфны.

Д о к а з а т е л ь с т в о. Прообраз любой точки при отображении p находится во взаимно однозначном соответствии с множеством смежных классов H2 H1. Если H1 = H2, то отображение p взаимно однозначно.

/ Если H1 = 0, то пространство X1 накрывает любое пространство, накрывающее X. По этой причине накрывающее пространство с тривиальной фундаментальной группой называют универсальным; в таком слу чае накрытие p : X1 X тоже называют универсальным. Для 1-мерного комплекса универсальное накрывающее пространство является деревом. Универсальное накрывающее пространство существует для любого 1-мерного комплекса; оно определено однозначно с точностью до гомеоморфизма.

Пусть R = {r1,..., rm} - некоторое множество элементов свободной - группы Fn с образующими a1,..., an; N - наименьшая нормальная под - группа, содержащая R, т. е. пересечение всех нормальных подгрупп, содержащих R. Тогда группу G = Fn N называют группой, заданной об/ разующими a1,..., an и соотношениями r1,..., rm.

Т е о р е м а 2.11. Пусть G - группа, заданная n образующими - и m соотношениями. Тогда существует регулярное накрытие букета n окружностей с группой автоморфизмов, изоморфной G.

Д о к а з а т е л ь с т в о. Фундаментальная группа букета n окружностей изоморфна свободной группе Fn. Согласно теореме 2.9 для подгруппы N Fn существует накрытие, для которого образ фундаментальной группы накрывающего пространства в фундаментальной группе базы совпадает с N. Подгруппа N нормальна, поэтому накрытие регулярно. Для регулярного накрытия группа автоморфизмов изоморфна Fn N = G.

/ З а д а ч а 2.5. Постройте регулярные накрытия букета двух окружностей со следующими группами автоморфизмов: а) Z; б) Zn; в) Z Z;

г) Z2 Z3.

С помощью накрытий 1-мерных комплексов можно доказывать разные свойства свободных групп. Приведем несколько таких примеров.

З а д а ч а 2.6. а) Докажите, что любая подгруппа свободной группы G свободна.

б) Докажите, что если H - подгруппа свободной группы G и индекс - [G : H] = k <, то rk H = (rk G - 1)k + 1.

З а д а ч а 2.7. Докажите, что свободная группа ранга 2 содержит в качестве подгруппы свободную группу любого ранга n (в том числе и ранга ).

з 2. Гомотопические свойства графов Универсальное накрытие графа G (у которого могут быть двойные рёбра и петли) удобно строить с помощью матрицы R(G), которая определяется следующим образом. Начнём с того, что разобьём вершины графа G на множества V1,..., Vn так, чтобы из любой вершины v Vi выходило одно и то же число рёбер (своё для каждого j = 1,..., n), ведущих в вершины множества Vj (мы предполагаем, что петля с вершиной v Vi соответствует двум рёбрам, ведущим из v в вершины множества Vi). Такое разбиение можно построить следующим образом. На первом шаге разо бьём вершины на множества V1,..., Vk, объединив в одно множество все вершины одинаковой степени. На втором шаге измельчим это разбиение, объединив в одно множество все вершины множества Vi, из которых выходит одно и то же число рёбер, ведущих в вершины множества Vj.

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

По определению матрица R(G) имеет размер n n; её элемент rij равен числу рёбер, ведущих из вершины v Vi в вершины множества Vj.

П р и м е р. Для графа, изображённого на рис. 34, на первом шаге получаем два множества вершин, а на втором шаге получаем три множе 0 0 ства вершин. Для этого графа R(G) = 3 1.

4 2 Т е о р е м а 2.12. а) Пусть граф G накрывает граф G. Тогда R(G) = R(G); здесь имеется в виду, что матрицы совпадают после изменения нумерации множеств, на которые разбиты вершины.

б) Универсальное накрывающее пространство графа G однозначно задаётся матрицей R(G).

Д о к а з а т е л ь с т в о. а) Множества V1,..., Vn образуют требуе мое разбиение вершин графа G тогда и только тогда, когда множества V1 = p(V1),..., Vn = p(Vn) образуют требуемое разбиение вершин гра фа G (здесь p : G G - накрытие).

- б) Легко проверить, что связный граф, у которого нет циклов, однозначно задаётся матрицей R(G).

Рис. 34. Вычисление матрицы R(G) 56 Глава I. Графы С помощью теоремы 2.12 можно доказать следующее утверждение.

Т е о р е м а 2.13 (см. [86]). Пусть конечные связные графы G и G имеют общее универсальное накрытие. Тогда они имеют конечное общее накрытие, т. е. существует конечный граф H, накрывающий оба графа G и G.

Д о к а з а т е л ь с т в о. Согласно теореме 2.12 R(G) = R(G ) = R = = (rij). Пусть V1,..., V и V1,..., V - соответствующие разбиения - вершин графов G и G. Для удобства мы заменим графы G и G на ориентированные графы, заменив каждое ребро на пару противоположно направленных рёбер, а каждую петлю на пару ориентированных петель.

Пусть ni = |Vi| - число вершин типа i, mij - число рёбер типа i j - - в графе G. Определим число s как наименьшее общее кратное чисел mij для всех i, j. Положим ai = s ni и bij = s mij (если mij = 0, то число bij / / не определено). Непосредственно из определения видно, что mij = nirij и числа ai и bij целые. Ясно также, что mij = mji, а потому bij = bji.

Важнейшее свойство чисел ai и bij заключается в том, что они полностью определяются матрицей R, т. е. для графов G и G они одинаковы. Чтобы доказать это свойство, проверим сначала, что число fi = ni n1 зависит только от матрицы R. Действительно, если ri1 = 0, / mi1 ri1 r1i / то fi = =, поскольку mi1 = m1i. Может, конечно, оказаться, m1i r1i ri/ что ri1 = 0. Но в любом случае найдётся такая последовательность чисел 1 = j1, j2,..., jh = i, что rj jl+1 = 0 при l = 1, 2,..., hi - 1 (это следует i l hi - из связности графа G). Тогда fi = rj jl+1 rj jl. Числа ai и bij / l l+l=можно теперь вычислить, исходя из следующих соотношений:

a1 = n-1НОК(mij) = n-1НОК(nirij) = n-1НОК(fin1rij) = НОК(firij), 1 1 ai = s ni = a1n1 ni = a1 fi, bij = ai rij.

/ / / / Занумеруем рёбра типа i j, выходящие из вершины v Vi, числами от 0 до rij - 1; пусть g(v, e) - номер ребра e при такой нумерации.

- Аналогично определим g (v, e ) для графа G.

Определим ориентированный граф H следующим образом. Вершины графа H имеют вид (i, v, v, p), где 1 i, v Vi, v Vi и 0 p < ai.

Рёбра графа H имеют вид (i, j, e, e, q), где 1 i, j, e и e - рёбра - типа i j в графах G и G, 0 q < bij. При этом вершина (i, v, v, p) является началом ребра (k, j, e, e, q) тогда и только тогда, когда i = k, v - - начало ребра e, v - начало ребра e, q = [p rij] и g(v, e) - g (v, e ) p - / (mod rij); вершина (i, v, v, p) является концом ребра (j, k, e, e, q) тогда и только тогда, когда i = k, v - конец ребра e, v - конец ребра e, - - з 3. Инварианты графов q = [p rij] и g(v, -e) - g (v, -e ) p (mod rij), где -e и -e - рёбра e / - и e с противоположной ориентацией.

Воспользовавшись тем, что ai = rijbij, несложно проверить, что начало ребра (i, j, e, e, q) однозначно определено. Действительно, пусть x g(v, e) - g (v, e ) (mod rij) и 0 x < rij. Положим p = qrij + x. Ясно, что условия 0 p < ai = rijbij, q = [p rij], 0 q < bij и p g(v, e) / - g (v, e ) (mod rij) определяют именно это число p. Началом ребра (i, j, e, e, q) является вершина (i, v, v, p). Ясно также, что вершина (i, v, v, p) является концом ребра (j, k, e, e, q) тогда и только тогда, когда она является началом ребра -(j, k, e, e, q) = (k, j, -e, -e, q).

Поэтому конец каждого ребра тоже определён однозначно. Корректность операции обращения ориентации рёбер следует из того, что bjk = bkj.

Таким образом, граф H корректно определён и его рёбра разбиты на пары противоположно ориентированных рёбер.

Накрытие p : H G определим следующим образом: отобразим ребро (j, k, e, e, q) графа H на ребро e графа G; ясно, что при этом вершина (i, v, v, p) отобразится в вершину v. Нужно лишь проверить, что рёбра, выходящие из вершины (i, v, v, p), взаимно однозначно отображаются на рёбра, выходящие из вершины v. Рассмотрим произвольное ребро e типа i j, выходящее из вершины v. В графе G ему соответствует ребро e типа i j, выходящее из вершины v и имеющее номер g (v, -e ) g(v, -e) - p (mod rij). На ребро e отображается ровно одно ребро, выходящее из вершины (i, v, v, p), а именно, ребро (i, j, e, e, q), где q = [p rij].

/ Проекцией ребра -(i, j, e, e, q) = (j, i, -e, -e, q) является ребро -e, поэтому из накрытия p : H G ориентированных графов можно построить накрытие исходного (неориентированного) графа G, заменив каждую пару противоположно направленных рёбер одним неориентированным ребром.

Накрытие p1 : H G1 строится аналогично.

Построенный граф H не обязательно связен, но любая его компонента связности обладает требуемым свойством.

з 3. Инварианты графов Мы будем рассматривать графы, которые могут иметь петли и двойные рёбра.

Пусть e - ребро графа G. Графы, которые получаются из гра - фа G после уничтожения ребра e и после стягивания ребра e в точку, будем обозначать G - e и G e, соответственно. Отметим, что ес/ 58 Глава I. Графы ли e - петля, то G - e = G e. Легко проверить, что операции стя - / гивания и уничтожения ребра коммутируют, т. е. если e1 и e2 - два - ребра графа G, то (G e1) e2 = (G e2) e1, (G - e1) - e2 = (G - e2) - e/ / / / и (G e1) - e2 = (G - e2) e1.

/ / Будем говорить, что графы G1 и G2 изоморфны, если существует гомеоморфизм h: G1 G2, который одновременно является взаимно однозначным отображением вершин этих графов. Иными словами, графы G1 и G2 изоморфны, если существует взаимно однозначное соответствие между их вершинами, при котором две вершины соединены ребром тогда и только тогда, когда соответствующие им вершины соединены ребром.

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

Наиболее важные полиномиальные инварианты графов удовлетворяют соотношению F(G) = aF(G e) + bF(G - e), (1) / где a и b - некоторые фиксированные многочлены (или константы). При - этом возможны два основных варианта: либо соотношение (1) выполняется для любого ребра e (в том числе и для петли), либо соотношение (1) выполняется только для тех рёбер e, концы которых различны.

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

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

Поэтому нужно проверить, что разные последовательности вычислений многочлена F(G) приводят к одному и тому же результату.

Т е о р е м а 3.1. Многочлен F(G) определён корректно.

з 3. Инварианты графов Д о к а з а т е л ь с т в о. Пусть e1 и e2 - рёбра графа G. Тогда - aF(G e1) + bF(G - e1) = / =a2F((G e1) e2) +abF((G e1) -e2) +abF((G -e1) e2) +b2F(G -e1 -e2) = / / / / =a2F((G e2) e1) +abF((G e2) -e1) +abF((G -e2) e1) +b2F(G -e1 -e2) = / / / / =aF(G e2) +bF(G -e2).

/ Поэтому результат вычислений не зависит от того, в каком порядке мы уничтожаем и стягиваем рёбра графа.

Ясно, что если графы G1 и G2 изоморфны, то, уничтожая одновременно соответственные рёбра этих графов, мы придём к одному и тому же результату, поэтому F(G1) = F(G2), т. е. F - полиномиальный инва - риант графа. Многочлен F в некоторых случаях позволяет распознать неизоморфные графы.

Придавая разные значения многочленам a и b и задавая разные значения многочлена F на графах Kn (или на графах, состоящих из изолированных вершин с петлями), мы будем получать разные многочлены F.

Некоторые из них имеют интересную геометрическую интерпретацию.

3.1. Хроматический многочлен Хроматический многочлен P(G, t) определяется соотношением P(G, t) = -P(G e, t) + P(G - e, t), / которое выполняется для любого ребра e. Значение многочлена P(G, t) на графе G, состоящем из n изолированных вершин, полагается равным tn.

Т е о р е м а 3.2. Если t - натуральное число, то P(G, t) - коли - - чество различных раскрасок вершин графа G в t цветов, при которых концы любого ребра разноцветные.

Д о к а з а т е л ь с т в о. Пусть t N и P (G, t) - количество раскра - сок графа G в t цветов. Отметим, что если граф G имеет хотя бы одну петлю, то P (G, t) = 0 (концы петли совпадают, поэтому они не могут быть разноцветными). Если граф G состоит из n изолированных вершин, то P (G, t) = tn = P(G, t). Поэтому достаточно проверить, что если e - - ребро графа G, то P (G, t) = -P (G e, t) + P (G - e, t).

/ Рассмотрим сначала случай, когда e - не петля. Пусть v1 и v2 - концы - - ребра e. Количество раскрасок графа G - e с одноцветными вершинами v1 и v2 равно P (G e, t), а количество раскрасок с разноцветными вер/ шинами v1 и v2 равно P (G, t). Поэтому P (G - e, t) = P (G, t) + P (G e, t), / что и требовалось.

60 Глава I. Графы Рассмотрим теперь случай, когда e - петля. В этом случае P (G, t) = - и P (G e, t) = P (G - e, t), поскольку графы G e и G - e совпадают.

/ / С л е д с т в и е. Количество раскрасок графа G в t цветов полиномиально зависит от t.

У п р а ж н е н и е 1. Докажите, что если Kn - полный граф с n вер - шинами, то P(Kn, t) = t(t - 1)... (t - n + 1).

Т е о р е м а 3.3 (Уитни [142]). Пусть G - граф с n вершинами, - не имеющий петель. Тогда P(G, t) = tn - a1tn-1 + a2tn-2 - a3tn-3 +..., где ai 0.

Pages:     | 1 |   ...   | 6 | 7 | 8 | 9 | 10 |   ...   | 49 |    Книги по разным темам