Графы
Математический язык для описания систем, состоящих из объектов и связей между ними. Главные понятия: узел, ребро, степень узла, направленный и ненаправленный граф, полный граф, окрашенные рёбра. Удобен везде, где главное — структура связей, а не сами объекты по отдельности.
Узлы и рёбра
Граф — это пара множеств:
- Узлы (вершины, vertices) — объекты, между которыми могут быть связи. Изображаются точками
- Рёбра (edges) — связи между узлами. Изображаются линиями, соединяющими точки
Что такое узлы и рёбра — зависит от задачи:
- Социальная сеть: узлы — люди, рёбра — знакомства
- Дорожная сеть: узлы — города, рёбра — дороги
- Молекула: узлы — атомы, рёбра — химические связи
- Веб: узлы — страницы, рёбра — ссылки
Граф абстрагируется от природы объектов: важна только структура связей. Поэтому одна и та же математика работает для всех этих систем.
Направленные и ненаправленные графы
Ненаправленный граф — рёбра симметричны. Если A связан с B, то B связан с A автоматически. Используется для отношений типа «дружба», «знакомство», «химическая связь».
Направленный граф (орграф) — рёбра имеют направление. Связь от A к B не означает связь от B к A. Изображается стрелками. Используется для отношений типа «ссылается на», «отправляет данные», «является родителем».
Один и тот же граф можно сделать направленным или ненаправленным в зависимости от того, важна ли симметрия. Например, граф транспорта может быть ненаправленным (дорога работает в обе стороны) или направленным (улицы с односторонним движением).
Степень узла
Степень узла — число рёбер, инцидентных ему (то есть подсоединённых к нему).
В ненаправленном графе у каждого узла одно число — степень. В направленном — два: входящая степень (сколько рёбер ведут к узлу) и исходящая (сколько отходят).
Распределение степеней по узлам говорит о структуре графа:
- Однородное распределение — все узлы примерно одинаковы (как в случайном графе)
- Степенное распределение (long-tail) — несколько узлов с очень высокой степенью, остальные с малой. Типично для социальных сетей, веба, биологических сетей. Эти высокостепенные узлы называются «хабами»
Пути и связность
Путь — последовательность узлов, в которой каждые два соседних соединены ребром.
Связный граф — между любыми двумя узлами есть путь. Несвязный — распадается на несколько отдельных компонент.
Расстояние между двумя узлами — длина самого короткого пути между ними. Это базовая мера «близости» в графе.
Из теории графов известен парадокс «шесть рукопожатий»: в больших социальных сетях расстояние между любыми двумя людьми в среднем около шести рёбер. Это свойство называется «small-world» (тесный мир) — много локальных связей плюс несколько длинных, которые резко сокращают расстояния.
Полный граф
Полный граф Kₙ — граф на n узлах, в котором соединены каждые два узла. Каждый узел имеет степень n−1, общее число рёбер равно n(n−1)/2.
Полные графы — самые плотные графы заданного размера. Они моделируют ситуации «всё связано со всем»: все участники малой группы знакомы друг с другом, все 6 функций имеют отношение к каждой другой.
Примеры количества рёбер:
- K₃ — треугольник, 3 ребра
- K₄ — 6 рёбер
- K₅ — 10 рёбер
- K₆ — 15 рёбер
- Kₙ — n(n−1)/2 рёбер
Окрашенные рёбра
Если рёбра графа имеют разные «типы», их представляют как окрашенные: каждое ребро получает цвет, и цвет несёт информацию о типе связи.
Это позволяет в одном графе описывать несколько разных типов отношений между одними и теми же узлами. Например, в социальной сети: рёбра одного цвета — дружба, другого — рабочие связи, третьего — родство. Узлы те же, но структура каждого «слоя» отличается.
В терминах теории это эквивалентно мульти-графу — графу с несколькими параллельными рёбрами разных типов между парой узлов. Окрашивание — удобный способ это представить визуально.
Окраска рёбер полезна, когда есть структурный закон: «между этими двумя узлами обязательно есть ровно одно ребро каждого из K цветов». Тогда система становится регулярной: K окрашенных полных графов на одних и тех же узлах, и каждое ребро в одном из K цветов.
Применения
Граф — универсальная структура, через неё описывают:
- Социальные сети (анализ структуры сообществ, поиск влиятельных узлов)
- Транспорт и логистику (оптимизация маршрутов)
- Биологию (метаболические сети, нейронные связи, генные регуляторные сети)
- Лингвистику (синтаксические деревья, семантические сети)
- Машинное обучение (графовые нейронные сети)
Главная сила графов — отвлечься от конкретного содержания и работать только со структурой связей. Многие закономерности (плотность связей, наличие хабов, кратчайшие пути, кластеризация) проявляются одинаково в системах самой разной природы — просто потому, что у них одинаковая графовая топология.