Как поступить
в Онлайн-школу и получить аттестат?

Подробно расскажем о том, как перевестись на дистанционный формат обучения, как устроены онлайн-уроки и учебный процесс, как улучшить успеваемость и повысить мотивацию!

Нажимая на кнопку, я соглашаюсь на обработку персональных данных

Конспект урока: Графические информационные модели

Моделирование и формализация

Графические информационные модели

 

План занятия

 

  1. Введение в тему.
  2. Многообразие графических информационных моделей.
  3. Графы.
  4. Использование графов при решении задач.

 

Цели занятия

 

  1. Научиться различать ребра и дуги графов.
  2. Научиться различать ориентированные, неориентированные и взвешенные графы.
  3. Научиться использовать графы при решении задач.

 

Разминка

 

  1. Какие модели называют словесными?
  2. Какие модели называют математическими?
  3. Какие модели называют компьютерными математическими?

 

 

Введение в тему

 

Благодаря графическому представлению информацию легче запоминать и усваивать. Неслучайно при подготовке к различным самостоятельным и контрольным работам многим обучающимся для быстрого запоминания советуют изображать изучаемый материал в виде схем, таблиц, графиков, диаграмм и др. Благодаря такому отображению информации можно быстро провести сравнение данных, выявить закономерности, обнаружить ошибки и несоответствия и др. 

 

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

 

Многообразие графических информационных моделей


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


Типы графических информационных моделей:

 

  • Схема – это графическое изображение структуры системы (рис. 1)
     

Рис. 1. Схема метро Санкт-Петербурга

 

  • Карта – это отображение местности в уменьшенном масштабе (рис. 2)

Рис. 2. Физическая карта мира

 

  • Чертеж – это условное графическое изображение предмета с точным соотношением его размеров, получаемое методом проецирования (рис. 3).

Рис. 3. Чертеж шестерни

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

Рис. 4. График функции

 

  • Диаграмма графическое представление данных линейными отрезками или геометрическими фигурами, позволяющее быстро оценить соотношение нескольких величин (рис. 5).

Рис. 5. Диаграмма “Режим дня”

 

Типы диаграмм и способы их построения будут рассмотрены при изучении электронных таблиц.

 

Графы


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


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

 

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

 

Линии бывают двух видов:

 

  • Ребра – это ненаправленные линии, которые соединяют вершины графа и не имеют стрелок на концах.

Граф, вершины которого соединены ребрами, называется неориентированным (рис. 6).

Рис. 6. Неориентированный граф

 

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

Граф, вершины которого соединены дугами называется ориентированным (рис. 7).

 

Рис. 7. Ориентированный граф

 

