Лекции Русакова, страница 8

Тогда скалярное произведение i-той строкиматрицы Ak-1 на j-тый столбец матрицы A равен сумме произведений. Каждоепроизведение означает кол-во путей из vi в vj, проходящих через vl напредпоследнем шаге. В сумме получается общее кол-во.62Утверждение.Для того, чтобы n-вершинный орграф D с матрицей смежности A=A(D)имел хотя бы один контур, ⇔ чтобы матрица K=A2+A3+… An имеланенулевые диагональные элементы (следствие предыдущего).ДоказательствоПусть ρ — отношение достижимости на множестве V всех вершин(неориентированного) графа G.

(либо v=w, либо ∃ маршрут, соединяющий vи w).Тогда1) ρ — отношение эквивалентности;2) vρw ⇔ вершины v,w принадлежат одной компоненте связности;3) для ∀ класса эквивалентности V1 псевдограф G1, порожденныймножеством V1, является компонентой связности псевдографа G.Для орграфа.Пусть ρ1 — отношение достижимости на множестве V всех вершинориентированного псевдографа D. Пусть ρ2-отношение двустороннейдостижимости на множестве V.

(ρ2=ρ1∩ρ1-1).Тогда1) ρ1 — рефлексивно, транзитивно;2) ρ2 — эквивалентность на V;3) vρ2w ⇔ когда вершины v,w ∈ одной компоненте сильной связности;4) для∀классаэквивалентностиV1ориент.псевдографD1,порожденный множеством V1, является компонентой связности ор.псевдографа G.Число компонент сильной связности орграфа D обозначается P(D), длянеориентированного — P(G).63Определение.Под операцией удаления вершины из графа (орграфа) будем пониматьоперацию, заключающуюся в удалении некоторой вершины вместе синцидентными ей ребрами (дугами).Определение.Вершина графа, удаление которой увеличивает число компонентсвязности, называется точкой сочленения.Пример.Утверждение.Если D' – орграф, полученный в результате удаления нескольких вершиниз орграфа D, то матрица смежности A(D') получается из матрицы смежностиA(D) в результате удаления строк и столбцов, соответствующих удаленнымвершинам.

(Для неориентированного графа то же самое).Определение.Матрицей достижимости орграфа D называется квадратная матрицаT(D)=[tij] порядка n, элементы которой равны1, v j достижима из vi ,tij =  0 в противном случае.Определение.Матрицей сильной связности орграфа D называется квадратная матрицаS(D)=[sij] порядка n, элементы которой равны641, v j достижима из vi и vi достижима из v jsij = в противном случае.0Определение.Матрицей связности графа G называется квадратная матрица S(G)=[sij]порядка n, элементы которой равны1, если ∃ маршрут, соединяющий v j и vi ,sij = в противном случае.0Утверждение.Пусть G=(V,X) – граф, V={v1,…, vn}, A(G) – его матрица смежности.ТогдаS(G)=sign[E+A+A2+A3+… An-1] (E- единичная матрица порядка n).(Следует из предыдущего).Утверждение.Пусть D=(V,X) – орграф, V={v1,…, vn}, A(D) – его матрица смежности.Тогда1) T(D)=sign[E+A+A2+A3+… An-1],2) S(D)=T(D)&TT(D) (TT-транспонированная матрица, &- поэлементноеумножение).Алгоритм выделения компонент сильной связности.1.

Присваиваем p=1, S1=S(D).2. Включаем в множество вершин Vp компоненты сильной связностиDp=(Vp,Xp) вершины, соответствующие единицам первой строки матрицы Sp.В качестве матрицы A(Dp) возьмем подматрицу матрицы A(D), состоящую изэлементов матрицы A, находящихся на пересечении строк и столбцов,соответствующих вершинам из Vp.3. Вычеркиваем из Sp строки и столбцы, соответствующие вершинам изVp.

