Граф с какими свойствами называют деревом что такое корень дерева ветви листья

Корневые деревья

Произвольно зафиксируем
некоторую вершину  дерева
 и назовем
ее корнем дерева. Само дерево в этом случае будем называть деревом
с корнем или корневым деревом.

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

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

На рис. 4. 38 приведены примеры дерева
с корнем , 
его ориентированного дерева  и сети сборки .

Деревья графов

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

Существует простой способ определить количество
различных остовов мультиграфа  с  вершинами. Для этого нужно записать матрицу
 размера
, по главной диагонали которой
выписаны степени вершин, а элементы   равны взятому со знаком минус числу ребер,
связывающих вершины  и
,
.
Вычислив минор любого элемента главной диагонали матрицы , получим искомое число возможных
остовов графа.
Например, для графа на рис. 4.39 имеем:

;    .

Следовательно, существует
50 различных деревьев, покрывающих этот граф. Один из 50 остовов мультиграфа
 изображен на рис. 4.39 жирными линиями.

Экстремальные графы

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

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

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

   Для решения задач такого рода разработаны достаточно
эффективные алгоритмы. Далее мы воспользуемся одним из них — алгоритмом Дж. Краскала. Его суть состоит в следующем. На первом шаге выбирается
первая ветвь искомого остова — это ребро графа с
наименьшим (наибольшим) весом. Затем на каждом следующем шаге рассматривается
минимальное (максимальное) по весу ребро и, если оно не образует цикла
с ранее выбранными ветвями, вводится в остов. Построение заканчивается
после отбора для остова  ребер.

Теорема 4.13. Алгоритм Краскала позволяет построить экстремальный
граф любого связного графа.

Пример 4.3. Необходимо построить автомобильные дороги, связывающие
девять поселков так, чтобы их суммарная длина была наименьшей. Любые
два поселка должны быть связаны дорогой либо непосредственно, либо
дорогами, проходящими через другие поселки. Известно расстояние между
поселками (в км):

На первом шаге выбираем самый короткий участок искомой сети дорог, связывающей
поселки. Это дорога длиною 12 км между поселками П1 и П2. Затем добавляем
к ней дороги между П1 и П3 (13 км), П1 и П9 (14 км), П5 и П7 (15 км),
П3 и П4 (18 км). Следующее минимальное расстояние между поселками
равно 19 км. Таково расстояние между П1 и П8 и между П6 и П7. Так
как обе эти дороги не образуют цикла с уже отобранными дорогами, то
обе они добавляются в список. Следующие по длине (25 км и 26 км) дороги
между П1, П2 и П5, П6 нельзя добавлять в наш список — иначе появятся циклы: П1, П2, П3, П2 или П5, П6, П7,
П5. Восьмая и последняя дорога искомого минимального остова имеет
длину 28 км, она проходит между П5 и П8. Минимальный остов, связывающий
девять поселков, изображен на рис. 4.40. Минимальная длина дорог, связывающих поселки, равна
138 км.

                                  Рис.4.40

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

Билет6

1 В теории графов, дерево — связный (ориентированный или неориентированный) граф, не содержащий циклов (для любой вершины есть один и только один способ добраться до любой другой вершины). Древовидная структура — тип организации, в котором каждый объект связан с хотя бы одним другим.

Степень узла — количество поддеревьев узла

Концевой узел (лист) — узел со степенью нуль.

Узел ветвления — неконцевой узел.

Уровень узла определяется рекурсивным образом:

Уровень корня дерева T равен нулю

Уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева дерева T, содержащего данный узел.

Остовное дерево (остов) — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.

Лес — множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев.

Ориентированное дерево — это ориентированный граф без циклов, в котором в каждую вершину, кроме одной, называемой корнем ориентированного дерева, входит одно ребро. В корень ориентированного дерева не входит ни одного ребра (входящая степень равна 0). Иногда, термин «ориентированное дерево» сокращают до «дерева».

N-арное дерево (неориентированное) — это дерево (обычное, неориентированное), в котором степени вершин не превосходят N+1.

