Тема 04. Формальные описания реальных объектов (Графы и таблицы)

🏠 Главная / Теория / Тема 04. Формальные описания реальных объектов (Графы и таблицы)

На ОГЭ эта тема проверяет умение работать с графами: сопоставлять граф с таблицей смежности, находить кратчайший путь, считать степени вершин.

---

## 1. Основные понятия теории графов

| Термин | Описание |
|--------|----------|
| **Граф** | Схема из точек (вершин) и линий (рёбер) между ними |
| **Вершина** | Точка на схеме (город, пункт, узел) |
| **Ребро** | Линия, соединяющая две вершины (дорога, связь) |
| **Дуга** | Ребро со стрелкой — указывает направление |
| **Вес ребра** | Число на ребре (расстояние, время, стоимость) |
| **Степень вершины** | Количество рёбер, выходящих из вершины |
| **Ориентированный граф** | Граф, где все рёбра — дуги (со стрелками) |

> **Совет:** Степень вершины легко посчитать: просто считайте линии, которые "касаются" этой точки.

---

## 2. Таблица смежности (матрица весов)

Таблица смежности — удобная запись графа в виде таблицы.

- Строки и столбцы = вершины.
- В ячейке [i][j] — вес ребра от i до j (или "–" / 0, если ребра нет).

**Пример:**

|   | А | Б | В | Г |
|---|---|---|---|---|
| **А** | – | 5 | 3 | – |
| **Б** | 5 | – | – | 2 |
| **В** | 3 | – | – | 4 |
| **Г** | – | 2 | 4 | – |

Граф: А–Б(5), А–В(3), Б–Г(2), В–Г(4).

> **Совет:** Если таблица симметрична относительно диагонали → граф неориентированный (дороги двусторонние). Можно смотреть только верхнюю или нижнюю половину.

---

## 3. Алгоритм сопоставления таблицы и графа

Когда вершины в таблице называются П1, П2... а на графе — А, Б, В...

**Алгоритм:**
1. Для каждой вершины **на графе** подсчитайте степень (количество рёбер).
2. Для каждой строки **в таблице** подсчитайте количество заполненных ячеек (не "–").
3. Сопоставьте по степеням. Если только у одного объекта степень = 4 → найдено совпадение.
4. После нахождения одного — остальные определяются по рёбрам.

> **Совет:** Начинайте с уникальных вершин — тех, у кого степень встречается только один раз.

---

## 4. Нахождение кратчайшего пути

### Метод перебора ("Дерево путей")

Для небольших графов (4–6 вершин) — перебираем все пути вручную.

**Пример.** Граф: А–Б(5), А–В(3), Б–Г(2), В–Г(4). Найти кратчайший путь А → Г.

| Путь | Длина |
|------|-------|
| А → Б → Г | 5 + 2 = **7** |
| А → В → Г | 3 + 4 = **7** |

Оба пути дают 7 — кратчайший путь = **7**.

### Алгоритм Дейкстры (для сложных задач)

1. Присвоить начальной вершине метку **0**, всем остальным — **∞**.
2. Из текущей вершины "посетить" всех соседей, обновить их метки (текущая + вес ребра).
3. Выбрать вершину с **наименьшей** необработанной меткой — она становится текущей.
4. Повторять до достижения конечной вершины.

> **Совет:** На ОГЭ граф обычно небольшой (5–7 вершин), поэтому полный перебор путей работает отлично. Алгоритм Дейкстры — запасной вариант.

---

## 5. Типичные задачи

### "Найдите кратчайший путь из А в Д"
1. Выпишите все возможные маршруты (следите за стрелками, если граф ориентированный!).
2. Сложите веса рёбер для каждого маршрута.
3. Выберите наименьший результат.

### "Какой вершине соответствует П3?"
1. Найдите степень П3 в таблице (количество заполненных ячеек в строке или столбце).
2. Найдите вершину на графе с такой же степенью.
3. Проверьте по рёбрам.

---

## 6. Типичные ошибки

- **Считать движение против стрелки.** В ориентированном графе дуга А→Б означает: можно идти только из А в Б, но не наоборот!
- **Не проверить все пути.** Короткий по виду путь может быть длиннее по весам.
- **Перепутать степень и вес.** Степень — количество рёбер. Вес — число на ребре.
- **Считать рёбра дважды.** В неориентированном графе ребро А–Б засчитывается и для А, и для Б.

---

## 7. Лайфхаки для ОГЭ

> **Совет:** Выпишите степени всех вершин столбиком — это помогает быстро сопоставить таблицу и граф.

> **Совет:** Перед тем как считать пути, убедитесь — граф ориентированный или нет? Это меняет всё.

> **Совет:** Если нужно найти кратчайший путь "с пересадкой через X", сначала найдите кратчайший до X, потом от X до финиша. Сложите.

Назад к списку