Как найти валентность графа

Лекция 7. Графы и деревья

1. Способы задания графа в программировании

1.1. Неформальное определение понятия графа

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

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

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

Ребрам графа может приписываться некоторая ориентация (при изображении на дугах ставится «стрелочка») — в этом случае граф называется ориентированным. В противном случае граф называется неориентированным.

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

Кроме того, иногда вершинам графа приписываются некоторые значения (данные). В этом случае можно, например, все вершины графа проиндесировать значениями 1,2,3,...,n (начиная с 1 и заканчивая числом вершин n, без пропусков). Тогда данные, связанные с вершинами могут хранится в отдельном одномерном массиве длины n, каждый i-ый элемент которого должен соответствовать i-ой вершине графа.

1.2. Формальные определения

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

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

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

Определение. Говорят, что над множеством $A$ определено мультимножество, если на этом множестве задана функция принадлежности $mu: A to {{0,1,2,…}}$, причем $a in A Leftrightarrow mu(a)>0$, при этом значение $mu(a)$ называется кратностью элемента $a$.

В частном случае, когда кратнасти элементов некоторого мультимножества не превышают 1, имеем обычное множество.

Перейдем теперь к понятию графа. Пусть $V$ — множество вершин (некоторое абстрактное множество), и пусть $overline{V}=Vcup{}$, где $$ — это символ, обозначающий факт отсутствия вершины (иногда отсутствующую вершину $*$ называют еще внешней вершиной).

Определение. Ориентированным мультиграфом называется пара $(V, varepsilon)$, где $varepsilon$ — некоторе отображение $overline{V} times overline{V} to {0,1,2,…}$.

При этом $E={(u,v)inoverline{V} times overline{V} |varepsilon((u,v))ne 0}$ — множестово всех ребер графа.

Употребляя термин — граф, мы имеем ввиду сейчас самый общий случай: ориенированный мультиграф. Граф часто обозначают одной буквой, например $G=(V, varepsilon)$.

В частности, если ребра ориентированного мультиграфа не имеют кратностей больших 1, то можно считать, что $G=(V,E)$, т.е. — что граф представляет собой пару множеств: множество вершин и множество ребер.

В любом случае, при условии $varepsilon((u,v)) ne 0$, $(u,v)$ — это обычное ребро. При этом, считается, что ребра $(u,v)$ и $(v,u)$ имеют противоположную ориентацию.

При этом ${(u,) | u in V, varepsilon((u,))ne 0} cup {(,v) |v in V, varepsilon((,v))ne 0 }$ — это множество всех висячих ребер.

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

Ребро вида $(u,u)$ называется петлей.

Граф без петель, без кратных и висячих ребер называется простым графом. Именно с простыми графами чаще всего приходится иметь дело.

Неориентированный граф. В частности, если ориетированный простой граф обладает следующим свойством:
$(u,v) in E Leftrightarrow (v,u) in E (une v)$, то такой граф можно считать неориентированным графом, если каждую пару противонаправленных ребер рассматривать как одно ненаправленное ребро.

1.3. Способы задания графа

Из сказанного в предыдущем разделе должно быть ясно, что задать граф — означает задать множество его вершин $V$ и функцию принадлежности $varepsilon: overline{V} times overline{V} to {0,1,2,…}$.

Обычно считается, что $V={1,2,3,…,n}$, тогда функция принадлежности $varepsilon$ может быть задана квадратной матрицей размера $ntimes n$, в которой $i,j$-элемент равет $varepsilon((i,j))$.

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

Функцию принадлежности можно задать также с помощью матрицы инциденций, т.е. с помощью прямоугольной матрицы, строки которой индексируются номерами вершин графа, а столбцы — номерами ребер (имеется ввиду, что множество $E$ каким-либо образом, безразлично каким, упорядочено), при этом её $i,j$-элемент равен 0, если только $e_j[1]ne i$, и $varepsilon((i,e_j[2]))$, в противном случае.

Здесь по умолчанию предполагалось следующее соглашение об обозначениях: если $e_j=(u,v)$, то $e_j[1]=u, e_j[2]=v$.

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