Взвешенный граф – это граф, у которого вершины и/или линии (ребер/дуг) характеризуются дополнительной информацией (весами вершин и/или ребер (или дуг) (рис. 8).

Рис. 8. Взвешенный граф

 

Рассчитаем вес ребер графа (рис. 8). Для этого необходимо сложить веса всех ребер: 10 + 7 + 27 + 15 + 21 + 32 + 31 + 8 + 9 + 11 + 15 + 17 = 203. 

 

Так как у всех графов имеется ограниченное количество вершин и ребер (или дуг), то их можно посчитать. Информацию о количестве вершин называют мощностью вершин. Информацию о количестве линий в графе называют мощностью ребер (или дуг). Например, мощность вершин графа, изображенного на рисунке 8, составляет 9, а мощность ребер (т.к. граф неориентированный) – 12. 

 

Маршрут (путь) графа – это последовательность чередующихся вершин и ребер (или дуг). 

Рассмотрим пример построения маршрута графа из пункта А в пункт H для графа, изображенного на рисунке 8. Для удобства формирования маршрута графа, расставим нумерацию ребер в данном графе. Ребра подпишем как: R1, R2, R3 и т.д. Граф с подписанными ребрами изображен на рис. 9.

Рис. 9. Граф с пронумерованными ребрами

 

Построим маршрут графа, например, AR2BR4FR6H. Заметим, что для данного графа можно построить несколько маршрутов, например, можно построить маршруты: AR2BR3GR12IR11HAR1CR5FR6и др. 

 

Маршрут простая цепь – маршрут, который получается если в него входят все различные вершины и ребра. Например, AR2BR3GR12IR11H.

 

Длина маршрута – количество линий, входящих в маршрут. Например, длина маршрута AR2BR3GR12IR11составляет 4, т.к. в данном маршруте присутствует 4 ребра: R2, R3, R12 и R11.

 

Если начальная и конечная вершины маршрута совпадают и любое ребро (или дуга) встречается не более одного раза, то такой маршрут называется замкнутым (циклом). Например, для графа изображенного на рисунке 9 можно построить замкнутые маршруты: AR1CR5FR4BR2A, AR2BR3GR12IR11HR6FR5CR1и др. 

 

Не у каждого графа можно получить замкнутый маршрут. Граф с циклом называется сетью. Если вершины графа взаимодействуют друг с другом через ребра (или дуги), то такой граф называется семантической сетью. Например, в вершинах находятся абоненты, а через дуги осуществляется их коммуникация (рис. 10).

 

Рис. 10. Семантическая сеть

 

Граф, у которого нет циклов, называется деревом (рис.11).

Рис. 11. Дерево

 

Перечислим особенности графа типа «дерево»:

 

  1. Между любыми его двумя вершинами существует только один путь.
  2. Всегда имеется главная вершина, называемая корнем.
  3. Каждая вершина (кроме корня) имеет только одного предка.
  4. Каждая вершина может порождать неограниченное количество потомков.
  5. Вершины, у которых нет потомков называются листьями.

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

 

Использование графов при решении задач

 

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

 


Пример 1

 

Ниже представлена схема дорог (рис. 12), которая связывает населенные пункты А, Б, В, Г, Д, Е, К. По каждой дороге можно идти только в направлении, которое указано стрелкой. Сколько существует различных путей из населенного пункта А в пункт К?

Рис. 12. Иллюстрация к примеру 1

 

Решение:

 

Для удобства решения данной задачи разделим граф на 2 графа (по количеству дорог исходящих из вершины А). Способ разделения одного графа на несколько удобно применять, когда нужно построить большой граф и сложно определить, сколько места на листе бумаги потребуется для его построения. Данный способ позволит избежать наложения данных, а следовательно, ошибок в расчетах.

 

Получим первый граф (рис. 13). Назовем его А-Б.

Рис. 13. Граф А-Б.

 

Исходя из полученного графа, в пункт К можно попасть тремя путями:

 

  1. А  БВ К
  2. А Б К
  3. А Б Д К

Получим второй граф (рис 14). Назовем его А-Г.

Рис. 14. Граф А-Г

 

Исходя из полученного графа, в пункт К можно попасть тремя путями:

  1. АГ В К
  2. АГ К
  3. АГЕК

Сложим полученное количество путей и найдем общее количество различных путей из населенного пункта А в пункт К: 3 + 3 = 6.

 

Ответ: 6 путей.


Пример 2

 

Запишите все трехзначные числа содержащие цифры 3 и 4. 

 

Решение:

 

Так как в задаче требуется записать все трехзначные числа, а не просто определить их количество, то необходимо построить граф. Для удобства построим не один, а два графа с наборами трехзначных чисел. Пусть один набор начинается с цифры 3, а второй – с 4.

 

Построим граф (рис. 15), начинающийся с цифры 3. Назовем его Граф-3. 

Рис. 15 Граф-3

 

Построим граф (рис. 16), начинающийся с цифры 4. Назовем его Граф-4.

Рис. 16. Граф-4

 

Выпишем все трехзначные числа из наборов Граф-3 и Граф-4.

 

Из рисунка 15: 333; 334; 343; 344.

Из рисунка 16: 433; 434; 443; 444.

 

Ответ: 333; 334; 343; 344; 433; 434; 443; 444.


Пример 3

 

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

 

Решение:

 

  1. Построим граф реализующий решение данной задачи (рис. 17). В вершинах графа будем обозначать персонажей из задачи: Ч (человек), В (волк), З (заяц), К (капуста). Ребрами будем отображать происходящие изменения. Те состояния, которые противоречат правилам будем зачеркивать красными линиями. Вершины закрашенные синим цветом обозначают берег 1, на котором находятся персонажи до переправы. Вершины закрашенные зеленым цветом обозначают берег 2, на который необходимо перевезти человеку волка, зайца и капусту. Незакрашенные прямоугольники показывают, с какими персонажами происходят изменения.
  2. Анализируя рисунок 17, можно сформулировать план переправы на другой берег всех персонажей задачи:
  3. Человек заносит в лодку зайца и с ним отправляется на берег 2.
  4. Человек оставляет на берегу 2 зайца и возвращается на берег 1.
  5. Человек кладет в лодку капусту и отправляется на берег 2.
  6. Человек выкладывает капусту на берег 2 и заносит в лодку зайца.
  7. Человек с зайцем возвращается на берег 1.
  8. Человек выносит на берег 1 зайца и заводит в лодку волка.
  9. Человек с волком отправляется на берег 2.
  10. Человек оставляет волка вместе капустой на берегу 2 и возвращается за зайцем.
  11. Человек заносит в лодку зайца и с ним отправляется на берег 2.
  12. Человек, заяц, волк, капуста находятся на берегу 2.

Рис. 17. Граф переправы на другой берег 

Правила:

  1. Если рядом не будет человека, то волк съест зайца.
  2. Если рядом не будет человека, заяц съест капусту.
  3. Человек может перевозить что-то одно или кого-то одного.

Пример 4

 

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. У каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.

 

В начальный момент в первой куче было семь камней, во второй куче — S камней; 1 ≤ S ≤ 69.

 

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

 

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

 

Решение:

 

  1. Начинаем рассуждение с того, что Ваня ходит вторым, поэтому его первый ход – это второй ход игры.
  2. В начальный момент игры известно количество камней в первой куче 7, а во второй неизвестно х: Начальная позиция: (7, х).
  3. Чтобы Ваня выиграл своим первым ходом необходимо, чтобы ко второму ходу игры суммарное количество камней в кучах было не менее 35, т.е. получается, что до этого должно быть: .
  4. Получается, что для победы Вани своим первым ходом в начальный момент времени в кучах должно быть (7, 18) камней.
  5. Проверим полученные данные путем построения графа (рис. 18)

Рис. 18.  Пример 4 (решение)

Анализируя граф, получаем:

 

  1. В начале игры количество камней в кучах (7,18).
  2. Первый ход игры. Первый игрок Петя совершает ход, и он может пойти одним из следующих вариантов: (8, 18), (7, 19), (14, 18), (7, 36).
  3. Второй ход игры. Второй игрок Ваня совершает победный ход, если Петя ходил (7, 36). Ваня победит, если увеличит количество камней во второй куче в 2 раза, получив (7, 72), что в сумме составляет 79.

 

Ответ: 18.


Контрольные вопросы

 

  1. Что такое граф?
  2. Чем отличаются ориентированные графы от неориентированных?
  3. Какие графы называют взвешенными?
  4. Постройте маршрут B – I  графа, представленного на рисунке 9.
  5. Как изменятся графы из примера 2, если придется находить все четырехзначные числа?


Предыдущий урок
Обобщение и систематизация основных понятий темы «Моделирование и формализация»
Моделирование и формализация
Следующий урок
База данных как модель предметной области. Реляционные базы данных
Моделирование и формализация
  • Начальные сведения из стереометрии. Многогранники

    Геометрия

  • School and university subjects. Школьные предметы и дисциплины

    Английский язык

  • Понятие хозяйства. Его структура. Этапы развития хозяйства

    География

Зарегистрируйся, чтобы присоединиться к обсуждению урока

Добавьте свой отзыв об уроке, войдя на платфому или зарегистрировавшись.

Отзывы об уроке:
Пока никто не оставил отзыв об этом уроке