Тема урока:
«Системы, модели, графы.
Построение информационной модели в виде графа.»
Понятие СИСТЕМЫ и ГРАФА
Система – это объект, состоящий из взаимосвязанных элементов и существующий как единое целое.
ГРАФЫ
- Граф –информационная модель, представленная в графической форме.
- Граф состоит из вершин, связанных линиями.
- Впервые основы теории графов появились в работах Леонарда Эйлера (1707-1783; швейцарский, немецкий и российский математик ) , в которых он описывал решение головоломок и математических развлекательных задач.
- Теория графов началась с решения Эйлером задачи о семи мостах Кёнигсберга.
Информационные модели на графах
Граф состоит из вершин , связанных линиями.
Направленная линия (со стрелкой) называется дугой .
Линия ненаправленная (без стрелки) называется ребром .
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей .
ребро
дуга
В
вершина
петля
А
С
ПЕРЕЛИВАНИЕ КРОВИ
I
II
III
IV
Изображение вершин графа
ВИДЫ ГРАФОВ
- Неориентированный граф
- Ориентированный граф (орграф)
- Взвешенный граф
Неориентированный граф
Неориентированный граф - граф, вершины которого соединены ребрами.
С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений.
Юра
Аня
Маша
Витя
Коля
Граф, отражающий отношение «переписываются» между объектами класса «дети»
Ориентированный граф (орграф)
Ориентированный граф - граф, вершины которого соединены дугами.
С помощью таких графов могут быть представлены схемы односторонних отношений.
Юра
Аня
Маша
Витя
Коля
Граф, отражающий отношение «пишет письма».
Взвешенный граф
Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).
182
127
158
Москва, 1147
Владимир, 1108
Переславль Залесский, 1152
Типы моделей на графах
- Иерархия (дерево). Принцип связи – «один ко многим».
- Сеть. Принцип связи – «многие ко многим».
Информационные модели на графах
Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему.
Директор
Заместители директора
Учителя
Ученики
Отношения подчиненности в школе
Информационные модели на графах
Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь.
компьютер
суперкомпьютер
рабочая станция
персональный компьютер
настольный
портативный
карманный
Классификация компьютеров
Генеалогическое дерево Романовых
Домашнее задание:
Построить граф, отражающий семейное дерево ученика в текстовом редакторе Word.
Выучить тему: «Системы, модели, графы»