Афанасьева Светлана Викторовна ГОУ СОШ 420 г. Москва, 2009 ГОУ СОШ 420 г. Москва, 2009. - презентация

1 Афанасьева Светлана Викторовна ГОУ СОШ 420 г. Москва, 2009 ГОУ СОШ 420 г. Москва, 2009

2 Известно, что в настоящий момент: 1) Ваня сыграл шесть партий; 2) Толя сыграл пять партий; 3) Леша и Дима сыграли по три партии; 4) Семен и Илья сыграли по две партии; 5) Женя сыграл одну партию. Требуется определить: с кем сыграл Леша. Шахматный турнир проводится по круговой системе, при которой каждый участник встречается с каждым ровно один раз, участвуют семь школьников.

3 Изобразим участников турнира точками Для решения задачи будем использовать геометрическое представление графа Эти точки называются вершинами графа

4 Число в скобках называют степенью вершины, оно показывает сколько ребер выходит из данной вершины В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Для каждой точки укажем ее имя (по первой букве имени игрока) и количество партий, сыгранные этим игроком

5 Начать построение ребер следует с вершины В, так как это единственная вершина, которая соединяется со всеми другими вершинами графа В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Будем строить ребра графа с учетом степеней вершин

6 Для вершин В и Ж построены все возможные ребра В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Сделаем первые выводы:

7 Теперь однозначно определяются ребра вершины Т. С учетом ребра ВТ надо построить четыре ребра В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Построим следующие ребра

8 Все возможные ребра теперь построены для вершин Ж, В, Т, а также для вершин С и И В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Пора делать новые выводы

9 Теперь становится очевидным, каким должно быть недостающее ребро. Оно должно соединить вершины Л и Д В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Последний вывод

10 ОТВЕТ: Леша играл с Толей, Ваней и Димой В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Требовалось определить: с кем сыграл Леша. Граф к задаче построен

11 В шахматном турнире по круговой системе, в котором участвуют пять школьников, сыграно шесть партий. Больше всего встреч к настоящему моменту провели Ваня и Миша – по три. Какое число партий сыграл участник, проведший наименьшее число встреч?

12 В данной задаче однозначно построить граф нельзя В аня (3) М иша (3) 1 (?) Построим граф к данной задаче 2 (?) 3 (?)

13 Ваня и Миша не играли друг с другом В аня (3) М иша (3) 1 (?) 1 случай 2 (?) 3 (?) В этом случае каждый из остальных участников провел по две встречи

14 Ваня и Миша сыграли друг с другом, В аня (3) М иша (3) 1 (?) 2 случай 2 (?) 3 (?) Этот случай невозможен, поскольку проведя шестое ребро, но есть участник, не встречавшийся ни с Ваней,ни с Мишей мы получим противоречие с условием задачи, так как появится еще один участник, сыгравший 3 партии

15 Ваня и Миша сыграли друг с другом, В аня (3) М иша (3) 1 (?) 3 случай 2 (?) 3 (?) Есть только одна возможность провести шестое ребро, не нарушая условия задачи при этом каждый участник, встретился либо с Ваней, либо с Мишей, либо с обоими вместе В этом случае каждый из остальных участников провел по две встречи

16 В аня (3) М иша (3) 1 (2) 2 (2)3 (2) Наименьшее число встреч у участников 1,2,3 по две встречи Требовалось определить: Какое число партий сыграл участник, проведший наименьшее число встреч? 1 случай 2 случай 3 случай В аня (3) М иша (3) 12 3 Шестое ребро ? Случай невозможен В аня (3) М иша (3) 1 (2) 2 (2) 3 (2) Наименьшее число встреч у участников 1,2,3 по две встречи

17 Сумма степеней вершин графа равна удвоенному числу ребер Полезный факт для решения сложных задач У каждого ребра две вершины. Степень вершины показывает, сколько ребер из нее выходит. Сложив все степени, получим в результате, что каждое ребро подсчитано дважды. Сумма степеней вершин графа всегда является четным числом В графе число вершин нечетной степени четно

18 Если в компании из 100 человек каждый пожмет другому руку, то сколько будет рукопожатий? Иллюстрация применения леммы Каждый из 100 человек должен пожать руку остальным 99 членам компании. А так как в любом рукопожатии всегда участвуют 2 человека, то произведение 100*99 учитывает каждое рукопожатие дважды. Количество рукопожатий равно (100*99) : 2 = 4950

19 О.И.Мельников «Теория графов в занимательных задачах».- М. Издательский дом «ЛИБРОКОМ»,2008 О.И.Мельников «Незнайка в стране графов».- М. Издательский дом «ЛИБРОКОМ»,2006