Теория графов (конспект урока)

Цель:

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

Ход урока.

Орг. момент.

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

Дети шпионов перехватили шифровку:12342562756278. В ней разные цифры означают разные буквы, а одинаковые цифры - одинаковые буквы. У них получились варианты:

- «думай и трудись»;

- «привет от деда»;

- «мой вопрос прост»;

- «вперед к победам».

Какая расшифровка верна? (Ответ: «мой вопрос прост»).

Давайте, вспомним условия, которые необходимо выполнять на занятии.

Первое условие - это быть точным; второе - быть ясным, и насколько можно простым.

Разминка.

(Вам предлагаются задачи на проверку внимания, задачи на смекалку).

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

В комнате находятся свеча, керосиновая лампа и готовая к растопке печь. Что Вы зажжете в первую очередь? (спичку).

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

Дядька Черномор написал на листке бумаги число 20. Тридцать три богатыря передают листок друг другу, и каждый или прибавляет к числу или отнимает от него единицу.

Может ли в результате получится число 10? Нет, не может.

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

Это значит, что после 33-х изменений число станет нечетным, т.е. никак не сможет равняться 10).

В коробке лежит 200 мячей одного размера, но разных цветов: зеленые, красные, синие и белые. В темноте берут несколько мячей.

Какое наименьшее количество мячей нужно взять, чтобы среди них обязательно было 10 одного цвета? (Мы не знаем, сколько мячей каждого цвета в коробке, но цветов 4.

Поэтому 9х4=36-неприемлимый результат. Нужно взять 36+1=37 мячей, чтобы среди них было 10 одного цвета).

На гору ведут 5 дорог. Найти количество способов подняться и спуститься с него, если:

а) Подниматься и спускаться одной и той же дорогой можно; б)подниматься и спускаться одной и той же дорогой нельзя.

(а) если подняться на гору дорогой 1, то спуститься с нее можно дорогами 1, 2, 3, 4, 5, то есть 5-тью способами.

То же самое и для дорог 2, 3, 4, 5. Всего существует 25 способов подняться и спуститься с горы; б) Если подниматься и спускаться одной и той же дорогой нельзя, то получим на 5 способов меньше. Тогда остается 20 способов).

Повторение. Решение задач.

1. В ковре размером 3х3 метра Коля проделал 8 дырок. Докажите, что из него можно вырезать коврик размером 1х1 м, не содержащий внутри себя дырок.

Решение:

Разрежем на 9 ковриков размером 1х1м. Ковриков-«клеток»-9, а дырок-«кроликов»-8. Т.к. 8<9 ,то по принципу Дирихле, хотя бы одна «клетка» останется свободной. Другими словами- найдется коврик без дырок.

Учитель: В школьной программе нет этой темы, однако, на основе такого простого и даже чуть наивного принципа, математикам удается решать весьма трудные задачи, доказывать красивые теоремы, причем не только элементарные.

Весь материал - в документе.

Занятие математического кружка (6-7 класс).

Тема: Теория графов

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

Оборудование: мультимедийный проектор (презентация «Теория графов»), карточки с домашним заданием, раздаточный материал.

Епиграф: «Спорьте, заблуждайтесь, ошибайтесь, но ради бога, размышляйте, и хотя криво, да сами». Г.Лессинг

Оргмомент

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

Дети шпионов перехватили шифровку:12342562756278. В ней разные цифры означают разные буквы, а одинаковые цифры -одинаковые буквы. У них получились варианты:

«думай и трудись»;

«привет от деда»;

«мой вопрос прост»;

«вперед к победам».

Какая расшифровка верна? ( Ответ:«мой вопрос прост»).

Давайте, вспомним условия, которые необходимо выполнять на занятии.

Первое условие-это быть точным; второе- быть ясным, и насколько можно простым.

Разминка.

(Вам предлагаются задачи на проверку внимания, задачи на смекалку ).

• Вы вошли в темную комнату. В коробке у вас всего одна спичка. В комнате находятся свеча, керосиновая лампа и готовая к растопке печь. Что Вы зажжете в первую очередь? (спичку ).

• Класс шел парами. Один из учеников посмотрел вперед и насчитал девять пар, затем обернулся и насчитал пять пар. Сколько всего учеников шло в колонне ? ( 30 учеников ).

• Дядька Черномор написал на листке бумаги число 20. Тридцать три богатыря передают листок друг другу, и каждый или прибавляет к числу или отнимает от него единицу. Может ли в результате получится число 10? ( Нет, не может. После того как листок побывает в руках у богатыря, число, на нем написанное, будет менять свою четность, т.е. станет четным, если было нечетное и наоборот. Это значит, что после 33-х изменений число станет нечетным, т.е. никак не сможет равняться 10).

• В коробке лежит 200 мячей одного размера, но разных цветов: зеленые, красные, синие и белые. В темноте берут несколько мячей. Какое наименьшее количество мячей нужно взять, чтобы среди них обязательно было 10 одного цвета? (Мы не знаем, сколько мячей каждого цвета в коробке, но цветов 4. Поэтому 9х4=36-неприемлимый результат. Нужно взять 36+1=37 мячей, чтобы среди них было 10 одного цвета).

• На гору ведут 5 дорог. Найти количество способов подняться и спуститься с него, если: а) Подниматься и спускаться одной и той же дорогой можно; б)подниматься и спускаться одной и той же дорогой нельзя.

(а) если подняться на гору дорогой 1, то спуститься с нее можно дорогами 1,2,3,4,5, то есть 5-тью способами. То же самое и для дорог 2,3,4,5. Всего существует 25 способов подняться и спуститься с горы; б) Если подниматься и спускаться одной и той же дорогой нельзя, то получим на 5 способов меньше. Тогда остается 20 способов).

