Презентация на тему "Моделирование. Решение задач с использованием графов."(11 класс)

• 1 слайд

  Учитель информатики
  Степанова Татьяна Валерьевна
  Решение задач с использованием графов
  

• 2 слайд

  1
  2
  3
  4
  5
  a
  b
  c
  d
  e
  f
  Перечислите ребра и вершины.
  

• 3 слайд

  Рюрик
  Игорь
  Святослав
  Владимир Св.
  Ярополк
  Олег
  крышка
  ножка
  ножка
  ножка
  ножка
  СРУКТУРА УПРАВЛЕНИЯ ГОСУДАРСТВОМ
  

• 4 слайд

  Семантическая сеть
  выхожу
  я
  на дорогу
  один
  кто?
  что делаю?
  куда?
  сколько?
  

• 5 слайд

  Создайте семантическую сеть
  Отговорила роща золотая березовым, весёлым языком.
  Не обещайте деве юной любови вечной на земле.
  

• 6 слайд

  отговорила
  роща
  языком
  золотая
  березовым
  веселым
  Что сделала?
  Что?
  Чем?
  Какая?
  Каким?
  

• 7 слайд

  Не обещайте
  деве
  любови
  юной
  на земле
  вечной
  Что делайте?
  Какой?
  Какой?
  кому?
  Чего?
  где?
  

• 8 слайд

  А
  Б
  В
  Г
  Е
  Д
  В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым только один раз. К настоящему моменту некоторые игры уже проведены:
  Андрей сыграл с Борисом, Галиной и Еленой;
  Борис – с Андреем и с Галиной;
  Виктор – с Галиной, Дмитрием и Еленой;
  Галина - с Андреем и Борисом;
  Дмитрий – с Виктором;
  Елена – с Андреем и Виктором.
  Сколько игр проведено к настоящему моменту и сколько еще осталось?
  Решение
  Соединим зелеными отрезками тех, кто уже играл. Сколько получилось отрезков(ребер? То есть сколько проведено уже игр?
  
  
  

• 9 слайд

  А
  Б
  В
  Г
  Е
  Д
  

• 10 слайд

  
  
  Ответ: 8.
  10
  А
  Б
  В
  Е
  Д
  Г
  

• 11 слайд

  В автомобильных гонках Коля, Боря, Юра заняли первые четыре места.
  На вопрос, какие места они заняли, трое из них ответили:
  1)Коля ни первое, ни четвертое;
  2)Боря второе;
  3)Вова не был последним.
  Какое место занял каждый мальчик?
  
  Б
  К
  В
  Ю
  

• 12 слайд

  Три друга Олег, Борис и Арсений, закончив институт, разъехались по разным городам. И вот спустя несколько лет, они, встретившись на вечере встречи выпускников, решили разыграть своего товарища. На его вопрос, где они теперь живут, друзья ответили:
  Олег:я живу в Екатеринбурге, а Борис - в Мурманске.
  Борис:я живу в Волгограде, а Олег - в Мурманске.
  Арсений: я живу в Мурманске, а Олег - в Волгограде.
  Каждый из них один раз сказал правду и один раз солгал. Где живут Арсений, Борис и Олег? В ответе перечислите подряд без пробелов первые буквы названий городов, соответствующие именам друзей в указанном порядке, например ВМЕ.
  В6
  Ответ: МВЕ
  АБО
  
  ЕМВ
  

• 13 слайд

• 14 слайд

• 15 слайд

• 16 слайд

  Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
  
  весовая матрица
  взвешенный граф, где с каждым ребром связано некоторое число (вес), оно может обозначать, например, расстояние между городами или стоимость перевозки
  С
  А
  Д
  Е
  В
  3
  1
  4
  2
  2
  

