ВИС "Граф. Решение логических задач с помощью графа"
презентация к уроку по алгебре (7 класс)
ВИС "Граф. Решение логических задач с помощью графа"
Скачать:
Вложение | Размер |
---|---|
![]() | 1.01 МБ |
Предварительный просмотр:
Подписи к слайдам:
С дворянским титулом «граф» тему моей работы связывает только общее происхождение от латинского слова « графио » - пишу. Г Р А Ф И О Граф???
Графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки. Каждая пара точек в графе может быть соединена линиями . Линия указывает на связь между двумя точками . Основные понятия
Точки называются вершинами графа , а линиями рёбрами . Ребро может иметь направление, которое указывается стрелочкой. У графа обязательно есть вершины . Граф без рёбер называется пустым . Основные понятия
Направленная линия (со стрелкой) называется дуга . Линия ненаправленная (без стрелки) называется ребро . Линия , выходящая из некоторой вершины и входящая в неё же, называется петля . дуга ребро петля А В С А,В,С – вершины графа Основные понятия
Степень вершины графа - э то количество ребер, выходящих из данной вершины A B C D Степень A – 1 Степень B – 3 Степень C – 2 Степень D – 2 Основные понятия
Количество рёбер графа – равно сумме степеней всех его вершин, делённой на 2. A B C D E F (1+3+2+3+2+1) :2=6 Основные понятия
Неориентированный граф На схеме представлены дружеские связи в компании. Отношения являются двухсторонним, поэтому вершины соединены линиями без стрелок. Маша Юра Коля Витя Аня Граф называется неориентированным , если его вершины соединены ребрами . Какие бывают графы?
Ориентированный граф Маша Юра Коля Витя Аня Ориентированный граф - граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений. На рисунке представлена схема переписки Какие бывают графы?
Связные и несвязные графы Связный граф можно нарисовать не отрывая карандаша от бумаги Какие бывают графы?
Полный граф Граф называется полным , если каждая вершина связана со всеми другими вершинами графа. Если полный граф имеет n вершин , то количество ребер будет равно Какие бывают графы?
Дерево Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель. компьютер суперкомпьютер рабочая станция персональный компьютер настольный портативный карманный Какие бывают графы?
Коля Маша Юра Витя Аня Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза. Цикл – цепь, начальная и конечная вершины которой совпадают. Граф с циклом называют сетью Сеть Какие бывают графы?
Л . Эйлер ( 1707-1782), российский математик , швейцарец по происхождению, академик Петербургской и Берлинской академии наук) Г . Кирхгоф ( 1824-1871), иностранный член-корреспондент Петербургской академии наук разработал теорию деревьев) 14 Основоположники теории графов.
В 1736 году Эйлер нашел решение головоломки, носящей название «проблема Кёнигсбергских мостов». 15 Проблема Кёнигсбергских мостов
Задача , для решения которой Эйлер впервые применил графы, - это задача о мостах Кенигсберга. В XVIII веке город Кенигсберг (сейчас Калининград ) был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами. Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз? Задача Эйлера
План города Эйлер заменил его упрощенной схемой, на которой части города изображены точками (вершинами), а мосты - линиями (ребрами). Задача Эйлера
Получился следующий граф: Задача Эйлера
В итоге Эйлер доказал общее утверждение: для того чтобы обойти все рёбра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнения следующих двух условий: 1. из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (граф должен быть связным ); 2. из каждой вершины должно выходить чётное количество рёбер. Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечётное количество рёбер. В этом случае начинать движение следует с одной из этих двух вершин, а заканчивать - в другой. Задача Эйлера
Граф кёнигсбергских мостов имел четыре нечётные вершины , следовательно невозможно пройти по всем мостам , не проходя ни по одному из них дважды . Решение задачи о Кёнигсбергских мостах
Графы в современном мире
Медицина Кибернетика Информатика Химия Физика Транспорт Строительство Прикладная математика Экономика Науки, опирающиеся на знание теории графов:
В государстве 100 городов, а из каждого города выходит 4 дороги. Сколько всего дорог в государстве? Решение логических задач с помощью графов № 1 Решение: Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2 . (100 ∙ 4) : 2 = 200 .
Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог? Нет, не может, так как если X- число городов Решение: Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2 . Решение логических задач с помощью графов № 2
Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? Решение логических задач с помощью графов № 3
Решение: Пусть каждому из молодых людей соответствует точка на плоскости, а произведенные рукопожатия – отрезок, который будет соединять точки. Количество ребер полного графа (5 ∙ 4) : 2=10 . Значит , было сделано 10 рукопожатий Решение логических задач с помощью графов
Алексей, Борис, Виталий и Геннадий – друзья. Один из них –врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель. Журналист написал статьи об Алексее и Геннадии. Тренер и журналист вместе с Борисом ходили в поход. Алексей и Борис были на приеме у врача. У кого какая профессия? Решение логических задач с помощью графов № 4
Изобразим все данные условия на рисунке с помощью графов и ответ станет очевидным Алексей Борис Геннадий Виталий строитель тренер журналист врач Решение логических задач с помощью графов Алексей, Борис, Виталий и Геннадий – друзья. Один из них –врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель. Журналист написал статьи об Алексее и Геннадии. Тренер и журналист вместе с Борисом ходили в поход. Алексей и Борис были на приеме у врача. У кого какая профессия?
Исторический факт С помощью графов можно определить, как фразы одного писателя или поэта отличаются от других. На язык деревьев переводятся трудноуловимые особенности стиля. На основании этих графов можно определить автора текста. Например, основная черта стихов А.С. Пушкина – ритмичность и лаконизм (краткость) выражений, а у М.Ю. Лермонтова поэзия более цветистая, фразы более длинные. Домашнее задание Теория графов и анализ художественного текста
По теме: методические разработки, презентации и конспекты
![](/sites/default/files/pictures/2011/11/01/picture-28999.jpg)
Решение логических задач при помощи таблиц
В презентации представлены разноуровневые задания. Слайды удобно использовать для решения задач на интерактивной доске....
![](/sites/default/files/pictures/2012/02/13/picture-59066.jpg)
Электронный образовательный ресурс по математике "Решение комбинаторных задач с помощью графов"
Электронный образовательный ресурс "Решение комбинаторных задач с помощью графов" предназначен для обучающихся 5 - 6 классов. Он может быть использован как пособие для дистанционного обучения по этой ...
Материал к уроку "Решение логических задач с помощью таблиц"
Содержит конспект урока, презентацию к уроку, карточки с заданиями, ребусы. Можно успользовать как в 6 классе по ФГОС, так и в 7 классе УМК Л.Л.Босова...
![](/sites/default/files/pictures/2014/04/20/picture-439615-1398008601.jpg)
Задачи по теме "Решение логических задач с помощью круго Эйлера"
Задания по теме "Решение логических задач с помощью круго Эйлера" могут быть использованы 6 классе при изучении темы "Отношения между понятиями" по программе Босовой Л.Л...
![](/sites/default/files/pictures/2022/11/02/picture-1432765-1667396329.jpg)
Решение логических задач с помощью графов.
Презентация по алгебре на тему "Решение логических задач с помощью графов". Урок открытия нового знания. К учебнику: «Алгебра» Углублённый уровень: 7 класс/ А.Г. М...