В.А. Носов - Комбинаторика и теория графов (1023552), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Диаметры почти всех графов равны 2.Теорема. Почти все графы гамильтоновы.87Теорема. Множество автоморфизмов почти каждого графа состоит из одноготождественного автоморфизма.88§ 4. Кратчайшие пути.Пусть G(V,E) - конечный неориентированный граф и пусть заданы две его вершины s и t. Требуется найти кратчайший путь (длина пути равна числу входящих в негоребер) от вершины s к вершине t. Сначала мы опишем алгоритм, который находит длинукратчайшего пути.Алгоритм ДЛИНА1) Помечаем вершину s пометкой 0. Полагаем i = 0.2) Находим все непомеченные вершины, связанные ребром с вершинами, имеющими отметку i.

Если таких вершин нет, t недостижимо из s, стоп. Если такие вершины есть, помечаем их i+1.3) Если вершина t помечена, переходим к 4). Если нет, то увеличиваем iна 1 и повторяем шаг 2).4) Длина кратчайшего пути от s к t равна i+1, стоп.Корректность алгоритма следует из следующего утверждения.Факт 1.

Вершина v графа G(V,E) помечается в алгоритме пометкой l (v) тогда итолько тогда, когда длина кратчайшего пути от вершины s к v равна l (v).♦ Доказательство индукцией по i. Ясно, что при i = 0, l (v) = 0 влечет v = s и утверждение справедливо. Предположим, что утверждение верно для всех вершин v, длякоторых l (v) ≤ m. Если вершина u не помечена, значит нет пути от s к u, меньше чемm+1. Если u связана ребром с вершиной, помечной,то ее пометка , во-первых , будетравна m+1 , во-вторых , имеется путь длины m от s к данной вершине и, значит, длинакратчайшего пути от s к u равна m+1.

Если u не связaна ребром с вершиной, имеющейпометку m, то не существует пути, короче, чем m+1 от s к u, поскольку предыдущаявершина на этом пути имела бы пометку m.Сделаем к данному алгоритму дополнительные замечания.1. Если граф G конечен и нет пути от s к t, то алгоритм остановится после того,как будут помечены все вершины, достижимые из s.2. Если граф G ориентирован и ищется ориентированный путь из s к t, то алгоритм применим, и в этом случае, если шаг 2) записать в виде: 2’) Найти все непомеченные вершины, которые достижимы дугами, выходящими из вершин, имеющих пометкуi. Когда Алгоритм ДЛИНА выдал нам значение l (t) кратчайшего пути от s к t, то нетрудно теперь найти некоторый такой путь, используя пометки l (v).

Приводимый нижеалгоритм выдает путь v(0), v(1), … , v( l (t)) такой, что v(0) = s, v( l (t)) = t.89Алгоритм ПУТЬ.1) Полагаем i = l (t) и помечаем v(i) = t.2) Находим вершину u такую, что u связана ребром с v(i) и l (u) = i-1. Помечаемv(i-1) = u.3) Если i = 1, то стоп. Если нет, уменьшаем i на 1 и повторяем шаг 2). ♦Приводимое ниже утверждение позволяет находить число путей фиксированной длинымежду любыми двумя вершинами.Для графа G(V,E), V= n определим матрицу смежности, т.е. (n×n) - матрицуA = (aij), i, j = 1, … , n, где1, если вершины i , j cоединены ребромaij =0, в противном случае.( l)Теорема 2. Пусть А l = (a ij ), i , j = 1, … , n, где l - натуральное число. Тогда( l)a ij равно числу путей длины l , соединяющих вершины i и j.При l = 1утверждение верно по определению.

Пусть для l -1 это выполняется.Тогда образуем А l = А l−1 * A.( l)( l−1)Имеем a ij = a i1(l −1)Элемент a ik(l−1)⋅ a1j + a i2(l−1)⋅ a2j + … + a in⋅ anj .⋅ akj ≠ 0 в том и только в том случае, когда имеется путь длины( l−1)( l -1) из вершины i в вершину k, и вершины k и j соединены дугой. По индукции a ik( l−1)число путей длины l -1 из i в k. Значит a ik-⋅ akj, - число путей длины l из i в j, таких,что k - предыдущая вершина для j. Просуммировав по всем k, получаем общее числопутей длины l .90§ 5. Деревья.1.

