1)докажите, что число людей, когда-либо живших на земле и сделавших нечетное число , четно.2)у короля 19 вассалов. может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей? почему?
1) в рукопожатием принимают участие 2 человека, поэтому рукопожатие удваивается, т.е. умножается на 2
2)Под графом мы будем понимать множество точек (вершин), некоторые из которых соединены отрезками (ребрами).
Степень вершины графа — это количество выходящих из нее (или, что то же самое, входящих в нее) ребер (еще говорят: количество ребер, инцидентных данной вершине). Вершина графа называется четной, если ее степень четна, и нечетной в противном случае.
Некоторая часть вершин данного графа называется компонентой связности, если из любой ее вершины можно «дойти» до любой другой, двигаясь по ребрам.
В некоторых случаях на ребрах графа выбирается «направление движения» (например, когда на автомобильной дороге вводится одностороннее движение). При этом получается ориентированный граф. (Если направление движения по ребрам не определено, то граф называется неориентированным). В ориентированном графе различают положительную и отрицательную степень каждой вершины (то есть количество ребер, соответственно, входящих и выходящих из нее). Две вершины могут быть соединены и несколькими ребрами, направления движения по которым противоположны («дорога с двусторонним движением»). Изменяется понятие компоненты связности: теперь каждый «маршрут» от одной вершины до другой должен учитывать направление движения по ребрам.Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин. ответ. Нет.
Решение. Сделаем вассалов вершинами графа; ребрами соединим тех из них, которые являются соседями. По условию все вершины этого графа нечетны, а всего их 19, то есть тоже нечетное число. Но по теореме 2 такого быть не может.
Пошаговое объяснение:
1) в рукопожатием принимают участие 2 человека, поэтому рукопожатие удваивается, т.е. умножается на 2
2)Под графом мы будем понимать множество точек (вершин), некоторые из которых соединены отрезками (ребрами).
Степень вершины графа — это количество выходящих из нее (или, что то же самое, входящих в нее) ребер (еще говорят: количество ребер, инцидентных данной вершине). Вершина графа называется четной, если ее степень четна, и нечетной в противном случае.
Некоторая часть вершин данного графа называется компонентой связности, если из любой ее вершины можно «дойти» до любой другой, двигаясь по ребрам.
В некоторых случаях на ребрах графа выбирается «направление движения» (например, когда на автомобильной дороге вводится одностороннее движение). При этом получается ориентированный граф. (Если направление движения по ребрам не определено, то граф называется неориентированным). В ориентированном графе различают положительную и отрицательную степень каждой вершины (то есть количество ребер, соответственно, входящих и выходящих из нее). Две вершины могут быть соединены и несколькими ребрами, направления движения по которым противоположны («дорога с двусторонним движением»). Изменяется понятие компоненты связности: теперь каждый «маршрут» от одной вершины до другой должен учитывать направление движения по ребрам.Теорема 2. Всякий (неориентированный) граф содержит четное число нечетных вершин. ответ. Нет.
Решение. Сделаем вассалов вершинами графа; ребрами соединим тех из них, которые являются соседями. По условию все вершины этого графа нечетны, а всего их 19, то есть тоже нечетное число. Но по теореме 2 такого быть не может.