1. Графы и таблица смежности

Модель данных: граф

Почему граф — а не дерево или база данных

Многие задачи IT и повседневной жизни устроены так, что объекты связаны с другими произвольными связями, которые нельзя представить древовидной иерархией:

• Социальные сети — пользователи связаны взаимными подписками, и между людьми существуют «кольца» и «кластеры», а не иерархия.
• Транспорт и логистика — станции метро соединены пересадками, городские дороги — перекрёстками.
• Сети и телеком — маршрутизаторы связаны линиями, по которым пакеты могут ходить по любому пути.
• Алгоритмы — зависимости между модулями, задачи, процессы.

Для таких данных существует отдельная структура — граф (graph). Это набор объектов (вершин) и связей между ними (рёбер).

Основные термины

• Вершина (vertex, node) — объект, элемент графа.
• Рёбро (edge) — связь между двумя вершинами.
• Степень вершины (degree) — количество рёбер, ведущих к этой вершине.
• Изоморфные графы — два графа называют изоморфными, если их можно преобразовать друг в друга, переименовывая вершины.

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

• Неориентированный граф — ребро не имеет направления (дорога с двусторонним движением).
• Ориентированный граф (digraph) — ребро имеет направление (подписка в соцсети: я подписался на вас).

Для неориентированного графа в таблице смежности заполняются обе клетки (i, j) и (j, i). Для ориентированного — только (i, j).

Таблица смежности

Формат и правила заполнения

Таблица смежности (adjacency table) — это квадратная таблица размером N×N, где N — количество вершин. Правила:

1. Строки и столбцы пронумерованы от 1 до N.
2. Клетка (i, j) содержит метку (вес, атрибут) рёбра, соединяющего вершины i и j.
3. Если рёбра нет — клетка пустая.
4. Диагональ всегда пуста (петли не рассматриваются).

Для неориентированного графа таблица симметрична относительно главной диагонали: T[i][j] = T[j][i].

Запись данных

Рассмотрим небольшой граф с тремя вершинами. Рёбра: 1–2 (вес 5), 2–3 (вес 8), 1–3 (вес 3).

	1	2	3
1	—	5	3
2	5	—	8
3	3	8	—

# Adjacency table for a small undirected graph with 3 vertices
# values: edge weight, None = no edge

adjacency = [
    [None, 5, 3],   # vertex 1
    [5, None, 8],   # vertex 2
    [3, 8, None],   # vertex 3
]

def get_neighbors(table, vertex):
    """Return list of (neighbor, weight) pairs for a given vertex."""
    row = table[vertex - 1]
    return [(j + 1, w) for j, w in enumerate(row) if w is not None]

# Example: neighbors of vertex 2

## Примеры: восстановление графа

### Пример 1: восстановление графа из таблицы (ЕГЭ, Задание 16)

**Условие.** Дано неориентированное граф с вершинами А, Б, В, Г, Д, Е, Ж. Соседние вершины соединены рёбрами следующих пар:

А–Б, А–Д, Б–Д, Б–Ж, Д–Г, Г–В, Д–В, Д–Е, В–Е, В–Ж, Е–Ж

По таблице ниже определите номера вершин А, Б, В, Г, Д, Е, Ж. Затем найдите сумму длин рёбер **Б–Д** и **Г–В**.

|   | 1  | 2  | 3  | 4  | 5  | 6  | 7  |
|---|----|----|----|----|----|----|----|
| **1** | —  | —  | 4  | —  | 7  | —  | —  |
| **2** | —  | —  | —  | 9  | 5  | —  | —  |
| **3** | 4  | —  | —  | —  | 6  | —  | 11 |
| **4** | —  | 9  | —  | —  | 8  | 3  | 12 |
| **5** | 7  | 5  | 6  | 8  | —  | 10 | —  |
| **6** | —  | —  | —  | 3  | 10 | —  | 13 |
| **7** | —  | —  | 11 | 12 | —  | 13 | —  |

**Решение.**

**Шаг 1. Определяем количество вершин.**
Из таблицы видно, что граф содержит 7 вершин (таблица 7×7).

**Шаг 2. Посчитаем степени вершин.**
Степень вершины — количество заполненных ячеек в её строке:

| Вершина | Степень |
|---------|---------|
| 1       | 2       |
| 2       | 2       |
| 3       | 3       |
| 4       | 4       |
| 5       | 5       |
| 6       | 3       |
| 7       | 3       |

**Шаг 3. Посчитаем степени вершин по списку рёбер.**

| Вершина | Соседи              | Степень |
|---------|---------------------|---------|
| А       | Б, Д                | 2       |
| Б       | А, Д, Ж             | 3       |
| В       | Г, Д, Е, Ж          | 4       |
| Г       | Д, В                | 2       |
| Д       | А, Б, В, Г, Е       | 5       |
| Е       | Д, В, Ж             | 3       |
| Ж       | Б, В, Е             | 3       |

**Шаг 4. Подбираем соответствие.**
Начнём с уникальных степеней:
- Степень 5 у вершины Д. В таблице степень 5 у строки 5. → **Д = 5**
- Степень 4 у вершины В. В таблице степень 4 у строки 4. → **В = 4**

Теперь степени 2: А и Г.
- А соединена с Б и Д.
- Г соединена с Д и В.
- Так как Д = 5, обе строки содержат 5.
- Строка 2 содержит 4 (это В). Значит, строка 2 = Г (Г соединена с В).
- Строка 1 = А.
- → **А = 1**, **Г = 2**

Теперь степени 3: Б, Е, Ж.
- Б соединена с А = 1, Д = 5, Ж.
- Е соединена с Д = 5, В = 4, Ж.
- Ж соединена с Б, В = 4, Е.
- Строка 6 содержит 4 (В) и 5 (Д). → Это Е. → **Е = 6**
- Строка 3 содержит 1 (А) и 5 (Д). → Это Б. → **Б = 3**
- Строка 7 содержит 3 (Б), 4 (В), 6 (Е). → Это Ж. → **Ж = 7**

Итоговое соответствие: **А = 1, Б = 3, В = 4, Г = 2, Д = 5, Е = 6, Ж = 7**.

**Шаг 5. Находим ответ.**
- Ребро **Б–Д**: Б = 3, Д = 5. Клетка (3, 5) = **6**.
- Ребро **Г–В**: Г = 2, В = 4. Клетка (2, 4) = **9**.
- Сумма: 6 + 9 = **15**.

**Ответ: 15.**

# Output: [(1, 5), (3, 8)]
print(get_neighbors(adjacency, 2))

Чтение данных

Чтение из таблицы тривиально:

• Все соседи вершины i — непустые клетки строки i.
• Вес ребра (i, j) — содержимое клетки T[i][j].
• Степень вершины i — количество непустых клеток в строке i.