Проект Решение логических задач с помощью графов

МБОУ «Орловская СОШ»

Направление: «Образовательные проекты и исследование».

Работу выполнили: ученики 7 класса

Руководитель работы:

Лазарева Л.Л., учитель математики и информатики.

Содержание

1	Введение	2
2	Что такое граф в математике.	3
3	Примеры графов в окружающем мире.	3
4	Леонард Эйлер и теория графов.	8
5	Задача об Эйлеровом пути.	8
6	Графы изоморфные и плоские.	9
7	Задачи, придуманные участниками проекта.	14
8	Задачи из ЕГЭ (математика, информатика).	24
9	Задача олимпиады «Осенняя разминка» для 7 классов	27
10	Поэтические странички	28
11	Заключение	30
12	Используемая литература	31
13	Об авторах	32

Введение

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

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

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

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

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

Ход работы над проектом:

1.     изучение специальной литературы;

2.     знакомство с решениями некоторых известных задач;

3.     составление собственных задач по изучаемой теме;

4.     изготовление пространственных фигур для проведения эксперимента с объемными и плоскими графами;

5.     решение задач, предлагаемых на ЕГЭ и олимпиаде по математике;

6.     изготовление панно для иллюстрации задачи;

7.     представление условий задач в стихотворной форме.

Что такое граф в математике.

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

Примеры графов в окружающем мире.

Хорошо знакомый  всем москвичам образец графа – схема московского метро.

Вершины – конечные станции и станции пересадок, ребра – пути, соединяющие эти станции.

Другой пример графа – генеалогическое дерево. В качестве примера продемонстрируем  генеалогическое дерево великого русского поэта А.С.Пушкина. 

Впервые основы теории графов появились в 1736 г. в работе Леонарда Эйлера, где он описывал решения головоломок и математических развлекательных задач.

 Широкое развитие теория графов получила с 50-х гг. ХХ в. в связи со становлением кибернетики и развитием вычислительной техники.

Обитатели неба. Созвездия.

«Путешествуя» по небесным просторам среди бесчисленных звёзд и туманностей, немудрено и заблудиться, если нет под рукой надёжной карты. Чтобы составить её, нужно точно знать положение тысяч звёзд на небе.

В давние времена созвездиями называли характерные группы ярких звёзд, которым давали имена, заимствованные из мифологии (Андромеда, Геркулес) или из быта (Весы, Телега).

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

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

Наше наблюдение: чтобы выделить отдельные созвездия из общего «звездного хаоса», первые астрономы условно соединили наиболее яркие звёзды линиями (построили графы). Всё множество видимых звёзд разделилось на отдельные группы – созвездия. Если граф ассоциировался с каким-либо знакомым объектом, то созвездию давалось соответствующее название.

 

Пример из медицины

 

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

Существуют четыре группы крови. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы.

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

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

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

Леонард Эйлер и теория графов

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

Широкое развитие теория графов получила с 50-х гг. ХХ в. в связи со становлением кибернетики и развитием вычислительной техники.

Задача об эйлеровом пути

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

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

Графы изоморфные и плоские

В 1859 г. английский математик Уильям Гамильтон выпустил в продажу головоломку. Она представляла собой деревянный додекаэдр (12–гранник), в вершинах которого вбиты гвоздики. Каждая из 20 вершин была помечена названием одного из крупных городов мира – Дели, Брюссель, Кантон и т.д. Требовалось найти замкнутый путь, проходящий по ребрам додекаэдра и позволяющий побывать в каждой его вершине по одному разу. Путь следовало отмечать с помощью шнура, зацепляя его за гвоздики. Эта игрушка оставила заметный след в математике.

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

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

  

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

Два графа, изображенные на рисунке 1 , в этом смысле одинаковы: у них одинаковое число вершин, и если две вершины одного графа соединены ребром, то вершины второго графа, имеющие те же номера, так же соединены ребром.

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

	Рисунок 1

 

 

	Графы на рисунке 2 тоже изоморфны. Отметим, что у одного из них некоторые рёбра пересекаются, у второго же таких пересечений нет
			Рисунок 2

 

