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

Д о к а з а т е л ь с т в о. Если граф G состоит из одной вершины и не имеет рёбер, то P(G, t) = t. Пусть {e1,..., ek} - множество всех - рёбер графа G. Тогда P(G) = P(G - e1) - P(G e1) = / = P(G - e1 - e2) - P((G - e1) e2) - P(G e1);

/ / здесь графы G e1 и (G - e1) e2 имеют по n - 1 вершин. Ясно также, что / / G - e1 - e2 -... - ek = Kn - граф, состоящий из n изолированных вер - шин. Поэтому P(G) = P(Kn) - g1 -... - gk = tn - g1 -... - gk, где g1,..., gk - хроматические многочлены графов, каждый из которых - содержит n - 1 вершину.

Т е о р е м а 3.4 (Уитни [142]). Хроматический многочлен графа можно вычислять по следующей комбинаторной формуле:

P(G, t) = (-1)e(H)tc(H), HG где суммирование ведётся по всем подграфам H G, множество вершин которых совпадает с множеством вершин графа G; здесь e(H) - число рёбер, c(H) - число компонент связности.

- - Д о к а з а т е л ь с т в о. Рассмотрим многочлен P (G, t) = (-1)e(H)tc(H).

HG У графа G = Kn есть ровно один подграф H, вершины которого совпадают с вершинами графа G, а именно, H = G = Kn. При этом e(H) = и c(H) = n. В таком случае P (G, t) = (-1)e(H)tc(H) = tn = P(G, t).

HG з 3. Инварианты графов Остаётся проверить, что P (G, t) = -P (G e, t) + P - e t). Для это/ (G, го представим многочлен P (G, t) в виде P (G, t) = +. Легко проeH e H верить, что = -P (G e, t) и = P (G - e, t); знак минус появляется / eH e H в первом равенстве из-за того, что у графа H e на одно ребро меньше, / чем у графа H.

3.2. Многочлен от трёх переменных В [101] введён полиномиальный инвариант f(G; t, x, y), удовлетворяющий соотношению f(G) = xf(G e) + yf(G - e) (для всех рёбер e, в том / числе и для петель) и принимающий на графе Kn значение tn.

У п р а ж н е н и е 2. а) Докажите, что если G - связное дерево, со - держащее n рёбер, то f(G) = t(x + ty)n.

б) Докажите, что если G - цикл длины n, то f(G) = t(x + ty)n + - + (t - 1)xn.

Коэффициенты многочлена f имеют следующую комбинаторную интерпретацию.

Т е о р е м а 3.5. Пусть G - граф, содержащий v вершин и e рё - бер. Тогда e v j f(G) = bijt xe-iyi, i=0 j=где bij - количество таких i-элементных подмножеств Y множе - ства рёбер графа G, что после уничтожения в графе G всех рёбер, принадлежащих множеству Y, получается граф, содержащий j компонент связности.

Д о к а з а т е л ь с т в о. Непосредственно из определения многочлена f видно, что его можно вычислять следующим образом. Разобьём рёбра графа G на два множества X и Y. Затем все рёбра из множества X стянем, а все рёбра из множества Y уничтожим. Такому набору операj ций соответствует моном t xe-iyi. Чтобы вычислить многочлен f, нужно рассмотреть все подмножества Y и сложить все полученные мономы.

С л е д с т в и е 1. Коэффициенты многочлена f неотрицательны.

С л е д с т в и е 2. Если графы K и H не имеют общих вершин, то f(K H) = f(K) f(H).

С л е д с т в и е 3. Если пересечение графов K и H состоит в точности из одной вершины, то f(K H) = t-1 f(K) f(H).

62 Глава I. Графы Д о к а з а т е л ь с т в о. Пусть Y1 и Y2 - подмножества рёбер графов - K и H. Предположим, что после выбрасывания из K и H рёбер, принадлежащих Y1 и Y2, получаются графы, содержащие j1 и j2 компонент связности. Тогда после выбрасывания из K H рёбер, принадлежащих множеству Y1 Y2, получается граф, содержащий j1 + j2 - 1 компонент связности (общая вершина графов K и H соединяет две компоненты связности в одну).

