Вершина, ребро, путь, граф

Граф – универсальная дискретная модель для представления объектов и их связей. В информатике графы описывают сети (коммуникационные, социальные), зависимость модулей, маршруты, состояния автоматов. Для ЕГЭ по информатике умение работать с графами критично: нужно уверенно читать матрицы смежности, считать степени вершин, различать типы путей, находить кратчайшие пути в невзвешенных графах, распознавать связность и корректно интерпретировать входные данные.

Базовые определения (строго)

1. Граф
   

   Граф (неориентированный): G = (V, E),

   V – множество вершин, E ⊆ { {u, v} | u, v ∈ V, u ≠ v }.

   Ориентированный граф (орграф): G = (V, E),

   E ⊆ { (u, v) | u, v ∈ V, u ≠ v }.

   По умолчанию на ЕГЭ рассматриваются простые графы (без петель и кратных рёбер), если не оговорено иное.

2. Ребро и степень
   

   • В неориентированном графе ребро – неупорядоченная пара {u, v}.

   • В орграфе ребро – упорядоченная пара (u, v).

   Степень вершины в неориентированном графе:

   deg(v) = число рёбер, инцидентных v.

   Полустепени в орграфе:

   deg⁺(v) = |{ (v, x) ∈ E }|   // исходящая

   deg⁻(v) = |{ (x, v) ∈ E }|   // входящая

   Лемма о рукопожатиях (неориентированный):

   Σ_{v ∈ V} deg(v) = 2|E|.

   Для орграфа:

   Σ_{v ∈ V} deg⁺(v) = Σ_{v ∈ V} deg⁻(v) = |E|.

3. Маршрут, цепь, путь, цикл
   

   Пусть даны вершины v0, v1, …, vk.

   • Маршрут (walk) – последовательность вершин, где каждое соседнее пары соединены ребром. Повторы вершин/рёбер разрешены.

   • Цепь (trail) – маршрут без повторения рёбер.

   • Путь (path) – маршрут без повторения вершин (в орграфе учитываем направление).

   • Цикл – закрытый путь: v0 = vk, k ≥ 3 (для неориентированного) или ориентированная замкнутая последовательность (для орграфа).

   Длина маршрута/пути:

   len = число рёбер в последовательности.

4. Связность
   

   • Неориентированный граф связен, если между любой парой вершин существует путь. Иначе множества вершин распадаются на компоненты связности.

   • В орграфе различают:

   • сильную связность (из u достижима v и из v достижима u),

   • слабую связность (если заменить ориентированные рёбра на неориентированные – граф связен).

Представления графа (данные для программ)

1. Матрица смежности
   

   Квадратная матрица A размера n×n, где n = |V|.

   • Для неориентированного графа:

   A[i][j] = 1, если {vi, vj} ∈ E; иначе 0.   A – симметрична.

   • Для орграфа:

   A[i][j] = 1, если (vi, vj) ∈ E; иначе 0.

   Степени через матрицу смежности:

   deg(vi)   = Σ_{j=1..n} A[i][j]                  // неориентированный

   deg⁺(vi)  = Σ_{j=1..n} A[i][j];  deg⁻(vi) = Σ_{j=1..n} A[j][i]  // ориентированный

2. Списки смежности
   

   Для каждой вершины v хранится перечень её соседей:

   Adj[v] = { u | {v, u} ∈ E }  // неориент.

   Adj⁺[v] = { u | (v, u) ∈ E },  Adj⁻[v] = { u | (u, v) ∈ E }  // ориент.

   Списки смежности экономят память при разреженных графах (|E| ≪ |V|²) и обеспечивают линейные обходы.

3. Матрица инцидентности (реже на ЕГЭ)
   

   Матрица B размера |V|×|E|: столбец – ребро, строки – вершины. Удобна для задач линейной алгебры на графах.

Подсчёт путей и кратчайшие пути

