Дискретная математика 3 (стр. 5 из 10)

Найдем общее решение соответствующего однородного рекуррентного соотношения

или

. Начальные условия изменятся следующим образом

С₁=3, С₂=-2

К(х)=1-3х+2х²

С(х)=U(x)×K(x)=

(1-3x+2x²)=

-3x

+ +2x²

F(x)=x²-3x+2=(x-2)(x-1)

K(x)=(1-2x)(1-x)

U(x)=

Итак,

§11. Числа Фибоначчи.

Последовательность Фибоначчи задается рекуррентным соотношением u_n₊₂=u_n₊₁+u_n, u₀=1, u₁=1. То есть 1, 1, 2, 3, 5, 8, 13, 21, …. Найдем u_n.

K(x)=1-x-x²

U(x)=

С(x)=K(x)×U(x)=u₀+u₁x+u₂x²+…-u₀x-u₁x²-u₂x³-…-u₀x²-u₁x³-u₂x⁴-…=

=u₀+u₁x-u₀x=1+x-x=1

F(x)=x²-x-1=

K(x)=

U(x)=

Þ B=

, A=1-B=

U(x)=

u_n=

Покажем, что u_n и u_n₊₁ – взаимно простые числа. Воспользуемся методом математической индукции.

База индукции. (u₀, u₁)=1, выполняется.

Индукционное предположение. Допустим, что (u_n_-1, u_n)=1.

Шаг индукции. Докажем, что (u_n, u_n₊₁)=1.

Действительно, если предположить, что (u_n₊₁, u_n)=d>1, то получаем u_n₊₁∶d и u_n∶d, но u_n₊₁=u_n+u_n_-1. Два члена последнего равенства делятся на d, а значит, и третий член u_n_-1 должен делится на d. Следовательно, (u_n, u_n_-1)=d. Получили противоречие с индукционным предположением. Значит, (u_n, u_n+1)=1.

Введение в теорию графов

Множество самых разнообразных задач естественно формулируется в терминах точек и связей между ними, то есть в терминах графов.

Первой работой теории графов, как математической дисциплины, считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кенигсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.

С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема метрополитена. Точками на ней представлены станции, а линиями – пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы строим так называемое генеалогическое древо. И это древо – граф.

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

§1. Основные понятия теории графов.

Определение 1. Пара (V(G), E(G)) называется простым графом, если V(G) – непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а E(G) – конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами (или линиями).

Иногда V(G) называют множеством вершин, а E(G) – множеством ребер графа G.

#1. V(G)={u, v, w, z},

E(G)={{u, v}, {v, w}, {u, w}, {w, z}}.

Говорят, что ребро {u, v} соединяет вершины u и v.

Отметим, что E(G) является множеством, (то есть каждый элемент в нем может встречаться один раз), а, значит, в простом графе каждую пару вершин можно соединить не более чем одним ребром.

Определение 2.Общим графом, или просто графом называется пара (V(G), E(G)) где V(G) – непустое конечное множество элементов, называемых вершинами, а E(G) – конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами.

V(G) – множество вершин,

E(G) – семейство ребер.

#2. V(G)={u, v, w, z},

E(G)={{u, v}, {v, v}, {v, v}, {v, w}, {v, w}, {u, w}, {u, w}, {u, w}, {w, z}}.

Определение 3.Орграфом (ориентированным графом) D называется пара (V(D), A(D)) где V(D) – непустое конечное множество элементов, называемых вершинами, а A(D) – конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами).

Дуга, у которой вершина v является первым элементом, а вершина w – вторым, называется дугой из v в w и обозначается (v, w).

#3.

V(D)={u, v, w, z},

A(D)={(u, v), (v, v), (v, w), (w, v), (w, v), (w, u), (w, z)}.

Определение 4. Граф называется псевдографом, если в нем допускаются петли и кратные ребра, то есть две вершины могут быть соединены более чем одним ребром. Псевдограф без петель называется мультиграфом.

#4.

