Решение рекуррентных уравнений

3. u_n+2 = u_n+1 + 2u_n , u₀ = 1, u₁ = 1;

4. u_n+2 = u_n+1 + 2u_n , u₀ = 0, u₁ = 1 ;

5. u_n+2 = 3u_n+1 – 2u_n , u₀ = 1, u₁ = 1 ;

6. u_n+2 = u_n+1 + 6u_n , u₀ = a, u₁ = b ;

7. u_n+2 – 4u_n+1 – 5u_n = 0, u₀ = 8, u₁ = 10 ;

Ответ: u_n = 7+3ⁿ

3. u_n+3 – 3u_n+2 +u_n+1– 3u_n = 0, u₀ = 1, u₁ = 3, u₂ = 8 ;

Ответ: u_2n= (93²ⁿ+(-1)ⁿ)/10, u_2n+1= (93²ⁿ⁺¹+3(-1)ⁿ)/10, n≥0.

3. u_n+3 + u_n+2 – u_n+1– u_n = 0, u₀ = 1, u₁ = 2, u₂ = 3 ;

Ответ: u_n=(-1)ⁿ(n-1)+2

3. u_n+2 – 4u_n+1 + 4u_n = 0, u₀ = a, u₁ = b ;

4. u_n+2 = 2u_n+1 – 2u_n , u₀ = 1, u₁ = 2 .

Указание: Производящая функция последовательности u_n

u(x)=

Ответ:

3. u_n+3 = 3u_n+2 – 3u_n+1+ u_n , u₀ = 1, u₁ = 3, u₂ = 3 ;

Указание: Искать решение в виде u_n=A+ Bn + Cn².

3. u_n+3 = – 3u_n+2 – 3u_n+1– u_n , u₀ = 0, u₁ = 1, u₂ = –2 ;

4. u_n+2 = u_n+1 – u_n , u₀ = 1, u₁ = 9 ; Ответ:

5. u_n+2 = 2u_n+1 – 4u_n , u₀ = 1, u₁ = 2 ; Ответ:

4. ТЕОРИЯ ГРАФОВ

Основатель теории графов – Леонардо Эйлер (1707 – 1783), крупнейший математик 18 века. Эйлер работал в Санкт-Петербурге в 1725-1741 годах и в 1766-1783. История теория графов хорошо описана в [16]. По теории графов рекомендуем книги [3], [5], [9], [14], [20].

4.1. Эйлеровы графы

Задача о Кенигсбергских мостах(Эйлер, 1736 год). На рисунке 4.1 слева изображена часть реки Прейгель, находящейся в Кенигсберге (ныне Калининграде). Буква Л обозначает левый берег, П – правый, А и Б – острова.

Требуется найти маршрут пешехода, проходящий через все мосты, через каждый мост пешеход должен пройти ровно один раз. Эйлер доказал, что эта задача не имеет решений.

Сначала напомним определение простого графа, приведенное в пп. 1.5. Для произвольного множества Vобозначим черезP₂(V)множество, состоящее из подмножеств {v₁,v₂}V, каждое из которых состоит из двух не равных между собой элементов.

Определение 1. Простым (неориентированным) графом=(V,E)называется пара, состоящая из множестваVи произвольного подмножестваEP₂(V). Элементы изVназываютсявершинами, а изE–ребрами.

Вершины простого графа изображаются как точки или круги, а ребра – как отрезки.

Рис. 4.1. Схема мостов и соответствующий ей граф

Обобщим определение простого графа.

Определение 2.Графомназывается тройка (V,E,), состоящая из множествV,Eи функции:E P₂(V), сопоставляющей каждомуeEнеупорядоченную пару{u,v}. Элементы изEназываютсяребрами, элементы изV –вершинами.

Если (e)={u,v}, то вершины uиvназываютсяконцамиребраe. В этом случаеuиvназываютсясмежными вершинамииинцидентнымиребруe. Если концы ребраeравны ((e)состоит из единственного элемента), то реброeназываетсяпетлей.

Степенью вершиныvназывается число инцидентных ей ребер. Ребро, являющееся петлей, учитывается два раза. В частности, петля дает степень 2. Для графа, соответствующего схеме Кенигсбергских мостов, степени вершин равны 3, 3, 3 и 5. Путем в графе называется последовательность вершин и реберv₀₁v₁₂v₂ ∙∙∙ v_n-1_nv_n , таких чтоv_iиv_i+1инцидентны ребрам_i+1, для всехi{1,2, ∙ ∙ ∙ ,n}. Граф, допускающий путь, не содержащий кратных ребер и содержащий все ребра, называетсяэйлеровым. Такой путь тоже называетсяэйлеровым.

На рис. 4.1 справа изображен граф, ребра которого соответствуют мостам, а вершины – частям суши. Задача о Кенигсбергских мостах имеет решение тогда и только тогда, когда этот граф является эйлеровым.