1. Количество маршрутов фиксированной длины (через степени матрицы)
   

   Пусть A – матрица смежности. Тогда

   (A^k)[i][j] = число маршрутов длины k из vi в vj.

   Важно: это – маршруты (walks), не обязательно простые пути.

2. Кратчайшие пути в невзвешенном графе (BFS)
   

   Поиск в ширину (BFS) от s находит расстояния dist[v] – длины кратчайших путей по числу рёбер.

   Инициализация: dist[⋅] := ∞, dist[s] := 0; очередь Q := {s}

   Пока Q не пуста:

     v := pop(Q)

     для каждого соседа u ∈ Adj[v]:

         если dist[u] = ∞:

             dist[u] := dist[v] + 1; parent[u] := v; push(Q, u)

   Сложность: O(|V| + |E|) при списках смежности.

3. Подсчёт путей в ацикличном орграфе (DAG)
   

   В DAG можно посчитать число простых путей из s в t динамически, идя в топологическом порядке:

   ways[s] := 1; для остальных 0

   для v в топологическом порядке:

       для каждого ребра (v → u):

           ways[u] := ways[u] + ways[v]

   Сложность: O(|V| + |E|).

Специальные классы графов и свойства

1. Деревья
   

   Неориентированный связный граф без циклов. Эквивалентные свойства (для n=|V|):

   |E| = n - 1

   Между любой парой вершин – единственный простой путь

   Граф связен и ацикличен

2. Эйлеровы и гамильтоновы структуры (кратко)
   

   • Эйлеров цикл в неориентированном графе существует тогда и только тогда, когда граф связен по рёбрам и у каждой вершины чётная степень.

   • Эйлерова цепь (не цикл) – когда ровно у двух вершин нечётные степени (начало и конец).

   • Гамильтоновы пути/циклы – сложнее: общих простых критериев нет (в ЕГЭ обычно не требуют доказательств, только распознавание на малых графах).

Правила корректности для решений ЕГЭ

Правило 1. Явно фиксируйте индексацию: [1..n] или [0..n-1]. Никогда не смешивайте.
Правило 2. Для неориентированного графа матрица смежности симметрична; число рёбер:

|E| = (Σ_{i<j} A[i][j]) = (1/2) Σ_{i,j} A[i][j].

Правило 3. Петля {v, v} в неориентированном графе (если вдруг есть) добавляет 2 к deg(v) (редко на ЕГЭ, но знать полезно).
Правило 4. При чтении орграфа различайте deg⁺ и deg⁻; итоговые суммы равны |E|.
Правило 5. BFS – единственный корректный способ получать длины кратчайших путей в невзвешенном графе.
Правило 6. Для подсчёта числа маршрутов длины k используйте степени A^k; для простых путей в DAG – динамику в топологическом порядке.
Правило 7. В задачах «найти изолированные/листовые вершины»:

изолированная: deg(v) = 0,   лист (подвес): deg(v) = 1.

Правило 8. В неориентированном связном графе с n вершинами и n-1 рёбрами – всегда дерево.
Правило 9. При восстановлении пути после BFS храните parent[v] и идите назад от цели к источнику.
Правило 10. Всегда проверяйте граничные случаи: n=1, компонентность, отсутствие ребёр.

Мини-шпаргалка (копируемые формулы)

Рукопожатия (неориент.):      Σ deg(v) = 2|E|

Полустепени (ориент.):        Σ deg⁺(v) = Σ deg⁻(v) = |E|

Степени через A:              deg(vi)  = Σ_j A[i][j]

                              deg⁺(vi) = Σ_j A[i][j],   deg⁻(vi) = Σ_j A[j][i]

Маршруты через степени A:     (A^k)[i][j] = #маршрутов длины k из vi в vj

Кратчайшие пути (невзвеш.):   BFS, сложность O(|V|+|E|)

Дерево:                       связный, ацикличный, |E| = |V| - 1

Эйлеров цикл (неориент.):     граф связен по рёбрам ∧ ∀v: deg(v) – чётная

Эйлерова цепь (неориент.):    граф связен по рёбрам ∧ ровно две вершины нечётной степени

