Графическая модель что это

Что такое Графические, информационные модели? (Задание по Информатики)

Это пишется без запятой.

Графические (или геометрические) информационные модели являются простейшим видом моделей, которые передают внешние признаки объекта — размеры, форму, цвет.

Графические модели более информативны, чем словесные. Без карт трудно представить себе ботанику и биологию, географию, военное дело, судоходство и т. д.

Современные технологии не могут обойтись без информационных моделей технических устройств, зданий и т. д. в виде чертежей.

Электрические и радиосхемы — это информационные модели физики, радиотехники и радиоэлектроники.

Графики и диаграммы — это информационные модели, которые в нагляд­ной форме представляют числовые и статистические данные.

Особое место среди геометрических моделей занимают задачи на пост­роение. Такие задачи возникли еще в глубокой древности и были связаны с практическими потребностями. Они тренируют ум, учат комплексно применять знания, воспитывают нестандартный подход к решению проблем.

В качестве инструмента для графического моделирования сегодня ис­пользуется графический редактор. Для моделирования в среде графического редактора можно пользоваться обобщенной информационной моделью графического объекта.

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

Конструирование — это процесс сбора объекта и элементов. Конструиро­вать можно плоские и объемные объекты.

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

Виды графических моделей:

¨ Карта как информационная модель

¨ Чертеж – точная геометрическая копия реального объекта

¨ Схема – информационная модель сложных систем

¨ График – как модель процесса

¨ Фотография – точное визуальное изображение объекта

Карта описывает конкретную местность, которая является для нее объектом моделирования.

Карта создается с определенными целями для определения :

• местоположения населенных пунктов;

• используя линейку и учитывая масштаб карты, для измерения расстояний между реальными объектами на местности

Сейчас получили большое распространение геоинформационные модели

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

Схема – это графическое отображение состава и структуры сложной системы.

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

Графики могут быть представлены в виде круговых диаграмм, столбчатых диаграмм – гистограмм и линейных графиков.

4. Практическая работа в графическом редакторе Paint

В графическом редакторе создайте схему кабинета информатики. Соблюдайте пропорции всех объектов

Источник

Конспект урока «Графические модели»

9 класс, информатика

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

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

Развивать практические навыки работы в Paint

Воспитывать интерес к изучаемой теме

Актуализация прежних знаний

Что называют моделью?

Что такое моделирование?

Как можно разделить модели по фактору времени?

Что называют информационной моделью?

Какие типы информационных моделей знаете?

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

Одному и тому же объекту можно поставить в соответствие разные информационные модели (вербальные, математические, табличные, графические); все зависит от цели моделирования.

Вербальная модель – это письменное или устное представление информационной модели средствами естественного языка.

Примеры вербальных моделей:

информация в учебниках

произведения художественной литературы

тексты, описывающие алгоритмы

текстовое описание объектов и процессов

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

Изложение нового материала

Графические (или геометрические) информационные модели являются простейшим видом моделей, которые передают внешние признаки объек та — размеры, форму, цвет.

Графические модели более информативны, чем словесные. Без карт труд но представить себе ботанику и биологию, географию, военное дело, судо ходство и т.д.

Современные технологии не могут обойтись без информационных моделей технических устройств, зданий и т.д. в виде чертежей.

Электрические и радиосхемы — это информационные модели физики, радиотехники и радиоэлектроники.

Графики и диаграммы — это информационные модели, которые в нагляд ной форме представляют числовые и статистические данные.

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

В качестве инструмента для графического моделирования сегодня ис пользуется графический редактор. Для моделирования в среде графического редактора можно пользоваться обобщенной информационной моделью графического объекта.

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

Конструирование — это процесс сбора объекта и элементов. Конструиро вать можно плоские и объемные объекты.

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

Виды графических моделей:

Карта как информационная модель

Чертеж – точная геометрическая копия реального объекта

Схема – информационная модель сложных систем

График – как модель процесса

Фотография – точное визуальное изображение объекта

Карта описывает конкретную местность, которая является для нее объектом моделирования.

Карта создается с определенными целями для определения :

местоположения населенных пунктов;

используя линейку и учитывая масштаб карты, для измерения расстояний между реальными объектами на местности

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

Схема – это графическое отображение состава и структуры сложной системы.

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

Графики могут быть представлены в виде круговых диаграмм, столбчатых диаграмм – гистограмм и линейных графиков.

Практическая работа в графическом редакторе Paint

В графическом редакторе создайте схему кабинета информатики. Соблюдайте пропорции всех объектов

Что называют графической моделью?

Какие графические модели рассмотрели?

Какие профессии работают с компьютерными графическими моделями?

Кому может понадобится схема кабинета информатики?

Постройте графическую модель вашей комнаты, указав на ней расположение всех предметов мебели, окон и дверей. Запишите название построенной модели (карта, план, схема, чертёж, график).

