Домашнее задание к уроку 1.Можно ли построить граф с 7 вершинами так, чтобы из каждой вершины выходило 4 ребра? 2.Можно ли построить несвязный граф с 8 вершинами, степени которых равны 1, 1, 2, 2, 3, 3, 4, 4? 3.По столбу высотой 15 метров ползёт улитка. За

Ответ: 1. Нельзя, 2. Можно.

Решение:

1. Задача 1: Можно ли построить граф с 7 вершинами, чтобы из каждой вершины выходило 4 ребра?

   Сумма степеней всех вершин графа равна удвоенному числу ребер. Если у нас 7 вершин и из каждой выходит 4 ребра, то сумма степеней всех вершин равна 7 * 4 = 28.

   Число 28 четное, поэтому кажется, что такой граф построить можно. Однако, нужно учитывать, что сумма степеней всех вершин должна быть четной, так как каждое ребро соединяет две вершины и, следовательно, учитывается дважды в сумме степеней.

   В данном случае, если мы попытаемся построить такой граф, то у нас возникнет противоречие. Каждая вершина должна быть соединена с четырьмя другими, но так как вершин всего 7, это означает, что у каждой вершины должно быть 4 соседа. Однако, если мы попытаемся соединить каждую вершину с четырьмя другими, то мы получим граф, в котором сумма степеней всех вершин будет четной, но построить его не получится, так как число вершин нечетное.

   Таким образом, нельзя построить граф с 7 вершинами, чтобы из каждой вершины выходило 4 ребра.

2. Задача 2: Можно ли построить несвязный граф с 8 вершинами, степени которых равны 1, 1, 2, 2, 3, 3, 4, 4?

   Для того чтобы построить несвязный граф, достаточно разделить вершины на две или более изолированные группы. Вершины внутри каждой группы могут быть связаны ребрами, но между группами ребер нет.

   В данном случае, мы можем построить такой граф. Например, разделим вершины на две группы: одна группа с вершинами степеней 1, 1, 2, 2 и другая группа с вершинами степеней 3, 3, 4, 4.

   В первой группе с вершинами степеней 1, 1, 2, 2 мы можем соединить две вершины степени 1 с двумя вершинами степени 2. Таким образом, мы получим изолированную компоненту.

   Во второй группе с вершинами степеней 3, 3, 4, 4 мы можем соединить вершины так, чтобы получилась другая изолированная компонента. Например, соединим две вершины степени 3 с двумя вершинами степени 4. Таким образом, мы получим еще одну изолированную компоненту.

   Так как между двумя этими компонентами нет ребер, то граф будет несвязным.

   Следовательно, можно построить несвязный граф с 8 вершинами, степени которых равны 1, 1, 2, 2, 3, 3, 4, 4.

Ответ: 1. Нельзя, 2. Можно.