Определите, существует ли описанный ниже граф. Если да, то постройте его:\na) граф из семи вершин, в котором все вершины имеют степень 2 ;
б) граф из восьми вершин, в котором все вершины имеют степень 2 ;
в) граф из восьми вершин, в котором все вершины имеют степень 1 ;
г) граф из семи вершин, в котором все вершины имеют степень 1 ;
д) граф из семи вершин, в котором все вершины имеют степень 3 ;
е) граф из восьми вершин, в котором все вершины имеют степень 3.
Рассмотрим каждый пункт по отдельности, используя понятие суммы степеней вершин (теорема о рукопожатиях) и известные конструкции графов.
Пункт a)
Нам дан граф с 7 вершинами, каждая из которых имеет степень 2. Сумма степеней равна 7·2 = 14, что даёт 14/2 = 7 рёбер. Граф, в котором все вершины имеют степень 2, состоит из циклов. При 7 вершинах можно построить один единственный цикл длины 7 (цикл C7). Таким образом, существует граф — цикл из 7 вершин.
Пункт b)
Граф с 8 вершинами, каждая из которых имеет степень 2. Сумма степеней – 8·2 = 16, что дает 16/2 =...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