Источник

Учитель информатики

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

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

Информатика. 9 класса. Босова Л.Л. Оглавление

Ключевые слова:

• схема
• карта
• чертёж
• график
• диаграмма
• граф
• сеть
• дерево

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

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

Рис. 1.5. Примеры схем, используемых на уроках физики, биологии, истории

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

Чертёж — условное графическое изображение предмета с точным соотношением его размеров, получаемое методом проецирования. Чертёж содержит изображения, размерные числа, текст. Изображения дают представления о геометрической форме объекта, числа — о величине объекта и его частей, надписи — о названии, масштабе, в котором выполнены изображения.

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

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

1.3.2. Графы

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

Граф называется неориентированным, если его вершины соединены рёбрами (рис. 1.6, а). Вершины ориентированного графа соединены дугами (рис. 1.6, б). Путь — это последовательность рёбер (дуг), по которым можно перейти из одной вершины в другую.

Граф называется взвешенным, если его вершины или рёбра характеризуются некоторой дополнительной информацией — весами вершин или рёбер. На рис. 1.6, в с помощью взвешенного неориентированного графа изображены дороги между пятью населёнными пунктами А, В, С, D, Е; веса рёбер — протяжённость дорог в километрах.

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

Рис. 1.6. Графы

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

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

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

Всякая иерархическая система может быть представлена с помощью дерева. У дерева выделяется одна главная вершина, называемая его корнем. Каждая вершина дерева (кроме корня) имеет только одного предка, обозначенный предком объект входит в один класс1* высшего уровня. Любая вершина дерева может порождать несколько потомков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один-ко-многим». Вершины, не имеющие порождённых вершин, называются листьями.

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

Ресурс «Живая Родословная» (145555) — инструмент для формирования и анализа генеалогических деревьев, содержащий примеры родословных. С его помощью вы можете изучить генеалогические деревья многих известных семей и построить генеалогическое дерево своей семьи (http://sc.edu.ru/).

Класс — множество объектов, обладающих общими признаками.

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

Графы удобно использовать при решении некоторых классов задач.

Пример 1. На рисунке 1.7 изображена схема дорог, связывающих торговые точки А, В, С, D, Е. По каждой дороге можно двигаться только в направлении, указанном стрелкой. Сколько существует различных путей от точки А до точки Е?

Рис. 1.7. Схема дорог, представленная ориентированным графом

В вершину Е можно попасть только из вершин С и D. Если мы будем знать число путей из вершины А в вершину С и из вершины А в вершину D, то, сложив их, получим искомое число путей из А в Е. Действительно, для того чтобы попасть из вершины А в вершину Е, мы просто все пути из вершины А в вершину С дополним дугой СЕ, а пути из вершины А в вершину D дополним дугой DE. Число путей при этом не изменится. Итак, число путей из вершины А в вершину Е равно сумме путей из А в С и из А в П.

Можно сказать, что наша задача распалась на две более простые задачи. Решим каждую из них в отдельности.

В вершину С можно попасть непосредственно из вершины А и из вершины В. В свою очередь, существует единственный путь из вершины А в вершину В. Таким образом, из вершины А в вершину С можно попасть двумя путями: 1 (напрямую из А) + 1 (через В) = 2.

Попробуйте доказать, что путь из вершины А в вершину В — единственный.

Что касается вершины D, она является конечной вершиной для трёх дуг: BD, AD и CD. Следовательно, в неё можно попасть из вершин А, В и С:

1 (напрямую из А) + 1 (через В) + 2 (через С) = 4.

Итак, существуют четыре пути из вершины А в вершину D.

Теперь выполним подсчёт путей из А в Е:

2 (через С) + 4 (через D) = 6.

Решение задачи будет гораздо проще, если двигаться от вершины А (начало маршрута) к вершине Е и проставлять веса вершин — число путей из А в текущую вершину (рис. 1.8). При этом вес вершины А можно принять за 1. Действительно, существует единственный способ попасть из А в А — оставаться на месте.

Рис. 1.8. Схема дорог, представленная взвешенным ориентированным графом

Пример 2. Для того чтобы записать все трёхзначные числа, состоящие из цифр 1 и 2, можно воспользоваться графом (деревом) на рис. 1.9.

Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их количество. В этом случае рассуждать нужно так: в разряде сотен может быть любая из цифр 1 и 2, в разряде десятков — те же два варианта, в разряде единиц — те же два варианта. Следовательно, число различных вариантов: 2 • 2 • 2 = 8.

Рис. 1.9. Дерево для решения задачи о записи трёхзначных чисел

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

Пример 3. Рассмотрим несколько видоизменённую классическую задачу о переправе.

На берегу реки стоит крестьянин (К) с лодкой, а рядом с ним — собака (С), лиса (Л) и гусь (Г). Крестьянин должен переправиться сам и перевезти собаку, лису и гуся на другой берег. Однако в лодку кроме крестьянина помещается либо только собака, либо только лиса, либо только гусь. Оставлять же собаку с лисой или лису с гусём без присмотра крестьянина нельзя — собака представляет опасность для лисы, а лиса — для гуся. Как крестьянин должен организовать переправу?

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

Недопустимые по условию задачи состояния выделены пунктирной линией; они исключаются из дальнейшего рассмотрения. Начальное и конечное состояния переправы выделены жирной линией.

На графе видно, что существуют два решения этой задачи. Приведём соответствующий одному из них план переправы:

1) крестьянин перевозит лису;
2) крестьянин возвращается;
3) крестьянин перевозит собаку;
4) крестьянин возвращается с лисой;
5) крестьянин перевозит гуся;
6) крестьянин возвращается;
7) крестьянин перевозит лису.