Связный граф G(V, E), не имеющий циклов, называется деревом. Следующаятеорема перечисляет некоторые основные свойства деревьев.Теорема 1. Пусть граф G(V, E) имеет n вершин. Тогда следующие утвержденияэквиваленты.1) G является деревом;2) G не содержит циклов и имеет n - 1 ребер;3) G связен и имеет n - 1ребер;4) G связен, но удаление любого ребра нарушает связность;5) любые две вершины графа G соединены ровно одним путем;6) G не имеет циклов, но добавление любого ребра порождает ровно один цикл.♦ При n = 1 утверждение очевидно, поэтому считаем n ≥ 2. 1) ⇒ 2). По определению G не имеет циклов. Рассмотрим некоторое ребро l = (v1, v2) и удалим его. Получим граф G′. В графе G′ нет пути из v1 в v2 , т.к. если бы такой путь был, то в графе Gбыл бы цикл.

Значит G′ не связен и не имеет циклов. Значит он состоит из двух компонент, являющихся деревьями с числом вершин n1 и n2 соответственно (n1 + n2 = n) . Поиндуктивному предположению G′ имеетn1 - 1 + n2 -1 ребер. Следовательно, граф Gимеет n - 1 ребер.2) ⇒ 3). Если бы G был несвязен, то каждая его компонента представляла бысобой связный граф без циклов. Из предыдущего имеем, что число ребер в каждой компоненте меньше на один числа ее вершин. Значит, общее число ребер меньше числавершин по крайней мере на два, что противоречит тому, что G имеет n - 1ребер.3) ⇒ 4).

Удаление любого ребра приводит к графу с n вершинами и n-2 ребрами,который не может быть связным в силу Факта 2 § 1.4) ⇒ 5). В силу связности G, каждая пара вершин соединена путем. Если быданная пара была соединена более, чем одним путем, то они образовывали бы цикл. Нотогда удаление любого ребра в цикле не нарушает связности графа.5) ⇒ 6). Если бы G содержал цикл, то любые две вершины на цикле соединялись бы по крайней мере двумя путями. Добавим теперь к графу G ребро l = (v1, v2).Тогда образуется цикл, т.к. вершины v1 и v2 уже соединены путем. Ясно, что цикл единственный.916) ⇒ 1). Если бы G был несвязен, то добавление ребер, соединяющих вершиныиз разных компонент, не приводит к образованию цикла.

♦Следствие. Дерево с более чем одной вершиной имеет по крайней мере две вершины степени 1.♦ Действительно, пусть v1, … , vn - множество вершин, тогда имеемn∑ i=1 d(v i ) = 2(n − 1)В силу связности d(vi) ≥ 1 , отсюда и следует утверждение. ♦2. Для графа G(V, E) определим два полезные понятия.Вершинный подграф G(V′, E′) - это граф на множестве вершин V′ ⊂ V и ребрами E′ ⊂ E, такими, что оба конца ребра e′∈ E′ принадлежат V′.Реберный подграф G(V′, E′) - это граф, определяемый подмножеством реберE′⊂ E и множеством вершин V′ ⊂ V, состоящим из концевых вершин ребер из E′.

Остовным (покрывающим) деревом графа G(V, E) называется его реберный подграф с множеством вершин V, являющийся деревом.Факт 2. Граф G(V, E) имеет остовное дерево тогда и только тогда, когда он связен. ♦ Предложим процедуру построения остовного дерева. Ясно, что если граф G несвязен, то он не может иметь остовного дерева.Пусть граф связен. Если в графе нет ребра, удаление которого сохраняет связность графа, то G - дерево.Если такое ребро есть, удалим его и продолжим процедуру. Когда процедура неможет быть продолжена, полученный граф является деревом. ♦Рассмотрим теперь известную проблему нахождения минимального остовногодерева.