1.4. Использование разреженных матриц

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

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

Для Julia имеется соответствующий пакет SparseArrays (требующий предварительной установки), в котором для представления разреженных матриц определен специальный тип SparseMatrixCSC, позволяющий экономномить расходование компьютерной памяти, и при этом выполнять с такими матрицами привычные операции.

Например,

using SparseArrays
I=[1, 2, 5, 4, 5] # - индексы строк с ненулевыми значениями
J=[2, 2, 2, 3, 5] # - индексы столбцов с ненулевыми значениями
V=[10, 10, 10, 20, 30] # - сами не нулевые значения
A=sparse(I,J,V)

Тогда вывод разреженной матрицы A на экран будет иметь вид:

5×5 SparseMatrixCSC{Int64, Int64} with 5 stored entries:
 ⋅  10   ⋅  ⋅   ⋅
 ⋅  10   ⋅  ⋅   ⋅
 ⋅   ⋅   ⋅  ⋅   ⋅
 ⋅   ⋅  20  ⋅   ⋅
 ⋅  10   ⋅  ⋅  30

где точками отмечены позиции с нулевыми значениями.

При этом если бы среди элементов вектора V были бы нули, то эти нули не формально рассматривались бы как ненулевые значения, в том сысле, что они бы всё равно реально размещались в памяти компьютера. Например:

I = [1, 2, 5, 4, 5] 
J = [2, 2, 2, 3, 5] 
V = [10, 0, 10, 20, 30]
A = sparse(I,J,V)

5×5 SparseMatrixCSC{Int64, Int64} with 5 stored entries:
 ⋅  10   ⋅  ⋅   ⋅
 ⋅   0   ⋅  ⋅   ⋅
 ⋅   ⋅   ⋅  ⋅   ⋅
 ⋅   ⋅  20  ⋅   ⋅
 ⋅  10   ⋅  ⋅  30

(новое нулевое значение в выводе не заменено точкой, это означает, что оно реально размещено в памяти).

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

При этом, если требуется перебрать все формально ненулевые элементы (реально размещенные в памяти) разреженной матрицы, то для этого дополнительно имеются специальные функции rowvals, nonzeros и nzrange, позволяющие это делать экономично, с учетом структуры разреженной матрицы, например:

rows = rowvals(A) 
# rowvals(A) - возвращает вектор индексов строк A, содержащих ФОРМАЛЬНО не нулевые значения
  vals = nonzeros(A) 
  # nonzeros(A) - возвращает вектор значений всех ФОРМАЛЬНО не нулевых элементов матрицы A 
  m, n = size(A)
  for j = 1:n
     for i in nzrange(A, j) 
     #= 
     если в j-ом столбце нет формально не нулевых элементов, то диапазон индексов, возвращаемых функцией nzrange(A, j) будет пустым
     =#
        index_row = rows[i]
        val = vals[i]
        # val - очередное ФОРМАЛЬНО не нулевое значение, которое в матрице A имеет индексы  (index_row, j) 
     end
  end

1.5. Список смежностей

Всё отмеченное в предыдущем разделе делает возможным эффективно использовать разреженные матрицы в том числе и для представления графов.

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

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

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

Рассмотрим, например, полный граф с 5 вершинами (простой граф называется полным, если в нём каждая вершина смежна со всеми остальными). Представление этого графа списком смежностей будет иметь вид:

G=[[2,3,4,5],
   [1,3,4,5],
   [1,2,4,5],
   [1,2,3,5],
   [1,2,3,4]]

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

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

G=[[2,3,4,5],
   [],
   [1,2,4,5],
   [1,2,3,5],
   [1,2,3,4]]

У этого графа во вторую вершину направлены ребра из всех остальных вершин, но из ней в обратном направлении нет ни одного исходящего ребра.

В некоторых случаях список смежностей удобно представлять не в виде одномерного массива (вектора), а в виде значения типа Dict, т.е. в виде словаря. Словарь состоит из пар типа Pair (есть в Julia такой тип данных), при этом каждая пара типа Pair задается в виде: key => value_of_key (ключ => значение_соответствующее_ключу). Тип Dict, как и тип Pair, является двухпараметрическим, первый параметр определяет тип ключа, а второй — тип соответствующего значения.

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

