📌 Граф — сетевая модель данных, являющаяся набором вершин, соединённых рёбрами, представленным чаще всего в виде таблицы. При решении таких задач очень важно уметь преобразовывать таблицы в схемы и наоборот.
🤔 Что важно знать при решении задания 1
- Степень вершины в графе — количество ребер, соединенных с ней.
- Степень вершины можно определить по таблице: для этого нужно подсчитать количество ненулевых ячеек в строке или столбце.
- В некоторых заданиях граф необходимо построить самостоятельно.
- Если однозначно сопоставить вершину графа и пункт в таблице нельзя, нужно обратить внимание на вспомогательные условия.
💚 Алгоритм решения задания
- Подписать все вершины графа: указать собственную степень и степени смежных вершин.
- Определить, у каких вершин уникальный набор степеней, не совпадающих ни с какой другой вершиной.
- Соотнести такие вершины с пунктами в таблице: сравнить количество собственных степеней и степеней соседей.
- Посмотреть, есть ли вершины, связанные друг с другом или такие, у которых неизвестна только одна смежная — как правило, такие вершины легко определить по графу и сопоставить с таблицей.
- Сопоставить все вершины с номерами пунктов, чтобы понять, правильно ли решено задание.
- Дать ответ на вопрос условия.
Авторизуйтесь, чтобы оставить комментарий.