Пример 4. Рассмотрим следующую игру: сначала в кучке лежат 5 спичек; два игрока убирают спички по очереди, причём за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку. Выясним, кто выигрывает при правильной игре — первый (I) или второй (II) игрок.

Игрок I может убрать одну спичку (в этом случае их останется 4) или сразу 2 (в этом случае их останется 3).

Если после игрока II осталось 3 или 2 спички, то игрок I в каждой из этих ситуаций имеет шанс на выигрыш.

Таким образом, при правильной стратегии игры всегда выиграет первый игрок. Для этого своим первым ходом он должен взять одну спичку.

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

Рис. 1.11. Дерево игры

САМОЕ ГЛАВНОЕ

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

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

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

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

Источник

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

Вы будете перенаправлены на Автор24

Свойства графических информационных моделей

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

Поскольку человек с помощью зрения получает большую часть информации (порядка 70%), то по эффективности восприятия рисунок зачастую оказывается более эффективным, чем текст, формулы или устный рассказ.

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

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

Примеры графических моделей:

Рисунок 1. Чертеж. Автор24 — интернет-биржа студенческих работ

Готовые работы на аналогичную тему

Способы исполнения карт, схем, чертежей регламентированы отраслевыми стандартами. Так, географические карты выполняются в заданном масштабе, с использованием определенных правил преобразования трехмерной поверхности в двухмерную (проекции), с нанесением сетки координат, с использованием определенных цветов для обозначения высот и глубин. Кроме того, географические карты изображаются по-разному в зависимости от назначения: физические, экономические, климатические, демографические, военные и т.д.

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

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

Рисунок 2. Рекомендации по отображению диаграммы. Автор24 — интернет-биржа студенческих работ

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

Графические модели и вычислительная техника

Современное программное обеспечение предоставляет широкие возможности для подготовки графических моделей. Приведем несколько примеров таких приложений:

Особо следует отметить то обстоятельство, что графические модели используются и при разработке самого программного обеспечения: с помощью диаграмм семейства UML проектируются компьютерные программы. Такие диаграммы не зависят от предметной области и могут применяться в любом программном проекте. Кроме того, для подготовки таких диаграмм не нужна компьютерная техника (хотя ее применение и возможно). Диаграммы и схемы рисуются фломастерами на пластиковых досках или ватмане в ходе «мозговых штурмов», к которым могут быть привлечены как непосредственные разработчики, так и представители заказчика.

Рисунок 3. Диаграмма случаев использования из семейства UML. Автор24 — интернет-биржа студенческих работ

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

Источник

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

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

Графическая информационная модель – это наглядный способ представления объектов и процессов в виде графических изображений. К ним относятся: чертежи, графики, диаграммы, образные модели, схемы (карты, графы, блок-схемы).

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

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

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

Карта описывает конкретную местность, которая является для нее объектом моделирования. Это уменьшенное обобщённое изображение поверхности Земли на плоскости в той или иной системе условных обозначений.

Карта создается с определенными целями для определения:

местоположения населенных пунктов; рельефа местности; расположения автомагистралей; измерения расстояний между реальными объектами на местности

Графики и диаграммы — это информационные модели, которые в наглядной форме представляют числовые и статистические данные.

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

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

Отдельное место среди графических моделей занимают графы.

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

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

Если ребра графа указывают направление (представлены стрелками), то граф называют ориентированным (орграфом). Движение в ориентированном графе возможно тольеко в одном направлении (по стрелкам). Связи между объектами – вершинами в таком случае считаются несимметричными. У неориентированного графа связи между объектами – вершинами симметричны.

Одинаковые, но по-разному нарисованные графы, называют изоморфными. У изоморфных графов соединены одни и те же вершины.

Степенью вершины графа называется количество выходящих из нее ребер. Вершина, имеющая четную степень, называется четной вершиной, Вершина, имеющая нечетную степень, называется нечетной вершиной. На рисунке вершины A, B, D – чётные. Их степень равна 2. Вершины С, Е – нечётные. Их степень равна 3.

