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

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

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

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

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

Москва, 1147Переславль Залесский, 1152Владимир, 1108Взвешенный граф 182158127 Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза. Цикл – цепь, начальная и конечная вершины которой совпадают. Граф с циклом называют сетью. ЮраАняВитяКоляМаша

ЮраАняВитяКоля Маша

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

улетелапревратиласьпревратиласьсбросиланашелсжегИван-ЦаревичСтрелаВасилиса ПрекраснаяБаба ЯгаЛебедьКощей БессмертныйЛягушачья кожапустилприлетелауказаланашелпобедилЛягушка

Иерархия

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

Дерево

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