Решение задач с помощью графов

возрос. Элементы комбинаторики, статистики и теории вероятностей включены в новые стандарты по математике для основной и профильной школ. Формирование комбинаторных представлений и развитие комбинаторного мышления школьников входит в число основных целей обучения математике.
Однако обычно, когда говорят об элементах комбинаторики, имеют в виду задачи алгебраического содержания. Здесь мы рассмотрим комбинаторные задачи, которые можно решать с помощью графов.

элементов из V. Элементы множества V называются вершинами графа, элементы множества E – ребрами графа. Множество вершин и множество ребер называют графом.
Будем использовать геометрическое представление графа. Вершины графа изображаются в виде точек на плоскости. Если две вершины образуют ребро, то соответствующую пару точек соединяют линией.

Например, на рис.1 изображен граф G, заданный множеством вершин V={1,2,3,4,5} и множеством ребер E ={(1,2), (2,3), (4,3), (4,2)}
Число ребер, выходящих из вершины v, называют степенью вершины v и обозначается d(v). Вершина степени 0 называется изолированной, вершина степени 1 – висячей.
0≤ d(v) ≤ n-1, где n- число вершин графа.

Рис.1

вершины n-угольника равно
Из них n отрезков являются сторонами, остальные – диагонали.
Получим формулу для нахождения числа диагоналей:

Замечание:
Сумма степеней вершин графа равна удвоенному числу ребер.
Для пятиугольника :

Рис.2

сыгранных партиях представлена
в таблице. С кем сыграл Леша?

Решение.
Построим граф встреч игроков, в котором каждая вершина соответствует участнику.

В

Т

Л

Д

С

И

Ж

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

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

Рис.3

Решение.
Поставим в соответствие каждому игроку точку плоскости – вершину графа. Если 2 игрока встретились между собой, то соединим соответствующие вершины графа ребром. Получим граф встреч игроков. Надо доказать, что существуют 2 игрока, проведших одинаковое количество встреч, т.е.
в графе обязательно найдутся 2 вершины,
степени которых одинаковы.

Доказательство (от противного). Допустим, что существует граф H, степени всех вершин которого различны. В промежутке от 0 до n-1 существует ровно n целых чисел: 0,1, 2,…, n-1. Степени n вершин графа тоже расположены в этом промежутке. Поэтому должны существовать такие вершины v1, v2, …, vn , что d(v1)=0, d(v2)=1, …, d(vn)=n-1. Т.к. d(v1)=0 , то вершина v1 не соединена ребром ни с какой другой вершиной. d(vn)=n-1, следовательно, вершина vn соединена со всеми остальными вершинами, в том числе и с v1 . Пришли к противоречию. Существование графа H, степени всех вершин которого различны, невозможно.
Вывод: Хотя бы два игрока проведут одинаковое количество встреч.

Андрей делает 5 выстрелов и за каждое попадание получает еще по 2 выстрела. Андрей выстрелил 25 раз. Сколько раз он попал?
Решение.
Стрельбу Андрея можно описать деревом, которое называется корневым деревом.
В этом дереве все вершины, кроме верхней, соответствуют выстрелам. Если Андрей попал, то степень соответствующей вершины равна 3, если промахнулся -1. Степень верхней вершины равна 5. Дерево имеет 26 вершин и 25 ребер.
Пусть n - число попаданий. Тогда граф содержит n вершин степени 3, (25-n) вершин степени 1 и одну вершину степени 5.

Т.к. сумма степеней вершин графа равна удвоенному числу ребер, получим :
3·n+1·(25-n)+5=2·25
n=10
Ответ: Андрей попал 10 раз.