Презентация по вероятности для 7 класса «Графы. Вершины. Ребра».

• 1 слайд

  Графы. Вершина. Ребро. Представление задачи с помощью графов.
  

• 2 слайд

  Леонард Эйлер (1707г – 1783гг)
  Швейцарский, прусский и российский математик, внесший огромный вклад в развитие математики, физики, оптики, механики, астрономии и ряда прикладных наук. Член нескольких академий наук по всему миру.
  За всю свою жизнь он издал более 850 трудов, в которых содержатся глубокие исследования ботаники, химии, медицины, древних языков. Имел членство во многих Академиях наук по всему миру.
  В 1727 году Эйлер поступил в адъюнктуру высшей математики петербургской академии наук. Российские власти поселили его в квартире и назначили жалованье в размере трехсот рублей в год. Потребовалось изучение русского языка, с чем математик справился в самый короткий срок. Научная деятельность Эйлера в Санкт-Петербурге была направлена на глубокое изучение механики, архитектуры и теории музыки. Здесь он опубликовал порядка 470 трудов в самых разнообразных областях.
  

• 3 слайд

  Через старый город Кёнигсберг протекает река Преголя. Она делится на два рукава, огибает остров и имеет семь мостов.
  

• 4 слайд

• 5 слайд

  Современный Калининград.
  

• 6 слайд

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

• 7 слайд

  В 1736 году в одном из своих писем он сформулировал и предложил
  решение задачи о семи кёнигсбергских мостах,
  ставшей впоследствии одной из классических задач теории графов.
  Для решения задачи Эйлер сделал специальные обозначения: каждую часть суши (остров или берег реки) он обозначил кружком на бумаге, а затем соединил линиями те кружки, между которыми существуют мосты. Такие обозначения подчеркнули, что в этой задаче фактическое расположение, форма, длина и другие свойства объектов не представляют интереса, важны только связи между ними.
  

• 8 слайд

  Размышляя над этой и другими картинками из кружков и линий, Эйлер пришёл к следующим выводам о графах:
  Число нечётных вершин ( вершин, к которым ведёт нечётное число рёбер) графа должно всегда быть чётно. 
  Если все вершины графа чётные, то его можно начертить не отрывая карандаша от бумаги, при этом начинать можно с любой вершины графа и завершить его в ней же. 
  Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком. 
  Так было доказано, что задача о кёнигсбергских мостах не имеет решения. 
  
  

• 9 слайд

  Что такое граф
  Графом называется конечное множество точек, некоторые из которых соединены линиями.
  Точки называются вершинами графа, а соединяющие линии – рёбрами.
  (Каждое ребро соединяет ровно две вершины).
  Рёбра графа
  Вершины графа
  

• 10 слайд

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

• 11 слайд

  Нулевой граф
  Граф, состоящий из «изолированных» вершин, называется нулевым графом
  

• 12 слайд

  Пример нулевого графа
  Амазо́нка (исп. и португ. Amazonas), река в Южной Америке, величайшая река на Земле, самая большая по длине, площади бассейна и водоносности.
  
  Ширина реки Амазонка зависит от времени года и сезона. В более дождливый период ширина ее дельты может быть более 300 километров. Максимальный показатель ширины дельты был зафиксирован на уровне 325 километров. Ширина же русла реки в такой период составляет около 40 километров, и покрывает территорию площадью 350 тысяч квадратных километров. В период засухи, ширина Амазонки сокращается до 10-11 километров, в верхнем течении от 2 до 5 км.
  На Амазонке нет ни одного моста между населенными пунктами и островами.
  

• 13 слайд

• 14 слайд

  Неполный граф
  Графы, в которых не построены все возможные ребра, называются неполными графами.
  

• 15 слайд

  Пример неполного графа
  Пример неполного графа — железнодорожная сеть, в которой несколько точек напрямую друг с другом не соединены, но к ним можно добраться через другие точки
  

• 16 слайд

  Пример неполного графа
  Этот мост на самой окраине Калининграда называют Берлинским, хотя настоящее его название – Пальмбургский. Разведенные крылья моста до сих пор пугают несведущих автомобилистов.
  
  Разведенный мост по-прежнему возвышается над рекой Преголей, став загадкой и памятником эпохи.
  

• 17 слайд

  Примеры полных графов
  .
  

• 18 слайд

  Изображение графа
  Один и тот же граф может выглядеть на
  рисунках по-разному. На рисунке(а, б, в) изображен один и тот же граф.
  

• 19 слайд

  Не следует путать изображение графа с собственно графом (абстрактной структурой), поскольку одному графу можно сопоставить не одно графическое представление. Изображение призвано лишь показать, какие пары вершин соединены рёбрами, а какие — нет.
  Запомнить!
  Задание . Построить полный граф для 5 вершин.
  

• 20 слайд

  В графе 5 вершин, каждая из которых имеет степень 4. Нарисуем такой граф.
  

• 21 слайд

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

• 22 слайд

  Заметим, что если полный граф имеет n вершин, то количество ребер равно
  Задание . Существует ли полный граф с семью ребрами?
  Решение: Зная количество ребер, узнаем количество вершин.
  n(n-1)/2=7.
  n(n-1)=14.
  Заметим, что n и (n-1) – это два последовательных натуральных числа. Число 14 нельзя представить
  в виде произведения двух последовательных натуральных чисел, значит, данное уравнение не имеет решений. Следовательно, такого графа
  не существует.
  ОТВЕТ
  

• 23 слайд

  Задание. Определить изображают ли фигуры на рисунке один и тот же граф или нет.
  1)
  2)
  3)
  ОТВЕТ
  Рисунок 1 и рисунок 2 являются изображениями одного графа. Рисунок 3 изображением
  другого графа
  

• 24 слайд

  Задача
  Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
  

• 25 слайд

  Решение:
  А
  Г
  В
  Б
  Д
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  Ответ: 10.
  

• 26 слайд

  Задача
  По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвовали 4 человека?
  1
  2
  3
  4
  Ответ: 12.
  

• 27 слайд

  
  
  
  В стране Всезнайка, есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены дорогой в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3.
  
  
  Домашнее задание.
  Задача 1
  Задача 2
  Построить полный граф, если известно что он содержит в себе 7 вершин.