Данилов Г. В., Качан О. В., Борисова Н. К.
Об оценке центроидности поисковых деревьев

УДК 519.1, ВАК 05.13.18, ГРНТИ 28.29.51

Об оценке центроидности поисковых деревьев

Evaluation of search trees centroidness

Г. В. Данилов1, О. В. Качан2,

Н. К. Борисова1

G. V. Danilov1, O. V. Kachan2,

N. K. Borisova1

1Ухтинский государственный технический университет, Ухта

2Институт психологического консультирования «Новый век», СПб

1Ukhta state technical University, Ukhta

2Institute of psychological counseling «Novyy Vek», Saint Petersburg

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

The article describes the approach to measuring the degree of centroides search and other trees (connected graphs without cycles). It is proved that the measure takes the smallest possible value for tree type «trunk» and the highest for wood type «Bush».

Ключевые слова: связный граф, дерево, мера центроидности

Keywords: connected graph, tree, as centroides

Введение

Любая система, будь то физическая, информационная, экономическая, управленческая и т.д., обладает определённой структурой. Для математического моделирования структур обычно применяют такие объекты, как графы [1], представляющие собой множество V вершин и множество неупорядоченных пар элементов из V, называемых ребрами. Граф называется связным, если для любых его двух вершин существует маршрут, соединяющий эти вершины.

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


Рисунок 1. Пример дерева с 8 вершинами

Степенью вершины графа называется число инцидентных ей ребер. Для любого дерева справедливы следующие соотношения:

  1. m = n – 1
  2.     (1)
  3. количество висячих вершин не менее двух,

где: n – число вершин, m – число ребер, Хi – степень i-й вершины (i = 1, 2, …, n), «висячая» вершина – это вершина степени 1.

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

Количественная мера центроидности дерева

В связи с этим возникает необходимость ввести какую-то количественную меру центроидности дерева, которую обсудим пока на эвристическом уровне. Будем считать, что дерево типа «ствол» (рис. 2) является наименее ветвистым, а дерево типа «куст» (рис. 3) – наиболее ветвистым, и, следовательно, любая мера центроидности должна принимать наименьшее значение для ствола и наибольшее значение – для куста.


Рисунок 2. Дерево типа «ствол» n = 7


Рисунок 3. Дерево типа «куст» n = 7

Первое, что приходит в голову, это ввести в качестве меры центроидноcти наибольшую степень вершины:

(2)

Для ствола она принимает наименьшее значение, равное 2, а для куста наибольшее, равное n-1.

Однако следующий пример (рис. 4) показывает, что такая мера не годится, поскольку оба дерева имеют одно и то же Хmax = 3, хотя дерево Т2 интуитивно более ветвистое, чем Т1.

    
Рисунок 4. Пример двух деревьев (п = 7) разной ветвистости, но имеющих одинаковые значения Хтах = 3

 

Ещё одной мерой центроидности дерева могло бы быть число висячих вершин, которое также принимает наименьшее значение для ствола и наибольшее для куста. Но и эта мера не всегда соответствует нашим представлениям о ветвистости дерева. Например, на рис. 5 при одинаковом числе висячих вершин дерево Т4 представляется более ветвистым, чем Т3.

    

Рисунок 5. Пример двух деревьев (п = 13) разной ветвистости, но имеющих одинаковое число висячих вершин (8)

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

Рассмотрим упорядоченный по неубыванию перечень степеней всех n вершин дерева а = (Х1, Х2, …, Хn), X1 <= Х2 <= … <= Хn. Его можно рассматривать как точку в n-мерном пространстве степеней. Тогда множество всех деревьев с n вершинами разобьётся на классы, каждый из которых будет представлен определённой точкой, лежащей в гиперплоскости (1) в пространстве степеней, так что деревья, принадлежащие одному и тому же классу, будут неразличимы, т. е. принадлежность к данному классу будет для них топологическим инвариантом. Так, деревья Т2 и Т5 (рис. 6) будут представлены одной и той же точкой (1, 1, 1, 1, 2, 3, 3) пространства и в этом смысле неразличимы, хотя они и не являются изоморфными.

    

Рисунок 6. Пример двух различных деревьев (п = 7), неразличимых в пространстве степеней

Теперь, считая, что пространство степеней наделено евклидовой метрикой, введем в качестве меры центроидности данного класса деревьев квадрат расстояния этого класса от начала координат:

(3)

Докажем, что эта мера (назовём ее «кроной») принимает наименьшее возможное значение для дерева типа «ствол» (Предложение 1) и наибольшее – для дерева типа «куст» (Предложение 2).

Доказательство Предложения 1.

В произвольном, отличном от ствола дереве, имеющем n вершин (n > 3), Выделим две какие-нибудь висячие вершины. Не умаляя общности, можно считать, что они имеют номера n-1 и n соответственно. Теперь осуществим следующую пошаговую процедуру.