N-арное дерево (ориентированное) — это ориентированное дерево, в котором исходящие степени вершин (число исходящих рёбер) не превосходят N.

Свойства

Дерево не имеет кратных ребер и петель.

Любое дерево с n вершинами содержит n − 1 ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда B − P = 1, здесь B — число вершин, P — число рёбер графа.

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

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

Любое дерево является двудольным графом. Любое дерево, содержащее счётное количество вершин, является планарным графом.

Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.(гамильтонов)

Простой цикл — цикл, не проходящий дважды через одну вершину

Цикл — замкнутая цепь. Для орграфов цикл называется контуром.

Цикл (простой цикл) в орграфе — это простой путь длины не менее 1, который начинается и заканчивается в одной и той же вершине.

Цикломатическое число графа — число компонент связности графа плюс число рёбер минус число вершин.

2

Чи́сла Фибона́ччи — элементы числовой последовательности

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 + 1Fn. Для чисел Фибоначчи с отрицательными индексами остаются верными большинство нижеприведённых свойств.

Тождества

И более общие формулы:

• Числа Фибоначчи представляются значениями континуант на наборе единиц: , то есть

, а также ,

где матрицы имеют размер , i — мнимая единица.

• Числа Фибоначчи можно выразить через многочлены Чебышёва:

• Для любого n,

·        Следствие. Подсчёт определителей даёт

Свойства

• Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. (Fm,Fn) = F(m,n). Следствия:
  • Fm делится на Fn тогда и только тогда, когда m делится на n (за исключением n = 2). В частности, Fm делится на F3 = 2 (то есть является чётным) только для m = 3k; Fm делится на F4 = 3 только для m = 4k; Fm делится на F5 = 5 только для m = 5k и т. д.
  • Fm может быть простым только для простых m (с единственным исключением m = 4) (например, число 233 простое, и индекс его, равный 13, также прост). Обратное не верно, первый контрпример — . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.

• Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен x2 — x — 1 имеет корни и .

• Отношения являются подходящими дробями золотого сечения φ и, в частности, .
• Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы

.

• В 1964 Дж. Кон (J. H. E. Cohn) доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12: F0 = 02 = 0, F1 = 12 = 1, F2 = 12 = 1, F12 = 122 = 144. При этом для n=0,1,12 верно утверждение Fn = n2.

• Производящей функцией последовательности чисел Фибоначчи является:

• Множество чисел Фибоначчи совпадает с множеством положительных значений многочлена
      z(x,y) = 2xy4 + x2y3 − 2x3y2 − y5 − x4y + 2y,
  на множестве неотрицательных целых чисел x и y [2].

• Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.

• Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом 60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом 300, последние три цифры — с периодом 1500, последние четыре — с периодом 15000, последние пять — с периодом 150000 и т.д.

.Рекуррентные соотношения

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

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

Вывод рекуррентной формулы

При решении задач на вычисление сумм (произведений) членов конечных или бесконечных последовательностей, вычисления пределов последовательностей наибольшую трудность представляет получение рекуррентной формулы. Далеко не во всех задачах закономерность, связывающая предыдущий и последующий члены последовательности, очевидна, как, например, в последовательности

Любой член последовательности можно выразить как предыдущий умноженный на , т. е. аn+1=аn .

А вот в последовательности

выражение, связывающее следующий член с предыдущим, уже не так очевидно. В таком случае я показываю общую схему получения рекуррентной формулы.

Запишем формулу для любого члена последовательности (2)

Тогда n-ый член последовательности принимает вид:

. Разделим (n+1)-ый член на n-ый.

В результате получим знаменатель последовательности, т.е. тот множитель, который связывает следующий член последовательности с предыдущим.

Следовательно, рекуррентная формула имеет вид

Правильность полученной формулы доказывается индукцией.

Проверим, действительно ли по этой формуле получаем члены последовательности, идущие подряд.

При n=1

При n=2

При n=3 и т.д.

Полученная формула действительно формирует члены последовательности.