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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16 Выполните задание в рабочей тетради 64 – 65 с

17

18

19 «Похищение века» Встреча злоумышленников должна состояться в городе N -ска, до которого надо добираться один час. Неизвестно, на какой вокзал прибывает связной – их в городе три: от центра расположены в 15, 30 и 45 минутах ходьбы. Чтобы запутать следы, связной знакомится в центре(где он был замечен) с девушкой, и приглашает ее в кафе. В городе 3 кофейни, - в 5, 10 и 15 минутах от центра. В каком кафе можно поймать злоумышленников, если звонок связного из кафе сообщнику о том, что его уже ждут, запеленговали через полтора часа с момента отправки в город N -ск?

20 §2.10. с. 101 – 104; РТ 60,61,66 с. 78, 81.