Пусть G(V, E) неориентированный граф и пусть каждому ребру e ∈ Е поставленов соответствие положительное число l (e), называемое его весом. Требуется найти связный реберный подграф G′(V′, E′), такой, что V′ = V, причем суммаM(G′) =∑ l(e ′)e ′∈ E′минимальна.Ясно, что граф G(V′, E′) должен быть деревом. Действительно, если G(V′, E′) содержитцикл, то тогда любое ребро цикла можно удалить из графа и тем самым уменьшить суммарный вес ребер графа G(V′, E′).92Факт 3.

Пусть V - произвольная вершина связного графа G(V, E) и пусть e смежное с ней ребро, для которого l (e) минимально для всех ребер, смежных с V. Тогдасуществует минимальное остовное дерево для G(V, E), которое содержит ребро e.♦ Пусть Т - любое минимальное остовное дерево для G(V, E). Если e не является ребром Т, добавим e к Т. Поскольку T - дерево, то в силу теоремы, при этом образуется цикл. Возьмем ребро e′, лежащее на цикле и смежное с вершиной V, и удалим его.Поскольку l (e′) ≥ l (e), то получившееся дерево также минимально. ♦Следующая теорема дает алгоритм построения минимального остовного дерева,известный под названием алгоритма Краскала.Теорема 4. Пусть G(V, E) связный граф с n вершинами.

Тогда следующая процедура приводит к построению минимального остовного дерева.1) Выберем ребро e1, обладающее в G наименьшим весом.2) Определим по индукции последовательность ребер e2, … , en-1 (∗) , выбираяна каждом шаге ребро, отличное от предыдущих, с наименьшим весом и не образующеецикла с уже выбранными ребрами. Полученный подграф Т графа G, образованный ребрами e1, … , en-1, и есть искомое остовное дерево.♦ Поскольку Т не содержит циклов и имеет n - 1 ребер, то Т - остовное дерево, всилу теоремы 1.

Покажем, что сумма весов всех ребер Т минимальна. Предположим, чтов G существует некоторое другое остовное дерево Т′, такое, что M(Т′) < M(Т). Пусть ek первое ребро из последовательности (∗) теоремы, которое не принадлежит Т′. Добавимребро ek к Т′ - тогда в Т′ образуется цикл С, содержащий ребро ek. Цикл С содержит ребро e, принадлежащее Т′ и не принадлежащее Т. Удалим из Т′ ребро e и добавим ребро ek.Полученный подграф Т′′ также является остовным деревом.

По построениюl (ek) ≤l (e), поэтому M(Т′′) ≤ M(Т′). При этом число общих ребер у Т′′ и Т на одно больше, чему Т′ и Т. Повторяя описанную процедуру, можно преобразовать Т′ в Т, причем суммавесов на каждом шаге не увеличивается. Значит, M(Т) ≤ M(Т′), что противоречит допущению. ♦ Сделаем теперь несколько замечаний о применениях понятия остовного дерева.Представим себе, что мы хотим построить сеть связи, которая бы соединяла nданных городов, причем так, чтобы каждый город имел связь с каждым, быть можеттранзитную. Если при этом из экономических соображений требуется, чтобы общаядлина линий была минимальной, то ясно, что речь идет о минимальном остовном деревеграфа, вершины которого соответствуют городам, а ребра - соединяющим их линиям93связи.

Поиск минимального остовного дерева можно искать с помощью алгоритма теоремы 4. Это замечание справедливо, если минимальное остовное дерево определяетсякак остовное дерево, доставляющее минимум некоторой монотонной симметрическойфункции от весов составляющих его ребер.3. В этом пункте мы получим формулу Кирхгофа для числа остовных деревьевпроизвольного неориентированного графа и формулу Кэли для числа остовных деревьевполного графа. Получим сначала подготовительные результаты. Пусть G(V, E) ориентированный граф без петель, где V = {v1, … , vn}, E = {e1, … , em}. Определим матрицу инцидентности А графа G следующим образом:A = (aij), i = 1, … , n, j = 1, … , m, гдеaij =+ 1, если vi начальная вершина ej ;- 1, если vi конечная вершина ej ;0 , если vi не инцидентна ej . i1Напомним, что минором A j1i 2 ...

Характеристики

Список файлов книги