Задача 1. Элементы теории графов
Связный ориентированный граф G (Х, Г) задан множеством вершин X ={ x 1, x 2,…, xn } и отображением Г xi ={ x | I ± k |, x | I ± l | }, i =1, 2,…, n . Здесь i - текущий номер вершины, n- количество вершин графа. Значение индексов n , k и l возьмем из табл.1 в соответствии с номером варианта. Индексы k и l формируют значения индексов a, b , g… переменной x в отображении Г xi = { x a , x b , x g,…}. Если значения индексов a, b, g… переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Г xi . Выполнить следующие действия: а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами; б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов; в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов; г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi и xj
i*j при i ³ j; Kij = 1/ ( p +1) при i < j .
Найти передачу между вершинами x 1 и xn, используя правило Мезона. Построить структуру кибернетической системы, определяемой топологией графа; Таблица 1
Решение: Множество вершин
X = { x 1, x 2, x 3, x 4, x 5, x 6 }, n = 6 k = 2, l = 1 Г xi ={ x | I ± k |, x | I ± l | }.
а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами: Определим граф аналитическим способом: Г x 1 = { x 1 , x 3 , x 2 }; Г x 2 = { x 4 , x 1 , x 3 }; Г x 3 = { x 1 , x 5 , x 2 , x 4 }; Г x 4 = { x 2 , x 6 , x 3 , x 5 }; Г x 5 = { x3 , x 4 , x 6 }; Г x 6 = { x4, x 5 }.
Ориентированный граф графическим способом:
Неориентированный граф графическим способом:
Ориентированный граф матричным способом: RG - матрица смежности
AG - матрица инцидентности
Неориентированный граф матричным способом: RD - матрица смежности
AD - матрица инцидентности
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов: - матрица отклонений имеет вид:
- вектор отклонения
=> х2, х3, х4, х5 - центры графа с наименьшей удаленностью. Радиус ρ (G) = 2. Периферийными вершинами являются вершины х1, х6 с наибольшей удаленностью. Диаметр графа D (G) = 3. в) выделим в ориентированном графе два подграфа и найдем объединение, пересечение и разность подграфов.
Выделяем два подграфа: G 1 и G 2
X 1 - { x 1 , x 2 }, Г1х1 = { x 1 , x 2 }, Г1х2 = { x 1 }, X 2 - { x 1 , x 2 , x 3 }, Г2х1 = { x 2 }, Г2х2 = { x 3 }, Г2х3 = { x 2 }.
Объединение ,
, , , .
G
Пересечение
, , , .
G
Разность
, , , .
G
г) Считая, что передача между вершинами xi и xj
i*j при i ³ j; Kij = 1/ ( p +1) при i < j .
Сигнальный граф имеет вид
Система уравнений, соответствующая сигнальному графу имеет вид
x 1 = x 1 +2 x 2 +3 x 3 x 2 = x 1 +6 x 3 +8 x 4 x 3 = x 1 + x 2 +12 x 4 +15 x 5 x 4 = x 2 + x 3 +20 x 5 +24 x 6 x 5 = x 3 + x 4 +30 x 6 x 6 = x 4 + x 5
Определить передачу k 16 по правилу Мезона. Формула Мезона имеет вид
PS - передача пути, DS - алгебраическое дополнение, D - определитель.
Пути из х1 в х6 и передаточные функции для каждого из них имеют вид:
Контура:
; ; ; ; ; ; ; ; ; ; ; ; ; . ; .
Пары несоприкасающихся контуров
L 1 L 3, L 1 L 4, L 1 L 5, L 1 L 6, L 1 L 8, L 1 L 9, L 1 L 10, L 1 L 13, L 1 L 14, L 1 L 15, L 1 L 16, L 1 L 17, L 1 L 18; L 2 L 4, L 2 L 5, L 2 L 6, L 2 L 8, L 2 L 9, L 2 L 10, L 2 L 15, L 2 L 16, L 2 L 17, L 2 L 18; L 3 L 5, L 3 L 6, L 3 L 10, L 3 L 17, L 3 L 18; L 4 L 6, L 5 L 7; L 5 L 11, L 5 L 12, L 6 L 7, L 6 L 8, L 6 L 11, L 6 L 12, L 6 L 13, L 6 L 14; L 7 L 8, L 7 L 10, L 7 L 17, L 7 L 18; L 8 L 9, L 9 L 10, L 10 L 11, L 10 L 12, L 11 L 17, L 11 L 18, L 12 L 17, L 12 L 18.
Независимые тройки
L 1 L 3 L 5, L 1 L 3 L 6, L 1 L 3 L 10, L 1 L 3 L 17, L 1 L 3 L 18, L 1 L 4 L 6, L 1 L 6 L 8, L 1 L 6 L 13, L 1 L 6 L 14, L 1 L 8 L 9, L 1 L9L10, L2L 4 L6, L2L9L10, L6L7L 8 .
Отсюда
D = 1 - ( L 1 +L 2 +L 3 +L 4 +L 5 + L 6 +L 7 + L 8 +L 9 +L 10 +L 11 +L 12 + + L 13 +L 14 + L 15 +L 16 + L 17 +L 18 )+ ( L 1 L 3+L 1 L 4+L 1 L 5+L 1 L 6+L 1 L 8+L 1 L 9+L 1 L 10+L 1 L 13+L 1 L 14+L 1 L 15+L 1 L 16+L 1 L 17+L 1 L 18+L 2 L 4+L 2 L 5+L 2 L 6+L 2 L 8+L 2 L 9+L 2 L 10+L 2 L 15+L 2 L 16+L 2 L 17+L 2 L 18 + L 3 L 5+L 3 L 6+L 3 L 10+L 3 L 17+L 3 L 18 L 4 L 6+L 5 L 7+L 5 L 11+L 5 L 12+L 6 L 7+L 6 L 8+L 6 L 11+L 6 L 12+L 6 L 13+L 6 L 14+L 7 L 8+L 7 L 10+L 7 L 17+L 7 L 18+L 8 L 9+L 9 L 10+L 10 L 11+L 10 L 12+L 11 L 17+L 11 L 18+L 12 L 17+L 12 L 18 ) - ( L 1 L 3 L 5+L 1 L 3 L 6+L 1 L 3 L 10+L 1 L 3 L 17+L 1 L 3 L 18+L 1 L 4 L 6+L 1 L 6 L 8+L 1 L 6 L 13+L 1 L 6 L 14+L 1 L 8 L 9+L 1 L 9 L 10+L 2 L 4 L 6+L 2 L 9 L 10+L 6 L 7 L 8 ). D 1 = 1- L 8 ; D 2 = 1; D 3 = 1; D 4 = 1 - L 9 ; D 5 = 1; D 6 = 1. .
Структура кинематической системы представлена на рисунке:
Популярное: Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (197)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |