1 из 15 ГРАФЫ Л.Л. Босова, УМК по информатике для 5-7 классов Москва, 2007

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

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

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

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

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

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

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

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

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

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

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

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

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

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