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

Август 22, 2022

Главная
Информатика
Информационные модели на графах

Содержание

2. Граф Наглядным средством представления состава и структуры системы является граф. Граф состоит из вершин, связанных линиями.
3. Состав графа Направленная линия (со стрелкой) называется дугой. Линия ненаправленная (без стрелки) называется ребром. Линия, выходящая
4. Неориентированный граф Рассмотрим отношение «дети переписываются» (пишут письма друг другу). Отношение является двухсторонним, поэтому вершины соединены
5. Неориентированный граф Маша Юра Коля Витя Аня Цепь – путь по вершинам и ребрам, включающий любое
6. Ориентированный граф Маша Юра Коля Витя Аня Ориентированный граф - граф, вершины которого соединены дугами. С
7. Взвешенный граф Каким весом характеризуются вершины и дуги данного графа? Москва, 1147 Переславль Залесский, 1152 Владимир,
8. Семантическая сеть
9. Иерархия Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему. Системы,
10. Дерево Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не
11. Дерево Чемпион Финалисты Участники ½ финала Участники ¼ финала Первоначальные игроки Укажите перечисленные объекты у дерева
12. Файловая структура Укажите корневую вершину, объекты 1-го, 2-го и 3-го уровней
13. Задача 1 Какая связь между графом и таблицей на рисунке?
14. Задача 2 (Ответ: 2)
15. Задача 3 На схеме нарисованы дороги между пятью населенными пунктами A, B, C, D, E и
16. Задача 4 Между населенными пунктами A, B, C, D построены дороги, протяженность которых приведена в таблице:
17. Задача 5 На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж,
18. Задача 6 На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, К.
19. Решение задачи 6 Начнем с конца. В точку К можно попасть двумя способами: из точки Д
22. Скачать презентацию

Слайд 2

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

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

Слайд 3

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

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

дуга

ребро

петля

Слайд 4

Неориентированный граф
Рассмотрим отношение «дети переписываются» (пишут письма друг другу). Отношение является

двухсторонним, поэтому вершины соединены линиями без стрелок.

Маша

Юра

Коля

Витя

Аня

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

Слайд 5

Неориентированный граф
Маша
Юра
Коля
Витя
Аня
Цепь – путь по вершинам и ребрам, включающий любое ребро

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

Слайд 6

Ориентированный граф
Маша
Юра
Коля
Витя
Аня
Ориентированный граф - граф, вершины которого соединены дугами.
С помощью

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

Слайд 7

Взвешенный граф
Каким весом характеризуются вершины и дуги данного графа?
Москва, 1147
Переславль Залесский,

1152

Владимир, 1108

182

158

127

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

Слайд 8

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

Слайд 9

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

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

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

Слайд 10

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

единственный путь. Дерево не содержит циклов и петель.

Слайд 11

Дерево
Чемпион
Финалисты
Участники ½ финала
Участники ¼ финала
Первоначальные игроки
Укажите перечисленные объекты у дерева
Корень –

главная вершина дерева.
Предок – объект верхнего уровня.
Потомок – объект нижнего уровня.
Листья – вершины, не имеющие потомков.

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

Слайд 12

Файловая структура
Укажите корневую вершину, объекты 1-го, 2-го и 3-го уровней

Слайд 13

Задача 1
Какая связь между графом и таблицей на рисунке?

Слайд 14

Задача 2
(Ответ: 2)

Слайд 15

Задача 3
На схеме нарисованы дороги между пятью населенными пунктами A, B,

C, D, E и указаны протяженности данных дорог.
Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам).
В ответе укажите кратчайшее расстояние между
этими пунктами.
1) 8 2) 7 3) 6 4) 4

(Ответ: 1)

Слайд 16

Задача 4
Между населенными пунктами A, B, C, D построены дороги, протяженность

которых приведена в таблице:
Определите кратчайший путь между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).
1) 45
2) 55
3) 60
4) 70

(Ответ: 2)

Слайд 17

Задача 5
На рисунке — схема дорог, связывающих города А, Б, В,

Г, Д, Е, Ж, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Ответ: 6 (АГДК, АБДЕЖК, АВДУЖК, АВДК, АБДК, АГДЕЖК)

Слайд 18

Задача 6
На рисунке – схема дорог, связывающих города А, Б, В,

Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Слайд 19

Решение задачи 6
Начнем с конца. В точку К можно попасть двумя

способами: из точки Д и из точки Е.
В точку Д можно попасть из точек Б и В. А в точку Е из точек В и Г и т.д. Ход рассуждения отображен на схематичном рисунке.
Из рисунка видно, что у нас получилось различных 8 путей от начального пункта А до конечного пункта К.
Ответ: 8

Слайд 20

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

Содержание

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

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

Неориентированный графРассмотрим отношение «дети переписываются» (пишут письма друг другу). Отношение является

Неориентированный графМашаЮраКоляВитяАняЦепь – путь по вершинам и ребрам, включающий любое ребро

Ориентированный графМашаЮраКоляВитяАняОриентированный граф - граф, вершины которого соединены дугами. С помощью

Взвешенный графКаким весом характеризуются вершины и дуги данного графа?Москва, 1147Переславль Залесский,

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

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

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

ДеревоЧемпионФиналистыУчастники ½ финалаУчастники ¼ финалаПервоначальные игрокиУкажите перечисленные объекты у дереваКорень –

Файловая структураУкажите корневую вершину, объекты 1-го, 2-го и 3-го уровней

Задача 1Какая связь между графом и таблицей на рисунке?

Задача 2(Ответ: 2)

Задача 3На схеме нарисованы дороги между пятью населенными пунктами A, B,

Задача 4Между населенными пунктами A, B, C, D построены дороги, протяженность

Задача 5На рисунке — схема дорог, связывающих города А, Б, В,

Задача 6На рисунке – схема дорог, связывающих города А, Б, В,

Решение задачи 6Начнем с конца. В точку К можно попасть двумя

Похожие презентации