«ГРАФИЧЕСКИЕ �ИНФОРМАЦИОННЫЕ МОДЕЛИ»

1.3.1. МНОГООБРАЗИЕ ГРАФИЧЕСКИХ ИНФОРМАЦИОННЫХ МОДЕЛЕЙ

• В ГРАФИЧЕСКИХ ИНФОРМАЦИОННЫХ МОДЕЛЯХ ДЛЯ НАГЛЯДНОГО ОТОБРАЖЕНИЯ ОБЪЕКТОВ ИСПОЛЬЗУЮТСЯ УСЛОВНЫЕ ГРАФИЧЕСКИЕ ИЗОБРАЖЕНИЯ, ЗАЧАСТУЮ ДОПОЛНЯЕМЫЕ ЧИСЛАМИ, СИМВОЛАМИ И ТЕКСТАМИ.
• ПРИМЕРАМИ ГРАФИЧЕСКИХ МОДЕЛЕЙ МОГУТ СЛУЖИТЬ ВСЕВОЗМОЖНЫЕ СХЕМЫ, КАРТЫ, ЧЕРТЕЖИ, ГРАФИКИ И ДИАГРАММЫ.

СХЕМА

• СХЕМА — ЭТО ПРЕДСТАВЛЕНИЕ НЕКОТОРОГО ОБЪЕКТА В ОБЩИХ, ГЛАВНЫХ ЧЕРТАХ С ПОМОЩЬЮ УСЛОВНЫХ ОБОЗНАЧЕНИЙ.
• СХЕМА КАК ИНФОРМАЦИОННАЯ МОДЕЛЬ НЕ ПРЕТЕНДУЕТ НА ПОЛНОТУ ПРЕДОСТАВЛЕНИЯ ИНФОРМАЦИИ ОБ ОБЪЕКТЕ. 
• С ПОМОЩЬЮ ОСОБЫХ ПРИЁМОВ И ГРАФИЧЕСКИХ ОБОЗНАЧЕНИЙ НА НЕЙ БОЛЕЕ РЕЛЬЕФНО ВЫДЕЛЯЕТСЯ ОДИН ИЛИ НЕСКОЛЬКО ПРИЗНАКОВ РАССМАТРИВАЕМОГО ОБЪЕКТА. ПРИМЕРЫ СХЕМ ПРИВЕДЕНЫ НА РИС. 1.5.

ЧЕРТЁЖ

• ЧЕРТЁЖ — УСЛОВНОЕ ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ ПРЕДМЕТА С ТОЧНЫМ СООТНОШЕНИЕМ ЕГО РАЗМЕРОВ, ПОЛУЧАЕМОЕ МЕТОДОМ ПРОЕЦИРОВАНИЯ. 
• ЧЕРТЁЖ СОДЕРЖИТ ИЗОБРАЖЕНИЯ, РАЗМЕРНЫЕ ЧИСЛА, ТЕКСТ. ИЗОБРАЖЕНИЯ ДАЮТ ПРЕДСТАВЛЕНИЯ О ГЕОМЕТРИЧЕСКОЙ ФОРМЕ ОБЪЕКТА, ЧИСЛА — О ВЕЛИЧИНЕ ОБЪЕКТА И ЕГО ЧАСТЕЙ, НАДПИСИ — О НАЗВАНИИ, МАСШТАБЕ, В КОТОРОМ ВЫПОЛНЕНЫ ИЗОБРАЖЕНИЯ.

ГРАФИК

• ГРАФИК — ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ, ДАЮЩЕЕ НАГЛЯДНОЕ ПРЕДСТАВЛЕНИЕ О ХАРАКТЕРЕ ЗАВИСИМОСТИ ОДНОЙ ВЕЛИЧИНЫ (НАПРИМЕР, ПУТИ) ОТ ДРУГОЙ (НАПРИМЕР, ВРЕМЕНИ).
• ГРАФИК ПОЗВОЛЯЕТ ОТСЛЕЖИВАТЬ ДИНАМИКУ ИЗМЕНЕНИЯ ДАННЫХ.

ДИАГРАММА

• ДИАГРАММА — ГРАФИЧЕСКОЕ ИЗОБРАЖЕНИЕ, ДАЮЩЕЕ НАГЛЯДНОЕ ПРЕДСТАВЛЕНИЕ О СООТНОШЕНИИ КАКИХ-ЛИБО ВЕЛИЧИН ИЛИ НЕСКОЛЬКИХ ЗНАЧЕНИЙ ОДНОЙ ВЕЛИЧИНЫ, ОБ ИЗМЕНЕНИИ ИХ ЗНАЧЕНИЙ.
• БОЛЕЕ ПОДРОБНО ТИПЫ ДИАГРАММ И СПОСОБЫ ИХ ПОСТРОЕНИЯ БУДУТ РАССМОТРЕНЫ ПРИ ИЗУЧЕНИИ ЭЛЕКТРОННЫХ ТАБЛИЦ.

