Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему по математике на тему Графы

Содержание

ВведениеС дворянским титулом «граф» тему моей работы связывает только общее происхождение от латинского слова «графио» - пишу.ГРАФИОдальше
ЕГО ВЕЛИЧЕСТВО ГРАФ ВведениеС дворянским титулом «граф» тему моей работы связывает только общее происхождение от Что такое графСлово «граф» в математике означает картинку, где нарисовано несколько точек, Что такое графВ математике определение графа дается так:Графом называется конечное множество точек, Что такое графКоличество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина История возникновения графовТермин История возникновения графовОсновы теории графов как математической науки заложил в 1736 г. Задача о Кенигсбергских мостахБывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В Задача о Кенигсбергских мостахКенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам дальшеЯ здесь уже был! Задача о Кенигсбергских мостахПройти по Кенигсбергским мостам, соблюдая заданные условия, нельзя. Прохождение Задача о Кенигсбергских мостахНо, поскольку граф на этом рисунке имеет четыре нечетные Одним росчеркомГраф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Одним росчеркомЕсли все вершины графа четные, то можно не отрывая карандаш от Одним росчеркомГраф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш Одним росчеркомГраф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».  ?содержание Применение графовЛабиринт - это граф. А исследовать его - это найти путь в этом графе. дальше Первый многосвязный садовый лабиринт был сооружён в 1820-е годы в Чевнинге в Великобритании. Граф для садового лабиринта ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ ЕГО ВЕРШИНУ ТОЛЬКО ОДИН В 1857 году ирландский математик Гамильтон предложил игру, названную «Путешествием по додекаэдру». ЗадачаАВСКЕDPF ВыводыГрафы – это замечательные математические объекты, с помощью, которых можно решать математические, ТЕОРЕМАВ ГРАФЕ СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ЦИКЛ – ПУТЬ, У КОТОРОГО СОВПАДАЮТ НАЧАЛО И КОНЕЦ. G, H, E, B, A - ВИСЯЧИЕ ВЕРШИНЫДеревом называется связный граф, не имеющий циклов Применение графовИспользует графы и дворянство.На рисунке приведена часть генеалогического дерева знаменитого дворянского Перечислить все возможные варианты обедов из трех блюд (одного первого, одного второго Задача №2. У Аси есть любимый костюм, в котором она ходит в Применение графовЗадача:Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый Применение графовРешение:АГВБД12345678910дальше Задача 2. По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил Логические задачи Известно, что в настоящий момент: Ваня сыграл шесть партий;Толя сыграл пять Число в скобках называют степенью вершины, оно показывает сколько ребер выходит из Начать построение ребер следует с вершины В, так как это единственная вершина, Для вершин В и Ж построены все возможные ребраВаня (6)Толя (5)Леша (3)Дима Теперь однозначно определяются ребра  вершины Т.С учетом ребра ВТ надо построить Все возможные ребра теперь построены для вершин   Ж, В, Т, ОТВЕТ:  Леша играл с Толей, Ваней и ДимойВаня (6)Толя (5)Леша (3)Дима В одном дворе живут четыре друга. Вадим и шофер старше Сергея,Николай и ВадимКоляСергейАндрейслесарьтокарьэлектрикшоферНачинаем анализировать полученную схему.От каждого верхнего кружка должно исходить 4 линии к Андрей, Борис, Володя, Даша, Галя договорились созвониться по телефону о посещении кино. Спасибо за внимание
Слайды презентации

Слайд 2 Введение
С дворянским титулом «граф» тему моей работы связывает

ВведениеС дворянским титулом «граф» тему моей работы связывает только общее происхождение

только общее происхождение от латинского слова «графио» - пишу.
Г
Р
А
Ф
И
О
дальше


Слайд 3 Что такое граф
Слово «граф» в математике означает картинку,

Что такое графСлово «граф» в математике означает картинку, где нарисовано несколько

где нарисовано несколько точек, некоторые из которых соединены линиями.

В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними отрезками или дугами.

Дальше


Слайд 4 Что такое граф
В математике определение графа дается так:
Графом

Что такое графВ математике определение графа дается так:Графом называется конечное множество

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

называются вершинами графа, а соединяющие линии – рёбрами.

Рёбра графа

Вершина графа

Дальше


Слайд 5 Что такое граф
Количество рёбер, выходящих из вершины графа,

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

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

нечетной, а чётную степень – чётной.

Нечётная степень

Чётная степень

содержание


Слайд 6 История возникновения графов
Термин "граф" впервые появился в книге

История возникновения графовТермин

венгерского математика Д. Кенига в 1936 г., хотя начальные

важнейшие теоремы о графах восходят к Л. Эйлеру.

Дальше


Слайд 7 История возникновения графов
Основы теории графов как математической науки

История возникновения графовОсновы теории графов как математической науки заложил в 1736

заложил в 1736 г. Леонард Эйлер, рассматривая задачу о

кенигсбергских мостах. Сегодня эта задача стала классической.

содержание


Слайд 8 Задача о Кенигсбергских мостах
Бывший Кенигсберг (ныне Калининград) расположен

Задача о Кенигсбергских мостахБывший Кенигсберг (ныне Калининград) расположен на реке Прегель.

на реке Прегель. В пределах города река омывает два

острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.

Дальше


Слайд 9 Задача о Кенигсбергских мостах
Кенигсбергцы предлагали приезжим следующую задачу:

Задача о Кенигсбергских мостахКенигсбергцы предлагали приезжим следующую задачу: пройти по всем

пройти по всем мостам и вернуться в начальный пункт,

причём на каждом мосту следовало побывать только один раз.

Дальше


Слайд 10 дальше
Я здесь уже был!

дальшеЯ здесь уже был!

Слайд 11 Задача о Кенигсбергских мостах
Пройти по Кенигсбергским мостам, соблюдая

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

заданные условия, нельзя. Прохождение по всем мостам при условии,

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

дальше


Слайд 12 Задача о Кенигсбергских мостах
Но, поскольку граф на этом

Задача о Кенигсбергских мостахНо, поскольку граф на этом рисунке имеет четыре

рисунке имеет четыре нечетные вершины, то такой граф начертить

«одним росчерком» невозможно.

содержание


Слайд 13 Одним росчерком
Граф, который можно нарисовать, не отрывая карандаша

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

от бумаги, называется эйлеровым.
Решая задачу О кенигсбергских мостах,

Эйлер сформулировал свойства графа:
Невозможно начертить граф с нечетным числом нечетных вершин.

дальше


Слайд 14 Одним росчерком
Если все вершины графа четные, то можно

Одним росчеркомЕсли все вершины графа четные, то можно не отрывая карандаш

не отрывая карандаш от бумаги («одним росчерком»), проводя по

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

дальше


Слайд 15 Одним росчерком
Граф, имеющий всего две нечетные вершины, можно

Одним росчеркомГраф, имеющий всего две нечетные вершины, можно начертить, не отрывая

начертить, не отрывая карандаш от бумаги, при этом движение

нужно начать с одной из этих нечетных вершин и закончить во второй из них.

дальше


Слайд 16 Одним росчерком
Граф, имеющий более двух нечетных вершин, невозможно

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

начертить «одним росчерком».
?
содержание


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

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

- это найти путь в этом графе.
дальше


Слайд 20 Первый многосвязный садовый лабиринт был сооружён в 1820-е

Первый многосвязный садовый лабиринт был сооружён в 1820-е годы в Чевнинге в Великобритании.

годы в Чевнинге в Великобритании.


Слайд 21 Граф для садового лабиринта

Граф для садового лабиринта

Слайд 22 ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ

ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ ЕГО ВЕРШИНУ ТОЛЬКО

ЕГО ВЕРШИНУ ТОЛЬКО ОДИН РАЗ.
ГРАФ, СОДЕРЖАЩИЙ ГАМИЛЬТОНОВ ЦИКЛ, НАЗЫВАЕТСЯ

ГАМИЛЬТОНОВЫМ.

A

B

C

D

E

(C, D, A, B, E) – гамильтонов путь


Слайд 23 В 1857 году ирландский математик Гамильтон предложил игру,

В 1857 году ирландский математик Гамильтон предложил игру, названную «Путешествием по

названную «Путешествием по додекаэдру». Игра сводилась к обходу по

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

Слайд 24 Задача
А
В
С
К
Е
D
P
F

ЗадачаАВСКЕDPF

Слайд 25 Выводы
Графы – это замечательные математические объекты, с помощью,

ВыводыГрафы – это замечательные математические объекты, с помощью, которых можно решать

которых можно решать математические, экономические и логические задачи. Также

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

содержание


Слайд 26 ТЕОРЕМА
В ГРАФЕ СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН –

ТЕОРЕМАВ ГРАФЕ СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО ЧЕТНОЕ, РАВНОЕ

ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ ЧИСЛУ РЕБЕР ГРАФА:
ТЕОРЕМА
ЧИСЛО НЕЧЕТНЫХ

ВЕРШИН ЛЮБОГО ГРАФА – ЧЕТНО.

СЛЕДСТВИЕ

ЧИСЛО ВЕРШИН МНОГОГРАННИКА, В КОТОРЫХ СХОДИТСЯ НЕЧЁТНОЕ ЧИСЛО РЁБЕР, ЧЁТНО.

Степень А +степень В + степень С +…= 2*число рёбер

НЕЧЁТНОЕ ЧИСЛО ЗНАКОМЫХ В ЛЮБОЙ КОМПАНИИ ВСЕГДА ЧЁТНО.


Слайд 27 ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ

ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ

ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ТОЛЬКО ОДНИМ РЕБРОМ.
ДОПОЛНЕНИЕМ ГРАФА НАЗЫВАЕТСЯ

ГРАФ С ТЕМИ ЖЕ ВЕРШИНАМИ И ИМЕЮЩИЙ ТЕ И ТОЛЬКО ТЕ РЕБРА, КОТОРЫЕ НЕОБХОДИМО ДОБАВИТЬ К ИСХОДНОМУ ГРАФУ, ЧТОБЫ ОН СТАЛ ПОЛНЫМ.

ДОПОЛНЕНИЕ ГРАФА ДО ГРАФА


Слайд 28 ЦИКЛ – ПУТЬ, У КОТОРОГО СОВПАДАЮТ НАЧАЛО И

ЦИКЛ – ПУТЬ, У КОТОРОГО СОВПАДАЮТ НАЧАЛО И КОНЕЦ.

КОНЕЦ.


Слайд 29 G, H, E, B, A - ВИСЯЧИЕ ВЕРШИНЫ
Деревом

G, H, E, B, A - ВИСЯЧИЕ ВЕРШИНЫДеревом называется связный граф, не имеющий циклов

называется связный граф, не имеющий циклов


Слайд 30 Применение графов
Использует графы и дворянство.
На рисунке приведена часть

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

генеалогического дерева знаменитого дворянского рода Л. Н. Толстого. Здесь

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

дальше


Слайд 31 Перечислить все возможные варианты обедов из трех блюд

Перечислить все возможные варианты обедов из трех блюд (одного первого, одного

(одного первого, одного второго и одного третьего блюда), если

в меню столовой имеются два первых блюда: щи (щ) и борщ (б); три вторых блюда: рыба (р), гуляш (г) и плов (n); два третьих: компот (к) и чай (ч).
Решение.

Слайд 32 Задача №2. У Аси есть любимый костюм, в

Задача №2. У Аси есть любимый костюм, в котором она ходит

котором она ходит в школу. Она надевает к нему

белую, голубую, розовую или красную блузку, а в качестве «сменки» берет босоножки или туфли. Кроме того, у Аси есть три разных бантика (№ 1, 2, 3), подходящих ко всем блузкам.
а) Нарисуйте дерево возможных вариантов Асиной одежды.

Задача №3. Группа туристов планирует осуществить поход по маршруту Антоново – Борисово – Власово – Грибово. Из Антонова в Борисово можно сплавиться по реке или дойти пешком. Из Борисова во Власово можно дойти пешком или доехать на велосипедах. Из Власова в Грибово можно доплыть по реке, доехать на велосипедах или дойти пешком.
а) Нарисуйте дерево возможных вариантов похода.
б) Сколько всего вариантов похода могут выбрать туристы?
в) Сколько есть полностью не пеших вариантов?


