🔴 Сложный ⏱️ 50 минут

Графы (основные понятия)

📋 Содержание урока

Графы (основные понятия) 🕸️

Открой любое приложение, которым пользуешься каждый день, и присмотрись к тому, что оно на самом деле хранит. Соцсеть хранит не список людей, а список людей и связей между ними — кто с кем дружит, кто на кого подписан. Навигатор хранит не список перекрёстков, а сеть дорог, соединяющих их. Поисковик хранит не список страниц, а гигантскую паутину гиперссылок, ведущих с одной страницы на другую. Во всех трёх случаях объекты сами по себе — люди, перекрёстки, страницы — не так интересны, как связи между ними. Структура данных, которая делает эти связи первоклассным гражданином — не побочным атрибутом, а самой сутью представления, — называется графом, и это тема данного урока.

До сих пор в этом курсе ты работал со структурами, где связи были предсказуемо ограничены: у элемента связного списка один сосед впереди, у узла бинарного дерева не больше двух детей и один родитель. Граф снимает это ограничение полностью: у вершины графа может быть сколько угодно соседей, а связи между вершинами не обязаны укладываться в аккуратную иерархию. Это не усложнение ради усложнения — это честное отражение того, как на самом деле устроены самые интересные данные вокруг нас: дружба в соцсети не иерархична, ссылки в интернете не образуют дерево, а молекула не выстраивается в цепочку. Граф — это структура данных, которая умеет описывать произвольные, «неаккуратные» связи, и именно поэтому она оказывается фундаментом для одних из самых мощных современных инструментов машинного обучения.

Возьми графовые нейронные сети (Graph Neural Networks, GNN) — один из самых быстрорастущих классов архитектур последних лет. Их вход — это не таблица с фиксированным числом столбцов и не последовательность токенов, а именно граф: молекула как граф атомов, соединённых химическими связями; социальная сеть как граф людей, соединённых дружбой; дорожная сеть как граф перекрёстков, соединённых улицами. GNN обучается, распространяя информацию вдоль рёбер графа — узел «спрашивает» у своих соседей, что они знают, обновляет своё представление и передаёт его дальше. Понимание того, что такое граф, вершина, ребро и степень вершины, — это не абстрактная теория, предваряющая GNN, а буквально словарь, на котором эта архитектура описывается. Точно так же рекомендательная система — скажем, «пользователи, которые купили это, также купили…» — очень часто внутри устроена как граф «пользователь–товар», где ребро между пользователем и товаром означает покупку, просмотр или оценку, а задача рекомендации сводится к поиску новых рёбер в этом графе. А графы знаний (knowledge graphs), на которых строятся многие системы вопросно-ответных систем и поисковики, — это буквально граф, где вершины — это сущности («Москва», «Россия», «Эйфелева башня»), а рёбра — отношения между ними («столица», «расположена в»).

В этом уроке ты разберёшься с базовым словарём теории графов, без которого невозможно двигаться дальше: что такое вершина и ребро, чем ориентированный граф отличается от неориентированного, зачем рёбрам иногда нужен вес, что такое степень вершины и как она по-разному считается в ориентированном и неориентированном случае, что такое путь, цикл и связность графа, и, наконец, почему дерево, которое ты изучал в предыдущих уроках, — это не отдельная структура, а частный, особенно дисциплинированный случай графа. Следующие уроки курса построят на этом фундаменте: способы представления графа в памяти компьютера, алгоритмы обхода, поиск кратчайших путей и построение минимального остовного дерева — но всё это бессмысленно обсуждать, пока не устоялся точный язык, на котором граф описывается. Этим языком и займёмся.

История: мосты, которые нельзя обойти

В 1736 году город Кёнигсберг (сегодня — российский Калининград) стоял на реке Прегель, которая делила его на четыре части суши: два берега и два острова, соединённые между собой семью мостами. У горожан была популярная головоломка-развлечение: можно ли пройти по городу маршрутом, который пересекает каждый из семи мостов ровно один раз? Причём неважно, с какого места начинать и где заканчивать — просто пройти по всем мостам, ни разу не повторившись. Многие пытались найти такой маршрут на практике, гуляя по городу, но ни у кого не получалось — и никто не мог объяснить, почему.

Задачу решил швейцарский математик Леонард Эйлер, и способ, которым он это сделал, оказался куда важнее самого ответа. Эйлер понял, что конкретная форма островов, длина мостов и расположение улиц не имеют никакого значения для этой задачи — важно только то, какие части суши соединены друг с другом и сколько мостов ведёт к каждой из них. Он абстрагировал реальную географию до предельно простой схемы: четыре части суши он представил точками, а семь мостов — линиями между этими точками. Сегодня мы бы сказали, что он построил граф. Дальше Эйлер заметил ключевую вещь: если по мосту нужно пройти ровно один раз, то в каждую часть суши (кроме, возможно, начальной и конечной точки маршрута) нужно один раз войти и один раз выйти — то есть число мостов, ведущих к этой части суши, должно быть чётным. В кёнигсбергской схеме у всех четырёх частей суши число мостов было нечётным (3, 3, 3 и 5), а значит, искомый маршрут не существует в принципе — не потому, что его никто не догадался найти, а потому, что он математически невозможен. Работу об этом Эйлер опубликовал в 1736 году под названием «Solutio problematis ad geometriam situs pertinentis» («Решение задачи, относящейся к геометрии положения») — и именно эта статья сегодня считается точкой рождения теории графов и одновременно одной из первых работ в области топологии.

Показательно, что после Эйлера теория графов почти сто лет оставалась математическим курьёзом без явного развития — следующий крупный сдвиг случился только в XIX веке, когда Густав Кирхгоф применил идею графа к анализу электрических цепей (его законы для токов и напряжений формулируются именно на языке графа схемы), а Артур Кэли использовал графы-деревья для подсчёта числа возможных химических изомеров углеводородов. Слово «граф» в современном математическом смысле ввёл в 1878 году английский математик Джеймс Сильвестр, тоже отталкиваясь от химических структурных формул — молекулы действительно естественно изображаются как вершины-атомы, соединённые рёбрами-связями, и эта параллель между графом и молекулой, кстати, прямо предвосхищает то, зачем сегодня графовые нейросети обучают предсказывать свойства новых лекарственных соединений.

Вершины, рёбра и ориентированность графа

Интуиция

Прежде всего откажись от идеи, что граф — это обязательно что-то похожее на дерево или список. Граф — это максимально общая структура «объекты плюс связи»: набор точек (их называют вершинами или узлами) и набор линий между некоторыми парами этих точек (их называют рёбрами или дугами). Никакой встроенной иерархии, никакого выделенного корня, никакого ограничения на число соседей у одной вершины. Единственное содержательное решение, которое нужно принять при построении графа, — это то, важно ли направление связи. Дружба в «ВКонтакте» до появления одностороннего фолловинга была симметричной: если ты друг Пети, то и Петя друг тебе, направление роли не играет. А вот подписка в Твиттере несимметрична: ты можешь подписаться на знаменитость, но она вовсе не обязана подписываться на тебя в ответ. Первый случай описывается неориентированным графом, второй — ориентированным.

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

