Урок по математике на тему "Теория графов"

• 1 слайд

  Дата проведения занятия

• 2 слайд

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

• 3 слайд

  Знакомство с теорией графов Цель урока: получить первичные сведения о графах, научиться решать логические задачи с помощью графов. ВПЕРВЫЕ ПОНЯТИЕ «ГРАФ» ВВЕЛ В 1936 г. ВЕНГЕРСКИЙ МАТЕМАТИК ДЕННИ КЁНИГ. НО ПЕРВАЯ РАБОТА ПО ТЕОРИИ ГРАФОВ ПРИНАДЛЕЖАЛА ПЕРУ ВЕЛИКОГО ЛЕОНАРДА ЭЙЛЕРА И БЫЛА НАПИСАНА ЕЩЕ В 1736 г.

• 4 слайд

  Основные понятия Граф – это средство для наглядного представления состава и структуры системы ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ НЕКОТОРЫЕ ПАРЫ ТОЧЕК. ТОЧКИ НАЗЫВАЮТСЯ ВЕРШИНАМИ, ИЛИ УЗЛАМИ, ГРАФА, ЛИНИИ – РЕБРАМИ ГРАФА. Граф , в котором все линии направленные, называется ориентированным

• 5 слайд

• 6 слайд

  Интерпретация задачи в виде графа: Изобразить данный граф одним росчерком пера

• 7 слайд

  Степень вершины Степень вершины = количеству ребер, исходящих из этой вершины

• 8 слайд

  В ГРАФЕ G(V, X) СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ ЧИСЛУ РЕБЕР ГРАФА: ВЕРШИНА НАЗЫВАЕТСЯ ЧЕТНОЙ (НЕЧЕТНОЙ), ЕСЛИ ЕЕ СТЕПЕНЬ – ЧЕТНОЕ(НЕЧЕТНОЕ) ЧИСЛО. ЧИСЛО НЕЧЕТНЫХ ВЕРШИН ЛЮБОГО ГРАФА – ЧЕТНО. НЕВОЗМОЖНО НАЧЕРТИТЬ ГРАФ С НЕЧЕТНЫМ ЧИСЛОМ НЕЧЕТНЫХ ВЕРШИН.

• 9 слайд

  Степень вершины Закономерность 1: Если все вершины графа четные, то его можно изобразить «одним росчерком пера».

• 10 слайд

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

• 11 слайд

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

• 12 слайд

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

• 13 слайд

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

• 14 слайд

  Интерпретация задачи в виде графа: Укажите номер комнаты с ключом

• 15 слайд

  Решение задачи о ключе: 1. Посчитать степень каждой вершины графа 2. Начать движение из нечетной вершины

• 16 слайд

  Задача о составе экспедиции:

• 17 слайд

  Анализ графовой модели биолог врач синоптик гидролог механик радист A B C D E F G H

• 18 слайд

  Анализ графовой модели биолог врач синоптик гидролог механик радист A B C D E F G H

• 19 слайд

  ИНФОРМАЦИОННЫЕ МОДЕЛИ НА ГРАФАХ

• 20 слайд

  Применение графов в жизни Вершинами графа являются станции метро, линии отражают рельсовую связь между станциями.

• 21 слайд

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

• 22 слайд

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

• 23 слайд

  Применение графов в жизни Устройство шариковой ручки

• 24 слайд

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

• 25 слайд

  Взвешенный граф

• 26 слайд

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

• 27 слайд

  Дерево Рюрик (879) Игорь ( 945) Святослав (972) Ярополк (980) Владимир Св (1014) Олег (977) Изяслав Полоцкий(1001) Святополк (1018) Борис (1015) Ярослав (1054) Глеб (1015) ПРЕДОК ПОТОМКИ КОРЕНЬ

• 28 слайд

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

• 29 слайд

  Дерево Рюрик (879) Игорь ( 945) Святослав (972) Ярополк (980) Владимир Св (1014) Олег (977) Изяслав Полоцкий(1001) Святополк (1018) Борис (1015) Ярослав (1054) Глеб (1015) Восстановить всех предков Бориса.

• 30 слайд

  Дерево География: население и народное хозяйство России Введение Часть1. Общий обзор России Россия на карте мира Заселение территории Сфера влияния России Экономическое влияние России Человек и природа Природные условия и человек Часть 2. Районы России Подходы к районированию Заключение Иерархическая структура разделов книги

• 31 слайд

  Отразите в виде графа структуру следующего объекта, рассматривая его как систему: Плоские фигуры, круг, эллипс, трапеция, параллелограмм, прямоугольник, ромб, квадрат Плоская фигура Круг Эллипс Трапеция Параллелограмм Прямоугольник Ромб Квадрат

• 32 слайд

  На рисунке приведена схема организации танкового батальона ФРГ, по состоянию на середину 70х годов 20 века. Ромбиками обозначены танки, входящие, в то или иное подразделение. Подсчитайте количество танков в танковой роте и общее количество танков в батальоне.

• 33 слайд

  Творческое домашнее задание А) Представьте в виде графа свою родословную по отцовской линии Б) Представьте в виде графа свою родословную по материнской линии линии

• 34 слайд

  Анализ запутанных ситуаций Графы хорошо помогают анализировать запутанные ситуации. Пример№1 Боксёры с твёрдою походкой Не моют пол зубною щёткой. Кто моет пол зубною щёткой, Тот наделён душою кроткой. Кто пол мыть щёткой не желает, Суровым нравом обладает. Суровый нрав у тех бывает, Кто книжек вовсе не читает. Фосс враг и книжек и газет, Ответь, боксёр он или нет?