А всегда ли граф можно изобразить на плоскости так, чтобы его рёбра не пересекались? Оказывается, нет. Графы, для которых это возможно, называются плоскими.

Рассмотрим два графа, которые «не укладываются» на плоскость без пересечения рёбер. Первый из них – граф с пятью вершинами, каждые две из которых соединены ребром. Такой граф называется полным (рис.3).

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

	Рисунок 3

 

«В трех избушках жили трое друзей. Около их домиков находилось три колодца: один с соленой водой, второй – со сладкой, третий – с пресной. Но однажды друзья поссорились, да так, что и видеть друг друга не хотели. И решили они по-новому проложить тропинки от домов к колодцам, чтобы их пути не пересекались. Как это сделать?»

	Панно, иллюстрирующее задачу (девятую дорожку без пересечения других, провести не удается).

Плоские графы обладают многими интересными свойствами. Так, Эйлер обнаружил простую связь между количеством вершин (В), количеством ребер (Р) и количеством частей (Г), на которые граф разделяет плоскость:

В–Р+Г=2.

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

Проверим эту зависимость для сделанных нами многогранников: икосаэдра и додекаэдра.

Для икосаэдра: В = 12; Р = 25; Г = 15; 12 – 25 + 15 = 2.

Для додекаэдра: В = 20; Р = 30; Г = 12; 20 – 30 + 12 = 2.

Задача. В стране Озёрная 7 озёр, соединённых между собой 10 каналами, причём от любого озера можно доплыть до любого другого. Сколько в этой стране островов?

Решение. Рассмотрим граф, в котором вершины соответствуют островам, а рёбра — каналам. Понятно, что полученный граф будет плоским и связным, значит, для него выполняется формула Эйлера: В — Р + Г = 2. Для нашего графа В = 7, Р = 10. Подставляя в формулу, получаем 7 — 10 + Г = 2. Отсюда следует, что Г = 5, то есть, рёбра графа разбивают плоскость на 5 частей. Островам соответствуют все грани, кроме внешней (она бесконечно большая во все стороны и острову соответствовать не может), значит, их 4.

 

Задачи, придуманные участниками проекта.

Задача о районе Митино.

Одна из классических задач теории графов называется «задачей коммивояжера» или «задачей о бродячем торговце».

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

Например:

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

Решить эту задачу очень непросто, особенно когда число вершин графа велико.

В нашей работе мы решили мы решили привести пример задачи о районе Митино.

Задача

На карте нашего района Митино обозначены пункты, которые чаще всего посещаются учениками нашей школы.

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

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

	15

Задача туриста.
(Автор: Бгатцев Алексей)

Составь туристический маршрут , посетив города: Варшава, Берлин, Париж, Лондон, начиная свой путь из Москвы.

Выбери самый короткий путь,  если расстояние :

от Москвы  до Варшавы – 1100 км,

от Москвы  до Берлина – 1600 км,

от Москвы  до Парижа – 2500 км,

от Москвы  до Лондона – 2500км,

от Варшавы  до Берлина – 500км,

от  Варшавы  до Парижа – 1300км,

от  Варшавы  до Лондона – 1500км ,

от Берлина  до Парижа – 900км,

от Берлина  до Лондона – 900км,

от Парижа  до Лондона – 300км.

Сколько вариантов маршрутов может быть?

 

