#algorithm #math #graph-theory #vertices #undirected-graph
#алгоритм #математика #теория графов #вершины #неориентированный граф
Вопрос:
Лемма о рукопожатии утверждает, что в неориентированном графе четное число вершин должно иметь нечетную степень.
Однако 3 человека обмениваются рукопожатиями друг с другом, 6 рукопожатий или по два на каждого. Таким образом, нет вершин с нечетной степенью.
Выполняется ли лемма о рукопожатии, потому что 0 четно и существует ноль вершин нечетной степени?
Я не сомневаюсь, что лемма верна, просто думаю, что я упускаю что-то действительно очевидное.
Ответ №1:
Выполняется ли лемма о рукопожатии, потому что 0 четно и существует ноль вершин нечетной степени?
ДА. Поскольку все 3 вершины имеют четную степень, следовательно, существует ноль вершин нечетной степени.
Вы абсолютно правы. То же самое имеет место, когда people = 1.
Комментарии:
1. Спасибо, я увидел вашу опечатку, но я допустил похожую опечатку, когда публиковал свой вопрос.
2. @user1768079 — Я надеюсь, что это понятно и вам логически.
An even number of people must have shaken an odd number of other people's hands— что тоже можно проверить логически.3. Мне было ясно, я просто не был уверен, не упускаю ли я чего-то в подобных случаях. Я подумал, может быть, я неправильно понял определение чего-то. Все приведенные мне примеры показывали графики без цикла, которые включали каждую вершину, или имели какое-либо другое условие, которое отличало его от графика с нечетным числом вершин одинаковой четной степени.
4. @user1768079 — Хорошо, что вы решили задать это здесь. Это показывает, что вы любознательны. Так держать! Удачи.