Определение. Граф — это пара $G = (V, E)$, где $V$ — конечное непустое множество вершин (vertices, узлов), а $E$ — множество рёбер (edges), каждое из которых соединяет какую-то пару вершин из $V$. В неориентированном графе ребро — это неупорядоченная пара вершин $\{u, v\}$: связь симметрична, ребро $\{u,v\}$ и ребро $\{v,u\}$ — это одно и то же. В ориентированном графе (или орграфе, digraph) ребро (в этом контексте его чаще называют дугой) — это упорядоченная пара $(u, v)$: связь идёт строго от $u$ к $v$, и наличие дуги $(u,v)$ не подразумевает наличие дуги $(v,u)$.

Две вершины, соединённые ребром, называются смежными (соседними), а само ребро называется инцидентным обеим этим вершинам. Число вершин графа принято обозначать $n = |V|$, число рёбер — $m = |E|$.

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

Пример 1. Граф дружбы (неориентированный). Пусть в небольшой группе пять человек: Аня, Боря, Вера, Гриша, Даша. Известно, что Аня дружит с Борей, Аня дружит с Верой, Боря дружит с Гришей, Вера дружит с Дашей. Формально: $V = \{A, B, V, G, D\}$, $E = \{\{A,B\}, \{A,V\}, \{B,G\}, \{V,D\}\}$. Заметь, что $\{A,B\}$ и $\{B,A\}$ — одна и та же запись; если Аня дружит с Борей, то и Боря дружит с Аней, отдельно это записывать не нужно.

    A
   / \
  B   V
  |    \
  G     D

Пример 2. Граф подписок в Твиттере (ориентированный). Те же пять человек, но теперь связь — «подписан на». Пусть Аня подписана на Борю, Боря подписан на Аню (взаимно), а Вера подписана на Аню, но Аня на Веру — нет. Формально: $V=\{A,B,V\}$, $E = \{(A,B), (B,A), (V,A)\}$. Обрати внимание: здесь $(A,B)$ и $(B,A)$ — это два разных элемента множества $E$, оба присутствуют, потому что подписка взаимная; а вот $(A,V)$ отсутствует — Аня не подписана на Веру.

A ⇄ B      V → A

Пример 3. Граф веб-страниц (ориентированный). Страница wiki/Python содержит гиперссылку на wiki/Guido_van_Rossum, а обратной ссылки нет. Страница wiki/Guido_van_Rossum содержит ссылку на wiki/Python. Это два разных ориентированных ребра: $(\text{Python}, \text{Guido})$ и $(\text{Guido}, \text{Python})$ — то, что они существуют оба, надо установить явной проверкой каждой страницы, а не выводить одно из другого, как в неориентированном случае.

Разберём, как это выглядит в коде — простейшее представление графа через списки смежности (подробнее о представлениях — в следующем уроке):

# Неориентированный граф дружбы
friendship = {
    "Аня": ["Боря", "Вера"],
    "Боря": ["Аня", "Гриша"],
    "Вера": ["Аня", "Даша"],
    "Гриша": ["Боря"],
    "Даша": ["Вера"],
}
# ребро {Аня, Боря} хранится дважды: в списке Ани и в списке Бори — это плата
# за удобство прямого доступа "с кем дружит X" в обе стороны

# Ориентированный граф подписок
follows = {
    "Аня": ["Боря"],
    "Боря": ["Аня"],
    "Вера": ["Аня"],   # Вера подписана на Аню
    # у Ани нет "Вера" в списке — подписка не взаимная
}

Почему это важно

Выбор между ориентированным и неориентированным графом — это не техническая деталь, а моделирующее решение, которое напрямую определяет, какие вопросы к данным вообще можно задавать. Если ты по ошибке смоделируешь ориентированные подписки как неориентированную дружбу, ты потеряешь принципиально важную информацию — то, что влияние в соцсети направлено (блогер с миллионом подписчиков и один из его читателей находятся в принципиально разных позициях графа), и алгоритмы вроде PageRank, о которых пойдёт речь дальше в курсе, вообще не имеют смысла без направленности рёбер. В графовых нейросетях выбор ориентированности определяет саму архитектуру: message passing (передача сообщений между вершинами вдоль рёбер) на ориентированном графе обычно распространяет информацию только в одну сторону, если явно не добавить обратные рёбра, — и то, забыл ли инженер об этом при построении графа молекулы или транспортной сети, может радикально повлиять на качество модели.

Взвешенные графы

Интуиция

Одного факта «эти две вершины соединены» часто недостаточно. Между двумя городами может быть дорога, но 50 километров — это не то же самое, что 500. Пользователь может поставить товару оценку 5, а может — оценку 1, и оба факта — это «связь» в графе рекомендаций, но противоположная по смыслу. Когда важна не только сама связь, но и её «сила», «стоимость» или «интенсивность», к ребру приписывается число — вес.

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

Определение. Взвешенный граф — это граф $G=(V,E)$ вместе с функцией веса $w: E \to \mathbb{R}$, которая каждому ребру ставит в соответствие число (вес). Граф без такой функции (где значение имеет только сам факт наличия связи) называется невзвешенным; формально его можно считать взвешенным графом, где все веса равны единице. Вес ребра может обозначать что угодно в зависимости от предметной области: расстояние, время в пути, пропускную способность, стоимость, силу связи, вероятность.

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

Пример 1. Дорожная карта. Вершины — перекрёстки и населённые пункты, рёбра — дороги между ними, вес ребра — расстояние в километрах (или время в пути с учётом пробок). Граф здесь неориентированный (по большинству дорог можно проехать в обе стороны) и взвешенный: ребро Москва–Тверь весит примерно 180, а не просто «существует».

roads = {
    ("Москва", "Тверь"): 180,
    ("Тверь", "Санкт-Петербург"): 480,
    ("Москва", "Санкт-Петербург"): 650,   # напрямую длиннее, чем через Тверь
}

Пример 2. Граф «пользователь–товар» в рекомендательной системе. Вершины двух типов: пользователи и товары (такой граф с двумя непересекающимися группами вершин, где рёбра идут только между группами, называется двудольным — bipartite graph, подробнее об этом виде графов вспомнишь в дальнейших курсах). Ребро между пользователем и товаром означает взаимодействие — покупку, просмотр, оценку, — а вес ребра кодирует силу этого взаимодействия: оценка от 1 до 5, число повторных покупок, время просмотра в секундах. Рекомендательная система, по сути, ищет вершины товаров, «близкие» в этом графе к вершине конкретного пользователя, и вес ребра напрямую участвует в этой оценке близости.

# вес = рейтинг, поставленный пользователем товару
interactions = {
    ("user_42", "item_101"): 5,
    ("user_42", "item_205"): 2,
    ("user_87", "item_101"): 4,
}