Иллюстративные алгоритмы (псевдокод)

Подсчёт степеней из матрицы (неориент.):

for i := 1..n:

    deg[i] := 0

    for j := 1..n:

        deg[i] := deg[i] + A[i][j]

BFS с восстановлением пути:

for v in V: dist[v] := ∞; parent[v] := ⊥

dist[s] := 0; Q := {s}

while Q not empty:

    v := pop(Q)

    for u in Adj[v]:

        if dist[u] = ∞:

            dist[u] := dist[v] + 1

            parent[u] := v

            push(Q, u)

# восстановление пути s→t (если достижим):

path := []

x := t

while x ≠ ⊥:

    prepend(path, x)

    x := parent[x]

Подсчёт числа путей s→t в DAG:

order := TopologicalOrder(G)

for v in V: ways[v] := 0

ways[s] := 1

for v in order:

    for (v → u) in E:

        ways[u] := ways[u] + ways[v]

Пять упражнений (академический формат)

Упражнение 1. Степени и число рёбер по матрице смежности
Дан неориентированный граф из n вершин с матрицей смежности A.
a) Вычислите вектор степеней deg[i] = Σ_{j=1..n} A[i][j].
b) Докажите, что Σ_{i=1..n} deg[i] = 2|E|, и выразите |E| через элементы A.
c) Определите число изолированных и листовых вершин. Укажите, как меняется ответ, если в графе допустимы петли (каждая петля добавляет 2 к степени).

Упражнение 2. Кратчайшие пути (невзвешанный граф) и восстановление маршрута
Дан связный неориентированный граф (списки смежности) и две вершины s и t.
a) Проведите BFS от s и постройте массив dist[⋅].
b) Восстановите один из кратчайших путей s → t по массиву parent[⋅].
c) Обоснуйте, почему BFS всегда даёт кратчайшие пути по числу рёбер, и оцените сложность алгоритма.

Упражнение 3. Количество маршрутов заданной длины
Пусть A – матрица смежности ориентированного графа из n вершин.
a) Вычислите A² и интерпретируйте элемент (i, j) как число маршрутов длины 2 из vi в vj.
b) Обобщите на A^k и поясните, почему получаются маршруты, а не обязательно простые пути.
c) Предложите способ на малом DAG преобразовать матричное решение в подсчёт простых путей (подсказка: топологический порядок и динамика).

Упражнение 4. Эйлеровы условия
Дан неориентированный граф (матрица смежности).
a) Найдите степени вершин и проверьте условия существования эйлерового цикла и эйлеровой цепи.
b) Если условия для цикла нарушены, но для цепи выполнены, укажите возможные начальную и конечную вершины эйлеровой цепи.
c) Объясните, почему наличие ровно двух вершин нечётной степени необходимо и достаточно для эйлеровой цепи (интуитивное доказательство через «вход-выход» по рёбрам).

Упражнение 5. Свойства деревьев и единственность пути
Дан связный неориентированный граф с n вершинами и n-1 ребром.
a) Докажите, что граф ацикличен (иначе противоречие с |E| = n-1).
b) Докажите, что между двумя любыми вершинами существует единственный простой путь.
c) Опишите алгоритм поиска этого пути за O(|V| + |E|) (один обход в глубину/ширину с хранением parent[⋅]).

Заключение

Триада «вершина – ребро – путь» задаёт базовый язык описания дискретных структур. Строгие определения, матричные и списковые представления, леммы о степенях, корректные обходы (BFS/DFS), а также умение отличать маршруты от простых путей формируют фундамент навыков, необходимых на ЕГЭ. Следуя изложенным правилам корректности и отрабатывая упражнения, вы научитесь уверенно решать типовые задачи: считать степени и рёбра, проверять связность, находить кратчайшие пути, интерпретировать степени матрицы смежности и распознавать деревья и эйлеровы структуры. Это не только повышает скорость и точность решений, но и делает ваши аргументы строгими и проверяемыми.