Маршрут		Результат
М-В-Б-П-Л-М	1100+500+900+300+2500	5300
М-В-Б-Л-П-М	1100+500+900+300+2500	5300
М-В-П-Б-Л-М	1100+1300+900+900+2500	6700
М-В-П-Л-Б-М	1100+1300+300+900+1600	5200
М-В-Л-Б-П-М	1100+1500+900+900+2500	6900
М-В-Л-П-Б-М	1100+1500+300+900+1600	4600
М-Б-В-П-Л-М	1600+500+1300+300+2500	4200
М-Б-В-Л-П-М	1600+500+1500+300+2500	6400
М-Б-П-В-Л-М	1600+900+1300+1500+2500	7800
М-Б-П-Л-В-М	1600+900+300+1500+1100	5400
М-Б-Л-В-П-М	1600+900+1500+1300+2500	6800
М-Б-Л-П-В-М	1600+900+300+1300+1100	5200
М-П-В-Б-Л-М	2500+1300+500+900+2500	7700
М-П-В-Л-Б-М	2500+1300+1500+900+1600	7800
М-П-Б-В-Л-М	2500+900+500+1500+2500	7900
М-П-Б-Л-В-М	2500+900+900+1500+1100	6900
М-П-Л-В-Б-М	2500+300+1500+500+1600	6400
М-П-Л-Б-В-М	2500+300+900+500+1100	5300
М-Л-В-Б-П-М	2500+1500+500+900+2500	7900
М-Л-В-П-Б-М	2500+1500+1300+900+1600	7800
М-Л-Б-В-П-М	2500+900+500+1300+2500	7700
М-Л-Б-П-В-М	2500+900+900+1300+1100	6700
М-Л-П-В-Б-М	2500+300+1300+500+1600	6200
М-Л-П-Б-В-М	2500+300+900+500+1100	5300

Ответ: самый короткий путь -

 Москва-Берлин-Варшава-Париж-Лондон-Москва

Его длина 4200 км и 24 варианта маршрутов.

 

Задача о рейсах самолетов
(Автор: Гончаревич Настя)

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

Можно ли удовлетворить пожеланиям летчиков? Если да, то перечислите возможные варианты вылетов.

 

Ответ: возможно 2 варианта.

1)    первый рейс – в Варшаву, второй – в Лондон, третий – в Париж, четвертый – в Берлин.

2)    первый рейс – в Берлин, второй – в Варшаву, третий – в Лондон, четвертый – в Париж.

Задача «Расписание уроков»
(Автор: Азибекян Арен)

Для учащихся 7 “б” класса нужно составить расписание уроков на понедельник. Должны быть такие предметы: 2 урока математики, по 1 уроку русского языка, истории, биологии и географии. Учитель математики высказала пожелание, чтобы ее уроки были 1 и 3. Учителя русского языка   и истории согласны заниматься с учащимися на 2 или 4 уроках. Учителя биологии и географии – на 5 или 6.

Сколько вариантов расписания можно составить?

 

Можно составить 16 вариантов расписания. Вот некоторые из них:

 

Задача «Школьное меню»
(Автор:  Демидова Ксения )

В школьной столовой на первое можно заказать борщ,  щи, рыбный или гороховый суп , на второе – «ёжики», рыбу или котлету , а на третье - сок, чай или компот .

Сколько вариантов обеда можно получить из указанных блюд ?

 

Всего 36 вариантов меню.

 

Задача 1 из ЕГЭ по информатике.

Два игрока играют в следующую игру.

Перед ними лежат 2 кучки камней,
в 1-й из которых 4, а во 2-й – 3 камня.
У каждого игрока неограниченно много камней.
Игроки ходят по очереди.
Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то кучке, или добавляет 3 камня в какую-то кучку.
Выигрывает игрок, после хода которого в одной из кучек становится не менее 24 камней.
1) Кто выигрывает при безошибочной игре: игрок, делающий 1-й ход, или игрок, делающий 2-й ход?
2) Каким Должен быть 1-й ход выигрывающего игрока?

 

Задача 2 из ЕГЭ по информатике.

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

На 3-м месте в цепочке стоит одна из бусин А, В, Г. На 2-м месте – одна из бусин А, Б, В. На 1-м месте – одна из бусин Б, В, Г, не стоящая в цепочке на втором или третьем месте.
Сколько существует различных цепочек, соответствующих этому правилу.

 

Задача 3 из ЕГЭ по математике.