Пример 3. Граф знаний с весами уверенности. Граф знаний хранит факты в виде троек (субъект, отношение, объект): (Эйлер, родился_в, Базель), (Кёнигсберг, находится_в, Пруссия). Если граф знаний строится автоматически — например, языковой моделью, извлекающей факты из текста, — не все извлечённые факты одинаково надёжны. Вес ребра в этом случае может обозначать уверенность модели в достоверности факта: ребро (Эйлер, родился_в, Базель) может иметь вес 0.98, если факт подтверждён множеством источников, а сомнительное, единично встреченное утверждение — вес 0.3. Дальнейшая обработка графа (например, фильтрация фактов для ответа на вопрос пользователя) может учитывать только рёбра с весом выше некоторого порога.

Почему это важно. Вес ребра — это то, что превращает граф из чисто топологической структуры («что с чем соединено») в количественную модель реального явления («насколько сильно», «как далеко», «с какой уверенностью»). Почти все содержательные алгоритмы на графах, которые встретятся дальше в курсе, — поиск кратчайшего пути алгоритмом Дейкстры, построение минимального остовного дерева — не имеют смысла без весов: «кратчайший» путь и «минимальное» дерево определяются именно суммой весов рёбер, а не количеством рёбер как таковым. В графовых нейросетях вес ребра часто становится частью так называемых edge features — признаков, которые сеть учитывает при передаче сообщения вдоль этого ребра, наряду с признаками самих вершин.

Степень вершины

Интуиция

Степень вершины отвечает на простой вопрос: насколько эта вершина «занята» связями? У человека в соцсети с 800 друзьями степень намного выше, чем у новичка с тремя друзьями, — и это прямо отражает его позицию в сети, вероятность быть «мостом» между разными сообществами, потенциальную скорость распространения информации от него. В ориентированном графе вопрос раздваивается: интересно не только «сколько связей у вершины вообще», а «сколько связей входит в неё» и «сколько выходит из неё» — и это два принципиально разных числа, которые несут разный смысл.

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

Определение. В неориентированном графе степенью вершины $v$ (обозначается $\deg(v)$) называется число рёбер, инцидентных этой вершине (то есть число соседей вершины $v$, а если в графе допускаются петли — ребро из вершины в саму себя, — петля добавляет к степени сразу $2$). В ориентированном графе для вершины $v$ различают входящую степень $\deg^-(v)$ — число дуг, входящих в $v$, и исходящую степень $\deg^+(v)$ — число дуг, выходящих из $v$.

Из определения степени в неориентированном графе следует важный факт, известный как лемма о рукопожатиях: каждое ребро вносит вклад ровно в две степени (по одному разу для каждого из двух его концов), поэтому сумма степеней всех вершин графа всегда равна удвоенному числу рёбер:

$$\sum_{v \in V} \deg(v) = 2|E|.$$

Название «лемма о рукопожатиях» — это отсылка к бытовой аналогии: если на вечеринке каждое рукопожатие — это ребро между двумя людьми, то сумма чисел «со сколькими людьми пожал руку каждый гость» всегда чётна, потому что каждое рукопожатие засчитывается дважды — один раз для каждого участника.

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

Пример 1. Степень в графе дружбы. Вернись к графу из первого раздела: $E = \{\{A,B\}, \{A,V\}, \{B,G\}, \{V,D\}\}$. Степень Ани $\deg(A) = 2$ (соседи — Боря и Вера), степень Бори $\deg(B) = 2$ (Аня и Гриша), степень Гриши $\deg(G)=1$ (только Боря), степень Даши $\deg(D)=1$. Проверим лемму о рукопожатиях: сумма степеней $= 2+2+1+2+1 = 8$, число рёбер $|E|=4$, и действительно $8 = 2\cdot 4$.

Пример 2. Входящая степень как основа PageRank. В графе веб-страниц входящая степень страницы — это число других страниц, которые на неё ссылаются. Интуитивно, чем больше страниц ссылаются на данную, тем она «авторитетнее» — именно на этой интуиции, доведённой до строгого рекурсивного алгоритма (важна не просто входящая степень, а «важность» тех, кто ссылается), был построен PageRank — алгоритм ранжирования, с которого начинался поисковик Google. Пусть на страницу wiki/Python ссылаются пять других страниц, а ни одна страница, на которую ссылается сама wiki/Python, не имеет больше одной входящей ссылки, — уже одно это грубое сравнение входящих степеней подсказывает, какая страница вероятнее окажется выше в выдаче.

Пример 3. Исходящая степень и разреженность реального графа. В графе подписок Твиттера у обычного пользователя исходящая степень (число тех, на кого он подписан) обычно составляет несколько сотен, тогда как у популярных аккаунтов входящая степень (число подписчиков) может достигать десятков миллионов. Это иллюстрирует важное эмпирическое свойство реальных сетей: распределение степеней вершин в социальных сетях, вебе, сетях цитирования крайне неравномерно — подавляющее большинство вершин имеют низкую степень, но существует небольшое число вершин-хабов с экстремально высокой степенью (такие сети называют безмасштабными, scale-free, а распределение степеней в них хорошо описывается степенным законом, а не привычным нормальным распределением).

def degree_undirected(graph, v):
    return len(graph[v])

def in_out_degree(digraph_edges, v):
    in_deg = sum(1 for (u, w) in digraph_edges if w == v)
    out_deg = sum(1 for (u, w) in digraph_edges if u == v)
    return in_deg, out_deg

edges = [("A","B"), ("B","A"), ("V","A")]
print(in_out_degree(edges, "A"))  # (2, 1) — входящих 2, исходящих 1

Почему это важно. Для ориентированного графа справедлив аналог леммы о рукопожатиях: сумма всех входящих степеней равна сумме всех исходящих степеней и равна общему числу рёбер, $\sum_v \deg^-(v) = \sum_v \deg^+(v) = |E|$ — это полезный инструмент самопроверки при построении графа руками или отладке кода, который его строит. А сама степень вершины — один из первых и самых дешёвых в вычислении признаков, которые используются при анализе графов и как входной признак вершины в графовых нейросетях: даже без единого шага обучения знание степени вершины часто уже неплохо предсказывает её «важность» в сети — от выявления инфлюенсеров в соцсети до поиска ключевых узлов, отказ которых развалит транспортную сеть на изолированные куски.

Путь, цикл и связность графа

Интуиция

Одиночная связь между двумя вершинами — это начало, но по-настоящему интересные вопросы к графу звучат иначе: можно ли вообще добраться от одной вершины до другой, если напрямую ребра между ними нет, а только через цепочку промежуточных? Существует ли способ вернуться туда, откуда начал, не повторяя уже пройденные шаги? И охватывает ли граф в целом одну связную «территорию» или распадается на несколько изолированных островов, между которыми вообще нет никакого сообщения? Эти три вопроса формализуются понятиями пути, цикла и связности — и именно они лежат в основе почти всех алгоритмов обхода и поиска, которые ждут тебя в следующих уроках курса.

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

