Skip to content

Latest commit

 

History

History
61 lines (41 loc) · 3.79 KB

README.md

File metadata and controls

61 lines (41 loc) · 3.79 KB

Лабораторная работа №3 — генерация случайных деревьев

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

Модель

Дерево строится последовательно. Каждая новая вершина соединяется с одной из уже существующих. Вероятность выбора родительской вершины зависит от её расстояния l до корня и пропорциональна l^k, где k — параметр модели.

Что реализовано

  • генерация случайного дерева из n вершин;
  • визуализация полученного дерева;
  • построение гистограммы распределения степеней вершин;
  • вычисление среднего диаметра по нескольким случайным реализациям;
  • сравнение среднего диаметра при разных значениях n и k.

Результаты

Зависимость среднего диаметра

Зависимость среднего диаметра от количества вершин

Примеры деревьев и распределений степеней

Число вершин Дерево Распределение степеней
10 Дерево из 10 вершин Распределение степеней для 10 вершин
30 Дерево из 30 вершин Распределение степеней для 30 вершин
50 Дерево из 50 вершин Распределение степеней для 50 вершин
100 Дерево из 100 вершин Распределение степеней для 100 вершин
1000 Дерево из 1000 вершин Распределение степеней для 1000 вершин

Запуск

python -m venv .venv

# Windows PowerShell
.venv\Scripts\Activate.ps1

pip install -r requirements.txt
python main.py

Запускайте программу из каталога Lab3: изображения сохраняются в локальную папку pictures. Параметры эксперимента n, k, n_values, k_values и sample_size задаются в функции main.

В текущем варианте n_values начинается с нуля. Для полного запуска эксперимента первое значение следует заменить на положительное, например использовать range(10, 300, 10), поскольку диаметр пустого графа не определён.

Файлы

  • main.py — генератор дерева, расчёты и функции визуализации;
  • requirements.txt — зависимости проекта;
  • pictures/ — полученные графики и изображения деревьев.

Технологии

  • Python;
  • NetworkX;
  • Matplotlib;
  • NumPy;
  • аннотации типов из стандартного модуля typing.