Дерево графа содержащее все его вершины называется

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 как двусторонне бесконечную последовательность, удовлетворяющую основному соотношению. Члены с такими номерами легко получить с помощью эквивалентной формулы «назад»: F_n = F_{n + 2} − F_{n + 1}:

Легко видеть, что F _{− n} = ( − 1) n + 1 F_n. Для чисел Фибоначчи с отрицательными индексами остаются верными большинство нижеприведённых свойств.

Тождества

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

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

Свойства

• Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. (F_m,F_n) = F_(m,n). Следствия:
  • F_m делится на F_n тогда и только тогда, когда m делится на n (за исключением n = 2). В частности, F_m делится на F₃ = 2 (то есть является чётным) только для m = 3k; F_m делится на F₄ = 3 только для m = 4k; F_m делится на F₅ = 5 только для m = 5k и т. д.
  • F_m может быть простым только для простых m (с единственным исключением m = 4) (например, число 233 простое, и индекс его, равный 13, также прост). Обратное не верно, первый контрпример — . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.
  • Последовательность чисел Фибоначчи является частным случаем возвратной последовательности , её характеристический многочленx 2 — x — 1 имеет корни и .
  • Отношения являются подходящими дробямизолотого сечения φ и, в частности, .
  • Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы
  • В 1964 Дж. Кон (J. H. E. Cohn) доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12: F₀ = 0 2 = 0, F₁ = 1 2 = 1, F₂ = 1 2 = 1, F₁₂ = 12 2 = 144. При этом для n=0,1,12 верно утверждение F_n = 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 -ый.

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

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

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

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

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

  Источник

  §2. Деревья, остовы, разрезы

  Деревом называется связный граф, не содержащий циклов. Граф, не имеющий циклов и состоящий из k компонент, называется лесом из k деревьев. Можно показать, что граф Г с n вершинами является деревом тогда и только тогда, когда он связен и число его ребер равно (n—1).

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

  

  Если остов выбран, то составляющие его рёбра называются ветвями, а рёбра, введение которых приводит к образованию замкнутых контуров, называются хордами. Количество хорд определяется по формуле, где— количество хорд,— количество рёбер,— количество вершин. Для приведенных выше остовов имеется по три хорды: (e₁, e₃, e₇), (e₂, e₃, e₇) и (e₂, e₄, e₇), соответственно. Число хорд графа называется дефицитом графа или числом Бетти. Число Бетти равно числу рёбер графа, которые надо удалить из него, чтобы получить дерево.

  

  Многие важные задачи, возникающие, например, при изучении потоков в сетях (см. §7), приводят к понятию разреза. Перед тем, как дать его формальное определение, введем более общее понятие. Пусть Г=(V, Е) – связный граф и – некоторое подмножество его рёбер. При этом F называется разделяющим множеством тогда и только тогда, когда подграф Г‘=(V, Е-F) несвязен. Здесь через Е-F обозначено множество ребер, которые принадлежат Е, но не принадлежат F. Разделяющие множества всегда существуют (если граф Г имеет, по крайней мере, две вершины), так как всегда можно положить F=E.

  В общем случае, если задан связный граф Г=(V, Е), и множество его вершин разбито на два непустых подмножества W и W‘, то множество ребер, соединяющих W и W‘, называется разрезом. Для любого W это множество ребер будет непусто в силу связности графа Г, и следовательно, разрез определен.

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

  Граф называется ориентированным, или орграфом, если на каждом ребре задано направление, т. е. у каждого ребра фиксируются начало и конец. Направление ребра указывается стрелкой. Такие направленные ребра называются дугами. Цепью в орграфе называется такая последовательность дуг, в которой каждые две соседних дуги имеют общую вершину и никакая дуга не встречается более одного раза. Если направление цепи совпадает с направлением всех принадлежащих ей дуг, то цепь называется путем. В орграфах циклом называется путь, начало и конец которого совпадают.

  

  На рис. 3 дуги (e₁, e₄, e₅) образуют цепь, а дуги (e₁, e₂, e₅) – путь. Последовательность дуг (e₁, e₂, e₃) составляет цикл, а последовательность (e₁, e₂, e₄) не является циклом.

  Каждая дуга считается положительно инцидентной для своей конечной вершины и отрицательно инцидентной для начальной. Число дуг, положительно инцидентных вершине v, называется положительной степенью v и обозначается δ + (v). Аналогично определяется отрицательная степень δ – (v). Например, на рис. 3 ребро e₃ положительно инцидентно вершине v₁ , рёбра e₁, e₄ – отрицательно, следовательно, δ + (v)=1, δ – (v)=2.

  При решении задач, связанных с графами, на компьютере, графическое задание орграфа оказывается неудобным. Вместо него используются так называемые матрицы инцидентности, которые определяются следующим образом. Пусть некоторый граф Г имеет m вершин v₁… v_m и n рёбер e₁… e_n. Матрица инцидентности будет состоять из m строк и n столбцов, каждая строка соответствует вершине, столбец – ребру. Элемент a_ij, соответствующий вершине v_i и ребру e_j, равен +1, если вершина является начальной для ребра, -1 – если конечной, 2 – если и то и другое (т.е. если e_j – петля в вершине v_i), 0 – в остальных случаях. Таким образом, в каждом столбце имеется один или два отличных от нуля элемента. Например, для графа, изображенного на рис. 3, матрица инцидентности имеет вид:

  Источник

  Читайте также:  Потолок комбинированный натяжной дерево