ГРАФЫ

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

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

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

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

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

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

Семантическая сеть

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

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

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

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

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

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