Графы и деревья

1. Понятие графа

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

Обозначения:

Термин	Обозначение	Пример
Множество вершин	V = {v₁, v₂, ..., vₙ}	V = {A, B, C, D}
Множество рёбер	E = {e₁, e₂, ..., eₘ}	E = {(A,B), (B,C), (C,D)}
Количество вершин	n =	V
Количество рёбер	m =	E

2. Виды графов

Неориентированный граф

Рёбра не имеют направления. Связь симметрична: если A соединено с B, то B соединено с A.

    A --- B
    |     |
    C --- D

Ориентированный граф (орграф)

Рёбра имеют направление (дуги). Связь может быть односторонней.

    A → B
    ↓   ↑
    C → D

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

Каждому ребру приписан вес (число). Например, расстояние между городами.

    A ---5--- B
    |         |
    3         4
    |         |
    C ---2--- D

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

Степень вершины — количество рёбер, инцидентных вершине. В орграфе различают:

• полустепень исхода (количество выходящих дуг)
• полустепень захода (количество входящих дуг)

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

Цикл — путь, в котором первая и последняя вершины совпадают.

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

4. Деревья

Дерево — связный граф без циклов. Свойства дерева:

• Между любыми двумя вершинами существует ровно один путь
• Количество рёбер на 1 меньше количества вершин: m = n − 1
• Удаление любого ребра делает граф несвязным
• Добавление любого ребра создаёт цикл

Корень — выделенная вершина, от которой строится иерархия.

Лист — вершина степени 1 (кроме корня).

Уровень вершины — расстояние от корня до вершины (количество рёбер на пути).

        [Корень]
        /   |   \
      [ ]  [ ]  [ ]
      / \       / \
    [ ] [ ]   [ ] [ ]   ← листья

5. Поиск кратчайшего пути (алгоритм Дейкстры)

Для взвешенного графа с неотрицательными весами:

1. Начальной вершине присвоить расстояние 0, остальным — ∞
2. Пока есть непосещённые вершины:
   а) Выбрать непосещённую вершину с минимальным расстоянием
   б) Для каждого соседа: если новое расстояние < текущего, обновить
   в) Пометить вершину как посещённую
3. Расстояния до всех вершин найдены

Пример

Граф дорог: A→B(5), A→C(3), B→D(4), C→D(2), C→E(6), D→E(1)

Кратчайший путь A→E: A→C→D→E (3 + 2 + 1 = 6)

6. Представление графа в памяти

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

Таблица n×n, где элемент [i][j] = 1 (или вес), если есть ребро из i в j.

    A B C D
A   0 5 3 0
B   5 0 0 4
C   3 0 0 2
D   0 4 2 0

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

Для каждой вершины — список соседей:

A: [B(5), C(3)]
B: [A(5), D(4)]
C: [A(3), D(2)]
D: [B(4), C(2)]

7. Важно!

• Дерево — это частный случай графа, а не отдельное понятие.
• В дереве нет циклов. Если в графе есть цикл — это не дерево.
• Взвешенный граф может быть как ориентированным, так и неориентированным.
• Алгоритм Дейкстры работает только с неотрицательными весами.
• На ОГЭ по информатике задачи на графы часто встречаются: определить кратчайший путь, найти количество путей, проверить связность.