1.3.2. ГРАФЫ

• ЕСЛИ ОБЪЕКТЫ НЕКОТОРОЙ СИСТЕМЫ ИЗОБРАЗИТЬ ВЕРШИНАМИ, А СВЯЗИ МЕЖДУ НИМИ — ЛИНИЯМИ (РЁБРАМИ), ТО МЫ ПОЛУЧИМ ИНФОРМАЦИОННУЮ МОДЕЛЬ РАССМАТРИВАЕМОЙ СИСТЕМЫ В ФОРМЕ ГРАФА. ВЕРШИНЫ ГРАФА МОГУТ ИЗОБРАЖАТЬСЯ КРУГАМИ, ОВАЛАМИ, ТОЧКАМИ, ПРЯМОУГОЛЬНИКАМИ И Т. Д.
• ГРАФ НАЗЫВАЕТСЯ ВЗВЕШЕННЫМ, ЕСЛИ ЕГО ВЕРШИНЫ ИЛИ РЁБРА ХАРАКТЕРИЗУЮТСЯ НЕКОТОРОЙ ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИЕЙ — ВЕСАМИ ВЕРШИН ИЛИ РЁБЕР.
• НА РИС. 1.6 С ПОМОЩЬЮ ВЗВЕШЕННОГО ГРАФА ИЗОБРАЖЕНЫ ДОРОГИ МЕЖДУ ПЯТЬЮ НАСЕЛЁННЫМИ ПУНКТАМИ А, В, С, D, Е; ВЕСА РЁБЕР — ПРОТЯЖЁННОСТЬ ДОРОГ В КИЛОМЕТРАХ.

• ПУТЬ ПО ВЕРШИНАМ И РЁБРАМ ГРАФА, В КОТОРЫЙ ЛЮБОЕ РЕБРО ГРАФА ВХОДИТ НЕ БОЛЕЕ ОДНОГО РАЗА, НАЗЫВАЕТСЯ ЦЕПЬЮ. ЦЕПЬ, НАЧАЛЬНАЯ И КОНЕЧНАЯ ВЕРШИНЫ КОТОРОЙ СОВПАДАЮТ, НАЗЫВАЕТСЯ ЦИКЛОМ.�ГРАФ С ЦИКЛОМ НАЗЫВАЕТСЯ СЕТЬЮ. ЕСЛИ ГЕРОЕВ НЕКОТОРОГО ЛИТЕРАТУРНОГО ПРОИЗВЕДЕНИЯ ПРЕДСТАВИТЬ ВЕРШИНАМИ ГРАФА, А СУЩЕСТВУЮЩИЕ МЕЖДУ НИМИ СВЯЗИ ИЗОБРАЗИТЬ РЁБРАМИ, ТО МЫ ПОЛУЧИМ ГРАФ, НАЗЫВАЕМЫЙ СЕМАНТИЧЕСКОЙ СЕТЬЮ.

• ДЕРЕВО — ЭТО ГРАФ, В КОТОРОМ НЕТ ЦИКЛОВ, Т. Е. В НЁМ НЕЛЬЗЯ ИЗ НЕКОТОРОЙ ВЕРШИНЫ ПРОЙТИ ПО НЕСКОЛЬКИМ РАЗЛИЧНЫМ РЁБРАМ И ВЕРНУТЬСЯ В ТУ ЖЕ ВЕРШИНУ. ОТЛИЧИТЕЛЬНОЙ ОСОБЕННОСТЬЮ ДЕРЕВА ЯВЛЯЕТСЯ ТО, ЧТО МЕЖДУ ЛЮБЫМИ ДВУМЯ ЕГО ВЕРШИНАМИ СУЩЕСТВУЕТ ЕДИНСТВЕННЫЙ ПУТЬ.
• У ДЕРЕВА ВЫДЕЛЯЕТСЯ ОДНА ГЛАВНАЯ ВЕРШИНА, НАЗЫВАЕМАЯ ЕГО КОРНЕМ. КАЖДАЯ ВЕРШИНА ДЕРЕВА (КРОМЕ КОРНЯ) ИМЕЕТ ТОЛЬКО ОДНОГО ПРЕДКА, ОБОЗНАЧЕННЫЙ ПРЕДКОМ ОБЪЕКТ ВХОДИТ В ОДИН КЛАСС ВЫСШЕГО УРОВНЯ. ЛЮБАЯ ВЕРШИНА ДЕРЕВА МОЖЕТ ПОРОЖДАТЬ НЕСКОЛЬКО ПОТОМКОВ — ВЕРШИН, СООТВЕТСТВУЮЩИХ КЛАССАМ НИЖНЕГО УРОВНЯ. ТАКОЙ ПРИНЦИП СВЯЗИ НАЗЫВАЕТСЯ «ОДИН-КО-МНОГИМ». ВЕРШИНЫ, НЕ ИМЕЮЩИЕ ПОРОЖДЁННЫХ ВЕРШИН, НАЗЫВАЮТСЯ ЛИСТЬЯМИ.�РОДСТВЕННЫЕ СВЯЗИ МЕЖДУ ЧЛЕНАМИ СЕМЬИ УДОБНО ИЗОБРАЖАТЬ С ПОМОЩЬЮ ГРАФА, НАЗЫВАЕМОГО ГЕНЕАЛОГИЧЕСКИМ ИЛИ РОДОСЛОВНЫМ ДЕРЕВОМ.�

