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

Фронтальный опрос

• Что такое табличные модели?
• Что такое графические модели?
• Какие табличные модели существуют?

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

Существуют 4 группы крови. При переливании крови от одного человека к другому не все группы совместимы. Но известно, что одинаковые группы можно переливать от человека к человеку, т.е. 1 – 1, 2 – 2 и т.д. А также 1 группу можно переливать всем остальным группам, 2 и 3 группу только 4 группе.

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

Донор

IY

II

I

III

Реципиент

III

II

I

IY

Реципиент

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

Донор

Группы крови

I

I

II

+

II

III

+

III

+

IV

IV

+

+

+

+

+

+

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

I

III

II

IV

Графы

Ненаправленный граф

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

с.Бор

д. Косы

ст. Луг

Вершина

д. Око

Ребро

Отношения: соединены дорогой

Дуга

д. Сыны

Отношение – это связи между элементами

(симметричные связи)

Неоднородный граф

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

Управление работой

Процессор

Иван Ильич

Устр-во вывода

Устр-во ввода

Передача информации

Внук Олег

Память

Состав графа

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

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

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

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

ребро

дуга

В

петля

А

С

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

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

Юра

Аня

Маша

Витя

Коля

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

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

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

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

Юра

Аня

Маша

Витя

Коля

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

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

Юра

Аня

Маша

Витя

Коля

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

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

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

182

127

158

Москва, 1147

Владимир, 1108

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

Каким весом характеризуются вершины и дуги данного графа?

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

указала

пустил

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

Баба Яга

сжег

нашел

Стрела

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

Лягушка

прилетела

победил

сбросила

нашел

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

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

Лебедь

улетела

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

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

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

Саша

Маша

Цикл

Даша

Гриша

Тип связи – «многие ко многим»

Иерархия -

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

Директор

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

Учителя

Ученики

Иерархические системы

ИС – системы, элементы которых находятся друг с другом в отношении вложенности или подчинённости.

Корень

Ветви

Листья

Тип связи – «один ко многим»

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

компьютер

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

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

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

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

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

настольный

портативный

карманный

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

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

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

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

Укажите перечисленные объекты у дерева

Чемпион

Финалисты

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

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

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

Проанализируем таблицу. Такую таблицу называют весовой матрицей . Какие особенности в таблице вы заметили?

A

A

B

B

2

C

2

C

10

10

D

D

E

9

9

8

8

E

16

16

1

1

3

3

4

4

11

11

Части таблицы, разделённые диагональю – симметричны, т.е. содержат одни и те же данные. Следовательно, можно рассматривать данные любой половины таблицы, разделенной диагональю.

Теперь приступим к построению графа.

A

A

B

B

C

C

2

2

10

10

D

D

8

9

8

E

9

E

16

16

1

1

3

3

4

4

11

11

Проверим правильность построения

B

2

1

A

A

B

B

2

C

2

C

10

10

D

D

8

E

E

9

9

8

16

16

1

1

3

3

4

4

11

11

9

A

8

10

D

3

C

16

4

11

E

Определим все пути в графе и расстояние, пройденное на этом пути (вес-расстояние в км.)

B

2

Будем делать обход по графу в алфавитном порядке, т.е. сначала все пути через АВ, АС, AD и т.д.

1

9

A

8

10

D

3

1.ABCDE – 25 км

C

2.ABCE – 15 км

3.ABDCE – 10 км

16

4

4.ACBDE – 31 км

11

5.ACDE – 24 км

6.ACE – 14 км

7.ADCE – 15 км

8.ADE – 19 км

9.AE – 16 км

E

Кратчайший путь в данном графе : ABDCE – 10 км

B

2

1

A

A

B

B

2

C

2

C

10

10

D

D

8

E

E

9

9

8

16

16

1

1

3

3

4

4

11

11

9

A

8

10

D

3

C

16

4

11

E

Итог урока

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

Домашнее задание

• Параграф 2.1 читать
• Учить определения
• Ответь письменно на вопросы на стр. 67 № 1, 2, 10