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

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

Структура дерева: Корень ( единственная вершина 1-го уровня) Вершины 2-го уровня Вершины 3-го уровня

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

Задача 1. Изображена система возможного переливания крови. I II II III III IV

Укажите: Тип графа Вершины Тип линий связей Какую кровь может получить человек с первой группой, со второй группой, с третьей группой, с четвертой группой крови?

Задача 2. Нарисуйте в виде графа систему, состоящую из одноклассников, между которыми существуют следующие взаимоотношения: дружат Андрей и Даша, Андрей и Маша, Даша и Коля, Коля и Андрей. С кем Андрей может поделиться секретом, не рискуя, что он станет известен кому-то другому?

Задача 3. Приведите примеры объектов, имеющих следующие структуры: 1) 2) 3)

Задача 4. Постройте блок-схему для какого-либо правила по русскому языку или по математике. Домашнее задание: Постройте своё родословное дерево по линии одного из родителей. Постройте граф для одной из следующих систем и укажите тип, вершины, тип связей между вершинами: - зонтик - стул - фломастер