Информационные модели на графах. Состав графа Наглядным средством представления состава и структуры системы является граф. Граф состоит из вершин, связанных. - презентация

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

2 Состав графа Наглядным средством представления состава и структуры системы является граф. Граф состоит из вершин, связанных линиями. Линия, направленная (со стрелкой), называется дугой. Линия, ненаправленная (без стрелки) называется ребром. Линия, выходящая из некоторой вершины и входящая в нее же, называется петлей.

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

4 Сети Маша Юра Аня Витя Коля Граф, отражающий отношение «переписываются» между объектами класса «дети» Граф называется неориентированным, если его вершины соединены ребрами

5 Сети Маша Юра Аня Витя Коля Путь по вершинам и ребрам графа, включающий любое ребро графа не более одного раза, называется цепью. Пример цепи: Юра – Аня – Витя – Коля

6 Сети Маша Юра Аня Витя Коля Цепь, начальная и конечная вершины которой совпадают, называются циклом. Пример цикла: Аня – Коля – Витя – Аня

7 Сети Граф называется ориентированным, если его вершины соединены дугами Маша Юра Аня Витя Коля

8 Сети Москва, 1147 Переславль Залесский, 1152 Владимир, Граф называется взвешенным, если его вершины или ребра (дуги) характеризуются некоторой дополнительной информацией – весом вершины или ребра (дуги)

9 Семантическая сеть Иван-Царевич Стрела Лягушка Василиса Прекрасная Баба Яга Лебедь Кощей Бессмертный Лягушачья кожа пустил нашел прилетела сбросила сжег превратилась улетела указала нашел победил

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

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

12 Чемпион Финалисты Участники ½ финала Участники ¼ финала Первоначальные игроки Укажите перечисленные объекты у дерева Корень – главная вершина дерева. Предок – объект верхнего уровня. Потомок – объект нижнего уровня. Листья – вершины, не имеющие потомков. Корень – главная вершина дерева. Предок – объект верхнего уровня. Потомок – объект нижнего уровня. Листья – вершины, не имеющие потомков. Олимпийская система спортивных соревнований ??

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

14 Графы при решении задач Сколькими способами можно рассадить в ряд на три стула трёх учеников? Выписать все возможные случаи. Чтобы выписать все случаи, решение можно представить в виде дерева. ??

15 Решение в виде дерева О На первый стул посадим любого ученика: А,В,С Если на первом стуле сидит ученик А, то на второй стул можно посадить В или С. Действуем аналогично и для других учеников. Очевидно, что третий стул в каждом случае займёт оставшийся ученик А В С ВСАСАВ СВС А А В Выпишем все возможные случаи: А-В-С, А-С-В, В-А-С, В-С-А, С-А-В, С-В-А.

16 Домашнее задание РТ: 147 (стр. 131), 150 (стр. 133), 152 (стр. 134) На дополнительную оценку: 148 (стр. 131), 160 (стр. 141)