Question

Можно ли изобразить связный граф отрывая карандаш не более 35 раз, если в нём 35 вершин, степень 20 вершин – четные

Answer 1

Ответ:

Нельзя

Пошаговое объяснение:

Если степень более чем двух вершин нечетна, то этого сделать нельзя.

Когда ты ведешь карандашом по графу, проходя через вершину ты отнимаешь у нее два ребра(на входе и на выходе), т.е. четность вершин не менятся, и получить из нечетной степени 0(четную) - нельзя. Исключения составляют начальная и конечная вершина, твоего "ведения карандашом". У них должна быть нечетная степень, потому что в первый(последний) раз ты отнимаешь 1 ребро. Надеюсь понятно))

Answer 2

Нет, невозможно изобразить связный граф с 35 вершинами и степенью 20 вершин, где все 20 вершин имеют четную степень, используя не более 35 ребер.

В связном графе с 35 вершинами каждая вершина должна быть соединена с другими вершинами, чтобы обеспечить связность графа. Если у каждой из 20 вершин степень равна 2 (что является четным числом), то они должны быть соединены друг с другом, образуя цикл. Это приведет к минимально возможному числу ребер, равному 20.

Остается 15 вершин, которые должны быть соединены с остальными вершинами в графе. Даже если каждая из этих 15 вершин соединена с каждой из оставшихся 15 вершин, это добавит еще 15 ребер. Таким образом, общее количество ребер будет равно 20 + 15 = 35.

Таким образом, чтобы изобразить связный граф с 35 вершинами, степенью 20 вершин, которые являются четными, потребуется не менее 35 ребер.