G=Dict{Int,Vector{Int}}([
                         1=>[2,3,4,5], 
                         2=>[],
                         3=>[1,2,4,5],
                         4=>[1,2,3,5],
                         5=>[1,2,3,4]
                        ])

Аргументом функции Dict{Int,Vector{Int}} в данном случае является вектор типа `Vector{Pair{Int, Vector{Int}}}.

Чтобы теперь, наоборот, из словаря G получить вектор из содержащихся в нём пар (если это вдруг понадобится), надо воспользоваться стандартной функцией collect:

collect(G) |> println # [1=>[2,3,4,5], 2=>[], 3=>[1,2,4,5], 4=>[1,2,3,5], 5=>[1,2,3,4]]

Тот же самый словарь G можно было бы создать и динамически:

G=Dict{Int, Vector{Int}}() # - создан пустой словарь нужного типа 
G[1]=[2,3,4,5] 
G[2]=[]
G[3]=[1,2,4,5]
G[4]=[1,2,3,5],
G[5]=[1,2,3,4]

В отличие от массива, в словарь можно добавлять новые пары вида индекс => вектор_смежных_индексов динамически, причем необязательно, чтобы соблюдался порядок следования индексов, т.е. необязательно, чтобы сначала добавилась пара 1 => [...], затем — 2 => [...] и т.д. В словарь такие пары можно будет добавлять в произвольном порядке, по мере того, как они будут определяться при обходе дерева.

1.6. Представление графа со взвешенными ребрами

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

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

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

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

В любом случае обычную матрицу смежностей можно трактовать как весовую матрицу графа, в котором все его ребра имеют единичный вес.

2. Способы задания корневых деревьев в программировании

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

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

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

Таким образом, валентность любой вершины графа равна сумме ее валентностей по входу и по выходу.

Говорят, что в графе вершина $v$ достижима из вершины $u$, если существует последовательность ребер графа $(v,v_1), (v_1,v_2),…,(v_n,u)$, в которой конец предшествующего ребра является началом последующего.

Корневым деревом называется ориентированный граф, у которого

• имеется ровно одна вершина, называемая корнем, валентность по входу которой равна 0;
• любая другая его вершина достижима из корня, и её валентоность по входу равна 1.

Очевидно, что

• в любом корневом дереве имеются вершины, валентности по выходу которых равны 0 (т.к. число вершин конечно); такие вершины называются листьями;

• никакое дерево не содержит циклов.

Представление корневого дерева списком смежностей.

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

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

Помимо этого, существуют еще некоторые специфические способы задания корневого дерева можно.

Представление корневого дерева вложенными векторами.

Рассмотрим это на примерах:

• Int[] — пустое дерево (не содержащее ни одной вершины);
• [1] — тривиальное дерево, состоящее только из корня;
• [[2], [3], 1] — дерево с корнем 1, которому соответствует список смежностей
  [[2, 3], Int[], Int[]];
• [[[4], [5], [6], 2], [[7], [8], 3], 1] — дерево с корнем 1, которому соответствует список смежностей [[2, 3], [4, 5, 6], [7, 8], Int[], Int[], Int[], Int[], Int[]];

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

Например:

• Int[] — пустое дерево (не содержащее ни одной вершины);
• [Int[], Int[], 1] — тривиальное дерево, состоящее только из корня;
• [[Int[], Int[], 2], [Int[], Int[], 3], 1] — дерево с корнем 1, которому соответствует список смежностей [[2, 3], [0, 0], [0, 0]];
• [[[Int[], Int[], 4], Int[], 2], [Int[], [Int[], Int[], 5], 3], 1] — дерево с корнем 1, которому соответствует список смежностей [[2, 3], [4, 0], [0, 5], [0,0], I[0,0]].

Представление дерева связанными структурами.

Структура, представляющая узел бинарного дерева:

mutable struct BiTree{T}
    index::T
    left::Union{BiTree{T},Nothing}
    right::Union{BiTree{T},Nothing}
    BiTree{T}(index) where T = new(index,nothing,nothing)
end

BTI = BiTree{Int}
t = BTI(1)
t.left = BTI(2)
t.right = BTI(3)

Структура, представляющая узел дерева с произвольной валентностью (по выходу):

struct Tree{T}
    index::T
    sub::Vector{Tree{T}}}
    Tree(index)=new(index, Tree{T}[])
end

Структура, представляющая узел дерева с фиксированной валентностью по выходу:

struct NTree{N,T}
    index::T
    sub::Vector{<:Union{NTree{N,T}, Nothing}}
    NTree{N,T}(index) where {N,T} = new(index, [nothing for _ in 1:N])
end

Замечание. Было бы ошибкой аннотировать тип поля sub так

sub::Vector{Union{NTree{N,T}, Nothing}}

Потому что тип Union является абстрактным типом, и, следовательно, невозможно будет впоследствии создать конкретный вектор типа Vector{Union{NTree{N,T}, Nothing}}, чтобы инициализировать поле subtees каким-либо значением, тип которого соответствовал бы такой аннотации.

3. Алгоритмы обхода корневых деревьев

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

Задача обхода дерева заключается в последовательой «обработке» всех поддеревьев данного дерева, включая и само дерево.

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

Вне зависимости от конкретного способа представления корневого дерева алгоритм обхода (обработки) сверху-вниз может быть записан рекурсивно так:

• обработать корень
• поочередно обработать каждое поддерево, непосредственно связанное с корнем

Соответственно, обход (обработка) снизу-вверх рекурсивно записывается так:

• поочередно обработать каждое поддерево, непосредственно связанное с корнем
• обработать корень

Например, если дерево представлено вложенными векторами, и под обработкой корня понимать просто вывод на печать значения его индекса, то в случае обхода сверху-вниз программный код будет выглядеть так:

function toptrace(tree::Vector)
    println(tree[end]) # на последней позиции в tree находится индекс корня
    for subtree in tree[1:end-1] # с первой до предпоследней поциции нахоятся поддеревья
        toptrace(subtree)
    end
end

Соответственно обход (обработка) снизу-вверх будет выглядеть так:

function downtrace(tree::Vector)  
    for subtree in tree[1:end-1] 
        downtrace(subtree)
    end
    println(tree[end])
end

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

Напимер, если дерево представлено типом NTree{N,T}, то тот же самый обход сверху-вниз записывается так:

function toptrace(tree::NTree{N,T}) where {N,T}
    println(tree.index)
    for i in 1:N
        toptrace(tree.sub[i])
    end
end

А если дерево представлено типом Tree{T}, то — так:

function toptrace(tree::Tree{T}) where T
    println(tree.index)
    for sub in tree.sub
        toptrace(tree.sub)
    end
end

В случае же, если дерево представлено списком смежностей, код будет выглядеть так:

ConnectList{T} = Vector{Vector{T}} 

function toptrace(rootindex::T, tree::ConnectList{T}) where T
    println(rootindex)
    for subindex in tree[rootindex]
        toptrace(subindex, tree)
    end
end

4. Метод рекуррентных соотношения для корневых деревьев

Многие задачи обработки деревьев могут быть элегантно решены на основе соответствующих рекуррентных соотношений. Рассмотрим конкретные прмеры.

4.1. Вычисление высоты дерева

Высота дерева — это набольшая длина пути к его концевым вершинам (листьям); по определению длина пути к корню дерева равна 1.

Пусть имеется некоторое дерево с $n$ поддеревьми, непосредственно связанных с его корнем, и нусть известно, что высоты этих поддеревьев равны $h_1,h_2,…,h_n$. Тогда для высоты $h$ всего дерева справедлива рекуррентная вормула:
$$
h=max{h_1,…,h_n}+1
$$

Этой формуле соответствует следующая рекурсивная функция:

function height(tree::Tree)
    h=0
    for sub in tree.sub
        h = max(h,height(sub))
    end
    return h+1
end

4.2. Подсчет всех вершин дерева

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

Пусть $N_1,…N_n$ — числа вершин всех $n$ поддеревьев, связанных с корнем некоторого дерева. Тогда число вершин $N$ самого дерева, очевидно, равно:
$$
N=N_1+…+N_n+1
$$

Полученной рекуррентной формуле соответствует следующая рекурсивная функция:

function vernumber(tree::Tree)
    N=1
    for sub in tree.sub
        N += vernumber(sub)
    end
    return N
end

4.3. Подсчет числа листьев дерева

Пусть $N_1,…N_n$ — числа листьев во всех $n$ поддеревьях, связанных с корнем некоторого дерева. Тогда число листьев $N$ в самом дереве, очевидно, равно:
$$
N=begin{cases}

1 &, если дерево состоит только из корня
N_1+…+N_n &, в противном случае
end{cases}
$$

Полученной рекуррентной формуле соответствует следующая рекурсивная функция:

function leavesnumber(tree::Tree)
    if isempty(tree.sum)
        return 1
    end
    N=0
    for sub in tree.sub
        N += leavesnumber(sub)
    end
    return N
end

4.4. Определение максимальной валентности вершин дерева

Пусть $p_1,…p_n$ — наибольшие валентности по выходу во всех $n$ поддеревьях, связанных с корнем некоторого дерева. Тогда наибольшая валентность по выходу $p$ в самом дереве, очевидно, равна:
$$
p=max{max{p_1,…,p_n}, валентность_корня}
$$

Этой рекуррентной формуле соответствует следующая рекурсивная функция:

function maxvalence(tree::Tree)
    p=length(tree.sub)
    for i in tree.sub
        p = max(p, maxvalence(sub))
    end
    return p
end

4.5. Вычисление средней длины пути к вершинам дерева

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

Чтобы её найти потребуется сначала вычислить суммарную длину пути ко всем вершинам и число всех вершин. После чего, поделив первое на второе, получим искомую характеристику.

Рекуррентная формула для вычисления числа всех вершин нам уже известна:
$$
N=N_1+…+N_n+1
$$
где $N_1,…N_n$ — числа вершин всех $n$ поддеревьев, связанных с корнем некоторого дерева.

Рекуррентная формула для суммарной длины длины пути:
$$
S=S_1+…+S_n+N
$$
где $S_1,…,S_n$ суммы длин путей к каждой вершине всех поддеревьев, $N$ — число вершин во всём дереве. К сумме длин путей в каждом из поддеревьев по отдельности $S_1+…+S_n$ надо прибавить ещё число всех вершин дерева $N$ потому, что длины путей ко всем вершинам каждого поддерева, отсчитываемых от его корня, при переходе к отсчету от корня самого дерева увеличиваются на 1 (включая сам корень, так как длина пути к корню считается равной 1).

Соответствующая функция, возвращающая кортеж из величин $S, N$ записывается так:

function sumpath_numver(tree::Tree)
    N=1
    S=0
    for sub in tree.sub
        s, n = sumpath_numver(sub)
        S += s
        N += n
    end
    return S, N
end

Поскольку эта функция самостоятельного значения не имеет, то её можно обернуть во внешнюю не рекурсивную функцию, возвращающую уже требуемый результат:

function meanpath(tree::Tree)

    function sumpath_numver()
        N=1
        S=0
        for sub in tree.sub
            s, n = sumpath_numver(sub)
            S += s
            N += n
        end
        return S, N
    end

    S, N = sumpath_numver()
    return S/N
end

Задача о нахождении ближайшей родительской вершины для заданного набора вершин корневого дерева

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

Идея решения состоит в следующем. Будем рекурсивно обрабатывать дерево сверху-вниз. При этом будем использовать две внешних по отношению к рекурсивной процедуре переменных:

• number_visited — cчетчик числа посещённых вершин из заданного набора setver
• general — переменная, в которой будет находиться индекс ближайщей общей родительской вершины для всех тех вершин из заданного набора setver, которые на данный момент были уже посещены (при рекурсивном обходе сверху-вниз)

Внешняя переменная general перед началом обхода инициализируется некоторым значением (не важно каким именно), но за пределами всех возможных значений индексов вершин, например, значением 0.

Рекурсивная процедура обхода дерева, назовем её recursrtace, будет иметь дополнительный второй аргумент parent, через который в неё будет в неё передаваться индекс корня дерева, очередное поддерево которого передаётся в качестве первого аргумента (назовем его tree).

Идея алгоритма состоит в следующем:

• как только (после обработки всех поддеревьев, т.е. на возвратном движении к корню) обнаруживается, что корень текущего дерева (поддерева) принадлежит заданному набору setver, счетчик числа посещенных вершин number_visited увеличивается на 1, и если при этом это случилось первый раз, то значению индекса ближайшей первой родительской вершины (переменной general) присваивается индекс этого корня;

• при последующих посещениях вершин из заданного набора (на возвратном движении) значение переменной general может изменяться, а может и оставаться прежним — это зависит от того, где именно (в иерархическом отношении) была обнаружена очередная вершина заданного набора: если текущее значение переменной general является индексом какой-либо её родительской (прародительской, прапрародительской и т.д.), то это значение остаётся неизменным, а в противном случае оно должно быть заменено индексом вершины, являющейся родительской (непосредственно) для очередной обнаруженной вершины заданного набора;

• для обеспечения последнего в рекурсивной процедуре обхода используется локальная логическая переменная (флаг) is_mutable_general, которая при входе в очередное поддерево (при движении от корня к переферии) принимает значение false, запрещающее изменять значение внешней переменной general, а на возвратном движении, как только произойдет возврат в вершину с индексом содержащимся в текущий момент времени в переменной general, флаг is_mutable_general должен принимать значение true, разрешающее изменение переменной general;

• при всём этом, при возвратном движении по подереву (от переферии к корню), если только изменение внешней переменной general разрешено (is_mutable_general = true), то её значение будет заменяться на значение индекса непосредственной родительской вершины (parent) для корня текущего дерева (поддерева, tree), но лишь в случае если счетчик числа посещенных вершин number_visited не достиг ещё числа всех элементов заданного набора setver.

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

function find_general(tree::Vector, setver::Set)

    number_visited = 0 # - cчетчик числа посещённых вершин из набора setver
    general = 0 # - в этой переменной формируется результат (начальное значение не должно только входить в диапазон индексов вершин дерева)

    function recurstrace(tree, parent=0) # - выполняет рекурсивную обработку дерева сверху-вниз      
        is_mutable_general = false # при движение по дереву вглубь от корня внешнюю переменную general изменять не надо 

        for subtree in tree[begin:end-1]
            if number_visited < length(setver)
                recurstrace(subtree, tree[end])
            end
        end

        # number_visited = число ранее посещенных вершин из заданного набора setver
        if tree[end] in setver
            number_visited +=1
            if number_visited == 1
                general = tree[end]
            end                        
        end
        # теперь - обратное движение по дереву - из глубины к корню
        if general==tree[end] 
            is_mutable_general = true # т.е. при движении к корню, внешнюю переменную general снова нужно отслеживать
        end
        if is_mutable_general && number_visited < length(setver)
            general = parent
        end

println((current=tree[end],parent=parent,general=general)) # - это для отладки
    end

    recurstrace(tree)
    return general
end

#-------------- TEST: -----------

tree=[[[[4],[5],[6],3],[[9],[[[17],[18],16],[19],10],7],2],[[11],[[14],[15],12],8],1]
#find_general(tree,Set((3,4,6,7))) |> println # 2
find_general(tree,Set((6,10,16))) |> println # 2

Отладочный вывод при этом получится таким:

(current = 4, parent = 3, general = 0)
(current = 5, parent = 3, general = 0)
(current = 6, parent = 3, general = 3)
(current = 3, parent = 2, general = 2)
(current = 9, parent = 7, general = 2)
(current = 17, parent = 16, general = 2)
(current = 18, parent = 16, general = 2)
(current = 16, parent = 10, general = 2)
(current = 19, parent = 10, general = 2)
(current = 10, parent = 7, general = 2)
(current = 7, parent = 2, general = 2)
(current = 2, parent = 1, general = 2)
(current = 1, parent = 0, general = 2)
2