«Транспортная задача»

Велосипедист собирается проехать из пункта A в пункт E, в который ведут 3 маршрута: через B, через C, через D. Расстояния в километрах показаны на схеме. Известно, что если ехать через B, то средняя скорость будет ровна 16 км/ч, если ехать через D, то средняя скорость будет равна 18 км/ч, а если ехать через C, то средняя скорость будет равна 20 км/ч. Исходя из этих данных, велосипедист выбрал маршрут так, чтобы доехать до E за наименьшее время.

Сколько минут он планирует пробыть в пути?

Граф, соответствующий условию задачи.

 

Решение

1)    (15 + 25) : 16 = 2,5 (ч) – время в пути ABE

2)    (19 + 17) : 18 = 2 (ч)  – время в пути ADE

3)    (11 + 34) : 20 = 2,25 (ч) – время в пути AСE

4)    2  < 2,25 < 2,5

5)    2 (ч) = 120 (мин)

Ответ : 120 минут он планирует пробыть в пути

Олимпиада «Осенняя разминка» для 7-х классов

2009-2010 учебный год

Три профессора (Иванов, Петров и Сидоров) преподают различные предметы (химию, биологию, историю) в университетах Москвы, Минска и Киева.

Известно что:

·         Иванов никогда не был в Киеве, а Петров - в Минске;

·         Киевлянин старше профессора истории;

·         Петров играет в шахматы лучше, чем биолог;

·         Минчанин преподает химию.

Вопрос: где и что преподает Сидоров?

 

1.      Т.к. Иванов никогда не был в Киеве, а Петров в Минске Þ Иванов не из Киева, а Петров  не из Минска. 2.      Петров играет в шахматы лучше, чем биолог  Þ Петров  не биолог. 3.      Минчанин преподает химию. Þ Петров не преподает химию. Þ Петров Историк. Þ Иванов не историк и Сидоров не историк. 4.      Киевлянин старше профессора истории Þ Петров не может быть киевлянином. Þ Петров – москвич. Киевлянином может быть только Сидоров. Þ Сидоров не может быть москвичом или минчанином Þ Иванов  - минчанин. 5.      Минчанин преподает химию Þ Иванов – химик. Þ Иванов не может быть биологом, а Сидоров – химиком  Þ Сидоров – биолог. 6.      Ответ: Сидоров – биолог и живет в Киеве.

  

 

.

 

Три домика и три колодца.
В одном селе стоят три дома, В них три хозяина живут. Есть три колодца, а к колодцам Тропинки от домов ведут. Колодцы эти непростые, В колодцах разная вода. Соленой хочешь, пресной, сладкой? Так знаешь сам идти куда. Пока хозяева дружили, Все славно жили, не тужили. Товар везли во все концы – Укроп, клубнику, огурцы. Но вдруг нагрянула беда, Всему виной была вода. Друзья поссорились, да так – Друг друга видеть не хотели. Сады с укропом поредели, Тропинки затянул репей - Безлюдно, пусто - хоть убей.	Но без воды не проживешь, Не сваришь суп, лук не польешь, А будешь дальше обижаться – Того гляди и сам помрешь. Но вот однажды повезло: Соседям в голову пришло К воде пути себе наметить, Да так, чтоб никого не встретить, Чтоб все колодцы обойти, Водицы разной принести. Задача трудной оказалась, Но все ж надежда  показалась Смыть грязь и пыльные мохры, А это не хухры-мухры. Что делать? - Людям подскажите, К воде тропинки проложите. Им нужен добрый ваш совет: Как быть и где найти ответ? Друг друга вечно сторониться, Или придется помириться?

Заключение

Выводы

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

Описание результатов работы

Мы научились решать задачи методом, который не изучается в нашей школьной программе. Эти задачи имеют повышенный уровень сложности. Большая часть из них относится к логическим задачам. Нам также удалось составить свои собственные задачи (их решения приводятся в проекте). Некоторые научные утверждения мы проверили в ходе экспериментов и убедились в их справедливости. Это было очень увлекательно!

