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