Центр радиус диаметр дерева

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Индивидуальный проект по дискретной математике

alexvilno/calc_tree

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Нахождение центра, радиуса и диаметра дерева, заданного двоичным кодом

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

Исходные данные берутся из файла input.txt. В первой строке записано одно число n — количество вершин в дереве. Во второй строке располагается двоичный код. Нужно записать три числа в файл output.txt количество вершин, образующих центр, радиус и диаметр.

Использованые структуры данных

Для реализиации списка смежности был использован std::vector

Корректным решением является:

• Создаем список смежности из двоичного кода
• Считаем диаметр
• Считаем радиус
• Находим центровые вершины

Создание списка смежности из двоичного кода

Для этого используем функцию

std::vectorint>> ReadTree(std::istream &in) < std::vectorint>> tree(1); ReadTreeRec(in, tree, 0); return std::move(tree); >

Она принимает в качестве аргумента входящий поток std::istream &in и создает список смежности на базе std::vector> первая его координата — рассматриваемая вершина, вторая &mdash вершина, которая ей смежна. Например список смежности для дерева, заданного двоичным кодом 0011 будет выглядеть так:

То есть по сути, наш список смежности выглядит так:

tree[c][0] = v — вершина c смежна вершине v

Создается он следующим образом:

Вызывается рекурсивная функция

void ReadTreeRec(std::istream &in, std::vectorint>> &tree, int v)

Кроме входящего потока, она принимает, собственно, список смежности, который требуется заполнить и параметр int v — индекс вершины

void ReadTreeRec(std::istream &in, std::vectorint>> &tree, int v) < for (char command; in >> command && command != '1';) < int u = tree.size(); tree.emplace_back(); //create in end tree[v].push_back(u); //create and push tree[u].push_back(v); ReadTreeRec(in, tree, u); > >