Самоанализ

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

Практическая значимость работы.

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

Используемая литература

1.   Энциклопедия для детей «Аванта», математика, том 11.
Изд. М.:«Аванта», 2002г.

2.   Энциклопедический словарь юного математика.
Сост. А.П. Савин – М.: Педагогика-Пресс, 1997г.

3.   И. Г. Семакин
«Информационные системы в базовом и профильном курсах информатики». Методическое пособие. Педагогический Университет «Первое сентября».

4.   Материалы сайта «Малый мехмат» http://mmmf.math.msu.su/vecher/circles/z7/

5.   Материалы ЕГЭ по математике.

6.   Материалы ЕГЭ по информатике.

 

• 1 слайд

  Решение логических задач с помощью графов
  Учебный проект по математике
  учеников 7 «Б» класса
  

• 2 слайд

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

• 3 слайд

  Пример из медицины
  II
  III
  IV
  I
  Известно, что у разных людей кровь отличается по группе.
  Существуют четыре группы крови. Оказывается, что при переливании крови от одного человека к другому не все группы совместимы.
  Граф показывает возможные варианты переливания крови. Группы крови – это вершины графов с соответствующими номерами, а стрелки указывают на возможность переливания одной группы крови человеку с другой группой крови.
  Из графа видно, что кровь 1-й группы можно переливать любому человеку, а человек с 1-й группой крови воспринимает кровь только своей группы.
  Видно также, что человеку с 4-й группой крови можно переливать любую, но его собственную кровь можно переливать только в ту же группу.
  

• 4 слайд

  Пример из астрономии
  В темную, безлунную и безоблачную ночь на небе видно множество звезд. Кажется, трудно разобраться в этой величественной картине звездного неба, о которой вдохновенно писал наш великий соотечественник М. В. Ломоносов (1711—1765):
  «Открылась бездна звезд полна,
  Звездам числа нет, бездне — дна».
  Но как же можно ориентироваться по звездам, если их видно на небе великое множество? Казалось бы, легко запутаться в этом обилии звезд. Вот для этого и нужно было, прежде всего, сгруппировать яркие звезды (которых на небе не так уже много) в фигуры, хорошо запоминающиеся своими контурами.
  

• 5 слайд

  Известные созвездия
  

• 6 слайд

  Генеалогическое дерево
  

• 7 слайд

  Московское метро
  

• 8 слайд

  Впервые основы теории графов появились в работе Леонарда Эйлера, где он описывал решения головоломок и математических развлекательных задач.
  Широкое развитие теория графов получила с 50-х гг. ХХ в. в связи со становлением кибернетики и развитием вычислительной техники.
  

• 9 слайд

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

• 10 слайд

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

• 11 слайд

  А всегда ли граф можно изобразить на плоскости так, чтобы его рёбра не пересекались? Оказывается, нет. Графы, для которых это возможно, называются плоскими.
  Для плоских графов справедлива формула Эйлера:
  В–Р+Г=2.
  
  Проверим эту зависимость для сделанных нами многогранников: икосаэдра и додекаэдра.
   
  Для икосаэдра: В = 12; Р = 25; Г = 15; 12 – 25 + 15 = 2.
  Для додекаэдра: В = 20; Р = 30; Г = 12; 20 – 30 + 12 = 2.
  
  

• 12 слайд

  «В трех избушках жили трое друзей. Около их домиков находилось три колодца: один с соленой водой, второй – со сладкой, третий – с пресной. Но однажды друзья поссорились, да так, что и видеть друг друга не хотели. И решили они по-новому проложить тропинки от домов к колодцам, чтобы их пути не пересекались. Как это сделать?»
  Рассмотрим два графа, которые «не укладываются» на плоскость без пересечения рёбер. Первый из них – граф с пятью вершинами, каждые две из которых соединены ребром. Такой граф называется полным.
  Второй граф, с шестью вершинами и девятью рёбрами, носит название «домики – колодцы». Оно произошло от старинной задачи – головоломки.
  