• 17 слайд

  Верный ответ 3).
  
  «Минимальная стоимость проезда из А в B не больше 6».
  1
  2
  4
  2
  3
  A
  B
  C
  D
  E
  1
  2
  4
  1
  3
  A
  B
  C
  D
  E
  1
  2
  4
  4
  3
  A
  C
  D
  2
  B
  E
  1
  2
  4
  4
  A
  C
  D
  1
  B
  E
  

• 18 слайд

  Ответ:
  А
  В
  С
  Д
  3
  

• 19 слайд

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

• 20 слайд

  В таблице приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите таблицу, для которой выполняется условие «Минимальная стоимость перевозки грузов от пункта А до пункта В не больше 3».
  

• 21 слайд

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

• 22 слайд

  4. В таблицах приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».
  

• 23 слайд

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

• 24 слайд

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

• 25 слайд

  
  На одной улице стоят в ряд 4 дома, в каждом из них живет по одному человеку. Их зовут Алексей, Егор, Виктор и Михаил. Известно, что все они имеют разные профессии: рыбак, пчеловод, фермер и ветеринар. Известно, что
  (1) Фермер живет правее пчеловода.
  (2) Рыбак живет правее фермера.
  (3) Ветеринар живет рядом с рыбаком.
  (4) Рыбак живет через дом от пчеловода.
  (5) Алексей живет правее фермера.
  (6) Виктор – не пчеловод.
  (7) Егор живет рядом с рыбаком.
  (8) Виктор живет правее Алексея.
  Определите, кто где живет, и запишите начальные буквы имен жильцов всех домов слева направо. Например, если бы в домах жили (слева направо) Кирилл, Олег, Мефодий и Пафнутий, ответ был бы КОМП.
  В6
  (ТР)
  

• 26 слайд

  (1) Фермер живет правее пчеловода.
  (2) Рыбак живет правее фермера.
  (3) Ветеринар живет рядом с рыбаком.
  (4) Рыбак живет через дом от пчеловода.
  (5) Алексей живет правее фермера.
  (6) Виктор – не пчеловод.
  (7) Егор живет рядом с рыбаком.
  (8) Виктор живет правее Алексея.
  1234
  
  Пчеловод
  Фермер
  Рыбак
  Ветеринар
  Алексей
  Алексей
  Виктор
  Виктор
  Виктор
  Егор
  Егор
  Михаил
  Решение:
  Ответ: МЕАВ
  

• 27 слайд

  Задание
  Дан граф. Составьте для него матрицу смежности и перечень ребер.
  2
  1
  3
  4
  5
  

• 28 слайд

  У султана много жен, и каждой он обещал посвятить песню, но придворный поэт внезапно заболел меланхолией, а султан сумел сочинить только две. Каждая жена расскажет о посвященной песне только своим подругам, которые не будут передавать информацию дальше. Сможет ли султан спеть каждой жене песню так, чтобы она не узнала о том, что еще кому-то посвящена точно такая же?
  У султана 8 жен и дружат они такими парами:
  1-22-58-51-87-33-67-4
  4-61-72-36-58-4
  Каким женам надо посвятить одну песню, а каким- другую?
  Задача2.
  

• 29 слайд

  На кольцевой трассе автогонок расположены 4 препятствия («болото», «трамплин», «крутой поворот», «скользкая дорога»). В судейском протоколе 4 этапа обозначены буквами А, Б, В, Г.
  Известно, что этап Б расположен между этапом А и «крутым поворотом». Этап В – это не «крутой поворот» и не «скользкая дорога». Он расположен между этапами «трамплином» и Г. Установите соответствие между этапами. В ответ запишите, какими буквами в судейском протоколе обозначены соответственно этапы «болото», «трамплин», «крутой поворот», «скользкая дорога». (Например, если этап «болото» обозначен буквой А, этап «трамплин» - буквой Б, этап «крутой поворот» - В, а этап «скользкая дорога» - Г, то в ответ нужно записать АБВГ )
  В6
  

• 30 слайд

  Решение:
  А
  Б
  Г
  В
  Ответ: ВАГБ.