- Главная
- Математика
- Решение задач с помощью графов
Содержание
- 2. В последнее время интерес к комбинаторике в школьном курсе математики заметно возрос. Элементы комбинаторики, статистики и
- 3. Пусть задано некоторое непустое множество V и множество E пар различных элементов из V. Элементы множества
- 4. Задача 1. Сколько диагоналей имеет пятиугольник? n-угольник? Решение. Всего отрезков, соединяющих 2 вершины n-угольника равно Из
- 5. Задача 2. В шахматном турнире по круговой системе участвуют 7 школьников. Информация о сыгранных партиях представлена
- 6. Задача 3. Соревнование проводится по круговой системе. Это означает, что каждая пара игроков встречается между собой
- 7. Задача 4. Андрей пошел с отцом в тир. Уговор был такой: Андрей делает 5 выстрелов и
- 9. Скачать презентацию
В последнее время интерес к комбинаторике в школьном курсе математики заметно
В последнее время интерес к комбинаторике в школьном курсе математики заметно
Однако обычно, когда говорят об элементах комбинаторики, имеют в виду задачи алгебраического содержания. Здесь мы рассмотрим комбинаторные задачи, которые можно решать с помощью графов.
Пусть задано некоторое непустое множество V и множество E пар различных
Пусть задано некоторое непустое множество 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
Задача 1. Сколько диагоналей имеет пятиугольник? n-угольник?
Решение.
Всего отрезков, соединяющих 2
Задача 1. Сколько диагоналей имеет пятиугольник? n-угольник?
Решение.
Всего отрезков, соединяющих 2
Из них n отрезков являются сторонами, остальные – диагонали.
Получим формулу для нахождения числа диагоналей:
Замечание:
Сумма степеней вершин графа равна удвоенному числу ребер.
Для пятиугольника :
Рис.2
Задача 2. В шахматном турнире по круговой системе
участвуют 7 школьников.
Информация о
Задача 2. В шахматном турнире по круговой системе
участвуют 7 школьников.
Информация о
в таблице. С кем сыграл Леша?
Решение.
Построим граф встреч игроков, в котором каждая вершина соответствует участнику.
В
Т
Л
Д
С
И
Ж
По графу видно, что Леша встречался с Ваней, Толей и Димой.
Кроме этого можно сказать, с кем встречались остальные школьники.
Задача 3. Соревнование проводится по круговой системе. Это означает, что каждая
Задача 3. Соревнование проводится по круговой системе. Это означает, что каждая
Рис.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, степени всех вершин которого различны, невозможно.
Вывод: Хотя бы два игрока проведут одинаковое количество встреч.
Задача 4. Андрей пошел с отцом в тир. Уговор был такой:
Задача 4. Андрей пошел с отцом в тир. Уговор был такой:
Решение.
Стрельбу Андрея можно описать деревом, которое называется корневым деревом.
В этом дереве все вершины, кроме верхней, соответствуют выстрелам. Если Андрей попал, то степень соответствующей вершины равна 3, если промахнулся -1. Степень верхней вершины равна 5. Дерево имеет 26 вершин и 25 ребер.
Пусть n - число попаданий. Тогда граф содержит n вершин степени 3, (25-n) вершин степени 1 и одну вершину степени 5.
Т.к. сумма степеней вершин графа равна удвоенному числу ребер, получим :
3·n+1·(25-n)+5=2·25
n=10
Ответ: Андрей попал 10 раз.