ИСПОЛЬЗОВАНИЕ ГРАФОВ ПРИ РЕШЕНИИ ЗАДАЧ

• ГРАФЫ УДОБНО ИСПОЛЬЗОВАТЬ ПРИ РЕШЕНИИ НЕКОТОРЫХ КЛАССОВ ЗАДАЧ.�ПРИМЕР 1. ДЛЯ ТОГО ЧТОБЫ ЗАПИСАТЬ ВСЕ ТРЁХЗНАЧНЫЕ ЧИСЛА, СОСТОЯЩИЕ ИЗ ЦИФР 1 И 2, МОЖНО ВОСПОЛЬЗОВАТЬСЯ ГРАФОМ (ДЕРЕВОМ) НА РИС. 1.7.

​

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

• ПРИМЕР 2. РАССМОТРИМ НЕСКОЛЬКО ВИДОИЗМЕНЁННУЮ КЛАССИЧЕСКУЮ ЗАДАЧУ О ПЕРЕПРАВЕ.

Для решения этой задачи составим граф, вершинами которого будут исходное размещение персонажей на берегу реки, а также всевозможные промежуточные состояния, достигаемые из предыдущих за один шаг переправы. Каждую вершину-состояние переправы обозначим овалом и свяжем рёбрами с состояниями, образованными из неё (рис. 1.8).

На графе видно, что существуют два решения этой задачи. Приведём соответствующий одному из них план переправы:�1) крестьянин перевозит лису;�2) крестьянин возвращается;�3) крестьянин перевозит собаку;�4) крестьянин возвращается с лисой;�5) крестьянин перевозит гуся;�6) крестьянин возвращается;�7) крестьянин перевозит лису.

• ПРИМЕР 3. РАССМОТРИМ СЛЕДУЮЩУЮ ИГРУ: СНАЧАЛА В КУЧКЕ ЛЕЖАТ 5 СПИЧЕК; ДВА ИГРОКА УБИРАЮТ СПИЧКИ ПО ОЧЕРЕДИ, ПРИЧЁМ ЗА 1 ХОД МОЖНО УБРАТЬ 1 ИЛИ 2 СПИЧКИ; ВЫИГРЫВАЕТ ТОТ, КТО ОСТАВИТ В КУЧКЕ 1 СПИЧКУ. ВЫЯСНИМ, КТО ВЫИГРЫВАЕТ ПРИ ПРАВИЛЬНОЙ ИГРЕ — ПЕРВЫЙ (I) ИЛИ ВТОРОЙ (II) ИГРОК.
• ИГРОК I МОЖЕТ УБРАТЬ ОДНУ СПИЧКУ (В ЭТОМ СЛУЧАЕ ИХ ОСТАНЕТСЯ 4) ИЛИ СРАЗУ 2 (В ЭТОМ СЛУЧАЕ ИХ ОСТАНЕТСЯ 3).�ЕСЛИ ИГРОК I ОСТАВИЛ 4 СПИЧКИ, ИГРОК П МОЖЕТ СВОИМ ХОДОМ ОСТАВИТЬ 3 ИЛИ 2 СПИЧКИ. ЕСЛИ ЖЕ ПОСЛЕ ХОДА ПЕРВОГО ИГРОКА ОСТАЛОСЬ 3 СПИЧКИ, ВТОРОЙ ИГРОК МОЖЕТ ВЫИГРАТЬ, ВЗЯВ ДВЕ СПИЧКИ И ОСТАВИВ ОДНУ.�ЕСЛИ ПОСЛЕ ИГРОКА II ОСТАЛОСЬ 3 ИЛИ 2 СПИЧКИ, ТО ИГРОК I В КАЖДОЙ ИЗ ЭТИХ СИТУАЦИЙ ИМЕЕТ ШАНС НА ВЫИГРЫШ.�ТАКИМ ОБРАЗОМ, ПРИ ПРАВИЛЬНОЙ СТРАТЕГИИ ИГРЫ ВСЕГДА ВЫИГРАЕТ ПЕРВЫЙ ИГРОК. ДЛЯ ЭТОГО СВОИМ ПЕРВЫМ ХОДОМ ОН ДОЛЖЕН ВЗЯТЬ ОДНУ СПИЧКУ.

​

На рис. 1.9 представлен граф, называемый деревом игры; на нём отражены все возможные варианты, в том числе ошибочные (проигрышные) ходы игроков