Слайд 33 Применение графов
Задача:
Аркадий, Борис. Владимир, Григорий и Дмитрий при

Применение графовЗадача:Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями

встрече обменялись рукопожатиями (каждый пожал руку каждому по одному

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

дальше


Слайд 34 Применение графов
Решение:
А
Г
В
Б
Д
1
2
3
4
5
6
7
8
9
10
дальше

Применение графовРешение:АГВБД12345678910дальше

Слайд 35 Задача 2. По окончании деловой встречи специалисты обменялись

Задача 2. По окончании деловой встречи специалисты обменялись визитными карточками (каждый

визитными карточками (каждый вручил свою карточку каждому). Сколько всего

визитных карточек было роздано, если во встрече участвовали: 1) 3 человека; 2) 4 человека; 3) 5 человек?

1) Во встрече участвовали 3 человека:

2) Во встрече участвовали 4 человека:

3) Во встрече участвовали 5 человек.


Слайд 36 Логические задачи

Логические задачи

Слайд 37 Известно, что в настоящий момент:
Ваня сыграл

Известно, что в настоящий момент: Ваня сыграл шесть партий;Толя сыграл

шесть партий;
Толя сыграл пять партий;
Леша и Дима сыграли по

три партии;
Семен и Илья сыграли по две партии;
Женя сыграл одну партию.

