В.А. Носов - Комбинаторика и теория графов (1023552), страница 12
Текст из файла (страница 12)
♦Обозначим l n - число латинских квадратовпорядка n, с элементами из множества X = {1, 2, … , n}, у которых элементы первого столбца и первой строки идут в естественном порядке. Приведем таблицу нескольких известных значений числа l n :n12345678ln1114569408169420805352814018565. Матрица A = (aij) размера n × n с действительными, неотрицательными элементами называется дважды стохастической, если73n∑ j=1 a ij = 1для всехi ∈1, n иn∑ i=1 a ij = 1для всехj ∈1, nДважды стохастические матрицы играют большую роль в теории вероятностей. С перманентами таких матриц связана знаменитая проблема Ван дер Вардена, поставленнаяим в 1926 году: 1. Доказать, что для любой дважды стохастической матрицы А справедper A ≥ливоn!nn2. Равенство достигается лишь для (n × n)-матрицы J = (1/n), все элементы которой равны 1/n.Эта проблема была положительно решена в 1980 году.Упражнения1. Найти число r-мерных наборов чисел 0, 1, 2, 3, в которых каждое число 1, 2, 3появится хотя бы один раз.Ответ: 4r - 3⋅3r + 3⋅2r -12.
Пусть a1, a2, … , an - целые неотрицательные числа. Доказать соотношениеnMax (a1, a2, … , an) = ∑ a i − ∑ Min(a i a j ) +K+ ( −1) n −1 Min(a 1 , K , a n )i =1i< j3. Решить рекуррентное уравнениеan + 6an-1 + 12an-2 + 8an-3 = 0a0 = 1, a1 = -2, a2 = 8 n2 n Ответ: an = − + 1 (−2) n2 24. Вычислить перманент (n × n)-матрицы74 1⋅1 1⋅ 2 2 ⋅1 2 ⋅ 2 ...... n ⋅1 n ⋅ 2... 1 ⋅ n ... 2 ⋅ n ... ... ... n ⋅ nОтвет: (n!)375ГЛАВА III.
ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ.§ 1. Основные понятия теории графов.1. Граф G(V,E) - комбинаторный объект, состоящий из двух конечных множеств: V - называемого множеством вершин и множества пар элементов из V, т.е. E ⊆V×V, называемого множеством ребер, если пары неупорядочены, и множеством дуг,если пары упорядочены. В первом случае граф G(V,E) называется неориентированным,во втором ориентированным. Если e = (v1, v2),e ∈ E, то говорят, что ребро e соединяет вершины v1,v2, если v1 = v2, то ребро e называется петлей.
Две вершины v1,v2 называются смежными, если существует соединяющее ихребро. Аналогично, два различных ребра смежны. если они имеют общую вершину.Степенью вершины v называется число ребер d(v), инцидентных ей, при этомпетля учитывается дважды. В случае ориентированного графа различают степень d0(v)по выходящим дугам и di(v) - по входящим.Путь - это последовательность ребер e1, e2, … , em, такая, что ei, ei+1 имеют общую вершину.
Число ребер называется длиной пути. Если ни одна из вершин не появляется более одного раза, то путь называется простым. Ясно, что в простом пути ни одноребро не используется дважды.Путь называется циклом, если его начальная вершина совпадает с конечной,простым циклом, если это не выполняется для других вершин.В случае ориентированного графа, если путь проходит в направлении дуг, онназывается ориентированным.
Аналогично определяется ориентированный цикл.Граф называется связным, если для любых двух вершин существует путь, их соединяющий. Ориентированный граф называется сильно связным, если для любых двухвершин существует ориентированный путь, их соединяющий. Для ориентированногографа определяем скелетный граф, как неориентированный граф, полученный снятиемориентации исходного графа.Примеры графов:1. Полный граф Kn. Это граф на n вершинах, у которого смежны любые две раз nличные вершины.
Ясно, что граф Kn имеет ребер. 22. Граф отображения F: X → X. Это ориентированный граф с множеством вершин X, при этом вершины xi и xj соединяются дугой, если xj= F(xi).763. Двудольные графы. Это графы, у которых множество вершин можно разбитьна два множества V1, и V2,, так что каждое ребро графа соединяет только некоторуювершину из V1 с некоторой вершиной из V2.4.
Граф единичного n-мерного куба Bn. Вершины графа - n-мерные двоичныенаборы. Ребра соединяют вершины, отличающиеся одной координатой.Факт 1. Любой граф содержит четное число вершин нечетной степени.♦ Если граф G имеет xi вершин степени i, тоx1+ 2x2+ … + kxk = 2 E(1)поскольку мы подсчитываем число концевых вершин ребер, а каждое ребро имеет точнодве концевые вершины. Отсюда получаем, что x1+ x3+ … + x2S+1 - четное число. ♦Число ребер в графе существенно влияет на его связность.
Заметим, что любой графможно разбить на связные части - компоненты связности, задав следующее отношениеэквивалентности на множестве его вершин: две вершины эквивалентны, если существует путь из одной вершины в другую. Таким образом, связный граф состоит из однойкомпоненты.Факт 2. Пусть G - граф с n вершинами и k компонентами. Тогда число m его реберудовлетворяет неравенствамn-k ≤m≤(n − k)(n − k + 1)2(2)♦ Нижнюю оценку доказывают индукцией по числу ребер в G. Если множестворебер пусто, то утверждение очевидно. Если в графе G число ребер минимально (скажемm0), удаление любого ребра приводит к увеличению числа компонент на единицу. Значит, в графе k + 1 компонента и m0 - 1 ребро. По предположению индукции ,m0- 1 ≥ n - (k + 1), откуда m0 ≥ n - k.
Для доказательства верхней оценки считаем каждуюкомпоненту графа G полным графом. Если Ci и Cj - две компоненты с ni и nj вершинами(ni ≥ nj > 1), то заменяя их на полные графы с ni + 1 и nj - 1 вершинами, мы, не меняячисла вершин, увеличиваем число ребер. Действительно,(n j − 1)(n j − 2)(n i + 1)n in (n −1) n j (n j −1)- i i= ni - n j + 1 > 0+2222Значит, максимальное число ребер имеет граф G , у которогоk - 1 изолированных вершин и компонента из полного графа наn - k + 1 вершинах.
Отсюда и следует верхняя оценка. ♦77Следствие. Любой граф с n вершинами, имеющий более, чем(n − 1)(n − 2)ре2бер, связан.♦ Действительно, если граф имеет k компонент, то по предыдущему, число егоребер не превышает(n − k)(n − k + 1)(n − 1)(n − 2)(n − k)(n − k + 1). Но неравенство<222справедливо только при k = 1. ♦Убедимся теперь в том, что степени вершин существенно влияют на наличие циклов вграфе.Факт 3. Если степень каждой вершины графа G(V,E) не меньше двух, то G содержитцикл.♦ Пусть v - произвольная вершина из V. Строим последовательность ребер(v,v1), (v1,v2), … , выбирая v1 смежной с v, … , vi+1 - смежной с vi, и отличной от vi-1. Поусловию вершина vi+1 существует.
В силу конечности V на некотором шаге будет выбрана вершина, уже встретившаяся раньше. Пусть это vk. Тогда часть последовательности ребер между вхождениями vk образует цикл.♦2. Пусть G – связный граф, u, v – произвольные вершины. Определим d(u, v) –расстояние между u и v как длину кратчайшего пути из u в v. При этом полагаемd(u, v) = 0 при u = v.Ясно, что введенное таким образом расстояние удовлетворяет аксиомам метрики:1.
d(u, v) ≥ 02. d(u, v) = 0 ⇔ u = v3. d(u, v) = d(v, u)4. d(u, v)+d(v, w) ≥ d(u, w) (неравенство треугольника)Для связного графа G диаметр d(G) определяется какd( G) = max d( u, v )u ,v3. Графы G1(V1, E1) и G2(V2, E2) называются изоморфными, если существует биекция f: V1 → V2, такая, что выполнено(v1, v2) ∈ E1 ⇔ (f(v1), f(v2)) ∈ E2.При этом f называется изоморфизмом графов G1 и G2. Изоморфизм графа G насебя называется автоморфизмом.Пример 1. Следующие графы имеют только тождественные автоморфмы78Пример 2.
Следующий граф имеет, кроме тождественного, автоморфизмы(1, 3) , (2, 4) , (13)(24).1243Широко известна так называемая проблема изоморфизма графов, в которой длялюбых двух графов требуется установить, изоморфны они или нет. Для знакомства срезультатами по данной проблеме следует обратиться к приведенному списку литературы.4. Поскольку графы можно рассматривать как частные случаи бинарных отношений, то для них могут быть определены аналогичные операции.
Укажем некоторые изних.Пусть G1 + (V1, E1), G2 = (V2, E2) – два графа.Объединение графов G1 и G2 есть граф, у которого V = V1 ∪ V2, E = E1 ∪ E2.СоединениеграфовG1+G2естьграф,укоторогоV = V1 ∪ V2,E = E1 ∪ E2 ∪ {(v1, v2)} для всех v1 ∈ V1, v2 ∈ V2.Прямоепроизведениеграфовестьграф,укоторогоV = V1 × V2,(( c 1 , v 2 ),( v 1′ , v ′2 )) ∈ E ⇔ ( v 1 , v 1′ ) ∈ E1 и ( v 2 , v ′2 ) ∈ E2 .Пример.
Пусть даны графы отображений f1: V1 → V1, f2: V2 → V2. Тогда их прямоепроизведениесоответствуетотображениюf1 × f2: V1 × V2 → V1 × V2, где f1 × f2(v1, v2) = (f1(v1), f2(v2)).Пусть f1 и f2 имеют l 10 и l 20 начальных вершин соответственно. Тогда f1 × f2 будет иметь l 0 = l 10 ⋅| v 2 |+ l 20 | v 1 |− l 10 ⋅ l 20 начальных вершин.795. Некоторые классы графов допускают характеристическое описание. В качестве примера приведем критерий двудольности графа (Кёниг, 1936 г.)Теорема. Для двудольности графа необходимо и достаточно, чтобы он не содержал циклов нечетной длины. Пусть G = (V, E) – двудольный граф, С – один из его циклов длины k. Фиксируем вершину v1 ∈ C и проходим цикл, начиная с v1.
Пусть это вершины v1, v2, ..., vk.Поскольку концы каждого ребра лежат в разных долях, то k – четное число.Пусть G = (V, E) – связный и все его циклы четной длины. Определим разбиениеV = V1 ∪ V2 следующим образом: Фиксируем произвольную вершину v1 ∈ V и включаем ее в V1. Теперь включаем u ∈ V1 ⇔ d(u, v1) – четное число. Остальные вершинывключаем в V2.Покажем, что граф G двудольный. Пусть, напротив, существует ребро (v′, v″),где v′, v″ ∈ V1. Следовательно, d(v1, v′), d(v1, v″) – четны. Ребро (v′, v″) дает цикл нечетной длины, содержащий путь от v1 к v′, ребро (v′, v″), путь от v″ к v1. Аналогично показываем, что нет ребер (v′, v″), v′, v″ ∈ V2.
80§ 2. Эйлеровы графы.Эйлеровым путем графа G(V,E) называется путь e1,e2, … , et такой, что каждоеребро появляется ровно 1 раз, т.е. t =E. Граф G(V,E) называется эйлеровым, если онимеет замкнутый эйлеровый путь, и полуэйлеровым, если существует эйлеров путь, неявляющийся замкнутым.Теорема 1. Связный граф G является эйлеровым тогда и только тогда, когда каждая вершина G имеет четную степень.♦ Предположим, что Р является эйлеровым циклом в графе G. Тогда при всякомпрохождении цикла через любую вершину графа используется одно ребро для входя иодно ребро для выхода. Поскольку каждое ребро используется один раз, то каждая вершина должна иметь четную степень.
Обратное утверждение доказываем индукцией почислу ребер в графе G. Пусть граф G связен и степень каждой вершины четна. На основании Факта 3 граф содержит цикл С. Если С содержит каждое ребро, то все доказано.Если же нет, то удаляем из графа G все ребра, принадлежащие циклу С. Получаем новый граф G1, возможно несвязный. Число ребер в G1 меньше чем в G, и каждая вершинаимеет четную степень. По индуктивному предположению в каждой компоненте графаG1 имеется эйлеров цикл. В силу связности графа G каждая компонента графа G1 имеетобщие вершины с циклом С. Теперь проходим ребра графа G следующим образом: идемпо ребрам цикла С до первой неизолированной вершины графа G1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
