Графы построение информационной модели

Тема урока:

«Системы, модели, графы.

Построение информационной модели в виде графа»

Понятие СИСТЕМЫ и ГРАФА

Система – это объект, состоящий из взаимосвязанных элементов и существующий как единое целое (из учебника).

Система – это целое, состоящее из объектов, взаимосвязанных между собой (человек, книга, обучение в школе и т.д.).

Граф – это средство для наглядного представления состава и структуры системы.

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

Граф состоит из вершин , связанных линиями.

Направленная линия (со стрелкой) называется дугой .

Линия ненаправленная (без стрелки) называется ребром .

Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей .

ребро

дуга

В

вершина

петля

А

С

ПЕРЕЛИВАНИЕ КРОВИ

I

II

III

IV

Изображение вершин графа

ГРАФЫ

• Граф –это схема являющаяся наглядным представлением состава и структуры системы.
• Граф состоит из вершин, связанных линиями.

Генеалогическое дерево Романовых

ВИДЫ ГРАФОВ

• Неориентированный граф
• Ориентированный граф (орграф)
• Взвешенный граф

Неориентированный граф

Неориентированный граф - граф, вершины которого соединены ребрами.

С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений.

Юра

Аня

Маша

Витя

Коля

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

Граф отношения «Переписываются»

Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза.

Цикл – цепь, начальная и конечная вершины которой совпадают.

Граф с циклом называют сетью .

Юра

Аня

Маша

Витя

Коля

Ориентированный граф (орграф)

Ориентированный граф - граф, вершины которого соединены дугами.

С помощью таких графов могут быть представлены схемы односторонних отношений.

Юра

Аня

Маша

Витя

Коля

Граф, отражающий отношение «пишет письма».

Взвешенный граф

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

182

127

158

Москва, 1147

Владимир, 1108

Переславль Залесский, 1152

Типы моделей на графах

• Иерархия (дерево). Принцип связи – «один ко многим».
• Сеть. Принцип связи – «многие ко многим».

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

Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему.

Директор

Заместители директора

Учителя

Ученики

Отношения подчиненности в школе

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

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

компьютер

суперкомпьютер

рабочая станция

персональный компьютер

настольный

портативный

карманный

Классификация компьютеров

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

Корень – главная вершина дерева.

Предок – объект верхнего уровня.

Потомок – объект нижнего уровня.

Листья – вершины, не имеющие потомков.

Чемпион

Финалисты

Участники ½ финала

Участники ¼ финала

Первоначальные игроки

Олимпийская система спортивных соревнований

Семантическая сеть

Иван-Царевич

указала

Баба Яга

пустил

Стрела

сжёг

нашёл

Лягушачья кожа

прилетела

Лягушка

сбросила

нашёл

победил

превратилась

Лебедь

Василиса Прекрасная

превратилась

улетела

Кощей Бессмертный

Практическая часть. Задание:

Построить граф, отражающий семейное дерево ученика в текстовом редакторе Word.