Графы: как устроены социальные сети и интернет

🎯 Зачем это нужно?

Открой Instagram или ВКонтакте - видишь подписки, друзей, лайки? 📱 Всё это граф! Google находит нужную страницу среди миллиардов за доли секунды - тоже граф. GPS строит маршрут от дома до школы - опять граф.

Графы везде:

• 🌐 Интернет - сайты связаны ссылками
• 👥 Соцсети - люди связаны дружбой/подписками
• 🗺️ Карты - города связаны дорогами
• 🧬 Нейросети - нейроны связаны синапсами
• 💰 Блокчейн - транзакции образуют граф

📚 История вопроса

В 1736 году жители Кёнигсберга спорили: можно ли пройти по всем 7 мостам города ровно по разу? 🌉 Эйлер доказал, что нельзя - и так родилась теория графов!

Сегодня графы помогают:

• Facebook находить “людей, которых вы можете знать”
• Google ранжировать сайты (PageRank)
• Uber оптимизировать маршруты
• Netflix рекомендовать фильмы

💡 Интуиция

Граф = точки + линии между ними. Всё!

Представь граф как: 🎮 Карту в игре - локации (вершины) соединены переходами (рёбрами) 🚇 Схему метро - станции связаны линиями 👥 Компанию друзей - кто с кем дружит

[МЕДИА: image_01] Описание: Простой граф с 5 вершинами, показывающий социальную сеть друзей Промпт: “simple graph visualization showing 5 people as nodes connected by friendship edges, social network style, modern clean design, colorful nodes, suitable for educational purpose”

📐 Формальное определение

Граф G = (V, E) состоит из:

• V - множество вершин (vertices/nodes)
• E - множество рёбер (edges), где каждое ребро соединяет две вершины

Примеры:

• Неориентированный граф: дружба в ВК (взаимная)
• Ориентированный граф: подписки в Instagram (односторонние)
• Взвешенный граф: дороги с расстояниями

Основные характеристики:

• Степень вершины deg(v) - количество рёбер, инцидентных вершине
• Путь - последовательность вершин, соединённых рёбрами
• Цикл - путь, который возвращается в начальную вершину
• Связность - существует путь между любыми двумя вершинами

🔍 Примеры с разбором

Пример 1: Анализ социальной сети

Пусть у нас есть граф друзей: A-B, B-C, C-D, A-D, B-D

[МЕДИА: image_02] Описание: Граф из 4 вершин A,B,C,D с рёбрами между ними Промпт: “graph with 4 vertices labeled A,B,C,D connected by edges, showing friend connections, clean mathematical style, nodes in different colors”

Анализ:

• deg(A) = 2 (связан с B и D)
• deg(B) = 3 (связан с A, C, D) - самый популярный!
• deg(C) = 2, deg(D) = 3
• Треугольник B-C-D - три взаимных друга
• Путь A→B→C длины 2

Пример 2: Поиск кратчайшего пути

В графе городов найдём путь от A до E:

A - B (3км) A - C (5км)
B - D (2км) C - D (1км) D - E (4км)

Варианты:

1. A→B→D→E = 3+2+4 = 9км
2. A→C→D→E = 5+1+4 = 10км

Кратчайший: A→B→D→E = 9км

Пример 3: Анализ веб-страниц

Граф ссылок между сайтами:

• Сайт A ссылается на B и C
• Сайт B ссылается на C
• Сайт C ссылается на A

PageRank: C получает ссылки от A и B → высокий рейтинг!

🎮 Практика

Базовый уровень 🟢

Задание 1: В графе 5 вершин и рёбра: (1,2), (2,3), (3,4), (4,5), (5,1), (1,3). Найди степень каждой вершины.

Задание 2: Можно ли нарисовать граф с 5 вершинами, где все степени равны 3? Обоснуй ответ.

Задание 3: В соцсети 4 человека. Каждый дружит ровно с двумя другими. Сколько рёбер в этом графе?

Задание 4: Найди все треугольники (циклы длины 3) в графе из задания 1.

Продвинутый уровень 🟡

Задание 5: Докажи, что в любом графе количество вершин нечётной степени чётно. (Лемма о рукопожатиях)

Задание 6: Граф представляет сеть дорог. Вершины - города, рёбра - дороги. Как найти, можно ли добраться из города A в город B?

Задание 7: В графе n вершин и каждая вершина имеет степень ≥ n/2. Докажи, что граф связен.

Задание 8: Instagram предлагает “людей, которых вы можете знать”. Как это работает с точки зрения графов?

Челлендж 🔴

Задание 9: Разработай алгоритм поиска самого влиятельного человека в социальной сети (аналог PageRank для друзей).

Задание 10: Эйлеров путь - путь, проходящий по каждому ребру ровно раз. При каком условии он существует?

Задание 11: Как Google определяет важность веб-страницы? Опиши алгоритм PageRank через графы.

⚠️ Частые ошибки

❌ Ошибка: Путать вершины с рёбрами ✅ Правильно: Вершины - объекты, рёбра - связи между ними 💡 Почему: В соцсети люди - вершины, дружба - рёбра

❌ Ошибка: Думать, что граф обязательно связен ✅ Правильно: Граф может состоять из нескольких компонент 💡 Почему: В соцсети могут быть изолированные группы друзей

❌ Ошибка: Забывать про направленность ✅ Правильно: Различать взаимные связи и односторонние 💡 Почему: Подписка в Instagram ≠ дружба в ВК

❌ Ошибка: Неправильно считать степени в ориентированном графе ✅ Правильно: Входящая степень + исходящая степень 💡 Почему: У вершины может быть много подписчиков, но мало подписок

🎓 Главное запомнить

✅ Граф G = (V, E) - вершины + рёбра между ними ✅ Степень вершины = количество соседей
✅ Графы моделируют сети: соцсети, дороги, интернет, нейросети

🔗 Связь с другими темами

Откуда пришли: Дискретная математика, комбинаторика Куда ведут: Алгоритмы на графах (поиск, кратчайшие пути), машинное обучение (Graph Neural Networks), анализ социальных сетей, PageRank, рекомендательные системы