Определение. Путь в графе — это последовательность вершин $v_0, v_1, \dots, v_k$, в которой каждая пара соседних вершин $(v_{i}, v_{i+1})$ соединена ребром графа. Длина пути обычно измеряется числом рёбер в нём (то есть $k$), либо, во взвешенном графе, суммой весов этих рёбер. Простой путь не повторяет вершин. Цикл — это путь, у которого начальная и конечная вершина совпадают ($v_0 = v_k$), а все промежуточные вершины различны (для простого цикла) и $k \ge 3$ в простом неориентированном графе без петель и кратных рёбер (два ребра, соединяющие ту же пару вершин, дали бы «цикл» длины 2, который обычно не считается содержательным). Неориентированный граф называется связным, если между любой парой его вершин существует путь. Если граф не связен, он распадается на компоненты связности — максимальные подмножества вершин, каждое из которых связно само по себе, но между разными компонентами пути нет.

Для ориентированных графов понятие связности расщепляется на два: граф сильно связен, если из любой вершины можно по направленным дугам добраться до любой другой (с учётом направления); граф слабо связен, если он стал бы связным, если временно забыть про направление рёбер. Граф подписок из примера 2 первого раздела ($A \leftrightarrows B$, $V \to A$) слабо связен (все три вершины в одной «территории», если не учитывать направление), но не сильно связен — из Веры можно дойти до Ани, но обратно из Ани в Веру пути нет, потому что дуги $(A, V)$ не существует.

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

Пример 1. Путь в графе дружбы и «шесть рукопожатий». В графе дружбы из первого раздела ($A$–$B$, $A$–$V$, $B$–$G$, $V$–$D$) путь от Гриши до Даши выглядит так: $G \to B \to A \to V \to D$ — четыре ребра, хотя Гриша и Даша никогда напрямую не знакомы. Это в точности та идея, которая стоит за знаменитой гипотезой «шести рукопожатий» (six degrees of separation) — эмпирическое наблюдение (впервые статистически исследованное психологом Стэнли Милгрэмом в 1960-х), что в графе человеческих знакомств практически любые два человека на Земле связаны цепочкой не более чем из шести-семи посредников, несмотря на то что напрямую знаком каждый лишь с ничтожной долей всех людей на планете.

Пример 2. Цикл в графе зависимостей задач. Представь систему сборки проекта, где модуль $A$ зависит от модуля $B$ (то есть чтобы собрать $A$, нужно сначала собрать $B$), $B$ зависит от $C$, а $C$ по ошибке зависит от $A$. Это ориентированный граф с дугами $(A,B), (B,C), (C,A)$ — и это цикл. Циклическая зависимость — это фатальная ошибка проектирования: невозможно определить, с чего начинать сборку, ведь каждый из трёх модулей требует, чтобы кто-то другой был собран первым. Реальные системы сборки (npm, Maven, Bazel) явно проверяют граф зависимостей на отсутствие циклов перед тем, как приступить к работе — эта проверка называется поиском цикла и станет темой одного из следующих уроков.

Пример 3. Компоненты связности в графе социальной сети. Пусть в базе пользователей соцсети есть группа из шести человек, где Аня–Боря–Вера образуют треугольник знакомств, а Гриша–Даша образуют отдельную пару, и между этими двумя группами нет ни единого общего друга, а седьмой пользователь Женя вообще ни с кем не знаком. Такой граф имеет три компоненты связности: $\{A,B,V\}$, $\{G,D\}$ и $\{Ж\}$ (изолированная вершина — тоже компонента связности, просто состоящая из одной вершины и не имеющая рёбер). На практике поиск компонент связности в графе взаимодействий — это ровно тот алгоритмический приём, который лежит в основе обнаружения сообществ (community detection) в соцсетях и кластеризации пользователей по паттернам поведения.

graph = {
    "A": ["B", "V"], "B": ["A", "V"], "V": ["A", "B"],
    "G": ["D"], "D": ["G"],
    "Ж": [],
}

def find_component(graph, start):
    visited, stack = set(), [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node])
    return visited

print(find_component(graph, "A"))  # {'A', 'B', 'V'}
print(find_component(graph, "Ж"))  # {'Ж'}

Почему это важно. Путь и связность — это не отвлечённая теория, а прямой ответ на вопрос «достижимо ли одно из другого», который постоянно возникает на практике: достижим ли сервер из данной точки сети, есть ли способ добраться от одной точки города до другой, существует ли цепочка знакомств между двумя пользователями. В графовых нейросетях идея пути напрямую связана с механизмом message passing: за один «слой» сети информация от вершины распространяется только до непосредственных соседей (путь длины 1), за $k$ слоёв — до вершин, достижимых путём длины не более $k$ (это называется рецептивным полем вершины, receptive field), и выбор числа слоёв сети — это прямой выбор того, насколько далёкие по графу связи модель способна учитывать.

Полный граф и дерево как частный случай графа

Интуиция

Полезно держать в голове два крайних случая, между которыми располагается любой связный граф. На одном полюсе — граф, где связей ровно столько, сколько нужно для связности, и ни одной лишней: убери любое ребро — и граф распадётся на две компоненты. Такой минимально достаточный, экономный граф без единого цикла — это в точности дерево, структура, которую ты подробно изучал в двух предыдущих уроках. На другом полюсе — граф, где связаны абсолютно все пары вершин без исключения, максимум возможных рёбер при данном числе вершин. Это полный граф. Между этими двумя полюсами лежит огромное пространство «обычных» графов реального мира — ни максимально экономных, ни максимально насыщенных.

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

Определение. Полный граф на $n$ вершинах, обозначается $K_n$, — это неориентированный граф, в котором каждая пара различных вершин соединена ребром. Число рёбер полного графа равно $\binom{n}{2} = \dfrac{n(n-1)}{2}$.

Дерево — это связный граф без циклов. Эквивалентная и очень полезная переформулировка: связный граф на $n$ вершинах является деревом тогда и только тогда, когда он содержит ровно $n-1$ ребро — ни одним больше (иначе неизбежно появился бы цикл), ни одним меньше (иначе граф не был бы связным). Ещё одно эквивалентное свойство дерева: между любыми двумя его вершинами существует ровно один простой путь — ни одного (граф не связен) и не два разных (это означало бы существование цикла).

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

Пример 1. Полный граф как модель полного доверия. В маленькой рабочей группе из четырёх человек, где действительно каждый лично знаком с каждым и все связи взаимны, граф дружбы — это $K_4$: $\binom{4}{2}=6$ рёбер. Если добавить пятого человека, знакомого со всеми предыдущими четырьмя, число рёбер полного графа подскакивает до $\binom{5}{2}=10$ — рост числа рёбер полного графа квадратичен по числу вершин, и именно поэтому по-настоящему большие полные графы (сотни тысяч вершин, все пары связаны) практически не встречаются в реальных данных: хранить и обрабатывать квадратичное число связей становится непозволительно дорого уже при относительно скромных $n$.