С понятием степени вершины связана одна из основных теорем теории графов – теорема о чётности числа нечетных вершин.

Теорема: Любой нормальный граф содержит четное число нечетных вершин.

Для иллюстрации рассмотрим задачу.

В городе Маленьком 5 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с 3-мя другими?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 3 провода, т. е. степень каждой вершины нашего графа – 3. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т. к. каждый провод имеет два конца и при суммировании степеней каждый провод взят 2 раза). (3*5)/2=15/2=7,5

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

Ответ. Соединить телефоны таким образом невозможно.

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

Вершина, не имеющая рёбер, называется изолированной вершиной и составляет отдельную компоненту связности. Вершина, имеющая только одно ребро, называется концевой или висячей.

Путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза, называется цепью (1). Цепь, начальная и конечная вершины которой совпадают, называется циклом (2). Дерево (иерархия) – это граф, в котором нет циклов (3), т. е. в нём нельзя из не­которой вершины пройти по нескольким различным рёбрам и вер­нуться в ту же вершину. Отличительной особенностью дерева явля­ется то, что между любыми двумя его вершинами существует един­ственный путь.

(1) (2) (3)

Всякая иерархическая система может быть представлена с по­мощью дерева. У дерева выделяется одна главная вершина, называе­мая его корнем. Каждая вершина дерева (кроме корня) имеет только одного предка, обозначенный им объект входит в один класс высше­го уровня. Любая вершина дерева может порождать несколько по­томков — вершин, соответствующих классам нижнего уровня. Такой принцип связи называется «один-ко-многим». Вершины, не име­ющие порождённых вершин, называются листьями.

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

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

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

Пример 1. Для того чтобы записать все трёхзначные числа, состо­ящие из цифр 1 и 2, можно воспользоваться графом (деревом).

Дерево можно не строить, если не требуется выписывать все воз­можные варианты, а нужно просто указать их количество. В этом случае рассуждать нужно так: в разряде сотен может быть любая из цифр (1или 2), в разряде десятков — те же два варианта, в разряде еди­ниц — те же два варианта. Следовательно, число различных вариан­тов: 2 • 2 • 2 = 8.

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

Пример 2. Рассмотрим несколько видоизменённую классическую задачу о переправе.

На берегу реки стоит крестьянин (К) с лодкой, а рядом с ним — собака (С), лиса (Л) и гусь (Г). Крестьянин должен переправиться сам и перевезти собаку, лису и гуся на другой берег. Однако в лодку кроме крестьянина помещается либо только собака, либо только лиса, либо только гусь. Оставлять же собаку с лисой или лису с гу­сем без присмотра нельзя — собака представляет опасность для лисы, а лиса — для гуся. Как крестьянин должен организовать пе­реправу?

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

На графе видно, что существует два решения этой задачи. При­ведём соответствующий одному из них план переправы:

крестьянин перевозит лису; крестьянин возвращается; крестьянин перевозит собаку; крестьянин возвращается с лисой; крестьянин перевозит гуся; крестьянин возвращается; крестьянин перевозит лису.

Пример 3. Рассмотрим следующую игру: сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причём за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке спичку. Выясним, кто выигрывает при правильной игре — первый (I) или второй (II) игрок.

Игрок I может убрать одну спичку (в этом случае их останется 4) или сразу 2 (в этом случае их останется 3).

Если игрок I оставил 4 спички, игрок II может своим ходом оста­вить 3 или 2 спички. Если же после хода первого игрока осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну.

Если после игрока II осталось 3 или 2 спички, то игрок I в каждой из этих ситуаций имеет шанс на выигрыш.

Таким образом, при правильной стратегии игры всегда выиграет первый игрок. Для этого своим первым ходом он должен взять одну спичку.

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

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

Вопросы и задания выполнить письменно в тетради.

Какие информационные модели относят к графическим? Приведите примеры графических информационных моделей, с которыми вы имеете дело: а) при изучении других предметов; б) в повседневной жизни. Что такое граф? Что является вершинами и рёбрами графа? Укажите на собственном графе-примере. Какой граф называют ориентированным? Какой граф называют взвешенным? Какие графы называют изоморфными?
Что такое степень вершины? Укажите степени вершин в вашем графе. Сформулируйте теорему о чётности числа нечетных вершин. Какой граф называют связным? Изобразите граф с двумя компонентами связности. Какую вершину называют изолированной? Укажите на собственном примере – графе. Какую вершину называют висячей? Укажите на собственном примере – графе. Что такое путь? Что такое цепь? Что такое цикл? Укажите на собственном примере – графе. Что такое граф-дерево? Моделями каких систем могут служить де­ревья? Приведите пример такой системы. Составьте семантическую сеть по русской народной сказке «Колобок».

Источник