Информационные модели: графы, таблицы, базы данных
Представления графов, оптимальные пути, подсчет путей в DAG и связи таблиц.
На экзамене
В нумерации проекта КИМ 2027 это задания 1, 3 и 23: сопоставление моделей, связанные таблицы и анализ графа с поиском оптимального пути или количества путей.
Формулы и факты
| Понятие | Короткое правило |
|---|---|
| Путь | Соседние вершины соединены ребром нужного направления |
| Длина пути | Сумма весов пройденных ребер |
| Степень вершины | Число примыкающих ребер; для орграфа входящие и исходящие дуги считают отдельно |
| Матрица смежности | Ячейка показывает наличие или вес ребра |
| DAG | Ориентированный ациклический граф: направленных циклов нет |
| Первичный ключ | Однозначно определяет запись таблицы |
| Внешний ключ | Ссылается на первичный ключ другой таблицы |
- Матрица смежности неориентированного графа симметрична относительно главной диагонали.
- В ориентированном графе переход разрешен только по направлению дуги.
- Условие "A и B": верны обе части. Условие "A или B": верна хотя бы одна часть.
- Количество: считай отобранные строки. Сумма: складывай нужное поле отобранных строк.
Алгоритм
Граф и таблица
- Определи, есть ли направления и веса.
- Сравни степени вершин или числа входящих и исходящих дуг.
- Начни с уникальных признаков: тупик, максимальная степень, редкий набор соседей.
- Зафиксируй соответствие и проверь всех соседей.
- Для пути проверь каждое направление и сложи веса.
Граф из файла
- Проверь формат строк, направления, веса, старт и финиш.
- Для числа путей в DAG найди топологический порядок: номера вершин его не заменяют.
- Поставь старту 1, остальным 0; передавай количество путей по исходящим дугам.
- Для оптимального пути в DAG используй минимум или максимум суммы результата предшественника и веса дуги.
- Алгоритм Дейкстры применим для кратчайшего пути с неотрицательными весами.
Связанные таблицы
- Определи смысл строки каждой таблицы.
- Найди первичный и внешний ключи.
- Соедини строки по равным значениям ключей.
- Примени условия отбора по отдельности.
- Посчитай именно то, что требуется: строки, разные объекты или сумму поля.
Ловушки
- Путают: число ребер и сумму весов. Сверь: выпиши веса маршрута отдельно.
- Путают: пустую ячейку и ребро веса 0. Сверь: прочитай обозначения таблицы.
- Путают: номер строки и ключ записи. Сверь: соединяй только указанные поля.
- Путают: строки и уникальные значения. Сверь: проверь, нужно ли убирать повторы.
- Путают: номера вершин и порядок расчета. Сверь: в DAG сначала обработай всех предшественников. Недостижимость не обозначай обычным нулевым расстоянием.