Степень вершины B - 3; степень вершины D - 9 и степень вершины P - 21. Можно ли данный граф начертить "одним росчерком"?

Question

Информатика

Ольгуся

20 октября, 00:24

Степень вершины B - 3; степень вершины D - 9 и степень вершины P - 21. Можно ли данный граф начертить "одним росчерком"?

+4

Ответы (2)

Знаете ответ?

Галюня · Answer 1

Любой граф содержит четное число нечетных вершин. Значит нельзя.

Максюша · Answer 2

Нет, нельзя (Задача о семи кёнигсбергских мостах)

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