Определите, существует ли описанный ниже граф. Если да, то постройте его:
 а) граф из семи вершин, в котором все вершины имеют степень 2;
 б) граф из восьми вершин, в котором все вершины имеют степень 2;
 в) граф из восьми вершин, в котором все вершины имеют степень 1;
 г) граф из семи вершин, в котором все вершины имеют степень 1;
 д) граф из семи вершин, в котором все вершины имеют степень 3;
 е) граф из восьми вершин, в котором все вершины имеют степень 3.
от

1 Ответ

а) Граф из семи вершин, в котором все вершины имеют степень 2: да, такой граф существует. Это циклический граф C7, где каждая вершина соединена с двумя соседями.

б) Граф из восьми вершин, в котором все вершины имеют степень 2: да, такой граф существует. Это циклический граф C8, где каждая вершина соединена с двумя соседями.

в) Граф из восьми вершин, в котором все вершины имеют степень 1: да, такой граф существует. Это набор из четырех рёбер (пара отрезков), который соединяет пары вершин.

г) Граф из семи вершин, в котором все вершины имеют степень 1: нет, такой граф не может существовать, так как при степени 1 необходимо четное количество вершин.

д) Граф из семи вершин, в котором все вершины имеют степень 3: нет, такой граф не может существовать, поскольку сумма степеней будет равна 21, а количество рёбер должно быть целым числом (S = 2 * m).

е) Граф из восьми вершин, в котором все вершины имеют степень 3: да, такой граф существует. Например, можно построить кубический граф с восемью вершинами, где каждая вершина соединена с тремя другими.
от