Схема граф сеть дерево

Информатика 1101

Информационные модели на графах. Использование графов при решении задач.
Практическая работа №14 «Создаём информационные модели – схемы, графы, деревья» (задания 4 и 6)

Презентация «Схемы»

Информационные модели на графах

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

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

Например, граф, отражающий отношение «переписываются» между объектами класса «дети», может выглядеть, как показано на рис. 44.

Отношение «переписываются» («пишут письма друг другу») яв¬ляется двухсторонним (симметричным). Поэтому соответствующие вершины соединены линиями без стрелок (рёбрами).

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

Иначе выглядит граф, отражающий отношение «пишет письма» между теми же объектами класса «дети». Линии со стрелками (дуги) придают ему совершенно иной смысл (рис. 45).

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

На рисунке 46 информация о городах Золотого кольца представлена взвешенным графом: веса его вершин — года основания городов, веса рёбер — расстояния в километрах между городами.

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

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

Деревья

Иерархия — это расположение частей или элементов целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях «является разновидностью», «входит в состав» и других отношениях подчинённости, называются иерархическими системами (системами с иерархической структурой).

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

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

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

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

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

Иерархию легко изобразить «лесенкой» — в виде многоуровневого списка. Объекты одного уровня иерархии располагаются на одном уровне в списке. Чем ниже уровень иерархии, тем правее находится соответствующий уровень списка:

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

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

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

Задача 1

Решение этой задачи удобнее всего представить в виде дерева. За его корневую вершину возьмём произвольную точку плоскости О.

На первый стул можно посадить любого из трёх учеников — обозначим их А, В л С. На схеме это соответствует трём ветвям, исходящим из точки О (рис. 51).

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

Очевидно, что третий стул в каждом случае займёт оставшийся ученик. Это соответствует одной ветви дерева, которая «вырастает» на каждой из предыдущих ветвей (рис. 53).

Выпишем все пути от вершин первого уровня к вершинам третьего уровня: А-В-Су А-С-В, В-А-С, В-С-А, С-А-Б, С-В-А. Каждый из выписанных путей определяет один из вариантов рассаживания учеников на стулья. Так как других путей нет, то искомое число способов — 6.

Дерево можно не строить, если не требуется выписывать все возможные варианты, а нужно просто указать их число. В этом случае рассуждать нужно так: на первый стул можно усадить одного из трёх человек, на второй — одного из двух оставшихся, на третий — одного оставшегося: 3-2-1 = 6.

Задача 2

Чтобы принести Царю-батюшке молодильные яблоки, должен Иван-царевич найти единственный верный путь к волшебному саду. Встретил Иван-царевич на развилке трёх дорог старого ворона и вот какие советы от него услышал:

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

Обозначим левую, среднюю и правую тропинки соответственно Л, С и П. Возможные маршруты представим в виде графа. При этом подсказки ворона отметим более «жирными» рёбрами. Так как только один совет ворона верен, то на графе ему будет соответствовать маршрут, имеющий одно «жирное» ребро. Этот маршрут обозначен дополнительной пунктирной линией (рис. 54).

Вопросы и задания

1. Приведите 2-3 примера схем, с которыми вы сталкиваетесь в повседневной жизни. Информационными моделями каких объектов являются эти схемы?

2. На каждом этаже в вашей школе должен быть план эвакуации при пожаре. Найдите и изучите его. Какие объекты представлены на этой схеме?

3. В каких сферах деятельности невозможно обойтись без карт — информационных моделей поверхности Земли?

5. С разных сторон на холм поднимаются три тропинки и сходятся на вершине. Перечислите множество маршрутов, по которым можно подняться на холм и спуститься с него. Решите ту же задачу, если вверх и вниз надо идти по разным тропинкам.

6. Сколько трёхзначных чисел можно записать с помощью цифр 1, 3, 5 и 7 при условии, что в записи числа не должно быть одинаковых цифр?

Источник