• Из входящего потока считывается двоичный код
• Если считываемый символ command != ‘1’ тогда
  • создается переменная u равная текущему размеру списка смежности — tree.size()
  • создается очередная вершина с индексом v
  • в список смежности tree[v].push_back(u) кладется смежная с ней u
  • для u делается то же самое: tree[u].push_back(v)
  • рекурсивно вызывается эта же функция, но уже от вершины с индексом u

  Довольно логично, что каждую инициализацию переменная u = tree.size() будет равна индексу очередной вершины в списке смежности

  Когда мы получили список смежности, возвращаем его без копирования return std::move(tree)

  Теперь когда мы имеем список смежности для дерева, мы можем посчитать диаметр дерева.

  Считать будем следующим образом:

  • найдем самое большое расстояние от корня дерева до крайней вершины
  • найдем самое большое расстояние от этой вершины до других вершин

  Функция, возвращающая диаметр дерева выглядит так:

  int CountDiameterLength(std::vectorint>> &tree) < int vertices_count = tree.size(); std::vectorint> distances(vertices_count); CountMaxDistanceRec(tree, distances, -1, 0); int new_root = FindVertexWithMaxDistance(distances); distances[new_root] = 0; CountMaxDistanceRec(tree, distances, -1, new_root); return distances[FindVertexWithMaxDistance(distances)]; >

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

  • int vertices_count = tree.size() запоминаем количество вершин и создаем массив такого размера std::vector distances(vertices_count)
  • заполним этот массив расстояниями от корня дерева с помощью функции void CountMaxDistanceRec(const std::vector &tree, std::vector &distances, int p, int v) — она будет описана ниже
  • от нового «нового корня» (т.е. от той вершины, расстояние до которой будет максимально) также запишем новые расстояния
  • вернем максимальное расстояние, находящееся в массиве расстояний по индексу, возвращаемому функцией FindVertexWithMaxDistance(distances) (реализациия её тривиальна, описываться не будет)

  Как работает void CountMaxDistanceRec(const std::vector> &tree, std::vector &distances, int p, int v) ?

  Она принимает ссылку на список смежности, ссылку на массив расстояний индекс родительского элемента (для корня это -1) и индекс элемента, от которого считаются расстояния

  • Проходимся по всем вершинам, кроме родительской
  • Считаем рекурсивно расстояния до всех других вершин

  То есть грубо говоря, мы прошлись DFS два раза

  Делаем это по формуле radius = (diameter + 1) / 2

  Считаем количество центров

  По формуле center = (diameter) % 2 + 1

  

  

  

  

  

  12 0001010110110001011011 

  

  

  

  

  

  Для тестов производительности есть функция, возвращающая случайное дерево из n вершин в виде двоичного кода

  std::string tree_generator(int v_count) < std::random_device random_device; std::mt19937 generator(random_device()); std::uniform_int_distribution<> distribution(0, 1); std::string generated = ""; int count_0 = 0; int count_1 = 0; for (int i = 0; i < v_count * 2; ++i) < int x = distribution(generator); if (count_0 >= v_count) < x = 1; generated += x + 48; continue; > if (x == 1 && count_1 < count_0) < generated += x + 48; ++count_1; > else if (x == 1 && count_1 >= count_0) < x = 0; generated += x + 48; ++count_0; > else < generated += x + 48; x == 1 ? ++count_1 : ++count_0; > > return generated; >

  Таблица зависимости количества вершин и времени обработки алгоритмом

  Количество	Время(SEC)
  1000	0.002
  10000	0.008
  25000	0.022
  100000	0.071
  500000	0.351
  1000000	0.894
  2000000	1.619
  3000000	2.580
  4000000	2.928
  5000000	3.587
  10000000	8.614
  25000000	20.40
  50000000	76.38

  About

  Индивидуальный проект по дискретной математике

  Источник

  §9. Метрические характеристики графа

  Пусть G = (S, U) – связный граф и x_i, x_j – две его произвольные вершины.

  Определение 9.1. Расстоянием d(x_i, x_j) между вершинами x_i и x_j называется длина кратчайшего маршрута, соединяющего эти вершины.

  Из определения 9.1 непосредственно следует:

  Определение 9.2. Эксцентриситетом вершины x называется величина

  e(x) = (9.1)

  Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удалëнной от неë.

  Определение 9.3. Диаметром d(G) графа G называется максимальный из всех эксцентриситетов вершин графа G, т.е.

  Определение 9.4. Вершина x называется периферийной, если e(x) = d(G).

  Определение 9.5. Диаметральной цепью называется простая цепь, расстояние между концами которой равно d(G).

  Теорема 9.1. Для любого связного графа G справедливо неравенство

  d(G)  rank G. 

  Определение 9.6. Радиусом r(G) графа G называется минимальный из всех эксцентриситетов вершин графа G, т.е.

  Определение 9.7. Вершина x называется центральной, если e(x) = r(G).

  Определение 9.8. Множество всех центральных вершин графа называется его центром.

  Заметим, что центр может состоять как из одной, так и из нескольких вершин.

  Пример 9.1. Найти эксцентриситеты вершин, радиусы и диаметры графа G, изображëнного на рис. 16, периферийные и центральные вершины. Привести

  пример диаметральной цепи.

  Р ешение. Найдëм эксцентриситеты всех вершин G: e(x₁) = e(x₄) = e(x₅) = 4,

  e(x₂) = e(x₆) = e(x₇) = e(x₈) = 3, e(x₃) = 2.

  Следовательно, d(G) = 4, r(G) = 2. Получаем, что вершины x₁, x₄ и x₅ являются периферийными, а вершина x₃ – центральной. Одной из диаметральных цепей является

  x₁ – x₇ – x₃ – x₆ – x₅. 

  §10. Деревья и их свойства. Лес

  Определение 10.1. Любой связный неорграф, не содержащий циклов, называется (неориентированным) деревом.

  Определение 10.2. Любой неорграф без циклов называется лесом, или ациклическим графом.

  Таким образом, компонентами связности любого леса являются деревья.

  На рис. 17 показан лес, состоящий из двух деревьев.

  Свойства деревьев сформулируем в виде следующей теоремы.

  Теорема 10.1. Пусть G = (S, U) и = n, = m. Тогда следующие условия эквивалентны:

  1. G – дерево;
  2. G – связный граф и m=n1;
  3. G – ациклический граф и m=n1;
  4. любые две различные вершины графа соединяет единственная простая цепь;
  5. G – ациклический граф, такой, что если какую-либо пару его несмежных вершин соединить ребром, то полученный граф будет содержать ровно один цикл. 

  Теорема 10.2 (Кэли). Число деревьев с n занумерованными вершинами равно . 

  Определение 10.3. Ориентированным деревом (ордеревом) называется

  орграф G = (S, U), удовлетворяющий следующим двум условиям:

  1. существует единственная вершина x_iS, называемая корнем, не имеющая предшествующих вершин (т. е. );
  2. любой вершине x_j, отличной от x_i, в орграфе G непосредственно предшествует ровно одна вершина (т. е. ).

  Определение 10.4. Узлом ордерева называется вершина, отличная от корня.

  Определение 10.5. Листом ордерева называется вершина x такая, что и

  Определение 10.6. Ветвью ордерева называется путь из корня в лист.

  Определение 10.7. Высотой ордерева называется длина его наибольшей ветви.

  Определение 10.8. Уровнем вершины ордерева называется расстояние от корня до этой вершины.

  Отметим, что корень имеет уровень 0.

  Определение 10.9. Ярусом ордерева называется множество вершин одного уровня.

  Замечание 10.1. Неориентированное дерево можно преобразовать в ориентированное, выбрав в качестве корня произвольную вершину. На рис. 18 корень графа – вершина x₇. 

  П ример 10.1. Рассмотрим ордерево, изображëнное на рис. 18. Тогда: все вершины, кроме x₇, являются узлами ордерева; вершины x₁, x₅, x₈, x₁₀, x₁₁, x₁₂ – листами; путь x₇  x₆  x₃  x₂  x₁₀ – одна из ветвей; высота ордерева равна 5; множество вершин x₁, x₅, x₉, x₁₀> уровня 4 образует один из ярусов ордерева. 

  Определение 10.10. Остовом неорграфа G = (S, U) называется его часть G = (S, U), такая, что S = S и G – лес, образующий дерево на любой связной компоненте графа G.

  Из определения 10.10 следует, что если G – связный неорграф, то остов G является деревом, которое будем называть остовным деревом графа G.

  Определение 10.11. Остовом орграфа G называется его часть G, такая, что ассоциированный с G неорграф F(G) является остовом графа F(G).

  Понятие остовного дерева для связного орграфа вводится аналогично.

  Замечание 10.2. 1) В каждом графе существует остов, который можно получить, разрушая в каждой связной компоненте циклы, т.е. удаляя лишние рëбра.

  2) Остов графа определяется неоднозначно. 

  П ример 10.2. На рис. 19 изображены неорграф G и один из его остовов G. 

  Для подсчета числа остовов в неорграфе используется матрица Кирхгофа.

  Теорема 10.3 (Кирхгофа). Число остовных деревьев в связном неорграфе G порядка n  2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа. 

  Из определения дерева вытекает следующая теорема.

  Теорема 10.4. Пусть G = (S, U) – произвольный неорграф, = n, = m , k – число компонент связности графа G. Число рëбер, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно m – n + k.

  Доказательство. Пусть i-я компонента связности G_i содержит n_i вершин и m_i рëбер. По условию G – связный граф. Следовательно, остов G_i графа G_i является деревом, а значит, он содержит (n_i – 1) ребро. Таким образом, для получения остова G_i из i-й компоненты связности G_i требуется удалить m_i – (n_i – 1) ребер.

  Просуммируем удаляемые ребра по всем компонентам связности, учитывая, что Получим 

  Определение 10.12. Число  (G) = m  n + k называется цикломатическим числом или циклическим рангом графа G.

  Определение 10.13. Число *(G) = n  k называется коциклическим рангом или корангом.

  Таким образом, *(G) равно числу рëбер, входящих в любой остов графа G. Очевидно, что  (G) +*(G) = m.

  Из теоремы 10.4 непосредственно вытекают два следствия.

  Следствие 10.4.1. Неорграф G является лесом тогда и только тогда, когда

  Следствие 10.4.2. Неорграф G имеет единственный цикл тогда и только тогда, когда  (G) =1. 

  Пример 10.3. Найти для графа G, изображенного на рис. 19, цикломатическое число и коциклический ранг.

  Решение. Граф G имеет 8 вершин, 14 ребер и 1 компоненту связности. Тогда, согласно по теореме 10.4, цикломатическое число  (G) = 14 – 8 +1 = 7, а коциклический ранг *(G) = 8 – 1 = 7 . 

  Источник

  Читайте также:  Дверь входная дерево со стеклом