Следствие 3 позволяет строить примеры неизоморфных графов с одинаковыми многочленами f(G). А именно, мы берём графы K и H и поочерёдно отождествляем одну из вершин графа K с разными вершинами графа H. При этом могут получаться неизоморфные графы, но у них многочлен f(G) будет одним и тем же. Есть ещё одно преобразование графов, при котором получаются графы с одинаковыми многочленами f(G).

Т е о р е м а 3.6. Пусть u1 и u2 - вершины графа K, v1 и v2 - - - вершины графа H. Предположим, что граф G1 получен из графов K и H отождествлением вершин u1 и v1, u2 и v2, а граф G2 получен из графов K и H отождествлением вершин u1 и v2, u2 и v1. Тогда f(G1) = f(G2).

Д о к а з а т е л ь с т в о. Выберем в множествах рёбер графов K и H подмножества X1 и X2. Такие подмножества находятся во взаимно однозначном соответствии с подмножествами в множествах рёбер каждого из графов Gi, i = 1, 2. При этом в графе G1 ребро, соединяющее вершины v1 и v2, входит в множество X = X1 X2 тогда и только тогда, когда оно входит в множество X в графе G2. Поэтому в графах G1 и G2 число компонент связности графа, образованного рёбрами из множества X, одно и то же.

3.3. Многочлен БоттаЦУитни - Многочлен БоттаЦУитни R(G, t) определяется соотношением - R(G, t) = R(G e, t) - R(G - e, t), (2) / которое выполняется только для рёбер e, которые не являются петлями.

Значение многочлена R на графе, состоящем из одной вершины и n петель, равно (t - 1)n; значение многочлена R на объединении графов такого вида равно произведению значений на отдельных графах.

У п р а ж н е н и е 3. Докажите, что R(G, 1) = 0.

Многочлен БоттаЦУитни имеет следующую интерпретацию.

- Т е о р е м а 3.7. Пусть G - граф, H - некоторое множество его - - рёбер, H - дополнение H в графе G (т. е. такой граф, что его - рёбрами являются те рёбра графа G, которые не входят в H;

з 3. Инварианты графов вершины у графа H те же самые, что и у графа G). Граф H гомотопически эквивалентен объединению попарно не пересекающихся букетов окружностей. Пусть b1(H) - количество всех окружно - стей в этих букетах. Тогда R(G, t) = (-1)e(H)tb (H), (3) HG где e(H) - число элементов множества H; суммирование ведётся - по всем подмножествам рёбер, включая пустое множество.

Д о к а з а т е л ь с т в о. Пусть граф G состоит из нескольких изолированных вершин с петлями. Если общее количество этих петель равно m, то m m m R(G, t) = (-1)itm-i = (-1)itm-i = (t - 1)m.

i i=0 |H|=i i=Остаётся доказать соотношение (3). Многочлен R(G) можно пред ставить в виде R(G) = +. Легко проверить, что = R(G e) / e H eH e H и = -R(G - e). Действительно, пусть e H; тогда e H. По услоeH вию e - не петля, поэтому графы H и H e гомотопически эквивалентны, - / а значит, b1 (H) = b1 (H e). Пусть теперь e H, т. е. H = H1 {e}. Тогда / e(H) = e(H1) + 1, а значит, (-1)e(H) = -(-1)e(H ). Кроме того, дополнение H в G совпадает с дополнением H1 в G - e.

Т е о р е м а 3.8. Пусть граф G состоит из двух графов G1 и G2, которые либо не пересекаются, либо имеют одну общую вершину и не имеют общих рёбер. Тогда R(G) = R(G1)R(G2).

Д о к а з а т е л ь с т в о. Воспользуемся равенством (3). Представим множество H в виде H = H1 H2, где Hi состоит из рёбер графа Gi.

Тогда e(H) = e(H1) + e(H2) и b1 (H) = b1 (H1) + b1 (H2), где H1 и H2 - до - полнения H в графах G1 и G2. Поэтому R(G) = R(G1)R(G2).

С л е д с т в и е 1. Если у графа G есть свободное ребро (т. е.

ребро, из одного конца которого не выходит других рёбер), то R(G) = 0.

