Дискретка / diskretochka (1)

Решение линейного рекуррентного соотношение второго порядка в случае равных

Если у нас есть линейное рекуррентное соотношение второго порядка, то его решением является:

17. Теорема об общем решении линейных рекуррентных соотношений с постоянными коэффициентами k- го порядка. Решение

рекуррентных соотношений с постоянными коэффициентами k- го порядка с помощью характеристического уравнения.

Теорема (об общем решении линейного рекуррентного соотношения k-ого

Метод решения Л.Р.С. k-го порядка с пост. коэф.

Записать и решить характеристическое уравнение для Л.Р.С. k-го порядка.

На основании т. об общем решении записать общее решение данного Р.С. (теорема выше)

Если заданы нач. условия, то найти значения констант, которые удовлетворяют нач. задан. условиям.

18.Производящая функция. Сумма производящих функций, операция подстановки.

19.Произведение и деление производящих функций.

20. Теорема о разложении функции.

21.Теорема о производящей функции для последовательности, задаваемой линейным рекуррентным соотношением. Теорема о

рациональной производящей функции.

22.Решение рекуррентных соотношений с помощью производящих функций.

23.Ориентированные и неориентированные графы.

Ориентированным графом называется пара , где - конечное множество вершин, а – отношение смежности, а матрица называется матрицей смежности. Пара (u,v) называется дугой орграфа, с началом u и концом v.

Неориентированным графом называется пара , где симметричное и антирефлексивное отношение. - симметричность. – антирефлексивность.

Симметризация орграфа (превращение в граф) – неориентированный граф (без дуг и петель) , где тождественное отношение (исключение петли).

Ворграфе степенью исхода вершины v называется число - равное количеству дуг, исходных из v. .

Ворграфе степенью захода вершины v называется число - равное количеству

, то спецификация: , где и . Если неориентированный граф, то .

Если вершина не имеет ребер (в графе), или дуг (в орграфе), то она называется

изолированной.

Для неориентированного графа:

1)Степенное множество графа – набор степеней его вершин. {1,2,…,n}

2)Вектор степеней графа – вектор, компонентами которого являются степени всех вершин графа, записанных по убыванию. (3,3,2,1)

24.Полный граф, дополнение, объединение, соединение графов.

Полный граф – граф, в котором любые две вершины соединены ребром .

Дополнение графа - . Объединение графов - Соединение графов -

25.Теорема о степенном множестве.

Теорема о степенном множестве. Для любого множества натуральных чисел

, где , найдется граф, число вершин которого равно и для которого множество является степенным множеством.

Доказательство.

По индукции.

Предположим, что она справедлива для чисел . Докажем, что теорема справедлива для чисел

.

Найдется граф, у которого число вершин будет , и у которого это множество будет степенным множеством.

Рассмотрим множество натуральных чисел:

, где . Число чисел <k , то есть найдется граф, у которого число вершин равно и оно является степенным множеством. число вершин равно .

Рассмотрим граф, построенный следующим образом:. Посчитаем число вершин . Покажем, что это действительно степенное множество этого графа

. Такое число есть в множестве.

– это степень вершины из . Граф может иметь любое число вершин из .

Предположим, оно равно , тогда , такое число есть.

=>Для любого натурального множества найдется граф, у которого это множество будет степенным, и т.д.

26.Теорема о соотношении суммы степеней вершин и числа ребер

(лемма о рукопожатии.)

Теорема. Лемма о рукопожатии.

В графе справедливы утверждения:

1)сумма степеней всех вершин равна удвоенному числу ребер (число ребер-m).

2)количество нечетных вершин четно.

3)если в графе вершин , то мощность степенного множества не превышает , (то есть, по крайней мере, 2 вершины имеют одинаковую степень)

Четная вершина графа – вершина с четной степенью.

Нечетная вершина графа – вершина с нечетной степенью.

Доказательство.

1)Очевидно.

2)

3)

Возможные степени вершин: у графа всего чисел, числа 0 и встретиться одновременно не могут => есть изолированная вершина => степень не может быть .

27.Алгоритм построения графа, по вектору степеней.

Пусть – вектор степеней какого-то графа. Алгоритм построения:

1)Изображается n точек, и им присваиваются метки: . В качестве начальной точки, выбирается 1-вая и ей присваивается значение 2)Начальная точка соединяется линиями с другими точками, в порядке убывания их меток.

3)Метка начальной точки кладется равной 0, метки всех точек, соединенных с начальной уменьшаются на 1.

4)Если метки всех точек равны 0, то конец алгоритма. Иначе, в качестве начальной точки, выбрать точку с максимальной меткой (одну из них), положить равной метке точки, выбранной в качестве начальной.

28.Изоморфизм графов. Теорема об изоморфизме графов.

Пусть даны графы: .

Взаимно-однозначное соответствие называется изоморфизмом, если оно сохраняет отношение смежности:

Доказательство.

Надо доказать: - это означает, что:

(*)

Необходимость.

29.Проверка на изоморфизм 2-х графов по их матрицам смежности.

1)Выписывается матрица предполагаемого изоморфизма , как матрица с неопределенными коэффициентами. .

2)Составляем матричное уравнение. Решаем систему, находим . 3)Если в каждом столбце и строке ровно одна 1, то изоморфизм есть, иначе – нет.