Графы

Занятие 13. Графы вокруг нас

1. Организационный момент

О, сколько нам открытий чудных

Готовит просвещенья дух…

А.С.Пушкин

Сегодня мы познакомимся с математическим понятием «граф»; рассмотрим примеры использования графов в различных областях знаний; задачи по теории графов. Работа на уроке будет проходить в группах. Надеюсь, что наша работа будет продуктивной.

2. Этап усвоения новых знаний

1. Рассмотрим задачу.

В первенстве класса по настольному теннису 6 участников: Артем, Булат, Влад Батыршин, Глеб, Дмитрий и Ермошин Влад. Первенство проводится по круговой системе– каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Артем сыграл с Булатом, Глебом  и  Ермошиным; Булат, как уже говорилось, с Артемом и еще с Глебом; Влад – с Глебом, Дмитрием  и  Ермошиным; Глеб – с Артемом и Булатом; Дмитрий – с Владом и  Ермошин – с Артемом и Владом. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Р ешение демонстрируется на доске.

Изобразим данные задачи в виде схемы. Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д.

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

2.Определение.

Графом называют конечное множество точек, которые соединены отрезками прямых.

Точки называются вершинами графа, а отрезки – ребрами графа.

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

Точки А, Б, В, Г, Д, Е называются вершинами графа, соединяющие их отрезки – ребрами графа.

Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. 7. Чтобы найти число игр, которые осталось провести, построим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не играли друг с другом. Ребер у этого графа осталось 8. Значит, осталось провести 8 игр.

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

Внимание на доску.

Примеры графов: схема метро; генеалогическое древо;

кристаллическая решетка; электрическая схема и другие.

Придумайте свои примеры графов.

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

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

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

3. Этап закрепления новых знаний

1. Рассмотрим задачу: 5 друзей при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Обменяйтесь, пожалуйста, рукопожатиями. Сколько всего рукопожатий было сделано?

Решение демонстрируется на доске. Задача легко решается с помощью теории графов. Изобразите в тетради 5 точек: А, Б, В, Г, Д.

Сколько всего рукопожатий было сделано?

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

Если подвести итог, то можно утверждать:если полный граф имеет n вершин, то количество ребер будет равно n(n - 1)/2.

2. Хочу предложить вам решить задачу – загадку. Перед вами граф – "распечатанное письмо". Попробуйте начертить этот граф не отрывая карандаша от бумаги и не проводя по одной линии дважды.

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

В какой вершине вы начали движение? В какой закончили? (Начала в А, закончила в Е). Есть другие варианты? (Да, я начал в Е, закончил в А)

Не расстраивайтесь. Мы сейчас с вами выведем алгоритм для решения этой задачи. Для этого нам нужно будет перенестись на более чем 200 лет назад и оказаться вместе с великим математиком Леонардом Эйлером в городе Кенигсберге (сейчас этот город называется Калининград).

Первая работа по теории графов принадлежит именно ему (1736), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. В начале 20 века наряду с термином «граф» употреблялись другие термины, например карта, комплекс, диаграмма, сеть, лабиринт.

4. Задача о Кёнигсбергских мостах.

Б ывший Кёнигсберг расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Жители города предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причем на каждом мосту следовало побывать только один раз. До Эйлера никто не мог этого сделать, но и доказать, что это невозможно, тоже ни у кого не получалось. Как поступил Эйлер?

Попробуйте найти нужный ответ и выдвиньте свою гипотезу. Через 3 минуты слушаем гипотезы.

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

Попробуйте провести линии по всем ребрам -"мостам", не отрывая карандаша от бумаги.

У кого получилось? Таких нет?  У Эйлера тоже не получилось..

А вы знаете почему?

Оказывается все дело в числе ребер, сходящихся в вершине.

Давайте посчитаем, сколько  ребер сходится в каждой вершине графа. Напишите рядом с каждой вершиной число, отражающее количество ребер, в ней сходящихся, иназовем  вершину четной или нечетной в зависимости от того, какое число, четное или нечетное, стоит рядом. Итак, в вершине А сходится 5 ребер, в вершине В-3, в вершине С-3, в вершине Д-3. Какими являются все  эти вершины? (Нечетными.)

Леонард Эйлер сформулировал правило:

Обход возможен:

• ЕСЛИ все вершины – четные, и его можно начать с любого участка.

• ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных вершин.

Обход невозможен если нечетных вершин больше 2.

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

5.Давайте вернемся к задаче "распечатанное письмо" и применим правило Эйлера.

– Сколько ребер сходится в каждой вершине? (В вершине А сходится 3 ребра, в вершине В-4, в вершине С-2, в вершине Д-4.)

– Что вы скажите о четности вершин в этом графе? ( Три вершины – четные, две – нечетные.)

– Как нужно совершить обход этого графа, согласно правилу Эйлера? (Начать обход в одной из нечетных вершин А или Е, а завершить в другой.)

4. Итог урока

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

Задачи на уроке:

Задача 1

В первенстве класса по настольному теннису 6 участников: Артем, Булат, Влад, Глеб, Дмитрий и Егор. Первенство проводится по круговой системе– каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Артем сыграл с Булатом, Глебом  и  Егором; Булат, как уже говорилось, с Артемом и еще с Глебом; Влад – с Глебом, Дмитрием  и  Егором; Глеб – с Артемом и Булатом; Дмитрий – с Владом и  Егором – с Артемом и Владом. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Задача 2

5 друзей при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Обменяйтесь, пожалуйста, рукопожатиями. Сколько всего рукопожатий было сделано?

З адача 3

Перед вами граф – "распечатанное письмо". Попробуйте начертить этот граф не отрывая карандаша от бумаги и не проводя по одной линии дважды.

З адача 4. о Кёнигсбергских мостах
Бывший Кёнигсберг расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Жители города предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причем на каждом мосту следовало побывать только один раз. До Эйлера никто не мог этого сделать, но и доказать, что это невозможно, тоже ни у кого не получалось. Как поступил Эйлер?

Задача 5. Нераспечатанное письмо

Домашнее задание

Леонард Эйлер сформулировал правило:

Обход возможен:

ЕСЛИ все вершины – четные, и его можно начать с любого участка.

ЕСЛИ 2 вершины – нечетные, но его нужно начать с одной из нечетных вершин.

Обход невозможен если нечетных вершин больше 2.

Домашнее задание.

1. Изобразить свое генеалогическое древо.

2. На рисунке - схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

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

Презентация