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