ведение 4
Глава 1. Основные определения и типы графов 6
§ 1 Граф и его основные характеристики 6
1.1 Определение графа 6
1.2 Степень вершины и матрица смежности 7
1.3 Маршрут, путь, цикл 8
§2 Графы специального вида 8
2.1 Полный, связный граф, граф - дерево 8
2.2 Ориентированный граф, эйлеров граф 10
Глава 2. Турнир и графическая последовательность 12
§3 Турниры 12
3. 1 Матрицы турниров 12
3. 2 Алгоритм построения ориентированного графа 13
§4 Графическая последовательность 16
4.1 Критерии графичности последовательности 16
4.2 Графическая последовательность и ориентированные графы 21
4.3 Графическая последовательность, связные графы и деревья 26
Глава 3. Элективный курс “Математика турниров” 30
§5 Пояснительная записка 30
§6 Решение задач на восстановление турнирной таблицы 32
6.1 Принцип крайнего 32
6.2 Принцип узких мест 34
6.3 Оценка результатов турнира 36
6.4 Задачи для самостоятельного решения 38
§7 Теория графов и её прикладное значение 39
7.1 Граф и его реализация 39
7.2 Основные понятия и свойства теории графов 41
7.3 Принцип Дирихле 42
7.4 Задачи для самостоятельного решения 43
§8 Полный граф, его свойства и решение задач о турнирах 44
8.1 Задачи для самостоятельного решения 46
§9 Графическая последовательность и решение задач о турнирах 47
9.1 Графическая последовательность и её реализация 47
9.2 Выбывание из турнира 48
9.3 Задачи для самостоятельного решения 50
§10 Ориентированные графы и турниры 51
10.1 Задачи для самостоятельного решения 52
§11 Дистанционный курс 53
Заключение 56
Список литературы 57
Турнир — это любой вид состязания, в котором принимают участие большое количество участников (от двух и более).В них могут принимать участие, как индивидуальные игроки (шахматы, бокс, олимпиада), так и многочисленные команды (футбол, волейбол, гандбол). По своему содержанию они могут быть различными: спортивный, математический и т.д.
Наибольшую популярность имеют многокруговые турниры, в которых каждая пара участников встречается друг с другом несколько раз. Существуют различные формы начисления очков. Одной из самых распространённых является футбольная,в которой за выигранную встречу участнику начисляется 3 очка, за ничью - одно очко, за проигрыш - ноль. Также широко распространены однокруговые турниры, в которых каждый из n игроков играет с каждым другим ровно один матч (партию). Предположим, что каждая игра заканчивается победой, либо поражением. Отдельную партию называют результативной, если она закончилась победой одного из участников, и ничейной в противном случае.
Результатом называется суммарное количество очков, набранных спортсменом во всех партиях.
Итоги турнира оформляются в виде турнирной таблицы. Каждая её строка и каждый столбец соответствует одному из игроков (участников турнира).
Олимпиадная математика с каждым годом становится всё популярнее среди школьников разных возрастов. Задачи о спортивных соревнованиях довольно часто появляются на математических олимпиадах. Они, как правило, разнообразны по формулировке, и помимо эстетической привлекательности имеют также прикладное значение. Широко распространены задачи о круговых турнирах, в которых каждый участник встречается с остальными ровно по одному разу, например, играет одну партию.
Решение математических задач о турнирах непосредственно связано с одним их разделов дискретной математики - теорией графов. В школах ему не уделяется должного времени на изучение, поэтому неподготовленные школьники не смогут решать задачи такого уровня сложности без подготовки. Это и определило актуальность моей работы.
Популярность турнирной тематики на олимпиадах по математике побудила меня изучить её более серьёзно и разработать материал, благодаря
которому заинтересованные школьники смогут познакомиться с формулировками задач о турнирах и научиться их решать.
Тема дипломной работы посвящена проблеме построения ориентированных графов с заданным списком степеней вершин и предписанными теоретико-графовыми свойствами.
Целями квалификационной работы является:
— Создание элективного курса, который поможет школьникам познакомиться с основными методами, идеями решения задач о математических турнирах.
— Реализация основных алгоритмов построения графов на языке программирования Python.
Задачами выпускной квалификационной работы являются:
— Изучение основных определений и типов графов: связных графов, полных графов, деревьев.
— Изучение алгоритма реализации графа с помощью правильных графических последовательностей.
— Применение процедуры построения неориентированных графов к реализации проблемы построения графа в задачах - турнирах.
— Изучение формулировок математических задач о турнирах и представление способов их решения.
В ходе выпускной квалификационной работы были решены следующие задачи:
— Изучены основные определения и типы графов: связные графы, полные графы, деревья;
— Изучены алгоритмы реализации графа с помощью правильных графических последовательностей.
— Применены процедуры построения неориентированных графов к реализации проблемы в задачах- турнирах.
— Изучены формулировки математических задач о турнирах и представлены способы их решения.
Были достигнуты поставленные цели:
— Реализованы алгоритмы построения связных графов и деревьев на языке Python. — Создан элективный (дистанционный) курс для 8-11 классов по теме “Математика турниров”
В выпускную квалификационную работу был включен интересный, на наш взгляд, материал, было использовано много примеров и задач. Многие задачи, рассмотренные в работе, встречались на различных олимпиадах и турнирах по математике. Эти задачи прежде всего интересны своим привлекательным и оригинальным содержанием, разнообразными способами решения и уровнем сложности.
Разработанный элективный (дистанционный) курс “Математика турниров” может быть использован в школе для повышению мотивации к изучению математики и развития логического мышления у школьников, а также компьютерной компетенции.
