Информационные модели на графах Использование графов при решении задач СХЕМЫ
Ключевые слова Граф Сеть
Информационные модели на графах Граф состоит из вершин, связанных линиями. Направленная линия (со стрелкой) называется дугой. Линия ненаправленная (без стрелки) называется ребром. Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей. АА ВВ СС петля ребро дуга
Изображение вершин графа
В социальной сети VK зарегистрированы Маша, Юра, Аня, Коля, Витя. Некоторые ребята дружат между собой. Маша, Юра и Аня могут видеть сообщения на «стене» друг друга. Аня, Коля и Витя тоже оставляют комментарии друг другу. Изобразите при помощи графа кто с кем дружит.
Неориентированный граф С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений. Маша Юра Аня Витя Коля Граф, отражающий отношение «переписываются» между объектами класса «дети» Неориентированный граф - граф, вершины которого соединены ребрами.
Граф отношения «переписываются» Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза. Цикл – цепь, начальная и конечная вершины которой совпадают. Граф с циклом называют сетью. Приведите примеры цепи и цикла. ?? Маша Юра Аня Витя Коля
Как можно при помощи графа изобразить ситуацию: Маша пишет письмо Юре, Юра – Ане, Аня – Маше, Вити и Коле, а Витя пишет Коле?
Ориентированный граф Ориентированный граф Ориентированный граф - граф, вершины которого соединены дугами. Граф, отражающий отношение «пишет письма». Приведите примеры цепи и цикла. ?? С помощью таких графов могут быть представлены схемы односторонних отношений. Маша Юра Аня Витя Коля РТ 60 с.78
Изобразите с помощью графа следующую информацию: Город Год основания Москва Переславль Залесский Владимир Москва км 182 км Переславль Залесский км 158 км Владимир км 158 км
Взвешенный граф - граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес). Каким весом характеризуются вершины и дуги данного графа? ?? Взвешенный граф Москва, 1147 Переславль Залесский, 1152 Владимир, РТ 65 с. 80
Семантическая сеть Иван- Царевич Стрела Лягушка Василиса Прекрасная Баба Яга Лебедь Кощей Бессмертный Лягушачья кожа пустил нашёл прилетела сбросила сжёг превратилась улетела указала нашёл победил
Информационные модели на графах Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему. Директор Заместители директора Учителя Ученики Отношения подчиненности в школе
Классификация компьютеров Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель. компьютер суперкомпьютер рабочая станция персональный компьютер настольныйнастольныйпортативныйпортативныйкарманныйкарманный Информационные модели на графах
Файловая структура Укажите корневую вершину, объекты 1-го, 2-го и 3-го уровней. ?? РТ 62 с. 78
Выполните задание в рабочей тетради 64 – 65 с
«Похищение века» Встреча злоумышленников должна состояться в городе N -ска, до которого надо добираться один час. Неизвестно, на какой вокзал прибывает связной – их в городе три: от центра расположены в 15, 30 и 45 минутах ходьбы. Чтобы запутать следы, связной знакомится в центре(где он был замечен) с девушкой, и приглашает ее в кафе. В городе 3 кофейни, - в 5, 10 и 15 минутах от центра. В каком кафе можно поймать злоумышленников, если звонок связного из кафе сообщнику о том, что его уже ждут, запеленговали через полтора часа с момента отправки в город N -ск?
§2.10. с. 101 – 104; РТ 60,61,66 с. 78, 81.