Если не остается ни одной строки (и столбца), то p — кол-во компонент65сильной связности. В противном случае обозначим оставшуюся послевычеркивания срок и столбцов матрицу Sp+1, присваиваем p:=p+1 ипереходим к п. 2.Пример.00A(D ) =  0010 1 0 00 0 0 01 0 1 1 ,1 0 0 00 0 1 0 1 0 1 10 0 0 01 0 1 0 ,0 0 0 01 1 0 0 10000001010  00  01  00  00  10011010000001010  0 0  01 = 1 0  00   00032A = A A = 1001010100001101001  00  00  00  00  10011010000001010  1 0  01 =  0 0  00   01 0 1 00 0 0 01 1 0 0 ,0 0 0 01 0 1 1 10A 4 = A3 A =  0001010100100100010  00  00  00  01  10011010000001010  0 0  01 =  0 0  00   11 1 0 00 0 0 01 0 1 1 ,0 0 0 01 0 1 0 002A = 0010011066111111010110111101 ,01 1  1 0  11  & 1 0  11  101000111110101010T(D)=sign[E+A+A2+A3+A4]=  10110S(D)=T&TT=  101111111010110111Выделение компонент (сильной) связности.1.

p=1,10S1 = S =  101010002. V1={v1, v3, v5},1010100010101010 1 0A(D1 ) =  0 0 1 1 0 0D1 1 03. S 2 =  ,012'. V2={v2 }, A(D2 ) = (0 )671  1 1  01 =  1 1  01  10 1 0 11 0 0 00 1 0 1 .0 0 1 00 1 0 1 D23'. S 3 = (1) ,2''. V3={v4 }, A(D3 ) = (0 )D32.10. Расстояние и протяжённость в графе.Определение.Пусть G — связный неориентированный граф. Так как любые двевершины a и b связаны, существуют простые цепи s (a, b ) с концами a и b .Длиныэтихпростыхцепейявляютсянеотрицательнымичислами.Следовательно, между a и b должны существовать цепи наименьшей длины.Эта наименьшая длина называется расстоянием d (a, b ) между a и b .Положим по определению d (a, a ) = 0 .Легко видеть, что эта описывающая расстояние функция удовлетворяетаксиомам метрики:1.

d (a, b ) ≥ 02. d (a, b ) = 0 ⇔ a = b683. d (a, b ) = d (b, a )4. Неравенство треугольника d (a, b ) + d (b, c ) ≥ d (a, c )Теорема.Пусть G связный граф, имеющий не более чем счётные локальныестепени. Тогда G имеет не более чем счётное число вершин и рёбер.Теорема.Пусть G – бесконечный локально конечный связный граф. Тогда изкаждой вершины G выходит бесконечная простая цепь.Определение.Для конечных связных графов можно также ввести протяжённостьe(a, b ) между двумя вершинами a и b как длину самой длиннойсвязывающей их простой цепи. Очевидно e(a, b ) удовлетворяет аксиомамметрики.Существуют диаметральные по протяжённости или длиннейшиепростые цепи, их длина l0 называется диаметром протяжённости.Определение.Для каждой вершины v существуют наиболее длинные простые цепи,имеющие v своим концом, их длинаl (r ) = max l (v, x )x∈vназывается числом протяжённости для вершины v .Определение.Центрами протяжённости называются вершины s0 с минимальнымчислом протяжённости.69l0 = l (s0 ) = min e(v ) .v∈VСоответствующие наиболее длинные простые цепи от этих центровможно назвать радиальными по протяжённости простыми цепями, а их длинуl0 — радиусом протяжённости.Теорема.Любые две длиннейшие простые цепи имеют общие вершины.Теорема.Число протяжённости удовлетворяет неравенствуe(v ) ≥1e(v ) ≥ l021(l0 + 1) соответственно для чётного и нечётного2l0или(радиусапротяжённости).Равенство может здесь достигаться только тогда, когда v расположенона каждой длиннейшей простой цепи.Теорема.Если ρ (a, b ) – простая цепь из вершины a , которую нельзя продолжитьза b , то b лежит на простом цикле, длина которого не меньше чем ρ (b ) + 1 .2.11.

