ПРезентация "Графы", 5-6 класс

• 1 слайд

  
  
  
  
  Занятие кружка по математике
  
  «Мосты Эйлера».
  Теория графов. Мосты Кёнигсберга.
  
  
  

• 2 слайд

• 3 слайд

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

• 4 слайд

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

• 5 слайд

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

• 6 слайд

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

• 7 слайд

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

• 8 слайд

  Признаки вычерчивания фигур одним росчерком:
  если нечетных точек в фигуре нет, то ее можно начертить одним росчерком, начиная вычерчивать с любого места;
  
  если в фигуре две нечетные точки (если фигура имеет нечетную точку, то она всегда имеет и вторую нечетную точку), то ее можно начертить одним росчерком, начав вычерчивание в одной из нечетных точек и закончив в другой;
  
  если в фигуре более двух нечетных точек, то ее нельзя вычертить одним росчерком.
  
  
  

• 9 слайд

  Попробуй начертить самостоятельно
  Давай
  проверим!
  

• 10 слайд

  Определите, какие из фигур можно начертить не отрывая карандаш от бумаги
  (и не проводя по одной линии дважды).
  признаки вычерчивания
  задачи
  физминутка
  

• 11 слайд

• 12 слайд

• 13 слайд

• 14 слайд

• 15 слайд

• 16 слайд

• 17 слайд

• 18 слайд

  История о Кенигсбергских мостах
  
  Бывший Кенигсберг Возникший в XIII веке (ныне Калининград) расположен на реке Прегель, делящей город на четыре главные части: Альтштадт, Кнайпхоф, Ломзе и Форштадт. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены.
  

• 19 слайд

  
  
  К концу 19 века в Кёнигсберге было построено 7 основных мостов. Примерно в эти же годы составлена классическая задача о семи мостах Кёнигсберга. Надо было пройти по всем городским мостам не проходя по одному из них дважды.
  

• 20 слайд

  Схема мостов Кёнигсберга
  

• 21 слайд

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

• 22 слайд

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

• 23 слайд

  Преподаватель Кёнигсбергского университета "Альбертина" Леонард Эйлер решил задачу, составленную Кантом.
  
  

• 24 слайд

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

• 25 слайд

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

• 26 слайд

  В Кенигсберге река, омывающая два острова, делится на два рукава, через которые перекинуто семь мостов. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?
  № 1
  

• 27 слайд

  
  Составим схему к решению задачи
  Из рисунка видно, что у полученной фигуры четыре нечетные вершины, следовательно, ее нельзя построить, не пройдя по одной линии дважды,
  а значит, нельзя пройти по мостам так, чтобы не пройти по одному и тому же два раза.
  А
  В
  С
  D
  Решение.
  

• 28 слайд

  Через реку, омывающую три острова, перекинуто 9 мостов. Можно ли обойти все эти мосты, гоняясь за зайцем, не побывав ни на одном из них более одного раза?
  А
  В
  С
  D
  E
  № 2
  

• 29 слайд

  
  Составим схему к решению задачи
  Из рисунка видно, что у полученной фигуры две нечетные вершины, следовательно, ее можно построить, не отрывая карандаша от бумаги, а значит, можно пройти по мостам, не пройдя по одному и тому же два раза, начиная, например, с одного из мостов островка Е.
  А
  В
  E
  D
  С
  Решение.
  А
  В
  Е
  С
  D
  

• 30 слайд

  Выводы:
  ЕСЛИ все вершины – четные, то его можно начертить «одним росчерком», начиная с любой вершины.
  ЕСЛИ 2 вершины – нечетные, то его нужно начать с одной из нечетных вершин.
  Обход невозможен, если нечетных вершин больше 2.
  

• 31 слайд

  
  Но история о семи мостах Кёнигсберга имеет свое продолжение:
  
  В 1905 году в Кенигсберге был поострен еще один мост. (Слайд 30) История кайзера Вильгельма: Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. К всеобщему удивлению, кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали — мост кайзера. А задачу с восемью мостами теперь мог решить даже ребёнок.
  
  

• 32 слайд

  
  Был построен в 1905 году по приказу канцлера Вильгельма.
  Своему появлению он обязан самой задачи Эйлера.
  ИМПЕРАТОРСКИЙ мост(Kaiser-brucke).
  

• 33 слайд

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

• 34 слайд

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

• 35 слайд

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

• 36 слайд

  
  Задача №2
  
  В школьный компьютерный класс завезли 5 компьютеров, которые требуется связать локальной сетью. Известны расстояния между компьютерами. Требуется связать компьютеры таким образом, чтобы общая длина кабеля была бы наименьшей.
  
  

• 37 слайд

  В таблице приведены данные о расстояниях между компьютерами.
  

• 38 слайд

  Граф будет иметь следующий вид:
  1
  5
  3
  2
  4
  

• 39 слайд

  Задача 3
  Мальчики 10 б класса Андрей, Витя, Сережа, Валера, Дима при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
  Решение:
  Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки - имена. Если подсчитать число рёбер графа, изображённого на рисунке, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.
  
  
  

• 40 слайд

  Задача 4
  Дан кусок проволоки, длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?
  Решение:
  Если куб – граф, тогда он имеет более двух нечетных вершин (8). Значит, невозможно изготовить такой каркас, не ломая проволоки.
  

• 41 слайд

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