Автор: Пользователь скрыл имя, 22 Ноября 2012 в 19:05, лабораторная работа
Изучение основ теории графов, базовых понятий и определений; ознакомление с задачами, возникающими в теории графов и методами их решения; освоение компьютерных способов представления графов и алгоритмов машинной обработки графов. Освоение компьютерных технологий обработки графов; изучение специализированных программных продуктов для ввода, редактирования и анализа графов на ЭВМ.
1. Цель работы_________________________________________________________________ 3
2. Практическая часть___________________________________________________________ 4
2.1 Задание 1____________________________________________________________ 4
2.2. Задание 2____________________________________________________________ 5
2.3. Задание 3____________________________________________________________ 7
2.4. Задание 4____________________________________________________________ 9
2.5. Задание 5____________________________________________________________ 9
2.6. Задание 6____________________________________________________________ 10
2.7. Задание 7____________________________________________________________ 11
2.8. Задание 8____________________________________________________________
В отчете представить построенный граф с выделенным деревом, центром и периферией, над вершинами надписать их эксцентриситеты, указать значения радиуса и диаметра графа (1 картинка).
Эксцентриситеты вершин:
ехс(1)=2; ехс(2)=5; ехс(3)=3; ехс(4)=4; ехс(5)=2; ехс(6)=4; ехс(7)=5; ехс(8)=3.
Центральные вершины:
1, 5 (ехс=2).
Периферийные вершины:
2, 7 (ехс=5).
Обычные вершины:
4, 6 (ехс=4), 3, 8(ехс=3).
Радиус графа:
R=exc(1)=ехс(5)=2¹0.
Диаметр графа:
D=exc(2)=ехс(7)=5¹R.
2.9. Задание 9
Придумать 6 свойств некой системы из 16 элементов. Построить ориентированный граф системы, задать в качестве вспомогательного веса вершин текстовые идентификаторы, а в качестве основного веса – бинарные цепочки (ширина равна количеству свойств). Проставить на вершинах основные веса в виде цепочки нулей и единиц в зависимости от того обладает вершина соответствующим свойством (1) или нет (0). Используя метод «свертка по кодам» выполнить три свертки построенного графа при различных сочетаниях нулей и единиц в маске макро-свойств. В отчете представить описание свойств, описание элементов системы, исходный граф системы с бинарными весами, три графа свертки по трем маскам макросвойств.
Элементы системы – вершины графа.
Свойства элементов:
1) вершина является истоковой
2) вершина имеет выходящие дуги
3) регулярная вершина
4) вершина имеет петлю
5)вершина имеет 2 исходящие дуги.
6)вершина не имеет исходящих дуг
Информация о работе Анализ структур сложных систем графовыми методами