Повторение. Решение задач.

1. В ковре размером 3х3 метра Коля проделал 8 дырок. Докажите, что из него можно вырезать коврик размером 1х1 м, не содержащий внутри себя дырок.

Решение:

Разрежем на 9 ковриков размером 1х1м. Ковриков-«клеток»-9, а дырок-«кроликов»-8. Т.к. 8

Учитель: В школьной программе нет этой темы, однако, на основе такого простого и даже чуть наивного принципа, математикам удается решать весьма трудные задачи, доказывать красивые теоремы, причем не только элементарные.

1. В одной семье было много детей. 7 из них любили капусту, 6 – морковь, 5 – горох, 4 – капусту и морковь, 3 – капусту и горох, 2 – морковь и горох, 1 – и капусту, и морковь, и горох. Сколько детей было в семье?

Решение:

Горох

1

Капуста

1

2

Горох

5

Капуста

7

3

1

1

3

1

2

4

Морковь

1

Морковь

6

Только капусту любит: 7-(2+3+1)= 1, только горох: 5-(2+1+1)=1, только морковь: 6-(3+1+1)=1.

Всего в семье 1+3+1+2+1+1+1=10 детей.

Ответ: 10 детей.

Учитель: Рисунки, которые нарисованы при решении этой задачи, называются «кругами Эйлера». Ученый писал, что «они очень подходят для того, чтобы облегчить наши размышления».

1. У меня зазвонил телефон,

- Кто говорит?

- Слон.

А потом позвонил крокодил…

А потом позвонили Зайчатки…

А потом позвонили Мартышки…

А потом позвонил Медведь…

А потом позвонили Цапли…

Итак, у Слона, Крокодила, Зайчаток, Мартышек, Медведя, Цапель и у меня установлены телефоны. Каждые два телефонных аппарата соединены проводом. Как сосчитать, сколько для этого понадобилось проводов?

Решение

Всего телефонных аппаратов 7, каждый соединен с шестью. Значит, соединений всего 7x6=42. А провод – это два соединения. Значит, всего понадобился 21 провод.

Ответ: 21 провод.

1. В одном дворе живут 4 друга. Вадим и шофер старше Сергея, Николай и слесарь занимаются боксом; электрик - младший из друзей. По вечерам Андрей и токарь играют в домино против Сергея и электрика. Определите профессию каждого из друзей.

Решение:

	Вадим	Сергей	Николай	Андрей
шофер	-	-	-	+
слесарь	-	+	-	-
электрик	-	-	+	-
токарь	+	-	-	-

Ответ: Андрей-шофер, Сергей-слесарь,Николай-электрик,Вадим-токарь.

Учитель: использование таблицы значительно ускоряет процесс решения.

1. Старатель намыл 8 мешочков золотого песка. Все они весят одинаково, кроме одного, который легче остальных, но на вид он совершенно такой же. Как старателю определить, какой мешочек легче других, всего за два взвешивания?

Решение: надо взять 6 мешочков и положить их по 3 на чашки весов. Этим взвешиванием старатель может определить, на какой чашке весов находится легкий мешочек. А если весы уравновесятся, значит, он среди тех двух мешочков, которые еще не взвешивали, и сравнивать их вес можно вторым взвешиванием. Если при первом взвешивании одна чашка оказалась легче, то надо из этих трех мешочков взять любые два и вторым взвешиванием сравнить их вес, а если весы уравновесятся, то это мешочек, который был отложен.

Проверка домашнего задания.

Слайд 1 (Задача не решается, и это тем досаднее, что она не решается только «чуть-чуть». Вторая же фигура легко вычерчивается одним непрерывным движением без повторений.

Почему так происходит? В этом нам сегодня и предстоит разобраться.

Введение в тему урока.

Вычерчивание фигур одним росчерком- тоже математическая задача! И относится она к теории графов (Слайд 2, Слайд 3)

Изучение новой темы.

Показ слайдов:4,5,6.

Слайд7: перед вами граф, назовите степень каждой вершины графа.

А теперь вернемся к домашнему заданию. Слайд 8

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

Показ слайдов 9,10,11,12 ( граф, который можно нарисовать, не отрывая карандаша от бумаги, называется Эйлеровым)

Показ слайдов 13,14 ( Решение: ребра и вершины куба образуют граф, все 8 вершин которого имеют степень 3, и следовательно обход невозможен).

Решение задач.

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

Нужно грамотно перевести это условие на язык теории графов.

Решение:

Нарисуем схему: планетами будут соответствовать точки, а соединяющими их маршрутами- непересекающиеся между собой линии. Теперь видно, что долететь от Земли до Марса нельзя.

Ме

З

Н

У

С

В

П

Ю

Ма

Ответ: долететь от Земли до Марса нельзя.

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

Решение:

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

а) б)

Число проведенных игр 7 (рис. а). Нужно найти число игр, которые осталось провести. Для этого будем соединять тех участников, которые еще не играли друг с другом. Осталось провести 8 игр (рис. б).

Ответ: число проведенных игр 7, осталось провести еще 8 игр.

Слайд 15 (Разве нельзя прийти к решению чисто математическим путем.

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

Показ слайдов 17,18,19,20,21,22.

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

• В электротехнике- при построении электрических схем;

• В химии и биологии- при изучении молекул и их цепочек;

• В географии- при составлении карт;

• В истории- при составлении генеалогических древ (родословной);

• В геометрии- чертежи многоугольников, многогранников, пространственных фигур;

• В экономике- при решении задач о выборе оптимального пути для потоков грузового транспорта.

О математике и говорить не приходится.

Домашнее задание - Слайд 24.

Итог урока – Слайд 25.

Наше занятие мне бы хотелось закончить словами венгерского математика Д.Пойа

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