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

//умножаем на

Уравнение называется характеристическим уравнением для рекуррентного соотношения .

– 2 действительных различных корня.

.

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

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

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

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

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

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

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

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

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

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

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