Пример 2. Дерево как иерархия графа знаний. Возьми биологическую систематику — классическую иерархию «вид → род → семейство → отряд → класс → тип → царство». Это дерево: у каждого узла (кроме корня, скажем, «Жизнь») ровно один родитель, циклов нет, а число рёбер ровно на единицу меньше числа узлов. В графах знаний общего вида иерархические отношения (is-a, «является частным случаем») часто образуют именно древовидную подструктуру внутри куда более общего графа, где остальные типы отношений (например, «расположен в», «является автором») добавляют дополнительные рёбра, разрушающие древовидность целого графа знаний, но не отдельной иерархической его части.

Пример 3. Проверка «дерево или нет» на конкретных числах. Дан связный граф на $n=6$ вершинах с $m=6$ рёбрами. Является ли он деревом? По критерию числа рёбер: дерево на 6 вершинах обязано иметь ровно $6-1=5$ рёбер, а у нас $m=6$ — на одно больше. Значит, граф не дерево: лишнее шестое ребро гарантированно создаёт хотя бы один цикл, даже если граф остаётся связным (сам по себе избыток рёбер над $n-1$ при сохранении связности всегда означает наличие хотя бы одного цикла — это прямое следствие определения дерева, но не наоборот: связный граф с $n-1$ ребром гарантированно дерево, а граф с $n-1$ ребром без гарантии связности деревом быть не обязан, потому что может распадаться на несколько компонент, суммарно дающих $n-1$ ребро при $n$ вершинах и являющихся набором из нескольких меньших деревьев — такую структуру называют лесом).

def is_tree(n, edges):
    if len(edges) != n - 1:
        return False  # необходимое условие, но нужно ещё проверить связность
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    visited = set()
    stack = [0]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node])
    return len(visited) == n  # все ли вершины достигнуты — граф связен

print(is_tree(4, [(0,1), (1,2), (1,3)]))  # True — дерево: 3 ребра, все вершины достижимы
print(is_tree(4, [(0,1), (1,2), (2,3), (3,0)]))  # False — 4 ребра при n=4, есть цикл

Почему это важно. Понимание дерева как частного, «бесциклового и минимально связного» случая графа — это не терминологическая тонкость, а мост между всем, что ты изучал в предыдущих двух уроках, и всем, что предстоит изучить дальше. Алгоритмы обхода дерева (которые ты уже видел) обобщаются на обход произвольного графа с единственной дополнительной сложностью — необходимостью следить за уже посещёнными вершинами, чтобы не зациклиться (в дереве циклов по определению нет, поэтому раньше эта проблема просто не возникала). А задача построения минимального остовного дерева, которая ждёт впереди в этом курсе, — это буквально задача «выбрать в связном взвешенном графе поддерево (в смысле — связный ациклический подграф, охватывающий все вершины) с минимальной суммой весов», то есть найти самое дешёвое дерево, «спрятанное» внутри более богатого графа.

Практика: 30 заданий

Базовые (задания 1–10)

Задание 1. Дан список вершин $V=\{1,2,3,4\}$ и рёбер $\{1,2\}, \{2,3\}, \{3,4\}, \{4,1\}$. Нарисуй граф и определи, ориентированный он или неориентированный.

Решение:

Шаг 1. Рёбра заданы как неупорядоченные пары в фигурных скобках $\{1,2\}$ — это признак неориентированного графа (для ориентированного использовалась бы запись со скобками и порядком, например $(1,2)$).

Шаг 2. Строим граф: вершины 1, 2, 3, 4 образуют цикл — 1 соединена с 2 и с 4, 2 соединена с 1 и с 3, 3 соединена с 2 и с 4, 4 соединена с 3 и с 1.

1 - 2
|   |
4 - 3

Ответ: граф неориентированный, представляет собой цикл (квадрат) из четырёх вершин

Задание 2. В неориентированном графе с рёбрами $\{A,B\}, \{A,C\}, \{A,D\}, \{B,C\}$ вычисли степень каждой вершины.

Задание 3. В ориентированном графе даны дуги $(A,B), (B,C), (C,A), (A,C)$. Вычисли входящую и исходящую степень вершины $A$.

Задание 4. Дан граф с рёбрами $\{1,2\}, \{2,3\}, \{3,4\}$. Является ли последовательность $1,2,3,4$ путём в этом графе? А последовательность $1,3,4$?

Задание 5. Дан граф с рёбрами $\{A,B\}, \{B,C\}, \{C,A\}$. Является ли последовательность $A,B,C,A$ циклом?

Задание 6. Дан граф с вершинами $\{1,2,3,4,5\}$ и рёбрами $\{1,2\}, \{2,3\}, \{4,5\}$. Является ли этот граф связным?

Задание 7. Сколько рёбер в полном графе $K_6$?

Задание 8. Сколько рёбер должно быть у дерева с $n=12$ вершинами?

Задание 9. Дана матрица смежности $3\times 3$ графа:

$$\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$

Является ли соответствующий граф ориентированным или неориентированным? Обоснуй по свойству матрицы.

Задание 10. В графе $7$ рёбер. Чему равна сумма степеней всех его вершин?

Средние (задания 11–20)

Задание 11. Граф дружбы: $\{A,B\}, \{B,C\}, \{A,C\}, \{D,E\}, \{F\}$ — вершина $F$ без единого ребра. Найди все компоненты связности.

Задание 12. Связный граф на $n=5$ вершинах содержит $4$ ребра. Является ли он деревом? Обоснуй, какого дополнительного условия было бы достаточно, а какого нет.

Задание 13. Взвешенный граф путей между тремя городами: $A$–$B$ вес $10$, $B$–$C$ вес $15$, $A$–$C$ вес $30$. Какой путь из $A$ в $C$ короче: напрямую или через $B$?

Задание 14. В ориентированном графе дуги $(A,B), (B,C)$. Существует ли путь из $C$ в $A$? Существует ли путь из $A$ в $C$?

Задание 15. Граф рекомендательной системы: пользователи $\{u_1, u_2\}$, товары $\{t_1, t_2, t_3\}$, рёбра-взаимодействия $\{u_1,t_1\}, \{u_1,t_2\}, \{u_2,t_2\}, \{u_2,t_3\}$. Вычисли степень каждого товара. Какой товар взаимодействует с наибольшим числом пользователей?

Задание 16. Граф знаний содержит тройки (Эйлер, родился_в, Базель), (Эйлер, решил, Задача_о_мостах), (Задача_о_мостах, находится_в, Кёнигсберг). Представь этот граф знаний как ориентированный граф: перечисли вершины и дуги.

Задание 17. Граф зависимостей задач (ориентированный): $(A,B), (B,C), (C,D), (D,B)$. Есть ли в этом графе цикл? Если да, укажи его.

Задание 18. В графе соцсети степени вершин: $A{:}150$, $B{:}3$, $C{:}5$, $D{:}2$, $E{:}4$. Какую вершину логично считать потенциальным «хабом» (инфлюенсером), и почему одной лишь степени вершины на практике часто недостаточно для точного вывода?

Задание 19. Дана матрица смежности взвешенного графа:

$$\begin{pmatrix} 0 & 3 & 0 \\ 3 & 0 & 7 \\ 0 & 7 & 0 \end{pmatrix}$$

Определи степень вершины 2 (считая степень как число ненулевых соседей, без учёта конкретных весов).

Задание 20. Дан граф по списку смежности: $1{:}[2,3]$, $2{:}[1]$, $3{:}[1]$, $4{:}[5]$, $5{:}[4]$. Вручную (без готового алгоритма, простым прослеживанием) определи число компонент связности и перечисли их.

Сложные (задания 21–30)

Задание 21. Кёнигсбергская задача о мостах: 4 части суши (обозначим $A$, $B$, $C$, $D$), 7 мостов, при этом степени вершин в графе мостов равны $\deg(A)=5$, $\deg(B)=3$, $\deg(C)=3$, $\deg(D)=3$. Используя рассуждение Эйлера про чётность степеней, объясни, почему обойти все мосты ровно по одному разу невозможно.

Задание 22. Докажи (на общем рассуждении, не для конкретного графа) формулу $\sum_{v} \deg(v) = 2|E|$, объяснив, почему каждое ребро учитывается ровно дважды.

Задание 23. В графе с вершинами $\{1,2,3,4,5,6\}$ и рёбрами $\{1,2\}, \{1,3\}, \{2,4\}, \{3,5\}, \{4,6\}$ представь, что сообщение (как в графовой нейросети) распространяется от вершины $1$ по одному «шагу» за раз — на шаге $k$ сообщение достигает всех вершин, находящихся на расстоянии ровно $k$ рёбер от вершины $1$. Перечисли, какие вершины получат сообщение на шаге 1 и на шаге 2.

Задание 24. Для разреженного графа со $100000$ вершинами, где у каждой вершины в среднем $10$ соседей, сравни (порядок величины, без точных формул хранения) объём памяти под список смежности и под полную матрицу смежности.

Решение:

Шаг 1. Список смежности хранит для каждой вершины список её реальных соседей — общий объём пропорционален числу рёбер: при $100000$ вершинах и среднем количестве соседей $10$ суммарное число хранимых «записей о соседстве» — порядка $100000 \times 10 = 1\,000\,000$.

Шаг 2. Матрица смежности хранит по одной ячейке на каждую возможную пару вершин, независимо от того, есть между ними ребро или нет — размер матрицы $100000 \times 100000 = 10^{10}$ ячеек.

Шаг 3. Сравниваем порядки величин: список смежности требует хранения порядка миллиона записей, матрица смежности — порядка десяти миллиардов ячеек, то есть матрица требует примерно в десять тысяч раз больше памяти для этого конкретного (разреженного) графа.

Ответ: для разреженного графа список смежности экономичнее матрицы смежности на несколько порядков — при $10$ соседях на вершину и $100000$ вершин список смежности хранит около миллиона записей против десяти миллиардов ячеек матрицы; в реальных социальных сетях и веб-графах, где число рёбер намного меньше квадрата числа вершин, матрица смежности практически никогда не используется как основное представление

Задание 25. Докажи содержательно: если связный граф на $n$ вершинах содержит строго больше $n-1$ ребра, он обязательно содержит хотя бы один цикл.

Задание 26. В ориентированном графе с дугами $(A,B), (B,C), (C,A), (C,D)$ определи, является ли граф сильно связным.

Задание 27. В графе соцсети $n=1000$ пользователей и $m=15000$ рёбер дружбы. Вычисли среднюю степень вершины и содержательно сравни полученную плотность графа с плотностью полного графа $K_{1000}$.

Задание 28. Взвешенный граф маршрутов: $A$–$B$ вес $4$, $B$–$D$ вес $5$, $A$–$C$ вес $2$, $C$–$D$ вес $6$, $A$–$D$ вес $11$. Переберите три возможных пути из $A$ в $D$ и определите путь с минимальной суммой весов.

Задание 29. Для трёх разных типов графовых данных — (а) очень плотный граф авиамаршрутов между 50 крупными аэропортами, где рейсы есть почти между каждой парой; (б) граф молекулы из 30 атомов, где у каждого атома от 1 до 4 связей; (в) граф веб-страниц из миллиарда узлов с несколькими ссылками у каждой страницы — для каждого предложи, какое представление (список смежности или матрица смежности) практичнее, и обоснуй.

Решение:

Шаг 1 (сценарий а). При 50 аэропортах и почти полной насыщенности связями граф близок к плотному — число рёбер приближается к $\binom{50}{2}\approx 1225$, что сопоставимо с размером матрицы $50\times 50=2500$ ячеек. Здесь матрица смежности практична: она компактна при таком малом $n$ и даёт мгновенную проверку наличия рейса между любой парой аэропортов за одно обращение к ячейке.

Шаг 2 (сценарий б). Молекула — разреженный граф (у атома не более 4 связей, а всего атомов 30): список смежности здесь заметно компактнее матрицы $30\times30=900$ ячеек, большинство из которых были бы нулями, тогда как реальных связей — не более $30\times4/2=60$.

Шаг 3 (сценарий в). Граф веб-страниц из миллиарда вершин с несколькими ссылками у каждой — предельно разреженный граф. Матрица смежности потребовала бы $10^{18}$ ячеек — физически невозможный объём памяти. Список смежности — единственный разумный вариант, объём которого пропорционален реальному числу ссылок, а не квадрату числа страниц.

Ответ: (а) матрица смежности — граф плотный и небольшой; (б) список смежности — граф разреженный, атомов немного, но матрица была бы избыточной; (в) список смежности — при миллиарде вершин матрица смежности физически неприменима, только разреженное представление

Задание 30. Спроектируй (без кода, в общих чертах) представление данных для трёх сценариев: (а) граф дружбы в соцсети на 500 миллионов пользователей; (б) граф знаний с миллионом сущностей и помеченными отношениями между ними, где важна уверенность в каждом факте; (в) дорожная карта города с временем в пути, которое меняется в зависимости от пробок. Для каждого укажи: ориентированный или нет, взвешенный или нет, и общий принцип представления (плотное/разреженное).

Решение:

Шаг 1 (сценарий а). Дружба в общем случае взаимна (если это модель «дружбы», а не «подписки») — граф неориентированный, невзвешенный (сам факт дружбы либо есть, либо нет, без степени). При 500 миллионах пользователей и типичном числе друзей в пределах пары сотен граф крайне разрежен — необходимо разреженное представление вроде списка смежности; плотная матрица потребовала бы порядка $(5\times10^8)^2$ ячеек, что абсолютно нереалистично.

Шаг 2 (сценарий б). Граф знаний по своей природе ориентированный (отношение «родился_в» имеет направление — от человека к месту, а не наоборот) и взвешенный, если нужно хранить уверенность в факте (вес ребра = вероятность/достоверность), либо, точнее, помеченный (каждая дуга несёт метку отношения) и дополнительно взвешенный. При миллионе сущностей и разумном числе фактов на сущность граф разрежен — представление на основе списка смежности (или, чаще на практике, набора троек субъект-отношение-объект, что структурно эквивалентно списку рёбер).