• 13 слайд

• 14 слайд

  Задача 1
  Задача туриста.
  (Автор: бгатцев алексей)
  
  Составь туристический маршрут , посетив города: Варшава, Берлин, Париж, Лондон, начиная свой путь из Москвы.
  Выбери самый короткий путь, если расстояние :
  от Москвы до Варшавы – 1100 км,
  от Москвы до Берлина – 1600 км,
  от Москвы до Парижа – 2500 км,
  от Москвы до Лондона – 2500км,
  от Варшавы до Берлина – 500км,
  от Варшавы до Парижа – 1300км,
  от Варшавы до Лондона – 1500км ,
  от Берлина до Парижа – 900км,
  от Берлина до Лондона – 900км,
  от Парижа до Лондона – 300км.
  Сколько вариантов маршрутов может быть?
  

• 15 слайд

  Решение
  В
  Москва
  Варшава
  Берлин
  Париж
  Лондон
  Б
  П
  Л
  В
  П
  Л
  В
  Б
  Л
  В
  Б
  П
  Варшава
  П
  Л
  Б
  Л
  Б
  П
  П
  Л
  В
  Л
  В
  П
  Б
  Л
  В
  Л
  Б
  Б
  П
  В
  П
  В
  Б
  Л
  П
  Л
  Б
  П
  Б
  Л
  П
  Л
  В
  П
  В
  Л
  Б
  Л
  В
  Б
  В
  П
  Б
  П
  В
  Б
  В
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  М
  

• 16 слайд

  Решение
  

• 17 слайд

  решение
  

• 18 слайд

  РЕШЕНИЕ
  Ответ: самый короткий путь Москва-
  Берлин-Варшава-Париж-Лондон-Москва
  Его длина 4200 км и 24 варианта маршрутов.
  

• 19 слайд

  Задача 2
  О рейсах самолетов
  (Автор: Гончаревич Настя)
  
  В связи с плохой погодой задерживаются четыре рейса самолетов – в Варшаву, Лондон, Париж и Берлин. Командиры самолетов высказали пожелания, чтобы рейс в Варшаву был первым или вторым, В Лондон – вторым или третьим, в Париж – третьим или четвертым, а в Берлин – первым или четвертым.
  Можно ли удовлетворить пожеланиям летчиков? Если да, то перечислите возможные варианты вылетов.
  Варшава
  Берлин
  Париж
  Лондон
  

• 20 слайд

  Решение
  
  Москва
  
  
  Лондон
  
  
  Париж
  
  
  Берлин
  
  
  Варшава
  
  Ответ: возможно 2 варианта.
  1)первый рейс – в Варшаву, второй – в Лондон, третий – в Париж, четвертый – в Берлин.
  2)первый рейс – в Берлин, второй – в Варшаву, третий – в Лондон, четвертый – в Париж.
  

• 21 слайд

  Задача 3
  «Расписание уроков»
  (Автор: Азибекян Арен)
  
  
  Для учащихся 7 “б” класса нужно составить расписание уроков на понедельник. Должны быть такие предметы: 2 урока математики, по 1 уроку русского языка, истории, биологии и географии. Учитель математики высказал пожелание, чтобы ее уроки были 1 и 3. Учителя русского языка и истории согласны заниматься с учащимися на 2 или 4 уроках. Учителя биологии и географии – на 5 или 6.
  Сколько вариантов расписания можно составить?
  

• 22 слайд

  Варианты для каждого урока
  2
  1
  3
  4
  5
  6
  Математика
  Русский язык
  История
  Математика
  Русский язык
  История
  Биология
  География
  Биология
  География
  

• 23 слайд

  Можно составить 16 вариантов расписания. Вот некоторые из них:
  1. Математика
  Русский язык
  Математика
  История
  Биология
  География
  
  1. Математика
  История
  Математика
  Русский язык
  Биология
  География
  
  1. Математика
  Русский язык
  Математика
  История
  География
  Биология
  
  