• 35 слайд

  Анализ запутанных ситуаций Для описания ситуации используем ряд утверждений и используем граф. Боксёр Не моет пол зубною щёткой Моет пол зубною щёткой Имеет кроткую душу Имеет суровый нрав Не читает книг Твёрдою походкой

• 36 слайд

  Анализ запутанных ситуаций Пример2 Широкоплечие мужчины Поют, садясь за руль машины. Мужчины с узкими плечами, Садясь за руль молчат как камень. Те, кто за руль садятся с пеньем, Не отличаются терпеньем. Те кто в машине молчаливы, Бывают очень терпеливы. Терпенье тем дано с избытком. Кто чинит домики улиткам. Чтоб домик починить улитке, Клей варят на электроплитке. Фосс не выносит запах клея, Он сразу падает, бледнея. Прошу ответить на вопрос: Широкоплеч ли мистер Фосс?

• 37 слайд

  Анализ запутанных ситуаций Широкоплечие мужчины поют поют Не отличаются терпеньем Терпеливы Чинит домики улиткам Клей варят на эл.плитках

• 38 слайд

  ДОМАШНЕЕ ЗАДАНИЕ Хвост Барбоса: Собаки с рыжими хвостами Себе овсянку варят сами. Тем, чьи хвосты стального цвета, Не позволяют делать это. Кто варит себе овсянку, Гулять выходит спозаранку. Все, кто гулять выходит рано, Не терпят фальши и обмана. Вид добродушный у Барбоса, Но на сорок он смотрит косо.. Он видит: норовят сороки У воробьёв списать уроки! Скажите – проще нет вопроса! Какого цвета хвост Барбоса? Построить граф, найти ответ на вопрос.

• 39 слайд

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

• 40 слайд

  Смысловая структура фраз Определим структуру фразы «С утра на улице шёл тёплый грибной дождь» с утра шёл на улице дождь тёплый грибной Какой? Какой? Когда? Где? Кто?\Что? Что делал? Если в вершинах графа заменить члены на другие родственные слова, то снова может получится осмысленная фраза.

• 41 слайд

  «В 5 утра по перрону прошёл скорый проходящий поезд» Смысловая структура фраз

• 42 слайд

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

• 43 слайд

  Смысловая структура фраз Представьте в виде графа связи в следующих предложениях: «Однажды в студеную зимнюю пору я из лесу вышел». Однажды в пору вышел из лесу я студёную зимнюю Какую? Какую? Когда? Откуда? Кто?\Что? Что делал?

• 44 слайд

  Смысловая структура фраз Представьте в виде графа связи в следующих предложениях: «Четыре чёрненьких чумазеньких чертёнка чертили чёрными чернилами чертёж черепа человека чрезвычайно чётко на чердаке в четверг.

• 45 слайд

  Смысловая структура фраз чертёнка чертили четыре чёрных чрезвычайно чётко чернилами на чердаке в четверг чертёж черепа человека Кто? Что делали? Что? Чего? Кого? Как? Как? Чем? Когда? Где? Сколько? Каких?

• 46 слайд

  ДОМАШНЕЕ ЗАДАНИЕ Представьте в виде графа связи в следующих предложениях придуманных Г. Остером: А) Мряка друсит пусики и на друську одного прусика тратит полдолготика. Б) Мряка 7 раз фрякнула Бряку марфуфочкой по чему попало, а Бряка фрякнула Мряку той же марфуфочкой по чему попало 9 раз.

• 47 слайд

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

• 48 слайд

  Смысл математических выражений 5*(3+7)*(8-2) дерево будет иметь вид Последовательность операций определяется от листьев к корню. листья корень

• 49 слайд

  Смысл математических выражений (4+2) (6+5) (12\(4+2)) (6+5)-(12\(4+2)) Дан граф. Запишите арифметическое выражение.

• 50 слайд

  МОДЕЛИ на двудольных графах

• 51 слайд

  Модели на двудольных графах Двудольный граф – разновидность семантической сети, в которой каждая связь может объединять не два, а большее число объектов. Вершины Чёрные (ставятся в соответствие объекты (понятия) Белые (ставятся в соответствие связи между объектами) Любая дуга на таком графе проходит между ДВУМЯ вершинами РАЗНЫХ цветов.

• 52 слайд

  Пример В форме двудольного графа требуется представить модель знаний о геометрическом объекте – ромбе. Ромб имеет 7 характеристик: длину сторона а, острый угол , тупой угол , площадь S, периметр P, диагонали d1 и d2 . Эти величины связаны формулами:

• 53 слайд

  Пример Тогда наш двудольный граф будет иметь семь ЧЁРНЫХ вершин (объекты а, , , S, P, d1 , d2) и ПЯТЬ белых вершин (формулы)

• 54 слайд

  Пример

• 55 слайд

  Домашнее задание Любой треугольник характеризуется следующими величинами : длины сторон a,b,c; углы ,, противолежащие сторонам; площадью S; периметром P, полупериметром p и связями между ними: 1)сумма углов треугольника равена 180 градусам; 2)периметр равен сумме всех его сторон; 3)Полупериметр равен половине периметра; 4)Площадь треугольника находится по формуле Герона; 5)Площадь треугольника равна половине произведения двух сторон на синус угла между ними. (через все углы) Постройте модель знаний о треугольнике в виде двудольного графа.

• 56 слайд

  Спасибо за внимание и работу!