Доклад "Новое во ФГОС. Теория графов", районное методическое объединение учителей математики
презентация к уроку по математике

Слайд 1

Новое во фгос. Теория графов

Тема графов очень интересна при изучении, что позволяет привлечь школьников к активной познавательной деятельности. Графы, как никакая другая модель, позволяет изучать свойства отношений в «чистом виде», а графическое представление решения логических задач делает этот процесс более наглядным. С помощью графов решать задачи очень удобно, интересно, можно рассмотреть несколько вариантов решения одной и той же задачи и выбрать наиболее легкое, удобное, красивое, интересное решение. Начальные сведения о графах достаточно просты, а работа с ними вызывает у детей большой интерес. В школьном курсе математики теория графов не рассматривается, но в учебниках начальных классов и основной школы, можно встретить задачи, которые намного проще решить с помощью графов, нежели другими способами. Олимпиадные задачи и некоторые задачи ЕГЭ тоже наполнены заданиями, которые легче решить, применяя графический способ. Но что мешает учителю включить в факультативный курс теорию графов и показать, как с ее помощью можно быстро решать «сложные» задачи. Тем более, что некоторый теоретический материал доступен для понимания детей уже даже начальной школы. Для школьника не обязательно давать строгое определение графа, как математического объекта. Им вполне достаточно будет сформулировать несколько определений и теорем и показать, как они работают при решении задач. Итак, сформулируем основные определения и теоремы на которых можно построить факультативный курс по графам

Слайд2

Граф — это конечное множество точек, некоторые из которых соединены линиями. точки называются вершинами графа, а соединяющие их линии — рёбрами. каждое ребро соединяет ровно две различные вершины.

Транспортный граф.

Социальный граф.

 Турнирный граф

Можно привести и другие примеры, когда графы возникают естественным образом: граф авиасообщений, генеалогическое древо.

Полный граф — это граф, в котором каждые две вершины соединены ребром.

Слайд 3

Степень вершины — это количество рёбер, концом которых является эта вершина.

Посчитаем степени вершин на примере графов из предыдущей лекции. 

У вершины A степень 1, у вершины B — 3, у вершины C — 2, у вершины D — 3, у вершины E — 1.

У вершины « Андрей» степень 3, у вершины «Вася» степень 1, у вершины «Евгений» степень 0, у вершины «Дима» степень 2, у вершины «Саша» степень 2.

Изолированная вершина — это вершина графа, степень которой равна нулю.

Слайд 4

Задача 1. В графе 9 вершин и 8 рёбер. Какое наибольшее количество вершин степени 1 в нём может быть?

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

Будем рассуждать от противного. Предположим у нас есть граф, состоящий из 9 вершин, каждая из этих вершин будет иметь степень 1 и всего 8 ребер. У этой вершины тоже степень 1. С другими не могут быть соединены. Сморим на третью вершину, она идет к четвертой вершине. 8 вершин. Из 9 вершины выходит ребро куда-то. Она не может идти в одну из этих данных вершин. Мы получили противоречие. Значит, такого графа не существует. Ответ: 8

Слайд 5

Формула  для нахождения количество рёбер

E=

где E –количество рёбер,

n- количество вершин,

 - степень вершин

Слайд 6

Следующие задачи демонстрируют, как можно использовать утверждение о вычислении количества рёбер в графе через сумму степеней его вершин.

Задача. (Подсчёт количества рёбер по известным степеням вершин.) В однокруговом футбольном турнире участвовали шесть команд. К середине турнира оказалось, что четыре команды сыграли по два матча, а две оставшиеся команды сыграли по одному матчу. Сколько матчей было сыграно к середине турнира?

1 команда -2                        Каждая команда –вершина, матч– ребро

2 команда -2                        E=

3 команда -2

4 команда -2

5 команда -1

6 команда -1

Слайд 7

Задача. (Поиск степени вершины по известным степеням остальных вершин и количеству рёбер.) В государстве есть 21 город: 10 малых городов, 10 средних городов и столица. Между городами построено 25 дорог. Известно, что из каждого малого города выходит ровно по одной дороге, а из каждого среднего — ровно по две. Сколько дорог может выходить из столицы?

Слайд 8

Лемма о рукопожатиях. В любом графе количество вершин нечётной степени чётно.

Лемма о рукопожатиях является необходимым условием существования графа, но не достаточным.

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

