Математические основы теории систем Задача 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 № варианта 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 N 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 K 2 3 4 1 1 1 3 5 2 4 2 3 4 5 6 L 1 1 1 2 3 4 2 1 3 3 1 1 1 1 1 № варианта 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 N 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 K 1 1 1 1 3 2 5 5 2 3 4 5 6 5 3 L 2 3 4 5 2 3 2 3 3 2 3 2 1 3 5 Решение: Множество вершин 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 - матрица смежности x1 x2 x3 x4 x5 x6 x1 1* 1 1 0 0 0 x2 1 0 1 1 0 0 x3 1 1 0 1 1 0 x4 0 1 1 0 1 1 x5 0 0 1 1 0 1 x6 0 0 0 1 1 0 AG - матрица инцидентности v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 x1 1* 1 -1 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 x2 0 -1 1 1 -1 0 0 0 0 0 0 0 0 1 -1 0 0 0 0 x3 0 0 0 -1 1 1 -1 0 0 0 0 -1 1 0 0 1 -1 0 0 x4 0 0 0 0 0 -1 1 1 -1 0 0 0 0 -1 1 0 0 1 -1 x5 0 0 0 0 0 0 0 -1 1 1 -1 0 0 0 0 -1 1 0 0 x6 0 0 0 0 0 0 0 0 0 -1 1 0 0 0 0 0 0 -1 1 Неориентированный граф матричным способом: RD - матрица смежности x1 x2 x3 x4 x5 x6 x1 1* 2 2 0 0 0 x2 2 0 2 2 0 0 x3 2 2 0 2 2 0 x4 0 2 2 0 2 2 x5 0 0 2 2 0 2 x6 0 0 0 2 2 0 AD - матрица инцидентности v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 x1 1* 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 x2 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 x3 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 0 x4 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 x5 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 0 0 x6 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов: - матрица отклонений имеет вид: x1 x2 x3 x4 x5 x6 x1 1 1 1 2 2 3 x2 1 0 1 1 2 2 x3 1 1 0 1 1 2 x4 2 1 1 0 1 1 x5 2 2 1 1 0 1 x6 3 2 2 1 1 0 - вектор отклонения => х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