Книги Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4Оре О. Теория графов. — 2-е изд.. — М.: Наука, 1980. — С. 336. Wikimedia Foundation . 2010 .
Источник
puuuk 1 В теории графов, дерево — связный (ориентированный или неориентированный) граф, не содержащий циклов (для любой вершины есть один и только один способ добраться до любой другой вершины). Древовидная структура — тип организации, в котором каждый объект связан с хотя бы одним другим.
Степень узла — количество поддеревьев узла
Концевой узел (лист) — узел со степенью нуль.
Узел ветвления — неконцевой узел.
Уровень узла определяется рекурсивным образом:
Уровень корня дерева T равен нулю
Уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева T, содержащего данный узел.
Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.
Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.
Ориентированное дерево — это ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра (входящая степень равна 0). Иногда, термин «ориентированное дерево» сокращают до «дерева».
N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.
N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.
Дерево не имеет кратных ребер и петель.
Любое дерево с n вершинами содержит n − 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда B − P = 1, здесь B — число вершин, P — число рёбер графа.
Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным элементарным путём.
Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами.
Любое дерево является двудольным графом. Любое дерево, содержащее счётное количество вершин, является планарным графом.
Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.(гамильтонов)
Простой цикл — цикл, не проходящий дважды через одну вершину
Цикл — замкнутая цепь. Для орграфов цикл называется контуром.
Цикл (простой цикл) в орграфе — это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.
Цикломатическое число графа — число компонент связности графа плюс число рёбер минус число вершин.
Чи́сла Фибона́ччи — элементы числовой последовательности
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS)
в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (или Фибоначчи) [1] .
Более формально, последовательность чисел Фибоначчи задается рекуррентным соотношением:
Иногда числа Фибоначчи рассматривают и для неположительных номеров n как двусторонне бесконечную последовательность, удовлетворяющую основному соотношению. Члены с такими номерами легко получить с помощью эквивалентной формулы «назад»: Fn = Fn + 2 − Fn + 1 :
Легко видеть, что F − n = ( − 1) n + 1 Fn . Для чисел Фибоначчи с отрицательными индексами остаются верными большинство нижеприведённых свойств.
Тождества где матрицы имеют размер , i — мнимая единица.
· Следствие . Подсчёт определителей даёт
Свойства Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. (Fm ,Fn ) = F (m ,n ) . Следствия: Fm делится на Fn тогда и только тогда, когда m делится на n (за исключением n = 2). В частности, Fm делится на F 3 = 2 (то есть является чётным) только для m = 3k ; Fm делится на F 4 = 3 только для m = 4k ; Fm делится на F 5 = 5 только для m = 5k и т. д. Fm может быть простым только для простых m (с единственным исключением m = 4) (например, число 233 простое, и индекс его, равный 13, также прост). Обратное не верно, первый контрпример — . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми. Последовательность чисел Фибоначчи является частным случаем возвратной последовательности , её характеристический многочленx 2 — x — 1 имеет корни и . Отношения являются подходящими дробямизолотого сечения φ и, в частности, . Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы В 1964 Дж. Кон (J. H. E. Cohn ) доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12: F 0 = 0 2 = 0, F 1 = 1 2 = 1, F 2 = 1 2 = 1, F 12 = 12 2 = 144. При этом для n=0,1,12 верно утверждение Fn = n 2 . Производящей функцией последовательности чисел Фибоначчи является: Множество чисел Фибоначчи совпадает с множеством положительных значений многочленаz (x ,y ) = 2xy 4 + x 2 y 3 − 2x 3 y 2 − y 5 − x 4 y + 2y ,x и y [2] . Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи. Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом 60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом 300, последние три цифры — с периодом 1500, последние четыре — с периодом 15000, последние пять — с периодом 150000 и т.д. Последовательность чисел или функций, в которой каждый следующий член выражается через предыдущий, называется рекуррентной, а формулы, устанавливающие эту связь, — рекуррентными соотношениями . Рекуррентные соотношения удобно использовать при составлении алгоритмов вычисления величин, при этом нет необходимости хранить все промежуточные значения. В выражении следующего значения некоторой величины через ее предыдущие значения и состоит суть метода рекуррентных соотношений.
Если последовательность чисел или функций конечна, то для нахождения значений функций (например, суммы, произведения или n -ого члена ) используется арифметический цикл, т.е. цикл, в котором заранее известно число повторений. Трудность при решении таких задач представляет нахождение самой рекуррентной формулы. Я предлагаю ученикам общий подход к получению рекуррентной формулы, опираясь на метод математической индукции.
Вывод рекуррентной формулы
При решении задач на вычисление сумм (произведений) членов конечных или бесконечных последовательностей, вычисления пределов последовательностей наибольшую трудность представляет получение рекуррентной формулы. Далеко не во всех задачах закономерность, связывающая предыдущий и последующий члены последовательности, очевидна, как, например, в последовательности
Любой член последовательности можно выразить как предыдущий умноженный на , т. е. а n+1 =а n .
А вот в последовательности
выражение, связывающее следующий член с предыдущим, уже не так очевидно. В таком случае я показываю общую схему получения рекуррентной формулы.
Запишем формулу для любого члена последовательности (2)
Тогда n -ый член последовательности принимает вид:
. Разделим ( n +1)-ый член на n -ый.
В результате получим знаменатель последовательности, т.е. тот множитель, который связывает следующий член последовательности с предыдущим.
Следовательно, рекуррентная формула имеет вид
Правильность полученной формулы доказывается индукцией.
Проверим, действительно ли по этой формуле получаем члены последовательности, идущие подряд.
Полученная формула действительно формирует члены последовательности.
Источник
, если вершины u и v различны и вершина u лежит на (единственной!) элементарной цепи, соединяющей корень с вершиной v .