Деревья.Определение.Деревом называется конечный связный граф без циклов (определениене полное).Примеры:70Не деревоЛес из трёх деревьев.Определение.Лесом из k деревьев называется граф G без циклов у которогоc(G ) = k , k > 1.Определение. Деревом называется связный, ориентированный граф безпетель и кратных ребер, не содержащий в себе циклов, удовлетворяющийследующим условиям:1. имеется в точности один узел, называемый корнем, в который невходит ни одно ребро,2. В каждый узел, кроме корня, входит ровно одно ребро,3.

Из корня к каждому узлу идет путь (который, как легко показатьединственный).Деревья являются простейшим видом связных графов. Любое дерево сn вершинами содержит n-1 ребер. Число различных деревьев, которые можнопостроить на n вершинах равно71n n −2Определение.Дерево с одной выделенной вершиной называется корневым деревом.ОпределениеОриентированный граф, состоящий из нескольких деревьев, называетсялесом.Определение.Пусть G=(Х, Г) – граф, являющийся лесом.

Если дуга (v,w)принадлежит Г, то v называется отцом узла w, а w – сыном узла v.Определение.Если есть путь из v в w, то v называется предком узла w, а w –потомком узла v.Определение.Узел без потомков называется листом.Определение.Узел v и его потомки вместе образуют поддерево леса G, и узел vназывается корнем этого поддерева.Определение.Глубина узла v в дереве – это длина пути из корня в v.Определение.72Высота узла в дереве – это длина самого длинного пути из этого узла вкакой-нибудь лист.Определение.Высотой дерева называется высота его корня.ПримерabefjgkdchilГлубина узла b, в данном примере, = 1, а его высота = 2.

Высота дерева= 3.Определение.Упорядоченным деревом называется дерево, в котором множествосыновей каждого узла упорядоченно. При изображении упорядоченногодерева, как правило, считается, что множество сыновей каждого узлаупорядоченно слева направо.Определение.Бинарным деревом называется такое упорядоченное дерево, что1. Каждый сын произвольного узла идентифицируется либо как левый сын,либо как правый сын.2. Каждый узел имеет не более одного левого и не более одного правогосына.73Обратите внимание, что бинарное дерево не является частным случаемдерева, это совершенно иное, хотя и тесно связанное понятие.Например:ABABУказанные бинарные деревья различны между собой ( в первом случаекорень имеет пустое правое поддерево, а во втором левое поддерево пусто),хотя как деревья они изоморфны, и мы можем рассматривать их как однодерево.Определение.Бинарное дерево называется полным, если длянекоторого целого числа K каждый узел, глубины меньшей k имеет каклевого, так и правого сына, и каждый узел глубины k является листом.Полное дерево глубины k имеет2 k +1 − 1 узлов.Очень часто используются алгоритмы, которые проходят дерево(посещают каждый его узел) в некотором порядке.

Известно несколькоспособов сделать это: прохождение дерева в прямом порядке, обратномпорядке и внутреннем.2.12. Помеченные графы. Перечисление помеченныхдеревьев.Определение.74Граф с n вершинами называется помеченным, если его множествовершин X = [1, n ]N .Определение.Помеченные графы G1 и G2 с n вершинами называются изоморфными,еслисуществуетбиективноеотображениеψ : U1 → U 2такое,что(композиция) (ρ  f 2  ψ )(u ) = (ρ  f1 )(u )∀u ∈U 1 , i = 1,2 .Замечание.Это определение похоже на определение изоморфизмов теории графов,отличие состоит в том, что изоморфизм графов реализуется паройбиективных отображений ϕ : X 1 → X 2 , ψ : U 1 → U 2 , а ϕ — тождественноеотображение.Пример:344234112231G1G3G2G1 изоморфен как помеченный граф, графу G2 и не изоморфен какпомеченный графу G3 .Ясно, что в обычном смысле G1 , G2 , G3 изоморфны.Задача.Сколько существует не изоморфных между собой неориентированныхпомеченных деревьев с n вершинами.75Обозначим число неизоморфных помеченных деревьев через T (n ) .Ясно, чтоT (1) = 1; T (2 ) = 1; T (3) = 3; T (4 ) = 161211213223341311324212431423134214322134231421432413312432143441212312342341Теорема Келли.T (n ) = n n − 2Свои результат по перечислению деревьев А.