Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 23

Путь – последовательность ребер вида , т.е. конец предыдущего ребра, является началом следующего ребра. Цикл – это путь, у которого начало первого ребра совпадает с концом последнего, т.е. i_k = i₁.

Возведем в квадрат матрицу смежности. Что будет её элементами?

A = {a_ij Î{0,1}},A²= {b_ij}, причем . = числу таких k, при которых a_ik = 1 и a_kj = 1,т.е. есть ребра (i, k) и (k, j), есть путь длины 2 из i в j.

Т.о. b_ij есть число различных путей длины 2 из i-й вершины в j-ую. A^k- число путей длины k из i в j, причем пути могут не быть простыми (= без циклов).

Два графа называются изоморфными, если существует такая нумерация вершин второго графа, при которой матрицы смежности обоих графов совпадут.

Трудоемкость проверки изоморфности перебором нумераций равна O( n²× n!).
Степень вершины i – это число единиц в i–ой строке матрицы смежности.

Теорема. Графы изоморфны Þ наборы степеней вершин у них совпадают.

Граф связный, если между любыми двумя вершинами есть путь.

Дерево – связный граф без циклов = связный граф, содержащий n-1 ребро.

Сколько различных деревьев существует на n вершинах?

№17. Алгоритм кодирования деревьев.

Пусть есть дерево

На k-м шаге мы выбираем в векторе степеней S самую левую вершину U_k с единичной степенью, удаляем ее, а у нее и ее отца O_k уменьшаем степень на 1.

На основе вектора S и картинки мы построим 2 вектора U и О (вместо картинки можно использовать матрицу смежности). Размерности векторов U и O = n-1. По построению пара (U_i, O_i) является ребром дерева. Все U_k – различны (удалить вершину можно только 1 раз), но в векторе U не хватает вершины 9, ее мы перекинем из O, и получим вектор O^*: dim(O^*)=n-2; и вектор U^*: dim(U^*)=n. Зная O^*, легко восстановить дерево. В самом деле, пусть N(i,A) - кратность числа i в векторе A. Очевидно, N(i,U^*)=1 для всех i. Восстанавливаем S:
S_i = N(i,O) + N(i,U) = N(i,O^*) + N(i,U^*) = N(i,O^*) + 1. Зная S, вычислим U₁ Þ 1-е удаленное ребро графа = (U₁, O₁). Уменьшив на 1 степени вершин U₁ и O₁, найдем U₂ и 2-е ребро графа (U₂, O₂) и т.д. Получили алгоритм декодирования. Рисовать восстанавливаемые ребра удобно в порядке, обратном удалению!

Соответствие между O^* и деревом – взаимнооднозначное (докажите),è число деревьев с помеченными вершинами = числу различных векторов O^* = n^n-2.

Напомним, что число неориентированных графов на n вершинах ‑2^n (n-1)/2.

Пример: Если n=3 и матрицу смежности неориентированного графа превратить в вектор из 0 и 1, то деревьям соответствуют 3 вектора из 8-ми: 110, 101 и 011.

Если n=4, то 4²=16 деревьев из 2⁶=64 неориентированных графов без петель.

Если n=5, то 5³=125 деревьев из 2¹⁰=1024 графов

Сколько различных неизоморфных деревьев можно построить на n вершинах?

n=3 (1 дерево):                                              n=5 (3 дерева):

n=4 (2 дерева):

Пусть S_i – степень вершин, R – количество ребер дерева Þ S S_i = 2*R = 2*(n-1). Выпишем упорядоченные по убыванию вектора степеней вершин при n=4:

2 2 1 1  и  2 1 1 1. Они различны, Þ графы неизоморфны. S S_i =2*3 = 6.

Сколько различных упорядоченных векторов степеней вершин?

Есть n мест. На них нужно разместить 2(n-1) единиц (не менее одной на место).