Презентация на тему "Графы и их применение"

Содержание

• 
  Слайд 1

  Графы и их применение(подготовка к ЕГЭ)

  Мастер – класс учитель Майсова Т.Б.

• 
  Слайд 2

  Некоторые основные понятия теории графов

  Граф – рисунок, состоящий из множества точек и множества отрезков, оба конца которых принадлежат заданному множеству точек. Степень вершины называется число ребер графа, которым принадлежит эта вершина. Путь графе от А1 до Аn в графе называется такая последовательность ребер, ведущая от А1 до Аn, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Цикл в графе называется путь, в котором совпадают его начальная и конечная вершины. Граф называется несвязным, если существуют хотя бы две вершины несвязные путем Граф называется деревом, если для каждой пары вершин существует единственный соединяющий их путь Рис. 2 Рис. 1

• 
  Слайд 3
  

  А B C D F K Рис. 1 Рис. 5 Рис. 3 Рис. 4 Какие из приведенных графов являются деревьями? Найдите степени вершин в графе на рисунке 2. На рисунке 3 изображен граф. Назовите один из путей от A до F . Существует ли путь от A до F проходящий через все вершины графа? Найдите в графе на рисунке 3 циклы, содержащие: 3 ребра; 6 ребер; Найдите несвязные графы . F G D А B C Рис. 2

• 
  Слайд 4

  Зачем нужны деревья?

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

• 
  Слайд 5

  Отыскание пути

  1 2 3 4 5 6 7 8 9 На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина?

• 
  Слайд 6

  Решение задачи

  2 3 4 5 6 7 8 9 1 1 2 5 4 8 9 6 9 5 8 9 8 9 7 9 5 8 9 8 9 7 9 5 8 9 8 9 7 1 ярус 2 ярус 3 ярус 4 ярус 5 ярус 6 ярус 7 ярус 7 5 9 5 3 5 Кратчайший путь: 1 5 9. Его длинна 2. Длина наиболее продолжительного пути 7: 1 2 3 6 5 7 8 9. Число путей 14 9 8 9 9 5 8 7

• 
  Слайд 7

  МАТРИЦЫ ГРАФОВ

  В0 В1 В2 В3 В4 В5 В6 4 6 5 5 3 7 4 4 8 2 11 9 . B0 B1 B2 B3 B4 B5 B6 B0 0 4 6 5 B1 4 7 3 B2 7 11 9 B3 6 3 4 5 B4 11 4 4 2 B5 5 5 4 8 B6 9 2 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

• 
  Слайд 8
  

  1 4 1 4 2 3 1 4 1 2 2 3 1 1 4 2 Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: “Минимальная стоимость проезда из А в B не больше 6”. Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями. 1) 2) 3) 4) B C D E A B C D E A B C D E A 3 1 4 2 B C D E A AC C B - 7 AC CE EB - 7 AC C B - 7 AE EC CB - 7 AC C B - 7 AC CE EB - 6 AD DC CB - 9 AD DC CE EB - 8

• 
  Слайд 9
  

  Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16 камней. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте. 2 ход 2 игрок 3,9, ∑ 12 12,2, ∑ 14 4,6, ∑ 10 5,2, ∑ 7 27,2, ∑ 29 3 ход 1 игрок 4 ход 2 игрок 15,3,∑18 12,4,∑16 12,9,∑21 12,4,∑16 36,3,∑39 13,3,∑16 12,9,∑21 4,27,∑31 3,18, ∑ 21 4,4, ∑ 8 5,3, ∑ 8 12,3, ∑ 15 4,9, ∑ 13 4,3, ∑ 7 3,4, ∑ 7 1 ход 1 игрок 3,6, ∑ 9 4,2, ∑ 6 3,3, ∑ 6 3,3, ∑ 6 9,2, ∑ 11 3,2, ∑ 5

• 
  Слайд 10

  Спасибо за внимание