🌐

Мережі та Теорія графів

Від алгоритму A* і PageRank до кластеризації та поширення по мережах — вивчайте теорію графів через інтерактивні симуляції.

6 симуляцій Canvas 2D · WebGL Shortest Path · TSP · SIR

Симуляції категорії

Graphs, paths, flows and spreading processes

Graph theory underpins the modern world — routing packets across the Internet, mapping protein interactions, scheduling airline connections and modelling how information (or disease) spreads through a social network. Here you can interact with the core algorithms step by step.

🗺️
★★☆ Середнє
Pathfinding Algorithms
Interactive grid where you can paint walls, move start/goal, and compare A*, Dijkstra and BFS side by side — open and closed node sets shown live.
Canvas 2D A* Dijkstra BFS
✈️
★★☆ Середнє
Travelling Salesman Problem
Place cities and watch Nearest-Neighbour, 2-Opt, 3-Opt and simulated annealing compete for the shortest Hamiltonian tour across all nodes.
Canvas 2D TSP 2-Opt Annealing
🧬
★★☆ Середнє
Генетичний алгоритм
Evolve solutions on a network-style fitness landscape using selection, crossover and mutation operators. Watch population fitness converge.
Canvas 2D GA Crossover Mutation
🦠
★☆☆ Beginner
Epidemic Spreading (SIR)
SIR / SEIR / SIS compartmental model with interactive β and γ sliders. Watch the infection curve flatten or explode depending on R₀ value.
Canvas 2D SIR ODE R₀
🔗
★★★ Складне
Граф із силовим розміщенням
Візуалізація графів Ердьоша-Реньї, Барабаші-Альберт та малого світу. Вузли пофарбовані за степенем, гістограма розподілу.
Canvas 2D Силовий макет Барабаші-Альберт
🌲
★★☆ Середнє
Мінімальне кістяне дерево
Покрокова анімація алгоритмів Краскала та Пріма на зваженому графі. Перемикайте алгоритми; ваги ребер показані на дугах.
Canvas 2D Краскал Прім
🕸️
★★☆ Moderate
Стійкість мережі
Безмасштабні мережі під цілеспрямованою атакою та випадковими відмовами — руйнування гігантської компоненти.
Силовий граф Безмасштабна Перколяція Теорія графів
🌐
★★☆ Середній Нове
Мережа малого світу
Перезвʼязування Ваттса–Строгатца: починаєм з правильної кольцевої решітки і поступово додаємо випадкові далекосяжні звʼязки. Коефіцієнт кластеризації залишається високим, а середня довжина шляху різко чоміє — ознака соціальних мереж, мозку і інтернету.
Ваттс–Строгатц Кластеризація Довжина шляху Canvas 2D
🌐
Нове ★★☆ Середній
Мережева наука
Граф Ердоша–Реньї, безмасштабний Барабаші–Альберт і дрібносвітний Ваттс–Строгатц із силовою розкладкою. Гістограма розподілу ступенів, коефіцієнт кластеризації та частка гігантської компоненти оновлюються в реальному часі.
Ердош–Реньї Барабаші–Альберт Силова розкладка

Key Concepts

Core graph theory and network science ideas

Graph Representations
Adjacency matrix O(V²) storage, adjacency list O(V+E). Dense graphs favour matrix for O(1) edge lookup; sparse graphs favour lists for traversal. Weighted graphs add cost to each edge — fundamentals for every pathfinding algorithm.
Shortest Path (A*)
f(n) = g(n) + h(n): g is the exact cost from start, h is the heuristic estimate to goal. An admissible (never-overestimating) heuristic guarantees the optimal path. Dijkstra is A* with h=0. Bi-directional search and Jump Point Search speed up grids.
Network Centrality
Degree centrality counts edges per node. Betweenness centrality counts how many shortest paths pass through a node — critical hubs in transport and social networks. PageRank extends eigenvector centrality to directed weighted networks.
Spreading Processes
SIR model on a network: each infected node spreads to each susceptible neighbour with probability β per step. Recovery at rate γ. Basic reproduction number R₀ = β/γ × average degree. Herd immunity threshold 1 − 1/R₀.

Learning Resources

Articles and references about graph algorithms

Reference Algorithms Glossary A*, Dijkstra, BFS, DFS, TSP, spanning trees — concise definitions with complexity bounds and pseudocode. → Article A* from Scratch in JavaScript Full implementation: grid encoding, open/closed sets, heuristic functions, and tie-breaking. Handles weighted terrain. →
All articles →

Ключові Концепції

Теми та алгоритми, які ви досліджуєте в цій категорії

Безмасштабні МережіМодель переважного приєднання Барабаші-Альберт
Мережі Малого СвітуПерекомутація Ваттса-Строгаца: короткі шляхи, висока кластеризація
Теорія ПерколяціїКритичний поріг зв'язності для стійкості мережі
Міри ЦентральностіСтупінь, між-центральність, близькість, власний вектор
Поширення ЕпідемійДинаміка SIR на топології мережі
Спектральна Теорія ГрафівВласні значення лапласіана та властивості мережі

Часті Запитання

Поширені запитання про цю категорію симуляцій

Що робить мережу безмасштабною?
Безмасштабна мережа слідує степеневому розподілу ступенів P(k) ~ k^(-γ). Вона формується через переважне приєднання: нові вузли підключаються переважно до вже добре з'єднаних ('багаті стають багатшими').
Що таке ефект малого світу?
Властивість малого світу означає, що більшість пар вузлів з'єднані дивовижно коротким шляхом, тоді як більшість вузлів кластеризуються локально. Модель Ваттса-Строгаца генерує такі мережі випадковим перекомутуванням частини ребер.
Як хвороба поширюється мережею?
Структура мережі кардинально впливає на епідемічну динаміку. Хаб-вузли — суперрозповсюджувачі: їх цільова вакцинація набагато ефективніша за випадкову.

Про Симуляції Мереж та Теорії Графів

Соціальні мережі, поширення епідемій, випадкові графи та зв’язність

Симуляції мереж візуалізують структуру та динаміку складних з’єднаних систем. Від моделей безмасштабних мереж Барабаші-Альберт до малих світів Ваттса-Строгаца — кожна симуляція показує, як топологія впливає на потоки інформації.

Моделі поширення інформації та епідемій на мережах демонструють роль хабів, кластерів та мостів. Алгоритми спільнот знаходять приховані групи в складних графах.

Кожна симуляція побудована з акцентом на точність. Мережеві моделі базуються на тій самій теорії, що використовується в аналізі соціальних мереж.

Other Categories