Граф состоит из вершин, связанных линиями.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.
Граф - наглядное средство представления состава и структуры системы. Граф состоит из вершин, связанных линиями. Направленная линия называется дугой, ненаправленная – ребром.
Иерархия - расположение частей (элементов) целого в порядке от высшего к низшему. Системы, элементы которых находятся в отношениях подчиненности, называются иерархическими системами.
Дерево - граф иерархической системы. Между любыми двумя вершинами дерева существует единственный путь.
Л.Л. Босова, УМК по информатике для 5-7
классов
ГРАФЫ
Москва,
2007
1 из 15
Состав графа
Граф состоит из вершин, связанных линиями.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется
ребром.
Линия, выходящая из некоторой вершины и входящая в
неё же, называется петлей.
дуга
В
ребро
А
петля
С
2 из 15
Изображение
вершин
3 из 15
Неориентированный
граф
граф, вершины которого соединены ребрами. С
помощью таких графов могут быть представлены
схемы двухсторонних (симметричных) отношений.
Юра
Маша
Коля
Аня
Витя
Граф, отражающий отношение
«переписываются» между объектами класса
«дети»
4 из 15
Граф отношения
«переписываются»
Цепь – путь по вершинам и ребрам, включающий
любое ребро графа не более одного раза.
Цикл – цепь, начальная и конечная вершины которой
совпадают. Граф с циклом называют сетью.
Юра
Маша
Коля
Аня
Витя
Приведите примеры цепи и цикла.
5 из 15
Ориентированный
граф
граф, вершины которого соединены дугами. С
помощью таких графов могут быть представлены
схемы односторонних отношений.
Юра
Аня
Маша
Коля
Витя
Граф, отражающий отношение «пишет письма».
Приведите примеры цепи и цикла.
6 из 15
Взвешенный граф
граф, у которого вершины или рёбра (дуги) несут
дополнительную информацию (вес).
182
127
158
Москва, 1147
Владимир, 1108
Переславль Залесский, 1152
Каким весом характеризуются вершины и дуги данного графа?
7 из 15
Семантическая сеть
пустил
ИванЦаревич
указала
Баба Яга
Стрела
нашел
сжег
Лягушачья кожа
прилетела
Лягушка
превратилась
сбросила
победил
нашел
Василиса Прекрасная
Лебедь
превратилась
улетела
Кощей Бессмертный
8 из 15
Иерархия -
это расположение частей или элементов целого в
порядке от высшего к низшему.
Директор
Заместители директора
Учителя
Ученики
Отношения подчиненности в школе
9 из 15
Дерево – граф иерархической
структуры. Между любыми двумя его вершинами
существует единственный путь. Дерево не
содержит циклов и петель.
компьютер
суперкомпьютер
рабочая станция
персональный
компьютер
настольный
портативный
карманный
Классификация компьютеров
10 из 15
Корень – главная вершина дерева.
Предок – объект верхнего уровня.
Потомок – объект нижнего уровня.
Листья – вершины, не имеющие потомков.
Укажите перечисленные объекты у дерева
Чемпион
Финалисты
Участники ½ финала
Участники ¼ финала
Первоначальные игроки
Олимпийская система спортивных соревнований
11 из 15
Файловая структура
Укажите корневую вершину, объекты 1го, 2го и 3го уровней
12 из 15
Самое главное
• Граф наглядное средство представления
состава и структуры системы. Граф состоит из
вершин, связанных линиями. Направленная линия
называется дугой, ненаправленная – ребром.
• Иерархия расположение частей (элементов)
целого в порядке от высшего к низшему. Системы,
элементы которых находятся в отношениях
подчиненности, называются иерархическими
системами.
• Дерево граф иерархической системы. Между
любыми двумя вершинами дерева существует
единственный путь.
13 из 15
Давайте обсудим
1. Какая связь между графом и таблицей на
рисунке?
14 из 15
Давайте обсудим
2. Как называется взвешенный граф иерархической
структуры, представляющий родственные связи семьи?
15 из 15
Графы.ppt
