Графы. Состав графа

1. ГРАФЫ

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

2. Состав графа

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

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

3 из 15

4. Неориентированный граф -

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