Вначале удалим какую-нибудь висячую вершину (отличную от (n-1)й и nй) имеете с инцидентным ей ребром и этот «тандем» присоединим к nй висячей, так что степень последней станет равной двум. Затем удалим следующую висячую (отличную от (n-1)й) вместе со своим ребром, которое присоединим к только что «переселённой» висячей вершине. Вообще, на jм шаге в дереве, образованном после (j-1)го шага, удаляем произвольную, отличную от (n-1)й вершину вместе с её ребром, которое присоединяем к висячей вершине, «переселённой» на (j-1)м шаге.

Очевидно, за конечное число шагов все вершины будут иметь степень 2, за исключением (n-1)й и последней переселившейся, которые будут висячими. Таким образом, описанная процедура всегда приводит к дереву типа ствол.

С другой стороны, на произвольном iм шаге крона дерева С получает приращение С, равное:

,

где к — степень вершины, из которой на указанное шаге выдёргивается для переселения ребро; поскольку к = 2, то Ci = 0. Но в связи с тем, что всякое дерево, отличное от ствола, имеет хотя бы одну вершину степени больше 2 и из этой вершины на каком-то шаге (допустим 1м) обязательно будет удалено ребро, то но крайней мере на этом шаге Ci < 0, и следовательно, суммарное приращение кроны будет отрицательным.

Поэтому ствол имеет наименьшую по сравнению с другими деревьями крону, и Предложение 1 доказано.

Доказательство Предложения 2.

В произвольном, отличном от куста дереве, имеющем n вершин (n > 3), выделим вершину, обладающую наивысшей степенью. (Если таких вершин несколько, то выбираем любую из них).

Теперь осуществим следующую пошаговую процедуру.

На первом шаге удалим любую висячую вершину вместе с инцидентным ей ребром не соединённым с выделенной вершиной, и присоединим к последней этот «тандем». В результате выделенная вершина будет иметь наивысшую степень по сравнению со всеми другими вершинами. Назовём ее лидером.

Вообще, на jм шаге очередную висячую вершину вместе с инцидентным ей ребром, не соединённым с лидером, отсоединяем и этот «тандем» присоединяем к лидеру.

Очевидно, за конечное число шагов все вершины (за исключением лидера) окажутся висячими и притом соединёнными с единственной вершиной — лидером.

Следовательно, описанная процедура всегда приводит к дереву типа куст.

С другой стороны, на каждом iм шаге этой процедуры крона дерева С получает приращение Ci, равное:

,

где кi — степень лидера перед iм шагом; l — степень вершины, из которой на данном шаге выдёргивается ребро.

Поскольку Кi = 1, то Ci > 0. Поэтому куст обладает наибольшей кроной по сравнению с другими деревьями, и Предложение 2 доказано.

Отметим, что в приведённых на рис. 4 и 5 примерах крона принимает большее значение для тех деревьев, которые как раз и представлялись нам более ветвистыми: С (Т2) = 26 > 24 = С (Т3) и С (Т4) = 88 > 60 = С (Т3).

После соответствующей нормировки получаем выражение для количественной меры центроидности дерева С*:

    

где , которая принимает значение 0 для ствола и значение 1 для куста.

Заключение

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

Список литературы

1. Харари Ф. Теория графов. – М.: Мир, 1973. – 283 с.

References

1. F. Harari, graph Theory. – M.: Mir, 1973. – 283 p.

 

РЕЦЕНЗИЯ

на статью

ФИО, Об оценке центроидности поисковых деревьев // Информационные технологии в управлении и экономике. 2016. № _.

Статья посвящена решению задачи вывода количественной оценки центроидности деревьев.

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

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

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

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

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

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

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

К достоинствам рассмотренного метода расчёта следует отнести доказательство, что эта мера принимает наименьшее возможное значение для дерева типа «ствол» и наибольшее – для дерева типа «куст».

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

Следует отметить, что статья написана ясным языком, не перегружена излишней узкоспециальной терминологией. Выводы автора являются весьма обоснованными. Статья ФИО «Об оценке центроидности поисковых деревьев» представляет научный интерес и соответствует всем требованиям, предъявляемым к работам такого рода.

Данная статья может быть рекомендована к публикации.

 

Рецензент:

Доцент кафедры вычислительной техники,

информационных систем и технологий

ФГБОУ ВО «УГТУ», к.т.н.
А. Н. Дорогобед

VN:F [1.9.17_1161]
Rating: 0.0/10 (0 votes cast)
VN:F [1.9.17_1161]
Rating: 0 (from 0 votes)
VN:F [1.9.17_1161]
Стиль изложения
Информативность
Сложность вопроса
Научная новизна
Коммерциализуемость
Rating: 0.0/5 (0 votes cast)