Задача. В шахматный клуб пришли 7 человек, они сыграли между собой несколько партий. Могло ли так оказаться, что каждый из них сыграл ровно 3 партии?

 Каждую партию играют два человека.

Переведем задачу на язык графов.
7 человек- это 7 вершин графа.

2 вершины будем соединять ребром, если 2 человека сыграли в партию.

Что тогда получится?

Какой вопрос в нашей задаче:

Существует ли граф, в котором ровно 7 вершин и степень каждой вершины 3?

Нет, не существует, так как это нечетное число вершин нечетных степей.
Это противоречит Лемме о рукопожатиях.

Слайд 9

Граф называется двудольным, если его вершины можно разбить на две группы (две доли) так, что каждое ребро в этом графе соединяет вершины, принадлежащие

разным группам.

Двудольный граф удобно изображать, нарисовав отдельно вершины двух долей. 

Пример. На школьном балу каждый мальчик станцевал с тремя девочками, а каждая девочка — с четырьмя мальчиками. Этот граф может выглядеть следующим

образом:

Не все графы являются двудольными. Например, граф с тремя вершинами, в котором каждые две вершины соединены ребром, не является двудольным.

Слайд 10

Утверждение. Сумма степеней всех вершин одной доли двудольного графа равна сумме степеней всех вершин другой его доли и равна общему числу рёбер в двудольном графе.

Задача. (Поиск количества вершин в одной доле по известным степеням всех вершин и количеству вершин в другой доле.) На школьном балу каждый мальчик станцевал с тремя

 девочками, а каждая девочка — с четырьмя мальчиками. Сколько мальчиков пришло на бал, если всего было 9 девочек?

Чтобы решить эту задачу, мы рассмотрим двудольный граф.

1 доля- это вершины мальчиков
2 доля- это вершины девочек.

2 вершины из разных долей мы будем соединять ребром, если соответствующие мальчик и девочка танцевали на балу.

Что мы знаем. Каждый М танцевал с 3 девочками. То есть степень каждой вершины из доли 1 равна 3.

Мы знаем, каждая девочка танцевала с 4 мальчиками. Поэтому степень каждой вершины из доли 2 равна 4.

При этом мы знаем, что девочек 9 и нам надо понять сколько М?

Выпишем формулу подсчета ребер в двупольном графе, а именно сумма степеней в левой доле равняется сумме степеней в правой доле.

Сумма степеней в левой доле 3х
Сумма степеней в правой доле 4*9

Отсюда находим х=12.
Ответ: 9 мальчиков пришло на бал.

Слайд 11

Пути и циклы, связность

Путь в графе — это последовательность рёбер, в которой любые два соседних ребра имеют общую вершину и каждое ребро в этой последовательности

 встречается не более одного раза. Длина пути — это число рёбер в этом пути. 

Цикл — это путь, у которого начальная и конечная вершины совпадают.

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

Примеры пути, цикла и простого цикла можно увидеть на рисунке ниже. В этом графе пути — это, например, A−B и B−C−E−F, циклы — это,

например A−B−D−E−F−D−A и A−B−D−A, простые циклы — это, например, B−C−E−D−B и A−B−D−A.

Утверждение. Если в графе есть цикл, то в нём есть и простой цикл.

Слайд 12

Задача. (Задача на проверку базового понимания, что такое цикл в графе.) Рассмотрим граф, изображённый на рисунке. Какие вершины этого графа

содержатся хотя бы в одном простом цикле длины четыре?

Дан граф с 6 вершинами. Нам надо понять сколько вершин участвуют хотя бы в одном простом цикле длиной 4.

Ну точнее какие вершины точно участвуют, а какие точно нет.

Первое, на что стоит обратить внимание, что у нас есть во такой простой цикл длины 4

B-D-E-C-B, поэтому вершины BCDE участвуют в этом цикле.

Напишем, B-C-E-D-B.

Осталось понять про две оставшиеся вершины в этом графе AF. Участвуют ли они в циклах длины 4.

Посмотрим на конфигурацию графа. Обе вершины имеют степень 2.Они соединены друг с другом, и обе соединены с вершиной D. Поэтому если бы вершина F участвовала в цикле длины 4, то вершины A и D точно в нем участвуют, но при этом из вершины А только есть ребро AF, то получается что все эти 3 ребра AF, AD, DF должны были бы участвовать в этом цикле, но это уже точно не цикл длины 4, а простой цикл длины 3.Так что вершины A и F не участвуют в простых циклах длины 4.

