Информационные модели на графах Использование графов при решении задач СХЕМЫ. - презентация

1 Информационные модели на графах Использование графов при решении задач СХЕМЫ

2 Ключевые слова Граф Сеть Дерево

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

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

5 В социальной сети VK зарегистрированы Маша, Юра, Аня, Коля, Витя. Некоторые ребята дружат между собой. Маша, Юра и Аня могут видеть сообщения на «стене» друг друга. Аня, Коля и Витя тоже оставляют комментарии друг другу. Изобразите при помощи графа кто с кем дружит.

6 Неориентированный граф С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений. Маша Юра Аня Витя Коля Граф, отражающий отношение «переписываются» между объектами класса «дети» Неориентированный граф - граф, вершины которого соединены ребрами.

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

8 Как можно при помощи графа изобразить ситуацию: Маша пишет письмо Юре, Юра – Ане, Аня – Маше, Вити и Коле, а Витя пишет Коле?

9 Ориентированный граф Ориентированный граф Ориентированный граф - граф, вершины которого соединены дугами. Граф, отражающий отношение «пишет письма». Приведите примеры цепи и цикла. ?? С помощью таких графов могут быть представлены схемы односторонних отношений. Маша Юра Аня Витя Коля РТ 146

10 Изобразите с помощью графа следующую информацию: Город Год основания Москва Переславль Залесский Владимир Москва км 182 км Переславль Залесский км 158 км Владимир км 158 км

11 Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес). Каким весом характеризуются вершины и дуги данного графа? ?? Взвешенный граф Москва, 1147 Переславль Залесский, 1152 Владимир, РТ 151

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

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

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

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

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

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

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

19 Самое главное Схема - это представление объекта в общих, главных чертах с помощью условных обозначений. Граф - наглядное средство представления состава и структуры системы. Граф состоит из вершин, связанных линиями. Направленная линия называется дугой, ненаправленная – ребром. Иерархия - расположение частей (элементов) целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях подчиненности, называются иерархическими системами. Дерево - граф иерархической системы. Между любыми двумя вершинами дерева существует единственный путь.

20 1. Приведите примеры схем, представляющих внешний вид объекта. 2. Приведите примеры схем, представляющих структуру объекта. 3. В каких сферах деятельности невозможно обойтись без карт? 4. Где применяются чертежи? 5. Всякая ли схема может претендовать на полноту представления информации об объекте? Давайте обсудим ??

21 6. Какая связь между графом и таблицей на рисунке? 7. Как называется взвешенный граф иерархической структуры, представляющий родственные связи семьи? Давайте обсудим ??