Файл: Урок 25. Представление об ориентированных графах Состав графа Граф состоит из вершин, связанных линиями.ppt

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

А

В

С

петля

ребро

дуга

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

Графы

Неориентированные

Ориентированные

- графы, вершины которых соединены дугами

- графы, вершины которых соединены ребрами

С помощью таких графов
могут быть представлены
схемы двухсторонних
(симметричных) отношений.

С помощью таких графов
могут быть представлены
схемы односторонних
отношений.

Пример

Неориентированного графа

Ориентированного графа

Граф, отражающий отношение
«переписываются» между
объектами класса «дети»

Юра

Аня

Витя

Коля

Маша

Граф, отражающий
отношение
«пишет письма»

Юра

Аня

Витя

Коля

Маша

- граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).

Москва, 1147

Переславль Залесский, 1152

Владимир, 1108

Взвешенный граф

182

158

127

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

Юра

Аня

Витя

Коля

Маша

Юра

Аня

Витя

Коля

Маша

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

улетела

превратилась

превратилась

сбросила

нашел

сжег

Иван-Царевич

Стрела

Василиса Прекрасная

Баба Яга

Лебедь

Кощей Бессмертный

Лягушачья кожа

пустил

прилетела

указала

нашел

победил

Лягушка

Иерархия

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

Директор

Заместители директора

Учителя

Ученики

Отношения подчиненности в школе

Дерево

Классификация компьютеров

компьютер

суперкомпьютер

рабочая станция

персональный компьютер

настольный

портативный

карманный

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

Чемпион

Финалисты

Участники ½ финала

Участники ¼ финала

Первоначальные игроки

Корень – главная вершина дерева
Предок – объект верхнего уровня
Потомок – объект нижнего уровня
Листья – вершины, не имеющие потомков

Олимпийская система спортивных соревнований