Д о к а з а т е л ь с т в о. Легко проверить, что если граф G1 состоит из одного ребра, то R(G1) = 0. Граф G со свободным ребром можно представить в виде объединения графа G1 и некоторого графа G2, пересекающего G1 в одной вершине. Поэтому R(G) = R(G1)R(G2) = 0.

С л е д с т в и е 2. Если граф G является циклом, то R(G) =t -1.

Д о к а з а т е л ь с т в о. Пусть e - ребро графа G. Тогда граф G - e - имеет свободное ребро, поэтому R(G - e) = 0. Граф G e является циклом / 64 Глава I. Графы с меньшим числом рёбер. Остаётся заметить, что если граф G состоит из одной петли, то R(G) = t - 1.

Многочлен БоттаЦУитни, в отличие от хроматического многочлена, - является топологическим инвариантом, т. е. гомеоморфные графы имеют одинаковые многочлены БоттаЦУитни.

- Т е о р е м а 3.9. Многочлен БоттаЦУитни является топологи - ческим инвариантом графа.

Д о к а з а т е л ь с т в о. Графы G и G гомеоморфны тогда и только тогда, когда существует последовательность графов с начальным членом G и конечным членом G, все пары соседних членов которой связаны следующим преобразованием: на ребре e берётся дополнительная вершина v и в результате ребро e заменяется на два ребра e1 и e2 с общей вершиной v. Поэтому достаточно проверить, что если граф G получается из графа G таким преобразованием, то R(G ) = R(G). Ребро e1 не является петлёй, поэтому R(G ) = R(G e1) - R(G - e1). У графа G - e1 есть / свободное ребро e2, поэтому R(G - e1) = 0. Ясно также, что граф G e/ изоморфен графу G.

В [143] Уитни определил набор инвариантов графа, который совпадает с набором коэффициентов многочлена R(G). Независимо Ботт [39] определил полиномиальный инвариант конечного клеточного комплекса, в 1-мерном случае совпадающий с R(G). Подробно свойства многочлена БоттаЦУитни изучены в [136].

- 3.4. Инварианты Татта Пусть g(G) - функция на множестве графов со значениями в неко - тором коммутативном ассоциативном кольце с единицей. Функцию g называют инвариантом Татта, или V -функцией), если выполняются следующие условия:

1) g() = 1;

2) если ребро e не является петлёй, то g(G) = g(G e) + g(G - e);

/ 3) если граф G является объединением непересекающихся графов K и H, то g(G) = g(K) g(H).

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

Одним из важнейших инвариантов Татта является введённый Таттом дихроматический многочлен Q(G, t, z) = zb (H)tc(H), HG ) Такое название использовал Татт.

з 3. Инварианты графов где суммирование ведётся по всем подграфам H G, множество вершин которых совпадает с множеством вершин графа G; b1 (H) - количество - независимых циклов в графе H (подробнее: граф H гомотопически эквивалентен объединению нескольких непересекающихся букетов окружностей; b1 (H) - это общее количество окружностей в этих букетах), c(H) - - - число компонент связности графа H.

Т е о р е м а 3.10. Дихроматический многочлен является инвариантом Татта.

Д о к а з а т е л ь с т в о. Свойство 1 очевидно. Чтобы доказать свой ство 2, представим дихроматический многочлен в виде Q(G) = +.

e H eH Ясно, что = Q(G - e); равенство = Q(G e) следует из того, что / e H eH b1 (H) = b1 (H e) и c(H) = c(H e). Свойство 3 следует из того, что для / / непересекающихся графов функции b1 и c аддитивны.

Пусть e - ребро с концами v1 и v2 в графе G. Ребро e называют мо - стом, если в графе G любой путь из v1 в v2 проходит через e. Татт [128] ввёл многочлен T(G, x, y), для которого свойство 3 выполняется лишь в том случае, когда ребро e не только не является петлёй, но и не является мостом. А именно, многочлен Татта T(G, x, y) обладает следующими свойствами:

а) если граф G имеет ровно одно ребро, то T(G, x, y) = x в том случае, когда это ребро - мост, и T(G, x, y) = y в том случае, когда это ребро - - - петля;