Слайд 13

Подграфом данного графа называется граф, все вершины и рёбра которого содержатся среди вершин и рёбер исходного графа.

Граф называется связным, если между каждой парой его вершин существует как минимум один путь. 

Компонента связности графа — это связный подграф, удовлетворяющий следующим условиям:

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

Слайд 14

Задача. (Задача на проверку базового понимания, что такое компоненты связности графа.) Какое наименьшее число рёбер необходимо провести

 в графе, изображённом ниже, чтобы он стал связным?

Для начала осознаем. Да, он не связный. Есть изолированная вершина. Чтобы подступиться к этой задаче, надо начать с того, чтобы посчитать компоненты связности. На сколько этих связных кусков наш граф распадается?

Постепенно ищем кусочки компоненты связности. Изолированная вершина –это первая компонента связности. Отметим цифрой 1. Другую вершину обозначим цифрой 2. Она явно входит в другую компоненту связности. Будем считать, что во вторую. Смотрим с чем она соединена. Она соединена с этой вершиной, значит будем считать, что она тоже во второй компоненте связности.

Третий компонент связности

Четвертый компонент связности

Мы поняли, что наш граф состоит из 4 компонентов связности.

Какая наша цель?

Мы хотим дорисовать сколько-то ребер, чтобы в графе 4 компоненты связности превратились в одну компоненту связности.

Давайте подумаем…

Когда мы рисуем одно ребро и оно будет соединять 2 вершины одной компоненты связности. Например, это4 компонента. Это никак не повлияет на общее количество компонентов связности.

Только прибавится ребро в данной компоненте.

Как было 4 компоненты, так и осталось.

А что если соединить 2 вершины из разных компонентов связности. Например, 3 и 4.

Тогда мы получим 3 компоненты связности. Через данное нарисованное ребро я могу добраться до любой вершины 4 компоненты связности. И, наоборот.

На самом деле, дорисовывая ребро, я уменьшаю количество компонентов связности ровно на 1.

Чтобы получить одну компоненту связности, мне нужно дорисовать еще 3 ребра:

3-4, 2-1, 3-2.

Граф стал единым

Слайд 15

Дерево — это связный граф без циклов.

Удобно изображать дерево следующим образом: сначала изобразить одну вершину в верхнем ярусе, затем во втором ярусе изобразить все вершины,

соединённые ребром с вершиной первого яруса, затем в третьем ярусе изобразить все вершины, соединённые ребром с вершинами второго яруса и т. д.

Работа с деревьями и анализ их свойств упрощается, если изображать их послойно. Например, граф на рисунке слева можно изобразить, как показано

 на рисунке справа.

Примерами деревьев могут являться генеалогическое древо, файловая система хранения данных на компьютере, дерево перебора, дерево вероятностей.

Слайд 16

Висячая вершина — это вершина степени один. 

Утверждение. Если дерево содержит не меньше двух вершин, то в нём найдётся хотя бы одна висячая вершина.

Утверждение. В дереве количество рёбер на единицу меньше количества вершин.

Утверждение. Связный граф с n вершинами содержит хотя бы n−1 ребро.

Слайд 17

Кратные рёбра — это рёбра, соединяющие одну и у же пару вершин.

Задача о кёнигсбергских мостах. Cреди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам, не проходя ни

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

изображённого ниже, ровно один раз? Или, говоря простым языком, можно ли нарисовать этот граф, не отрывая карандаша от бумаги и не проводя никакое ребро дважды?

Эйлеров путь — это путь, проходящий по каждому ребру графа ровно один раз.

Критерий эйлеровости графа. Эйлеров путь в графе существует тогда и только тогда, когда граф связен и содержит не более двух вершин нечётной степени.

Планарный граф — это граф, который можно изобразить на плоскости так, чтобы его рёбра не имели общих точек, кроме вершин. Области, на которые

 планарный граф разбивает плоскость, называются гранями.

Формула Эйлера. Пусть в связном планарном графе V вершин, E рёбер и G граней. Тогда V−E+G=2.

Слайд 18

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

Таким образом, применяя теорию графов в школьном курсе математики, решение многих математических задач и доказательств упрощается, придает им наглядность и простоту.