Шаг 3 (сценарий в). Дорожная сеть обычно неориентированная (по большинству дорог движение двустороннее, хотя дороги с односторонним движением потребовали бы отдельных ориентированных дуг для точности) и обязательно взвешенная — вес ребра — это динамически меняющееся время в пути, зависящее от текущей загруженности. Граф городских дорог разрежен (у перекрёстка обычно несколько соседних улиц, а не связь со всем городом) — разреженное представление, при этом веса рёбер должны обновляться в реальном времени по данным о трафике, а не храниться как статические константы.

Ответ: (а) неориентированный, невзвешенный, разреженное представление; (б) ориентированный, взвешенный/помеченный, разреженное представление; (в) обычно неориентированный (за исключением дорог с односторонним движением), взвешенный с динамически обновляемыми весами, разреженное представление — во всех трёх случаях реальные графы крайне далеки от полного графа, и это определяющий факт при выборе способа их хранения

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

❌ Ошибка: Считать, что граф — это обязательно нечто похожее на дерево, с выделенным корнем и иерархией.

✅ Правильно: Граф в общем случае не имеет ни корня, ни ограничения на число соседей вершины — дерево является лишь частным, особенно дисциплинированным случаем графа, а не наоборот.

💡 Почему: Путаница приводит к попыткам искать в произвольном графе несуществующую иерархию или ошибочно считать, что у любой вершины не может быть больше двух соседей — оба предположения ломаются на первом же графе с циклом или с вершиной высокой степени.

❌ Ошибка: При подсчёте степени вершины в ориентированном графе складывать входящие и исходящие дуги без разбора, как в неориентированном случае.

✅ Правильно: В ориентированном графе входящая степень $\deg^-(v)$ и исходящая степень $\deg^+(v)$ — это два разных числа, которые нужно считать отдельно и не путать друг с другом.

💡 Почему: Для многих задач (например, PageRank или анализ влиятельности в соцсети) именно входящая степень несёт основной смысл, и смешение её с исходящей даёт качественно неверный результат — путаница между «на сколько ссылаются» и «на сколько ссылается сам».

❌ Ошибка: Путать путь и цикл, в частности — считать любую последовательность вершин с повторяющимся ребром «циклом».

✅ Правильно: Цикл — это путь, у которого совпадают начальная и конечная вершины, а промежуточные вершины при этом все различны (для простого цикла); простое «хождение туда-сюда» по одному и тому же ребру циклом не считается.

💡 Почему: Ошибочное распознавание цикла напрямую портит алгоритмы проверки зависимостей (например, обнаружение циклических зависимостей в системе сборки) — можно либо пропустить реальный цикл, либо ложно сообщить о несуществующем.

❌ Ошибка: Считать связность графа синонимом его «плотности» или полноты — например, полагать, что связный граф обязательно содержит много рёбер.

✅ Правильно: Минимально достаточное число рёбер для связности графа на $n$ вершинах — это ровно $n-1$ (дерево); связный граф может быть крайне экономным по числу рёбер и при этом оставаться полностью связным.

💡 Почему: Смешение «связности» с «плотностью» приводит к неверным интуитивным оценкам вроде «раз граф связный, значит рёбер в нём много» — большинство реальных связных графов (деревья, разреженные сети) на самом деле содержат рёбер немногим больше теоретического минимума.

❌ Ошибка: Забывать, что в неориентированном графе петля (ребро из вершины в саму себя, если такие допускаются моделью) добавляет к степени вершины сразу два, а не один.

✅ Правильно: Каждый конец ребра вносит единицу в степень своей вершины; у петли оба конца — одна и та же вершина, значит она вносит два в её степень, а не один.

💡 Почему: Забытый множитель два для петель ломает проверку по лемме о рукопожатиях и даёт неверный подсчёт степени в графах, где петли моделируют содержательную вещь — например, «самоссылку» страницы на саму себя в веб-графе.

❌ Ошибка: Путать вес ребра (стоимость одной конкретной связи) с длиной пути (суммой весов вдоль всей цепочки рёбер), и в результате искать «кратчайший путь» по числу рёбер вместо суммы весов, когда граф взвешенный.

✅ Правильно: В взвешенном графе «кратчайший путь» почти всегда означает путь с минимальной суммой весов, а не с минимальным числом рёбер — путь с меньшим числом рёбер, но с большими весами, может оказаться длиннее пути с бо́льшим числом более дешёвых рёбер (как в задании 28 выше).

💡 Почему: Алгоритмы поиска кратчайшего пути, которые встретятся дальше в курсе (алгоритм Дейкстры), явно оптимизируют сумму весов — если спутать эту цель с минимизацией числа рёбер, результат работы алгоритма будет казаться «неправильным», хотя на самом деле неверно было исходное ожидание.

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

✅ Граф $G=(V,E)$ — это структура «объекты плюс связи»: множество вершин $V$ и множество рёбер $E$, без встроенного ограничения на число соседей одной вершины и без обязательной иерархии

✅ В неориентированном графе ребро $\{u,v\}$ симметрично; в ориентированном графе (орграфе) дуга $(u,v)$ задаёт направление, и наличие $(u,v)$ не подразумевает наличие $(v,u)$

✅ Взвешенный граф снабжён функцией веса на рёбрах — весом может быть расстояние, стоимость, вероятность или сила связи; невзвешенный граф эквивалентен взвешенному, где все веса равны единице

✅ Степень вершины $\deg(v)$ в неориентированном графе — число инцидентных ей рёбер; в ориентированном графе различают входящую $\deg^-(v)$ и исходящую $\deg^+(v)$ степени по отдельности

✅ Лемма о рукопожатиях: сумма степеней всех вершин неориентированного графа равна удвоенному числу рёбер, $\sum_v \deg(v) = 2|E|$, поскольку каждое ребро вносит вклад в степень обоих своих концов

✅ Путь — последовательность вершин, где каждая соседняя пара соединена ребром; цикл — путь, начинающийся и заканчивающийся в одной вершине, с различными промежуточными вершинами

✅ Связный граф — граф, где между любой парой вершин есть путь; несвязный граф распадается на компоненты связности; для ориентированных графов различают слабую и сильную связность

✅ Полный граф $K_n$ содержит все возможные $\binom{n}{2}$ рёбер между $n$ вершинами; это верхняя граница насыщенности графа связями

✅ Дерево — связный граф без циклов; эквивалентно: связный граф ровно с $n-1$ ребром; эквивалентно: граф, где между любыми двумя вершинами существует ровно один простой путь — дерево является частным, минимально достаточным случаем графа

✅ Задача Эйлера о семи кёнигсбергских мостах (1736) — точка рождения теории графов: маршрут, проходящий по каждому ребру ровно один раз, существует только если в графе не более двух вершин нечётной степени

Связь с темами курса