Псевдограф Мультиграф

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

Основные понятия для неориентированных и ориентированных графов удобно вводить «параллельно». Такое изложение позволит наглядно сопоставить соответствующие понятия.

*Неориентированные графы*	*Ориентированные графы*
Неориентированный графG задается двумя множествами G=(V, E), где V – конечное множество, элементы которого называют вершинами или узлами; E – множество неупорядоченных пар на V, то есть подмножество множества двухэлементных подмножеств V, элементы которого называют ребрами. Для каждого ребра {u, v}ÎE считаем, что u и v – различные вершины.	Ориентированный графG задается двумя множествами G=(V, E), где V – конечное множество, элементы которого называют вершинами или узлами; E – множество упорядоченных пар на V, то есть подмножество множества V´V, элементы которого называют дугами.
Если ребро e=(u, v), то говорят, что ребро e соединяет вершины u и v, и обозначают это u v; если необходимо указывают имя графа G: u v	Если дуга e=(u, v), то говорят, что дуга e ведет из вершины u в вершину v, и обозначают это u v; если необходимо указывают имя графа G: u v
Вершины u и v, соединенные ребром (u v), называют смежными, а также концами ребра {u, v}. Если u v, говорят, что вершины u и v связаны отношением непосредственной достижимости.	Вершины u и v такие, что из вершины u в вершину v ведет дуга (u v), называют смежными, причем u называют началом, а v – концом дуги (u, v). Дуга, начало и конец которой есть одна и та же вершина, называется петлей. Если u v, то говорят, что вершины u и v связаны отношением непосредственной достижимости.
Ребро е называется инцидентным вершине v, если она является одним из его концов.	Дугу (u, v) называют заходящей в v и исходящей из вершины u. Дугу называют инцидентной вершине v, если она заходит в v или исходить из нее.
Степенью вершиныv называют число dg v всех инцидентных ей ребер (при вычислении степени вершины v петля учитывается два раза, а не один).	Полустепенью захода вершины v называют число dg^-(v) заходящих в нее дуг, а полустепенью исхода вершины v – число dg⁺(v) исходящих из нее дуг. Степень вершины v, обозначаемая dg(v) – это сумма полустепеней захода и исхода.
Цепь в неориентированном графе G – это последовательность вершин (конечная или бесконечная) v₀, v₁, …, v_n, … такая, что v_i v_i₊₁ для любого i, если v_i₊₁ существует.	Путь в ориентированном графе G – это последовательность вершин (конечная или бесконечная) v₀, v₁, …, v_n, … такая, что v_i v_i₊₁ для любого i, если v_i₊₁ существует.
Для конечной цепи v₀, v₁, …, v_n число n (n³0) называют длиной цепи. Таким образом, длина цепи есть число ее ребер, то есть всех ребер, соединяющих вершины v_i и v_i₊₁ (i= ). Цепь длины 0 – это произвольная вершина графа.	Для конечного пути v₀, v₁, …, v_n число n (n³0) называют длиной пути (n³0). Тем самым длина пути есть число его дуг, то есть всех дуг, которые ведут из вершины v_i в вершину v_i₊₁ (i= ). Путь длины 0 – это произвольная вершина графа.
Простая цепь – это цепь, все вершины которой, кроме, быть может, первой и последней, попарно различны и все ребра попарно различны.	Простой путь – это путь, все вершины которого, кроме, быть может, первой и последней, попарно различны.
Простая цепь ненулевой длины с совпадающими концами называется циклом.	Простой путь ненулевой длины, начало и конец которого совпадают, называется контуром.
Произвольную цепь ненулевой длины с совпадающими концами, все ребра которой попарно различны, называют замкнутой цепью.	Произвольный путь ненулевой длины, начало и конец которого совпадают, называют замкнутым путем.
Неориентированный граф, не содержащий циклов, называется ациклическим графом.	Ориентированный граф, не содержащий контуров, называется бесконтурным графом.

#5. V={v₁, v₂, v₃, v₄, v₅, v₆, v₇},