Информационные модели на графах

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

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

Сети Маша Юра Аня Витя Коля Граф, отражающий отношение «переписываются» между объектами класса «дети» Граф называется неориентированным, если его вершины соединены ребрами

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

Сети Маша Юра Аня Витя Коля Цепь, начальная и конечная вершины которой совпадают, называются циклом. Пример цикла: Аня – Коля – Витя – Аня

Сети Граф называется ориентированным, если его вершины соединены дугами Маша Юра Аня Витя Коля

Сети Москва, 1147 Переславль Залесский, 1152 Владимир, Граф называется взвешенным, если его вершины или ребра (дуги) характеризуются некоторой дополнительной информацией – весом вершины или ребра (дуги)

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

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

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

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

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

Графы при решении задач Сколькими способами можно рассадить в ряд на три стула трёх учеников? Выписать все возможные случаи. Чтобы выписать все случаи, решение можно представить в виде дерева. ??

Решение в виде дерева О На первый стул посадим любого ученика: А,В,С Если на первом стуле сидит ученик А, то на второй стул можно посадить В или С. Действуем аналогично и для других учеников. Очевидно, что третий стул в каждом случае займёт оставшийся ученик А В С ВСАСАВ СВС А А В Выпишем все возможные случаи: А-В-С, А-С-В, В-А-С, В-С-А, С-А-В, С-В-А.

Домашнее задание РТ: 147 (стр. 131), 150 (стр. 133), 152 (стр. 134) На дополнительную оценку: 148 (стр. 131), 160 (стр. 141)