🔙 Откуда пришли: Из уроков 256–258 — определение дерева, бинарные деревья поиска и их самобалансирующиеся варианты. Всё это время дерево рассматривалось как самостоятельная структура; в этом уроке оказалось, что дерево — лишь частный, ациклический и минимально связный случай куда более общей структуры — графа.

🔜 Куда идём:

Представление графов в памяти компьютера (урок 260) — списки смежности, матрицы смежности и списки рёбер, компромиссы между ними по памяти и скорости операций, ровно та тема, которую в этом уроке уже пришлось затронуть в практических заданиях
Обход графов, DFS и BFS (урок 261) — систематические способы посетить все вершины графа, обобщающие обходы дерева на случай, когда нужно явно следить за уже посещёнными вершинами, чтобы не зациклиться
Топологическая сортировка (урок 262) — прямое практическое применение понятия цикла в ориентированном графе: упорядочивание задач с зависимостями возможно только тогда, когда граф зависимостей ацикличен
Алгоритм Дейкстры и алгоритм Флойда — Уоршелла (уроки 263–264) — поиск кратчайшего пути во взвешенном графе, прямое развитие идеи «сумма весов вдоль пути», разобранной в этом уроке
Минимальное остовное дерево (урок 265) — задача найти самое дешёвое по сумме весов дерево, «спрятанное» внутри связного взвешенного графа и охватывающее все его вершины

🎯 В машинном обучении: Словарь этого урока — вершина, ребро, степень, путь, связность — это буквально тот язык, на котором описываются входные данные графовых нейронных сетей (GNN): молекулы для предсказания свойств лекарств, социальные сети для анализа влияния и обнаружения сообществ, транспортные сети для прогноза трафика. Граф «пользователь–товар» с весами взаимодействий лежит в основе рекомендательных систем, использующих коллаборативную фильтрацию или графовые эмбеддинги. Графы знаний — ориентированные помеченные графы фактов — используются в поисковых системах, вопросно-ответных системах и как способ снабдить языковую модель структурированными, проверяемыми фактами вместо (или в дополнение к) параметрической памяти внутри весов сети.

Интересные факты

📌 Задача о семи мостах Кёнигсберга — не просто исторический курьёз: после Второй мировой войны город был почти полностью разрушен и позже отстроен заново как советский Калининград, а из семи исторических мостов уцелели лишь два. Сегодня туристы могут своими ногами пройти маршрутом мостов, который прославил Эйлера, хотя сама головоломка в её первоначальном виде — с семью оригинальными мостами — больше не воспроизводима на местности.

📌 Слово «граф» (graph) в математическом смысле впервые употребил в 1878 году английский математик Джеймс Джозеф Сильвестр — не в связи с абстрактной математикой, а обсуждая структурные формулы органических молекул, где атомы естественно изображались точками, а химические связи — линиями между ними; это на сто с лишним лет предвосхитило современное применение графовых нейросетей именно к молекулярным данным.

📌 Гипотеза «шести рукопожатий» — идея, что любые два человека на Земле связаны цепочкой знакомств не длиннее шести-семи человек, — была экспериментально проверена психологом Стэнли Милгрэмом в 1967 году с помощью реальных писем, которые нужно было передавать через знакомых до указанного адресата; современные исследования на графе дружбы Facebook (более миллиарда пользователей) показали среднюю длину кратчайшего пути между двумя случайными пользователями около 4,7 — даже короче, чем в классической гипотезе.

📌 «Число Эрдёша» — шуточная, но вполне серьёзно используемая в математическом сообществе метрика — это длина кратчайшего пути в графе соавторства научных статей от конкретного математика до венгерского математика Пала Эрдёша, одного из самых плодовитых авторов в истории науки (более 1500 совместных публикаций с разными соавторами). У самого Эрдёша число Эрдёша равно 0, у его непосредственных соавторов — 1, и так далее; это реальный, часто вычисляемый пример понятия «путь в графе», примерённого к академическому сообществу.

Лайфхаки

💡 Прежде чем писать хоть строчку кода для работы с графом, всегда явно проговори для себя три вещи: ориентированный граф или нет, взвешенный или нет, допускаются ли петли и кратные рёбра (несколько разных рёбер между одной и той же парой вершин). Эти три решения определяют и структуру данных, и корректность почти всех дальнейших алгоритмов — ошибка здесь на старте почти гарантированно всплывёт позже в виде трудноуловимого бага.

💡 Если не уверен, связен ли данный граф, не нужно перебирать все пары вершин вручную — достаточно запустить один обход (как показано в заданиях этого урока) из произвольной вершины и проверить, все ли вершины оказались посещены; это станет темой следующего урока про DFS и BFS, но сама идея уже полностью доступна на уровне интуиции.

💡 Для быстрой прикидки, дерево ли перед тобой граф, сначала проверь самый дешёвый признак — число рёбер равно $n-1$? Если нет, дальше можно даже не проверять связность и отсутствие циклов: граф точно не дерево. Если да, необходимое условие выполнено, и остаётся проверить связность (отсутствие циклов в этом случае гарантируется автоматически).

💡 При работе с реальными графами (соцсети, вебграф, граф молекулы) сразу закладывай в голову, что граф почти наверняка разреженный — число рёбер намного меньше $\binom{n}{2}$. Эта интуиция сразу подсказывает правильное представление в памяти (список смежности, а не матрица) ещё до того, как ты вообще увидел данные.

💡 Когда встречаешь незнакомую задачу и не сразу понятно, при чём тут графы, попробуй явно задать себе вопрос: «что здесь объекты, а что — связи между ними?». Огромное количество задач, на первый взгляд далёких от теории графов — расписание экзаменов, распределение задач между исполнителями, анализ зависимостей в коде, — сводятся к графовой формулировке именно через этот вопрос, и уже для графовой формулировки существует богатый набор изученных алгоритмов.

💡 Не пытайся с ходу держать в голове весь граф целиком, особенно если он большой. Гораздо продуктивнее мыслить локально — «что видно из этой вершины на расстоянии одного-двух шагов» — именно так на самом деле думают и алгоритмы обхода, и графовые нейросети: они никогда не смотрят на граф целиком за один раз, а строят понимание итеративно, шаг за шагом расширяя область видимости от каждой вершины.

Граф — это, пожалуй, самая универсальная структура данных из всех, что встретятся в этом курсе: списки, стеки, очереди и даже деревья — всё это частные, более дисциплинированные случаи графа, выбранные ради удобства и эффективности там, где связи данных заранее укладываются в более простой узор. Настоящий, «дикий» мир данных — дружба людей, ссылки в интернете, атомы в молекуле, факты о мире — устроен именно как граф, без аккуратной иерархии и без ограничений на число соседей. Освоив базовый словарь этого урока — вершину, ребро, ориентированность, вес, степень, путь, цикл, связность и дерево как частный случай, — ты готов к следующему, куда более практическому шагу: научиться хранить графы в памяти компьютера эффективно и обходить их так, чтобы ни одна вершина не осталась непосещённой и ни один алгоритм не зациклился навсегда.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку

💬 Нашёл ошибку или есть вопрос по уроку? Написать в Telegram →