Задача 1. Элементы теории графов
Связный ориентированный граф G (Х, Г) задан множеством вершин X={x1, x2, …, 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 = {xa , xb , xg,…}. Если значения индексов a, b, g… переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гxi.
Выполнить следующие действия:
а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;
б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;
в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;
г) описать систему уравнений, соответствующую сигнальному графу, считая, что передача между вершинами xi и xj
i*j при i ³ j;
Kij =
1/ (p+1) при i<j .
Найти передачу между вершинами x1 и 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 = {x1, x2, x3, x4, x5, x6 }, n = 6 k = 2, l = 1 Гxi={x|I±k|, x|I±l|}.
а) определим исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами:
Определим граф аналитическим способом:
Гx1 = { x1, x3, x2 };
Гx2 = { x4, x1, x3 };
Гx3 = { x1, x5, x2, x4 };
Гx4 = { x2, x6, x3, x5 };
Гx5 = { x3, x4, x6 };
Гx6 = {x4, x5 }.
Ориентированный граф графическим способом:
Неориентированный граф графическим способом:
Ориентированный граф матричным способом:
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 | |
|
|
|
|