• 24 слайд

  Задача 4
  «Школьное меню»
  (Автор: Демидова Ксения )
  
  В школьной столовой на первое можно заказать борщ, щи, рыбный или гороховый суп , на второе – ёжика , рыбу или котлету , а на третье - сок , чай или компот .
  Сколько вариантов обеда можно получить из указанных блюд ?
  

• 25 слайд

  Решение
  Борщ
  Щи
  Рыбный суп
  Гороховый суп
  Ёжик
  Рыба
  Котлета
  Меню
  Сок
  Чай
  Компот
  

• 26 слайд

  Всего 36 вариантов меню.
  Щи
  Котлета
  Сок
  Борщ
  Рыба
  Чай
  Рыбный Суп
  Ёжик
  Компот
  Борщ
  Ёжик
  Компот
  

• 27 слайд

  1
  2
  3
  4
  5
  6
  7
  Спас
  Радиорынок
  Школа
  1062
  Макдональдс
  К/т Люксор
  Культурный центр
  Бассейн «Жемчужина»
  Задача о Митино
  На карте нашего района Митино обозначены пункты, которые чаще всего посещаются учениками нашей школы.
  Предположим, что принято решение о посадке деревьев и кустарников вдоль дорог, соединяющих указанные объекты. Стоимость озеленения каждого участка зависит от его длины. Требуется найти самый дешевый вариант реализации плана озеленения.
  
  Используем, так называемый «жадный алгоритм».
  Задача 5
  

• 28 слайд

  1
  2
  3
  4
  5
  6
  7
  Спас
  Радиорынок
  Школа
  1062
  Макдональдс
  К/т Люксор
  Культурный центр
  Бассейн «Жемчужина»
  Решение
  Учтем, что стоимость озеленения пропорциональна длине пути между двумя пунктами. Расстояния между объектами укажем в см (измерено по карте).
  
  5-6 5-4 5-3 3-2 2-1 6-7 – этапы озеленения
  Таким образом, можно будет обойти все обозначенные на карте объекты, каждый раз проходя по аллеям.
  

• 29 слайд

  Два игрока играют в следующую игру.
  
  Перед ними лежат 2 кучки камней,
  в 1-й из которых 4, а во 2-й – 3 камня.
  У каждого игрока неограниченно много камней.
  Игроки ходят по очереди.
  Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то кучке, или добавляет 3 камня в какую-то кучку.
  Выигрывает игрок, после хода которого в одной из кучек становится не менее 24 камней.
  1) Кто выигрывает при безошибочной игре: игрок, делающий 1-й ход, или игрок, делающий 2-й ход?
  2) Каким Должен быть 1-й ход выигрывающего игрока?
  
  ЕГЭ
  

• 30 слайд

  Для
  решения
  задачи
  1
  4;3
  12;3
  4;6
  7;3
  4;9
  36;3
  7;6
  7;18
  7;6
  4;27
  21;6
  7;18
  7;54
  21;6
  63;6
  63;6
  7;54
  2
  3
  4
  Исходные числа.
  Все ходы, которые может
  сделать первый игрок.
  Все безошибочные ходы второго игрока. При 1и3
  вариантах игрок выигрывает,
  а при 2 и 4 игрок прибавляет 3 к меньшему числу.
  Все ходы которые может сделать первый игрок.
  Все безошибочные ходы второго игрока, они же выигрывающие.
  Ответ: выигрывает второй игрок.
  составим
  граф
  

• 31 слайд

  Цепочка из трех бусин формируется по следующему правилу.
  
  На 3-м месте в цепочке стоит одна из бусин А, В, Г. На 2-м месте – одна из бусин А, Б, В. На 1-м месте – одна из бусин Б, В, Г, не стоящая в цепочке на втором или третьем месте.
  Сколько существует различных цепочек, соответствующих этому правилу.
  
  ЕГЭ
  

