Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Математика / Презентации / Проект по математике "Графы и их применение"
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Математика

Проект по математике "Графы и их применение"

библиотека
материалов
Разработала: Богданова Ольга Николаевна, учитель математики МКОУ «Овечкинска...
Цель: Создать условия для самостоятельного освоения новых знаний, самообразов...
1. Теория графов 2. Применение графов 3. Графы игр 4. Задачи: № 1 № 2 № 3 7....
Теория графов В математике определение графа дается так: Графом называется ко...
Теория графов Понятие графа
Теория графов Понятие графа
Теория графов Понятие графа Рис.5
Теория графов Количество рёбер, выходящих из вершины графа, называется степен...
Теория графов Эйлеровы графы Рис.9 Рис.10 Рис.11
Теория графов Степени вершин и подсчета числа ребер Рис.6 Рис.8 Рис.7
Теория графов Одним росчерком Если все вершины графа четные, то можно не отры...
Теория графов Одним росчерком Граф, имеющий всего две нечетные вершины, можно...
Теория графов Одним росчерком Граф, имеющий более двух нечетных вершин, невоз...
Теория графов Связные графы Рис.12 Рис.13
Теория графов Деревья Рис.16 Рис.15 Рис.14
Теория графов Ориентированные графы Рис.17
Применение графов Графы помогают в решении различных головоломок, математичес...
Применение графов С помощью графов упрощается решение математических задач, г...
Применение графов Лабиринт - это граф. А исследовать его - это найти путь в э...
Применение графов Графами являются блок – схемы программ для ЭВМ.
Применение графов Графами являются сетевые графики строительства.
Применение графов Графы есть и на картах звездного неба.
Применение графов Графом является и система улиц города. Его вершины – площад...
Применение графов Типичными графами являются схемы авиалиний, которые часто в...
Применение графов Типичными графами на географических картах являются изображ...
Задача № 1 Мальчики 9 класса Андрей, Витя, Сережа, Валера, Дима при встрече о...
Задача № 1 Пусть каждому из пяти молодых людей соответствует определенная точ...
Задача № 2 Можно ли нарисовать графы изображенные на рисунках 19 и 20, не отр...
Задача № 2 Решение: На рисунке 19 можно, т. к. только 2 нечетные вершины. На...
Задача № 3 Кинигсбергские мосты . К XVIII веку через реку, на которой стоял г...
Задача № 3 Решение: Прохождение по всем мостам при условии, что нужно на кажд...
Задача № 4 В кафе предлагают два первых блюда: борщ, рассольник, а также четы...
Задача № 4 Решение: Обеды Борщ Рассольник Гуляш Сосиски Пельмени Котлеты Гуля...
Генеалогическое дерево Рис.23
Овечкина Юлия Алексеевна 1994 г. Овечкин Алексей Николаевич 1973 г. Овечкин Н...
ПРОВЕРЬ СЕБЯ Задача № 1 Задача № 2 Задача № 3 Задача № 4 Задача № 5 Задача №6...
Глоссарий . 1. Граф – это конечное множество точек, некоторые из которых соед...
Заключение В данном проекте рассмотрены математические графы, области их прим...
Литература 1. Весёлые задачи, Я. И. Перельман, Москва, 2003г 2. Графы и их пр...
Вопрос 1 Вопрос 2 Вопрос 3 Вопрос 4 Вопрос 5 Вопрос 6 Вопрос 7 Вопрос 8 Вопро...
Что такое конечное множество точек, некоторые из которых соединены линиями? О...
Как называются точки графа? Ответ
Как называются линии графа? Ответ
Что называется степенью вершины? Ответ
Какой граф называется полным? Ответ
Что значит «эйлеров граф»? Ответ
Что такое «мост» в теории графов? Ответ
Что такое «дерево» в теории графов? Ответ
Что такое «висячая вершина» в теории графов? Ответ
Какая вершина графа называется нечетной? Ответ
Какая вершина графа называется четной? Ответ
Что называется циклом в теории графов? Ответ
Как называется граф, состоящий из изолированных вершин? Нулевой граф 2. Как н...
Такое множество точек называется графом.
Точки графа называются вершинами.
Линии графа называются ребрами.
Количество ребер, выходящих из вершины графа, называется степенью вершины.
Граф, в котором построены все возможные ребра, называется полным.
Граф, в котором построены все возможные ребра, называется полным.
Ребро, после удаления которого граф из связного превращается в несвязный.
Дерево – это граф, в котором две любые вершины соединены ровно одним простым...
Висячей вершиной называется вершина, из которой выходит ровно одно ребро.
Вершина графа, имеющая нечетную степень называется нечетной.
Вершина графа, имеющая четную степень называется четной.
Циклом в теории графов называется путь, в котором совпадают начало и конец.
Циклом в теории графов называется путь, в котором совпадают начало и конец.
Задача № 5 В трех различных домах живут три поссорившиеся между собой соседа....
Задача № 5 Решение:Построим граф, вершины которого А, Б, В, 1, 2, 3 соответст...
Задача №6 По окончании деловой встречи специалисты обменялись визитными карто...
Решение:Используем полные направленные графы; стрелки на каждом ребре обозна...
Можно ли обвести карандашом, не отрывая его от бумаги и не проходя по одной...
Ответ: Так как пятиугольник – граф и все вершины его четные – то это выполнит...
Физминутка Комплекс упражнений гимнастики для глаз Быстро поморгать, закрыть...
На шахматной мини-доске (рис.1) размером 3х3 расположены четыре коня – два бе...
Пусть на столе лежит 5 спичек. Двое игроков по очереди берут 1 или 2 спички....
№1. В государстве 50 городов, и из каждого выходит 8 дорог. Сколько всего до...
№2 У царя Гвидона было 5 детей. Из всех его потомков (детей, внуков, правнук...
№3 В квадрате отметили 20 точек и соединили их непересекающимися отрезками д...
№4. В первенстве класса по настольному теннису 6 участников: Андрей, Борис,...
Проверь себя №5. В стране Озерная 7 озер, соединенных между собой 10 каналами...
№6 Ужасные грабители Кнопка и Скрёпка решили украсть из сейфа золотой ключик...
Проверь себя А: 3 В: 6 С: 4 №7 У Лёвы 2 конверта: обычный и авиа ,и 3 марки:...
№8 Сколько двузначных чисел можно составить из чисел 1,2,3.4 ,используя в зап...
№ 9 Антон, Борис и Василий купили 3 билета на 1-е,2-е и 3-е места первого ря...
Проверь себя А: 24 В: 18 С: 16
№1. Так как ребро графа соединяет две вершины, то 50 умножить на 8/2, получим...
№2. 57х3+5=176. Число потомков равно количеству ребер в графе – родословном д...
Пусть отмеченные точки и вершины квадрата – вершины, и соединяющие их отрезки...
Построим граф (рис,1) Сыграно 7 игр. На рис. 2 граф имеет 8 ребер, следовател...
№ 5. В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от...
Подумай хорошо! №1 №2 №3 №4 №5 №6 №7 №8 №9 №10
 код 1 2 3 1 2 4 3 1 2 3 4 1 2 3 4 1 2 3 4 4 Ответ: 16 № 6
письмо А О П Т К П Т А Ответ: 6 № 7
 число 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 Ответ: 12 № 8
№ 9 Ответ: 1место- 3 2 место-6 3 место-6
№ 10 Ответ: 24
Литература 1. Весёлые задачи, Я. И. Перельман, Москва, 2003г 2. Графы и их пр...
http://liubavyshka.ru/photo/64 - книга http://liubavyshka.ru/photo/58 - возду...
100 1

Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Описание презентации по отдельным слайдам:

№ слайда 1 Разработала: Богданова Ольга Николаевна, учитель математики МКОУ «Овечкинска
Описание слайда:

Разработала: Богданова Ольга Николаевна, учитель математики МКОУ «Овечкинская средняя общеобразовательная школа Завьяловского района» Алтайского края УМК любой 7 – 11 класс

№ слайда 2 Цель: Создать условия для самостоятельного освоения новых знаний, самообразов
Описание слайда:

Цель: Создать условия для самостоятельного освоения новых знаний, самообразования, интеллектуального и творческого развития. Задачи: 1.Познакомить с историей возникновения графов. 2.Формировать умения решать задания с помощью графов.

№ слайда 3 1. Теория графов 2. Применение графов 3. Графы игр 4. Задачи: № 1 № 2 № 3 7.
Описание слайда:

1. Теория графов 2. Применение графов 3. Графы игр 4. Задачи: № 1 № 2 № 3 7. Проверь себя. № 4 № 6 8. Игра «Что?Где?Как?» № 5 № 7 5.Генеалогическое дерево 9. Заключение 6.Глоссарий 10. Литература 11. Физминутка 12. Выход Содержание

№ слайда 4 Теория графов В математике определение графа дается так: Графом называется ко
Описание слайда:

Теория графов В математике определение графа дается так: Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами. Рёбра графа Вершина графа

№ слайда 5 Теория графов Понятие графа
Описание слайда:

Теория графов Понятие графа

№ слайда 6 Теория графов Понятие графа
Описание слайда:

Теория графов Понятие графа

№ слайда 7 Теория графов Понятие графа Рис.5
Описание слайда:

Теория графов Понятие графа Рис.5

№ слайда 8 Теория графов Количество рёбер, выходящих из вершины графа, называется степен
Описание слайда:

Теория графов Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной. Нечётная степень Чётная степень

№ слайда 9 Теория графов Эйлеровы графы Рис.9 Рис.10 Рис.11
Описание слайда:

Теория графов Эйлеровы графы Рис.9 Рис.10 Рис.11

№ слайда 10 Теория графов Степени вершин и подсчета числа ребер Рис.6 Рис.8 Рис.7
Описание слайда:

Теория графов Степени вершин и подсчета числа ребер Рис.6 Рис.8 Рис.7

№ слайда 11 Теория графов Одним росчерком Если все вершины графа четные, то можно не отры
Описание слайда:

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

№ слайда 12 Теория графов Одним росчерком Граф, имеющий всего две нечетные вершины, можно
Описание слайда:

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

№ слайда 13 Теория графов Одним росчерком Граф, имеющий более двух нечетных вершин, невоз
Описание слайда:

Теория графов Одним росчерком Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». ?

№ слайда 14 Теория графов Связные графы Рис.12 Рис.13
Описание слайда:

Теория графов Связные графы Рис.12 Рис.13

№ слайда 15 Теория графов Деревья Рис.16 Рис.15 Рис.14
Описание слайда:

Теория графов Деревья Рис.16 Рис.15 Рис.14

№ слайда 16 Теория графов Ориентированные графы Рис.17
Описание слайда:

Теория графов Ориентированные графы Рис.17

№ слайда 17 Применение графов Графы помогают в решении различных головоломок, математичес
Описание слайда:

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

№ слайда 18 Применение графов С помощью графов упрощается решение математических задач, г
Описание слайда:

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

№ слайда 19 Применение графов Лабиринт - это граф. А исследовать его - это найти путь в э
Описание слайда:

Применение графов Лабиринт - это граф. А исследовать его - это найти путь в этом графе.

№ слайда 20 Применение графов Графами являются блок – схемы программ для ЭВМ.
Описание слайда:

Применение графов Графами являются блок – схемы программ для ЭВМ.

№ слайда 21 Применение графов Графами являются сетевые графики строительства.
Описание слайда:

Применение графов Графами являются сетевые графики строительства.

№ слайда 22 Применение графов Графы есть и на картах звездного неба.
Описание слайда:

Применение графов Графы есть и на картах звездного неба.

№ слайда 23 Применение графов Графом является и система улиц города. Его вершины – площад
Описание слайда:

Применение графов Графом является и система улиц города. Его вершины – площади и перекрестки, а ребра – улицы.

№ слайда 24 Применение графов Типичными графами являются схемы авиалиний, которые часто в
Описание слайда:

Применение графов Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах.

№ слайда 25 Применение графов Типичными графами на географических картах являются изображ
Описание слайда:

Применение графов Типичными графами на географических картах являются изображения железных дорог.

№ слайда 26 Задача № 1 Мальчики 9 класса Андрей, Витя, Сережа, Валера, Дима при встрече о
Описание слайда:

Задача № 1 Мальчики 9 класса Андрей, Витя, Сережа, Валера, Дима при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? Решение

№ слайда 27 Задача № 1 Пусть каждому из пяти молодых людей соответствует определенная точ
Описание слайда:

Задача № 1 Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки - имена.( рис.18) Если подсчитать число ребер графа, изображенного на рисунке справа, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10. Решение: Рис.18

№ слайда 28 Задача № 2 Можно ли нарисовать графы изображенные на рисунках 19 и 20, не отр
Описание слайда:

Задача № 2 Можно ли нарисовать графы изображенные на рисунках 19 и 20, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз? Рис.19 Рис.20 Решение

№ слайда 29 Задача № 2 Решение: На рисунке 19 можно, т. к. только 2 нечетные вершины. На
Описание слайда:

Задача № 2 Решение: На рисунке 19 можно, т. к. только 2 нечетные вершины. На рисунке 20 нельзя, т. к. 4 нечетные вершины. Рис.19 Рис.20

№ слайда 30 Задача № 3 Кинигсбергские мосты . К XVIII веку через реку, на которой стоял г
Описание слайда:

Задача № 3 Кинигсбергские мосты . К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города. Задача заключается в следующем: нужно пройти (если это возможно) по всем семи мостам так, чтобы на каждом из них побывать лишь по одному разу и вернуться к тому месту, откуда начал маршрут Решение

№ слайда 31 Задача № 3 Решение: Прохождение по всем мостам при условии, что нужно на кажд
Описание слайда:

Задача № 3 Решение: Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа, представленного на рисунке 21. Вершины А и В – это острова. Вершина А имеет степень 3, а вершина В - степень 5, берега С и Д – имеют степень 3. Так как граф на этом рисунке имеет четыре нечетные вершины, то, согласно правилу такой граф начертить «одним росчерком» невозможно. Значит, и пройти по кенигсбергским мостам, соблюдая заданные условия, нельзя. Рис.21

№ слайда 32 Задача № 4 В кафе предлагают два первых блюда: борщ, рассольник, а также четы
Описание слайда:

Задача № 4 В кафе предлагают два первых блюда: борщ, рассольник, а также четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из двух блюд, которые может заказать посетитель. Проиллюстрируйте ответ, построив дерево возможных вариантов Решение

№ слайда 33 Задача № 4 Решение: Обеды Борщ Рассольник Гуляш Сосиски Пельмени Котлеты Гуля
Описание слайда:

Задача № 4 Решение: Обеды Борщ Рассольник Гуляш Сосиски Пельмени Котлеты Гуляш Сосиски Пельмени Котлеты

№ слайда 34 Генеалогическое дерево Рис.23
Описание слайда:

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

№ слайда 35 Овечкина Юлия Алексеевна 1994 г. Овечкин Алексей Николаевич 1973 г. Овечкин Н
Описание слайда:

Овечкина Юлия Алексеевна 1994 г. Овечкин Алексей Николаевич 1973 г. Овечкин Николай Александрович 1954 г. Овечкина Ольга Анатольевна 1974 г. Чарыкова Лидия Ивановна, 1956 г. Овечкина Любовь Ивановна, 1953 г. Чарыков Анатолий Михайлович. 1953 г. Овечкин Александр Артемьевич, 1908 г. Акентьева Александра Егоровна, 1919 г. Овечкина Екатерина Григорьевна, 1918 г. Шаговский Иван Демьянович,1930 г Родословная Овечкиной Юлии Чарыков Михаил Иванович,1926 г. Чарыкова Мария Петровна. 1929 г. Удовенко Екатерина Васильевна, 1930 г. Рис.24

№ слайда 36 ПРОВЕРЬ СЕБЯ Задача № 1 Задача № 2 Задача № 3 Задача № 4 Задача № 5 Задача №6
Описание слайда:

ПРОВЕРЬ СЕБЯ Задача № 1 Задача № 2 Задача № 3 Задача № 4 Задача № 5 Задача №6 Задача № 7 Задача № 8 Задача № 9 Задача №10

№ слайда 37 Глоссарий . 1. Граф – это конечное множество точек, некоторые из которых соед
Описание слайда:

Глоссарий . 1. Граф – это конечное множество точек, некоторые из которых соединены линиями. Точки – это вершины, линии - ребра 2. Степень вершины – это количество ребер, выходящих из вершины графа. 3. Вершина, имеющая четную степень называется четной, а нечетную степень называется нечетной. 4. Эйлеров граф – это граф, который можно нарисовать не отрывая карандаша от бумаги. 5. Связный граф – это граф, у которого две вершины могут быть соединены путем. 6. Мост – это такое ребро, после удаления которого граф из связного превращается в несвязный. 7. Циклом называется путь, в котором совпадают начало и конец. 8. Висячей вершиной называется вершина, из которой выходит ровно одно ребро. 9. Ориентированный или направленный граф – это граф, на ребрах которого расставлены стрелки. 10. Дерево – это граф, в котором две любые вершины соединены ровно одним простым путем.

№ слайда 38
Описание слайда:

№ слайда 39 Заключение В данном проекте рассмотрены математические графы, области их прим
Описание слайда:

Заключение В данном проекте рассмотрены математические графы, области их применения, решено несколько задач с помощью графов. Графы достаточно широко применяются в математике, технике, экономике, управлении. Выделяя из словесных рассуждений главное - объекты и отношения между ними, графы представляют изучаемые факты в наглядной форме. Приёмы решения логических задач с использованием графов подкупают своей естественностью и простотой, избавляют от лишних рассуждений, во многих случаях сокращающих нагрузку на память.   Теория графов в настоящее время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графов описываются многие объекты и ситуации: схемы электрических и электронных приборов, химические молекулы, отношения между людьми и многое другое.

№ слайда 40 Литература 1. Весёлые задачи, Я. И. Перельман, Москва, 2003г 2. Графы и их пр
Описание слайда:

Литература 1. Весёлые задачи, Я. И. Перельман, Москва, 2003г 2. Графы и их применение, О. Оре, Москва, 1979г 3. Ленинградские математические кружки: пособие для внеклассной работы, С. А. Генкин, И. В. Итенберг, Киров, 1994г 4. Математика (Дополнительные главы). Е. В. Смыкалова Санкт- Петербург СМИО Пресс 2006   5. Математическая смекалка, Е. И. Игнатьев, Москва 1994г 6. Сборник олимпиадных задач по математике, В. Г. Горбачев, 2004г 7. Физико-математический журнал «Квант», А. Савин, №6 1994г. 8.

№ слайда 41
Описание слайда:

№ слайда 42 Вопрос 1 Вопрос 2 Вопрос 3 Вопрос 4 Вопрос 5 Вопрос 6 Вопрос 7 Вопрос 8 Вопро
Описание слайда:

Вопрос 1 Вопрос 2 Вопрос 3 Вопрос 4 Вопрос 5 Вопрос 6 Вопрос 7 Вопрос 8 Вопрос 9 Вопрос 10 Вопрос 11 Вопрос 12 Блиц

№ слайда 43 Что такое конечное множество точек, некоторые из которых соединены линиями? О
Описание слайда:

Что такое конечное множество точек, некоторые из которых соединены линиями? Ответ

№ слайда 44 Как называются точки графа? Ответ
Описание слайда:

Как называются точки графа? Ответ

№ слайда 45 Как называются линии графа? Ответ
Описание слайда:

Как называются линии графа? Ответ

№ слайда 46 Что называется степенью вершины? Ответ
Описание слайда:

Что называется степенью вершины? Ответ

№ слайда 47 Какой граф называется полным? Ответ
Описание слайда:

Какой граф называется полным? Ответ

№ слайда 48 Что значит «эйлеров граф»? Ответ
Описание слайда:

Что значит «эйлеров граф»? Ответ

№ слайда 49 Что такое «мост» в теории графов? Ответ
Описание слайда:

Что такое «мост» в теории графов? Ответ

№ слайда 50 Что такое «дерево» в теории графов? Ответ
Описание слайда:

Что такое «дерево» в теории графов? Ответ

№ слайда 51 Что такое «висячая вершина» в теории графов? Ответ
Описание слайда:

Что такое «висячая вершина» в теории графов? Ответ

№ слайда 52 Какая вершина графа называется нечетной? Ответ
Описание слайда:

Какая вершина графа называется нечетной? Ответ

№ слайда 53 Какая вершина графа называется четной? Ответ
Описание слайда:

Какая вершина графа называется четной? Ответ

№ слайда 54 Что называется циклом в теории графов? Ответ
Описание слайда:

Что называется циклом в теории графов? Ответ

№ слайда 55 Как называется граф, состоящий из изолированных вершин? Нулевой граф 2. Как н
Описание слайда:

Как называется граф, состоящий из изолированных вершин? Нулевой граф 2. Как называется граф, у которого степени всех вершин равны? Однородный граф 3. Как называется граф, у которого на ребрах нанесены стрелки? Направленный граф

№ слайда 56 Такое множество точек называется графом.
Описание слайда:

Такое множество точек называется графом.

№ слайда 57 Точки графа называются вершинами.
Описание слайда:

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

№ слайда 58 Линии графа называются ребрами.
Описание слайда:

Линии графа называются ребрами.

№ слайда 59 Количество ребер, выходящих из вершины графа, называется степенью вершины.
Описание слайда:

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

№ слайда 60 Граф, в котором построены все возможные ребра, называется полным.
Описание слайда:

Граф, в котором построены все возможные ребра, называется полным.

№ слайда 61 Граф, в котором построены все возможные ребра, называется полным.
Описание слайда:

Граф, в котором построены все возможные ребра, называется полным.

№ слайда 62 Ребро, после удаления которого граф из связного превращается в несвязный.
Описание слайда:

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

№ слайда 63 Дерево – это граф, в котором две любые вершины соединены ровно одним простым
Описание слайда:

Дерево – это граф, в котором две любые вершины соединены ровно одним простым путем.

№ слайда 64 Висячей вершиной называется вершина, из которой выходит ровно одно ребро.
Описание слайда:

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

№ слайда 65 Вершина графа, имеющая нечетную степень называется нечетной.
Описание слайда:

Вершина графа, имеющая нечетную степень называется нечетной.

№ слайда 66 Вершина графа, имеющая четную степень называется четной.
Описание слайда:

Вершина графа, имеющая четную степень называется четной.

№ слайда 67 Циклом в теории графов называется путь, в котором совпадают начало и конец.
Описание слайда:

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

№ слайда 68 Циклом в теории графов называется путь, в котором совпадают начало и конец.
Описание слайда:

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

№ слайда 69 Задача № 5 В трех различных домах живут три поссорившиеся между собой соседа.
Описание слайда:

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

№ слайда 70 Задача № 5 Решение:Построим граф, вершины которого А, Б, В, 1, 2, 3 соответст
Описание слайда:

Задача № 5 Решение:Построим граф, вершины которого А, Б, В, 1, 2, 3 соответствуют домам и колодцам условия задачи, и попробуем доказать, что девятую тропинку — ребро графа, не пересекающее остальные ребра, провести нельзя. Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер). Таким образом, ответ на вопрос задачи будет таким: «Нельзя!»