б) если e - ребро графа G, которое не является ни петлёй, ни мостом, - то T(G, x, y) = T(G - e, x, y) + T(G e, x, y);

/ в) если e - мост, то T(G, x, y) = xT(G e, x, y), а если e - петля, - / - то T(G, x, y) = yT(G - e, x, y).

Ясно, что свойства аЦв позволяют вычислить многочлен Татта для любого связного графа G. Непротиворечивость этих свойств следует из того, что многочлен Татта можно задать следующей комбинаторной формулой:

T(G, x, y) = (x - 1)c(H)-c(G) (y - 1)e(H)-v(G)+c(H), HG где суммирование ведётся по всем подграфам H G, множество вершин которых совпадает с множеством вершин графа G.

Глава II Топология в евклидовом пространстве з 4. Топология подмножеств евклидова пространства 4.1. Расстояние от точки до множества Пусть A Rn - произвольное подмножество. Для произвольной точ - ки x Rn величину d(x, A) = inf x - a называют расстоянием от точaA ки x до множества A.

Т е о р е м а 4.1. а) Функция f(x) = d(x, A) непрерывна для любого подмножества A Rn.

б) Если множество A замкнуто, то функция f(x) = d(x, A) для всех x A принимает положительные значения.

Д о к а з а т е л ь с т в о. а) Пусть x, y Rn. Тогда d(x, A) = = inf x - a x - y + inf y - a = x - y + d(y, A), т. е.

aA aA d(x, A) - d(y, A) x - y. Аналогично доказывается, что d(y, A) - d(x, A) x - y. Следовательно, |f(x) - f(y)| x - y, поэтому функция f непрерывна.

б) Если множество A замкнуто, то множество Rn \ A открыто. Поэтому для любой точки x0 Rn \ A найдётся такое > 0, что шар радиуса с центром x0 принадлежит множеству Rn \ A. В таком случае d(x, A) > 0.

З а м е ч а н и е. Теорема 4.1 верна и для произвольного метризуемого топологического пространства. Доказательство в точности то же самое.

Это замечание относится и к теореме 4.2.

Пусть A, B Rn - произвольные подмножества. Величину d(A, B) = - = inf a - b называют расстоянием между множествами A и B.

aA, bB Т е о р е м а 4.2. Пусть A Rn - замкнутое подмножество, - C Rn - компактное подмножество. Тогда существует такая - точка c0 C, что d(A, C) = d(A, c0). Если множество A тоже компактно, то существует ещё и такая точка a0 A, что d(A, C) = = d(a0, c0).

з 4. Топология подмножеств евклидова пространства Д о к а з а т е л ь с т в о. Функция f(x) = d(x, A) непрерывна на компактном множестве C, поэтому она достигает минимума в некоторой точке c0 C. Если множество A компактно, то непрерывная функция g(x) = d(c0, x) на множестве A достигает минимума в некоторой точке a0 A.

З а д а ч а 4.1. Верно ли, что d(A, C) d(A, B) + d(B, C) Чтобы получить расстояние между множествами, удовлетворяющее неравенству треугольника, используют следующее определение. Пусть A, B Rn - произвольные подмножества. Рассмотрим множество T, со - стоящее из всех положительных чисел t, обладающих следующими свойствами:

- для любого a A существует такое b B что a - b t;

- - для любого b B существует такое a A что a - b t.

- Величину dH (A, B) = inf t называют расстоянием по Хаусдорфу tT между множествами A и B.

З а д а ч а 4.2. Докажите, что dH (A, C) dH (A, B) + dH (B, C).

4.2. Продолжение непрерывных отображений В топологии часто встречается задача о продолжении непрерывного отображения f : A Y, где A X, до непрерывного отображения всего пространства X в Y. Задача продолжения отображения наиболее просто решается в том случае, когда X = Rn и Y = R. Основой для построения продолжения в этом случае служит следующее утверждение, которое обычно называют леммой Урысона.

Т е о р е м а 4.3 (лемма Урысона [20]). Пусть A и B - непере - секающиеся замкнутые подмножества Rn. Тогда существует такое непрерывное отображение f : Rn [-1, 1], что f(A) = {-1} и f(B) = {1}.

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