Условие задачи

Требуется определить:
с кем сыграл Леша.

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


Слайд 38 Число в скобках называют степенью вершины, оно показывает

Число в скобках называют степенью вершины, оно показывает сколько ребер выходит

сколько ребер выходит из данной вершины
Ваня (6)
Толя (5)
Леша (3)
Дима

(3)

Семен (2)

Илья (2)

Женя (1)

Изобразим участников турнира точками
Для каждой точки укажем ее имя
(по первой букве имени игрока)
и количество партий, сыгранные этим игроком


Слайд 39 Начать построение ребер следует с вершины В, так

Начать построение ребер следует с вершины В, так как это единственная

как это единственная вершина,
которая соединяется со всеми другими

вершинами графа

Ваня (6)

Толя (5)

Леша (3)

Дима (3)

Семен (2)

Илья (2)

Женя (1)

Будем строить ребра графа с учетом степеней вершин


Слайд 40 Для вершин В и Ж построены все возможные

Для вершин В и Ж построены все возможные ребраВаня (6)Толя (5)Леша

ребра
Ваня (6)
Толя (5)
Леша (3)
Дима (3)
Семен (2)
Илья (2)
Женя (1)
Сделаем первые

выводы:

Слайд 41 Теперь однозначно определяются ребра вершины Т.
С учетом