• 32 слайд

  3 место
  В
  А
  В
  Г
  Б
  А
  В
  А
  Б
  В
  А
  Б
  В
  Б
  Г
  В
  Г
  Б
  Г
  Б
  Г
  Б
  Г
  Г
  Б
  В
  В
  Б
  Подчитаем все варианты цепочек: их 16.
  Ответ: 16 вариантов цепочек.
  1 место
  2 место
  Для
  решения
  задачи
  составим
  граф
  

• 33 слайд

  «Транспортная задача»
  (ЕГЭ: 11 класс)
  Велосипедист собирается проехать из пункта A в пункт E, в который ведут 3 маршрута: через B, через C, через D. Расстояния в километрах показаны на схеме. Известно, что если ехать через B, то средняя скорость будет ровна 16 км/ч, если ехать через D, то средняя скорость будет равна 18 км/ч, а если ехать через C, то средняя скорость будет равна 20 км/ч. Исходя из этих данных, велосипедист выбрал маршрут так, чтобы доехать до E за наименьшее время.
  Сколько минут он планирует пробыть в пути?
  

• 34 слайд

  Граф, соответствующий условию задачи.
  В
  D
  C
  Е
  А
  15
  25
  19
  17
  34
  11
  

• 35 слайд

  Решение
  
  (15 + 25) : 16 = 2,5 (ч) – время в пути A-B-E
  (19 + 17) : 18 = 2 (ч) – время в пути A-D-E
  (11 + 34) : 20 = 2,25 (ч) – время в пути A-С-E
  2 < 2,25 < 2,5
  2 (ч) = 120 (мин)
  
  Ответ : 120 минут он планирует пробыть в пути .
  
  

• 36 слайд

  Олимпиада «Осенняя разминка» для 7-х классов
  2009-2010 учебный год
  Три профессора (Иванов, Петров и Сидоров) преподают различные предметы
  (химию, биологию, историю) в университетах Москвы, Минска и Киева.
  Известно что:
  Иванов никогда не был в Киеве, а Петров - в Минске;
  Киевлянин старше профессора истории;
  Петров играет в шахматы лучше, чем биолог;
  Минчанин преподает химию.
  Вопрос: где и что преподает Сидоров?
  

• 37 слайд

  Химия
  Биология
  История
  Москва
  Киев
  Минск
  Москва
  Киев
  Минск
  Москва
  Киев
  Минск
  Химия
  История
  Москва
  Киев
  Минск
  Москва
  Киев
  Минск
  Москва
  Киев
  Минск
  Биология
  Киев
  Минск
  Москва
  Киев
  Минск
  Киев
  Минск
  Москва
  Биология
  Химия
  Москва
  История
  Иванов
  Петров
  Сидоров
  Графы, с помощью которых ищется решение задачи.
  

• 38 слайд

  Т.к. Иванов никогда не был в Киеве, а Петров в Минске  Иванов не из Киева, а Петров не из Минска.
  Петров играет в шахматы лучше, чем биолог  Петров не биолог.
  Минчанин преподает химию.  Петров не преподает химию.  Петров Историк. 
  Иванов не историк и Сидоров не историк.
  Киевлянин старше профессора истории  Петров не может быть киевлянином.  Петров – москвич. Киевлянином может быть только Сидоров. 
  Сидоров не может быть москвичом или минчанином  Иванов - минчанин.
  Минчанин преподает химию  Иванов – химик.  Иванов не может быть биологом, а Сидоров – химиком  Сидоров – биолог.
  Ответ: Сидоров – биолог и живет в Киеве.
  Решение
  

• 39 слайд

  Задача про озера
  В стране «Озерной» - 7 озер,
  Каналы их соединяют.
  А между ними – острова,
  И сколько их – никто не знает.
  
  Мы на вопрос дадим ответ,
  Учтем: всего каналов – 10.
  А сколько островов там есть?
  Ответь, как следует все взвесив.
  

• 40 слайд

  КОНЕЦ