Решение логических задач с помощью графов.
презентация к уроку по алгебре (7 класс)

Слайд 1

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

Слайд 2

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

Слайд 3

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

Слайд 4

Точки называются вершинами графа , а линиями рёбрами . Ребро может иметь направление, которое указывается стрелочкой. У графа обязательно есть вершины . Граф без рёбер называется пустым . Основные понятия

Слайд 5

Направленная линия (со стрелкой) называется дуга . Линия ненаправленная (без стрелки) называется ребро . Линия , выходящая из некоторой вершины и входящая в неё же, называется петля . дуга ребро петля А В С А,В,С – вершины графа Основные понятия

Слайд 6

Степень вершины графа - э то количество ребер, выходящих из данной вершины A B C D Степень A – 1 Степень B – 3 Степень C – 2 Степень D – 2 Основные понятия

Слайд 7

Количество рёбер графа – равно сумме степеней всех его вершин, делённой на 2. A B C D E F (1+3+2+3+2+1) :2=6 Основные понятия

Слайд 8

Неориентированный граф На схеме представлены дружеские связи в компании. Отношения являются двухсторонним, поэтому вершины соединены линиями без стрелок. Маша Юра Коля Витя Аня Граф называется неориентированным , если его вершины соединены ребрами . Какие бывают графы?

Слайд 9

Ориентированный граф Маша Юра Коля Витя Аня Ориентированный граф - граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений. На рисунке представлена схема переписки Какие бывают графы?

Слайд 10

Связные и несвязные графы Связный граф можно нарисовать не отрывая карандаша от бумаги Какие бывают графы?

Слайд 11

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

Слайд 12

Дерево Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель. компьютер суперкомпьютер рабочая станция персональный компьютер настольный портативный карманный Какие бывают графы?

Слайд 13

Коля Маша Юра Витя Аня Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза. Цикл – цепь, начальная и конечная вершины которой совпадают. Граф с циклом называют сетью Сеть Какие бывают графы?

Слайд 14

Л . Эйлер ( 1707-1782), российский математик , швейцарец по происхождению, академик Петербургской и Берлинской академии наук) Г . Кирхгоф ( 1824-1871), иностранный член-корреспондент Петербургской академии наук разработал теорию деревьев) 14 Основоположники теории графов.

Слайд 15

В 1736 году Эйлер нашел решение головоломки, носящей название «проблема Кёнигсбергских мостов». 15 Проблема Кёнигсбергских мостов

Слайд 16

Задача , для решения которой Эйлер впервые применил графы, - это задача о мостах Кенигсберга. В XVIII веке город Кенигсберг (сейчас Калининград ) был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами. Можно ли совершить прогулку, пройдя по каждому мосту ровно один раз? Задача Эйлера

Слайд 17

План города Эйлер заменил его упрощенной схемой, на которой части города изображены точками (вершинами), а мосты - линиями (ребрами). Задача Эйлера

Слайд 18

Получился следующий граф: Задача Эйлера

Слайд 19

В итоге Эйлер доказал общее утверждение: для того чтобы обойти все рёбра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнения следующих двух условий: 1. из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (граф должен быть связным ); 2. из каждой вершины должно выходить чётное количество рёбер. Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечётное количество рёбер. В этом случае начинать движение следует с одной из этих двух вершин, а заканчивать - в другой. Задача Эйлера

Слайд 20

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

Слайд 21

Графы в современном мире

Слайд 22

Медицина Кибернетика Информатика Химия Физика Транспорт Строительство Прикладная математика Экономика Науки, опирающиеся на знание теории графов:

Слайд 23

В государстве 100 городов, а из каждого города выходит 4 дороги. Сколько всего дорог в государстве? Решение логических задач с помощью графов № 1 Решение: Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2 . (100 ∙ 4) : 2 = 200 .

Слайд 24

Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог? Нет, не может, так как если X- число городов Решение: Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2 . Решение логических задач с помощью графов № 2

Слайд 25

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

Слайд 26

Решение: Пусть каждому из молодых людей соответствует точка на плоскости, а произведенные рукопожатия – отрезок, который будет соединять точки. Количество ребер полного графа (5 ∙ 4) : 2=10 . Значит , было сделано 10 рукопожатий Решение логических задач с помощью графов

Слайд 27

Алексей, Борис, Виталий и Геннадий – друзья. Один из них –врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель. Журналист написал статьи об Алексее и Геннадие . Тренер и журналист вместе с Борисом ходили в поход. Алексей и Борис были на приеме у врача. У кого какая профессия? Решение логических задач с помощью графов № 4

Слайд 28

Изобразим все данные условия на рисунке с помощью графов и ответ станет очевидным Алексей Борис Геннадий Виталий строитель тренер журналист врач Решение логических задач с помощью графов Алексей, Борис, Виталий и Геннадий – друзья. Один из них –врач, другой – журналист, третий – тренер спортивной школы, четвертый – строитель. Журналист написал статьи об Алексее и Геннадии. Тренер и журналист вместе с Борисом ходили в поход. Алексей и Борис были на приеме у врача. У кого какая профессия?

Слайд 29

Исторический факт С помощью графов можно определить, как фразы одного писателя или поэта отличаются от других. На язык деревьев переводятся трудноуловимые особенности стиля. На основании этих графов можно определить автора текста. Например, основная черта стихов А.С. Пушкина – ритмичность и лаконизм (краткость) выражений, а у М.Ю. Лермонтова поэзия более цветистая, фразы более длинные. Домашнее задание § 4, № 3.24, 3.26, 4.3. Теория графов и анализ художественного текста