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

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

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

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

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

02.03.2024
1733
0

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

 

План занятия

 

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

 

Цели занятия

 

  • научиться различать рёбра и дуги графов
  • научиться различать ориентированные, неориентированные и взвешенные графы
  • научиться использовать графы при решении задач

 

Разминка

 

  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, можно сформулировать план переправы на другой берег всех персонажей задачи:
    1. Человек заносит в лодку зайца и с ним отправляется на берег 2.
    2. Человек оставляет на берегу 2 зайца и возвращается на берег 1.
    3. Человек кладет в лодку капусту и отправляется на берег 2.
    4. Человек выкладывает капусту на берег 2 и заносит в лодку зайца.
    5. Человек с зайцем возвращается на берег 1.
    6. Человек выносит на берег 1 зайца и заводит в лодку волка.
    7. Человек с волком отправляется на берег 2.
    8. Человек оставляет волка вместе капустой на берегу 2 и возвращается за зайцем.
    9. Человек заносит в лодку зайца и с ним отправляется на берег 2.
    10. Человек, заяц, волк, капуста находятся на берегу 2.

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

 

Правила:

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

Пример 4

 

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

 

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

 

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

 

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

 

Решение

  1. Начинаем рассуждение с того, что Ваня ходит вторым, поэтому его первый ход — это второй ход игры.
  2. В начальный момент игры известно количество камней в первой куче (7), а во второй неизвестно х: начальная позиция: (7, х).
  3. Чтобы Ваня выиграл своим первым ходом, необходимо, чтобы ко второму ходу игры суммарное количество камней в кучах было не менее 35, т. е. получается, что до этого должно быть (7, 18).
  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, если придется находить все четырехзначные числа?


Предыдущий урок
Графические информационные модели
Моделирование и формализация
Следующий урок
Система управления базами данных
Моделирование и формализация
Урок подготовил(а)
teacher
Иван Андреевич
Учитель информатики
Опыт работы: 7 лет
Поделиться:
  • Одномерные массивы. Вычисление суммы элементов массива

    Информатика

  • Внутренняя и внешняя политика в 1801—1811 гг. Героический 1812 год

    История

  • Закон преломления света на плоской границе двух однородных прозрачных сред. Преломление света в призме. Дисперсия. Явление полного внутреннего отражения.

    Физика

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

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

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