№ слайда 71 Задача №6 По окончании деловой встречи специалисты обменялись визитными карто
Описание слайда:

Задача №6 По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвовали: 1) 3 человека; 2) 4 человека? Решение

№ слайда 72 Решение:Используем полные направленные графы; стрелки на каждом ребре обозна
Описание слайда:

Решение:Используем полные направленные графы; стрелки на каждом ребре обозначают передаваемую визитную карточку. 1). Во встрече участвовали 3 человека: 2 3 ребра 6 стрелок. Передано 6 визитных карточек 1 3 2) Во встрече участвовали 4 человека: 1 2 3 4 6 рёбер, 12 стрелок. Передано 12 визитных карточек.   . Ответ: 1) 6; 2) 12 Задача №6

№ слайда 73 Можно ли обвести карандашом, не отрывая его от бумаги и не проходя по одной
Описание слайда:

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

№ слайда 74 Ответ: Так как пятиугольник – граф и все вершины его четные – то это выполнит
Описание слайда:

Ответ: Так как пятиугольник – граф и все вершины его четные – то это выполнить можно. Задача 7

№ слайда 75 Физминутка Комплекс упражнений гимнастики для глаз Быстро поморгать, закрыть
Описание слайда:

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

№ слайда 76 На шахматной мини-доске (рис.1) размером 3х3 расположены четыре коня – два бе
Описание слайда:

На шахматной мини-доске (рис.1) размером 3х3 расположены четыре коня – два белых и два черных. Задача – переставить фигуры так, чтобы одинаковые кони оказались в противоположных углах доски (рис.2). Перемешать их можно только ходом шахматного коня и нельзя ставить фигуру на уже занятое поле. Графы игр Все попытки совершить такую перестановку терпят неудачу. Почему? Давайте начертим граф возможных ходов коней на доске (рис.3). Затем построим изоморфный ему граф без самопересечений в двух вариантах: на одном отметим первоначальное положение коней, а на другом – требуемое (рис.4,а, б). Вот теперь понятно, почему задача не решается. Движение коней по графу означает переходы в соседние вершины, и перейти из первой позиции во вторую невозможно без «перескока» через коня другого цвета. Рис.1 Рис.3 Рис.2 Рис.4

№ слайда 77 Пусть на столе лежит 5 спичек. Двое игроков по очереди берут 1 или 2 спички.
Описание слайда:

Пусть на столе лежит 5 спичек. Двое игроков по очереди берут 1 или 2 спички. Выигрывает тот, кто забирает последнюю Графы игр Нарисуем граф всевозможных продолжений игры (рис.19). Видно, что после первого хода на столе остается 3 или 4 спички. Если тот, кто начинает, оставит на столе 3 спички, то он выиграет: ведь его партнер вынужден будет оставить 1 или 2 спички, которые начинавший и заберет на следующем ходу. Если же начинающий игру оставит 4 спички, то он проиграет, так как партнер, взяв 1 спичку, оставит ему 3, что, как мы уже видели, ведет к проигрышу игрока, делающего очередной ход. Конечно же, второй игрок может оставить 2 спички и тут же проиграть, но это маловероятно. Можно сделать вывод: начинающий проигрывает, если исходное число спичек делится на 3, и выиграет в остальных случаях, оставляя партнеру всякий раз количество спичек, которое делится на три.

