Простейшие свойства графа.

Урок 56

Простейшие свойства графа.

Образовательные:

1. Формирование понятия «граф», рассмотреть его основные элементы: вершина, ребра. степень;

2. Формирование умения составлять граф по описанию отношений между предметами, применять при решении задач.

Развивающие:

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

Воспитательные:

1. Воспитывать взаимопомощь, усидчивость, трудолюбие.

Предметные:

Знать: понятие граф, элементы, степень графа; алгоритм построения эйлеровых графов.

Уметь: составлять граф по заданному описанию, применять при решении различных задач.

Личностные: мотивация к обучению; уметь проводить самооценку на основе критерия успешности учебной деятельности.

Метапредметные:

Коммуникативные –

• Умение оформлять свои мысли в устной форме;

• слушать и понимать речь других;

• совместно договариваться о правилах поведения и общения в школе и следовать им.

Регулятивные –

• умение ставить учебные цели.

Личностные – умение проводить самооценку на основе критерия успешности учебной деятельности.

Познавательные–

• умение ориентироваться в своей системе знаний: отличать новое от уже известного с помощью учителя;

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

Ход урока.

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

2. Актуализация знаний.

Для того, чтобы узнать тему сегодняшнего урока давайте мы с вами попробуем отгадать рисунки:

Параграф фотограф граффити

- Посмотрите внимательно на слова и давайте попробуем определить, какой слог встречается в каждом слове.?

- Правильно – слог Граф. Как вы думаете, что означает это слово? Какие ассоциации возникают у вас при этом слове.

(Выслушиваются ответ)

-Но у нас с вами урок информатики. А как связать это слово с информатикой? И главный вопрос - где его можно применить?

Формулировка темы урока.

-Решим небольшую задачу: У каждого из трех друзей: Васи, Миши, Коли есть свой шалаш. Они решили установить между собой связь с помощью проволочного телефона. Вопрос: какое наименьшее количество линий из проволоки им придется провести, чтобы каждый из них мог поговорить с каждым?

(Выслушиваются ответы детей)

-Молодцы! Конечно же 3 линии.

- Теперь давайте немного усложним задачу: К трем друзьям присоединился 4 друг и построил свой шалаш. Сколько же линий нужно провести в этом случае.

(Дается детям время на обсуждение. Выслушиваются разные мнения.)

- Давайте попробуем нарисовать эту задачу.

(Дети в тетрадях и ученик у доски выполняют рисунок.)

- А теперь посмотрим, что у нас с вами получилось?

(ответы детей: обозначили точками и соединили их линиями)

- Вот мы с вами граф и нарисовали. Давайте попробуем дать определение

(Заслушиваются ответы детей)

3. Изучение нового материала.

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

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

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

Пример:

Мультиграф — это граф, у которого пара вершин соединены несколькими ребрами. А такие ребра, которые соединяют одну и ту же пару вершин, называют кратными. Две различные вершины графа, соединенные ребром, называются смежными.

Ребро не всегда соединяет разные вершины. 

Петля — это ребро, которое соединяет вершину саму с собой.

Рис. 1

На рисунке 1 изображен мультиграф со смежными ребрами (выделены черным цветом), кратными ребрами (выделены красным) и  петлями (выделены синим).  

Степенью вершины называют количество ребер, выходящих из одной вершины. Для петли ребро выходит из вершины дважды. Обозначать степень вершины а будем как γ(а).

Пример:

На рисунке 2 изображен граф с 7 вершинами.

Рис. 2

Составим список степеней вершин этого графа: γ(a)=1,γ(b)=5,γ(c)=2,γ(d)=2,γ(e)=3,γ(f)=2,γ(g)=1.  

Свойства графов:

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

2. Для любого графа количество вершин нечетной степени всегда будет четное.

3. Сумма степеней всех вершин графа равна удвоенному числу его ребер.

Маршрут на графике — это последовательность ребер a1,a2,...,an, в которой конец одного ребра служит началом другого. Циклическим маршрут называется в том случае, если конец последнего ребра последовательности совпал с началом первого ребра.

Для графа, изображенном на рисунка 2,  a1,a2,a3,a7,a1,a5 — маршрут, a6,a2,a5,a7 — циклический маршрут, а последовательность a7,a6,a2,a1,a4 — маршрутом не является.

Рис. 2

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

Для графа, изображенном на рисунка 2, a1,a2,a6,a7,a4,a5,a7 — цепь, a2,a6,a7,a8,a4,a2,a6 — цикл.

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

Для графа, изображенном на рисунка 2, a1,a2,a6,a7,a4 — простая цепь, a2,a6,a7,a8,a4 — простой цикл.

Связанные вершины — это вершины a и b, для которых существует цепь, начинающаяся в a и заканчивающаяся в b.

Связный граф — это граф, у которого любые две вершины связанны. Если граф несвязен, то в нем можно выделить так называемые связанные компоненты (т.е. множества вершин, соединенных ребрами исходного графа, каждое из которых является связным графом).

Один и тот же граф может быть изображен по-разному. Например, граф на рисунке 2 тот же, что и изображен на рисунке 3. 

Рис. 3  

4. Закрепление новых знаний.

Задача №3 . Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий, Плутон – Венера, Земля – Плутон, Плутон – Меркурий, Меркурий – Венера, Уран – Нептун, Нептун – Сатурн, Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

- Что же нам необходимо сделать, чтобы решить эту задачу?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теория графов сейчас одна из самых развиваемых частей математики, так как современная жизнь требует появление новых профессий. Одна из них – специалист по логистике. (Приложение 3.) Менеджер по логистике занимается доставкой товаров, грузов, планирует транспортные маршруты, рассчитывает стоимость перевозок, организует хранение товаров, грузов и т.д. Одна из главных задач специалиста по логистике - анализ ситуации, поэтому он должен уметь хорошо считать, владеть теорией графов.

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

Графы применяются в различных отраслях науки. Например:

А) Графы и история.

Историк прослеживает родословные связи по генеалогическому дереву.

Генеалогическое дерево А.С. Пушкина.

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

Б) Графы и физика

Инженер чертит схемы электрических цепей. Еще недавно одной из наиболее сложных и утомительных задач для радиолюбителей было конструирование печатных схем.

Чтобы вы могли глубже оценить свою деятельность и вклад в урок предлагаю закончить следующие фразы…

1. Сегодня на уроке я узнал…

2. Сегодня на уроке мне понравилось…

3. Сейчас мое настроение ….

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

§ 51 стр. 219-223

Хронологически первой в теории графов считается задача о семи кенигсбергских мостах, которую решил Эйлер. Она состоит в следующем. Парк города Кенигсберга был расположен на обоих берегах реки Прегель и на двух островах. Острова с берегами и друг с другом были соединены семью мостами так, как на рис. 1. Любимой забавой горожан были поиски такого маршрута, который кончался бы на том же берегу, где и начинался, проходил бы по всем мостам, но по каждому мосту – только один раз. С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог. 

Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. В 1736 году. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. Задач вида «одним росчерком» (слайд 13.)