Теперь однозначно определяются ребра вершины Т.С учетом ребра ВТ надо построить

ребра ВТ надо построить четыре ребра
Ваня (6)
Толя (5)
Леша (3)
Дима

(3)

Семен (2)

Илья (2)

Женя (1)

Построим следующие ребра


Слайд 42 Все возможные ребра теперь построены для вершин

Все возможные ребра теперь построены для вершин  Ж, В, Т,

Ж, В, Т, а также для вершин С

и И

Ваня (6)

Толя (5)

Леша (3)

Дима (3)

Семен (2)

Илья (2)

Женя (1)

Пора делать новые выводы


Слайд 43 ОТВЕТ: Леша играл с Толей, Ваней и

ОТВЕТ: Леша играл с Толей, Ваней и ДимойВаня (6)Толя (5)Леша (3)Дима

Димой
Ваня (6)
Толя (5)
Леша (3)
Дима (3)
Семен (2)
Илья (2)
Женя (1)
Требовалось определить:

с кем сыграл Леша.

Граф к задаче построен


Слайд 44 В одном дворе живут четыре друга.
Вадим и

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

шофер старше Сергея,
Николай и слесарь занимаются боксом,
Электрик-младший из друзей.
По

вечерам Андрей и токарь играют в домино против Сергея и электрика.
Определите профессию каждого из друзей.

Условие задачи


Слайд 45 Вадим
Коля
Сергей
Андрей
слесарь
токарь
электрик
шофер
Начинаем анализировать полученную схему.
От каждого верхнего кружка должно

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

исходить 4 линии к кружкам нижнего ряда,одна из которых

сплошная(прочная связь) ,три-пунктирные. (разрывная связь). И от кружков нижнего ряда-аналогично.

От Сергея отходит 3 разрывные связи, значит, четвертая- прочная связь

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


Слайд 46 Андрей, Борис, Володя, Даша, Галя договорились созвониться по

Андрей, Борис, Володя, Даша, Галя договорились созвониться по телефону о посещении

телефону о посещении кино. Вечером у кинотеатра собрались не

все. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша – Андрею и Володе, а Галя – Андрею, Володе и Борису. Кто не пришёл в кино, если все они условились, что поход в кино состоится только в том случае, если созвонятся все?

Задача.


  • Имя файла: prezentatsiya-po-matematike-na-temu-grafy.pptx
  • Количество просмотров: 442
  • Количество скачиваний: 133