№ слайда 78 №1. В государстве 50 городов, и из каждого выходит 8 дорог. Сколько всего до
Описание слайда:

№1. В государстве 50 городов, и из каждого выходит 8 дорог. Сколько всего дорог в государстве? А:400 В:200 С:300 Проверь себя

№ слайда 79 №2 У царя Гвидона было 5 детей. Из всех его потомков (детей, внуков, правнук
Описание слайда:

№2 У царя Гвидона было 5 детей. Из всех его потомков (детей, внуков, правнуков и т.д.) 57 имели ровно трех сыновей, а остальные умерли бездетными. Сколько потомков было у царя Гвидона? А: 176 В: 184 С: 156 Проверь себя

№ слайда 80 №3 В квадрате отметили 20 точек и соединили их непересекающимися отрезками д
Описание слайда:

№3 В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников? А:52 В:32 С:42 Проверь себя

№ слайда 81 №4. В первенстве класса по настольному теннису 6 участников: Андрей, Борис,
Описание слайда:

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

№ слайда 82 Проверь себя №5. В стране Озерная 7 озер, соединенных между собой 10 каналами
Описание слайда:

Проверь себя №5. В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов? А: 3 В: 4 С: 5

№ слайда 83 №6 Ужасные грабители Кнопка и Скрёпка решили украсть из сейфа золотой ключик
Описание слайда:

№6 Ужасные грабители Кнопка и Скрёпка решили украсть из сейфа золотой ключик Буратино, который знает пока 4 цифры:1,2,3,4.Сколько вариантов придётся перебрать им, чтобы проникнуть в дом, подобрав двузначный код? Проверь себя А: 8 В: 12 С: 16

№ слайда 84 Проверь себя А: 3 В: 6 С: 4 №7 У Лёвы 2 конверта: обычный и авиа ,и 3 марки:
Описание слайда:

Проверь себя А: 3 В: 6 С: 4 №7 У Лёвы 2 конверта: обычный и авиа ,и 3 марки: прямоугольная , квадратная и треугольная. Сколькими способами он может выбрать кон верт и марку чтобы отправить письмо?

№ слайда 85 №8 Сколько двузначных чисел можно составить из чисел 1,2,3.4 ,используя в зап
Описание слайда:

№8 Сколько двузначных чисел можно составить из чисел 1,2,3.4 ,используя в записи числа каждую из них не более одного раза? А: 16 В: 6 С: 12 Проверь себя

№ слайда 86 № 9 Антон, Борис и Василий купили 3 билета на 1-е,2-е и 3-е места первого ря
Описание слайда:

№ 9 Антон, Борис и Василий купили 3 билета на 1-е,2-е и 3-е места первого ряда на футбольный матч. Сколькими способами они могут занять имеющиеся места? Проверь себя А: В: С: 1место- 3 2 место-9 3 место-6 1место- 3 2 место-6 3 место-9 1место- 3 2 место-6 3 место-6

№ слайда 87 Проверь себя А: 24 В: 18 С: 16
Описание слайда:

Проверь себя А: 24 В: 18 С: 16

№ слайда 88 №1. Так как ребро графа соединяет две вершины, то 50 умножить на 8/2, получим
Описание слайда:

№1. Так как ребро графа соединяет две вершины, то 50 умножить на 8/2, получим 200 ребер. Значит в государстве 200 дорог. Ответ: 200

№ слайда 89 №2. 57х3+5=176. Число потомков равно количеству ребер в графе – родословном д
Описание слайда:

№2. 57х3+5=176. Число потомков равно количеству ребер в графе – родословном дереве царя Гвидона. Ответ: 176

№ слайда 90 Пусть отмеченные точки и вершины квадрата – вершины, и соединяющие их отрезки
Описание слайда:

Пусть отмеченные точки и вершины квадрата – вершины, и соединяющие их отрезки и стороны квадрата – ребра плоского графа. Для каждого куска, на которые граф разбивает плоскость, посчитаем число ограничивающих ребер, и все полученные числа сложим. Поскольку каждое ребро разделяет два куска, то в итоге получим удвоенное число ребер. Так как все куски, кроме внешнего – треугольники, а внешний кусок ограничен 4 ребрами, то получаем 3 (F-1)+4=2F, т.е. Е=3(F-1)/2+2. (где F – число граней, а Е – число ребер) Заметим, что число вершин нашего графа равно 24 и подставим количества вершин ребер в формулу Эйлера 24-(3(F-1)/2+2) +F=2. отсюда F=43. итак, число треугольников – 42. Ответ: 42 № 3. Решение:

№ слайда 91 Построим граф (рис,1) Сыграно 7 игр. На рис. 2 граф имеет 8 ребер, следовател
Описание слайда:

Построим граф (рис,1) Сыграно 7 игр. На рис. 2 граф имеет 8 ребер, следовательно, осталось провести 8 игр.   № 4. Решение: Рис.1 Рис.2

№ слайда 92 № 5. В стране Озерная 7 озер, соединенных между собой 10 каналами, причем от
Описание слайда:

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

№ слайда 93 Подумай хорошо! №1 №2 №3 №4 №5 №6 №7 №8 №9 №10
Описание слайда:

Подумай хорошо! №1 №2 №3 №4 №5 №6 №7 №8 №9 №10

№ слайда 94  код 1 2 3 1 2 4 3 1 2 3 4 1 2 3 4 1 2 3 4 4 Ответ: 16 № 6
Описание слайда:

код 1 2 3 1 2 4 3 1 2 3 4 1 2 3 4 1 2 3 4 4 Ответ: 16 № 6

№ слайда 95 письмо А О П Т К П Т А Ответ: 6 № 7
Описание слайда:

письмо А О П Т К П Т А Ответ: 6 № 7

№ слайда 96  число 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 Ответ: 12 № 8
Описание слайда:

число 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 Ответ: 12 № 8

№ слайда 97 № 9 Ответ: 1место- 3 2 место-6 3 место-6
Описание слайда:

№ 9 Ответ: 1место- 3 2 место-6 3 место-6

№ слайда 98 № 10 Ответ: 24
Описание слайда:

№ 10 Ответ: 24

№ слайда 99 Литература 1. Весёлые задачи, Я. И. Перельман, Москва, 2003г 2. Графы и их пр
Описание слайда:

Литература 1. Весёлые задачи, Я. И. Перельман, Москва, 2003г 2. Графы и их применение, О. Оре, Москва, 1979г 3. Ленинградские математические кружки: пособие для внеклассной работы, С. А. Генкин, И. В. Итенберг, Киров, 1994г 4. Математика (Дополнительные главы). Е. В. Смыкалова Санкт- Петербург СМИО Пресс 2006   5. Математическая смекалка, Е. И. Игнатьев, Москва 1994г 6. Сборник олимпиадных задач по математике, В. Г. Горбачев, 2004г 7. Физико-математический журнал «Квант», А. Савин, №6 1994г. Интернет-ресурсы

№ слайда 100 http://liubavyshka.ru/photo/64 - книга http://liubavyshka.ru/photo/58 - возду
Описание слайда:

http://liubavyshka.ru/photo/64 - книга http://liubavyshka.ru/photo/58 - воздушные шарики http://liubavyshka.ru/photo/88 - смайлик http://4put.ru/view-max-picture.php?id=508730 - сова http://kzd.rzd.ru/photogal/public/ru?STRUCTURE_ID=4068& - схема железной дороги http://www.nastol.com.ua/railroad/92546-vl8-yelektrovoz-poezd-passazhirskij-sostav-putya-skorost.html - поезд http://samolety.org/airbus-a319-rossiya/ - самолет http://www.astrogalaxy.ru/skymap_sever.html - карта звездного неба http://sernam.ru/book_e_math.php?id=33 – графы в строительстве http://nenuda.ru/nuda/193/192325/192325_html_m13cbe7e.jpg - генеалогическое дерево Л.Н.Толстого 11.http://s.properm.ru/localStorage/collection/48/5d/67/d0/485d67d0_resizedScaled_659to416.jpg - схема улиц Интернет-ресурсы


Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Краткое описание документа:

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

Задачи: 1.Познакомить с историей возникновения графов. 2.Формировать умения решать задания с помощью графов.

Проект состоит из основных разделов (содержание): теория графов, применение графов, графы игр. Для проверки знаний по теме имеются следующие разделы: задачи, тест «Проверь себя», игра «Что? Где? Как?». Для снятия напряжения с глаз есть физминутка.

Автор
Дата добавления 17.08.2015
Раздел Математика
Подраздел Презентации
Просмотров1118
Номер материала ДA-006746
Получить свидетельство о публикации
Похожие материалы

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