УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

Белорусский Государственный Университет Информатики и Радиоэлектроники

Кафедра систем управления

Контрольная работа

по дисциплине «МОТС»

Вариант №6

Выполнил:

Студент ФЗВиДО, БГУИР

Специальности ИТиУвТС

Группы 602421с

Попов Л. А.

Минск 2008

Задание 1. Элементы теории множеств

Записать множество упорядоченных пар (х, у), выражающих отношение «х-делимое y» на множестве целых чисел от 2 до 20 включительно. Является ли это отношение функцией? Обладает ли оно свойством транзитивности?

Решение

f(x)={(2,4),(2,6),(3,6),(2,8),(4,8),(3,9),(2,10),(5,10),(2,12),(3,12),(4,12),(6,12),(2,14),(7,14),(3,15), (5,15), (2,16),(4,16),(8,16),(2,18),(3,18),(6,18),(9,18),(2,20),(4,20),(5,20),(10,20)}

Данное отношение является функцией и не обладает свойством транзитивности.

Задание 2. Элементы теории графов

Связный ориентированный граф G(Х, Г) задан множеством вершин X = {x₁, x₂, …, x_n} и отображением Гx_i = {x_|Ik|, x_|Il|}, i =1, 2,…, n. Здесь i – текущий номер вершины, n-количество вершин графа. Значение индексов n = 5, k = 1, l = 4. Индексы k и l формируют значения индексов ,  , … переменной x в отображении Гx_i = {x_ , x_ , x_,…}. Если значения индексов , , … переменной x не соответствуют ни одному из номеров вершин графа, то эта переменная не учитывается во множестве Гx_i.

Выполнить следующие действия:

а) определить исходный граф и ассоциированный с ним неориентированный граф графическим, матричным и аналитическим способами;

б) установить центры и периферийные вершины графов, найти радиусы и диаметры графов;

в) выделить в ориентированном графе два подграфа. Найти объединение, пересечение и разность подграфов;

г) определить количество покрывающих деревьев, которые можно построить на неориентированном графе; найти эти деревья;

д) для одного из деревьев записать символ дерева, представить дерево в корневой форме и записать код дерева.

Решение

а). X = {x₁, x₂, x₃, x₄, x₅}

Г_x1 = (x₂, x₅); Г_x2 = {x₁, x₃}; Г_x3 = {x₂, x₄}; Г_x4 = {x₃, x₅}; Г_x5 = {x₁, x₄}.

Ориентированный граф:

R_G =

Неориентированный граф:

A_D =

б). Вектор отклонённостей

	x1	x2	x3	x4	x5
d(xi)	2	2	2	2	2

Все вершины графа являются как центрами, так и периферийными вершинами.

Радиус: ρ(G) = 2; Диаметр: D(G) = 2.

в). Выберем подграфы.

1. Объединение D₁D₂ = {x₁, x₂, x₄, x₅};

2. Пересечение D₁D₂ = Ø;

3. Разность D₁\D₂ = {x₁, x₂},

D₂\D₁ = {x₄, x₅};

г). Для того чтобы определить количество покрывающих деревьев неориентированного графа, построим матрицу

B =

Для извлечения ответа используем теорему Трента:

L = Δ₃₃ = = 80

Найдём эти деревья:

Ω₂ = {1, 2, 6, 7}; Ω₃ = {2, 3, 7, 8}; Ω₄ = {3, 4, 8, 9}; Ω₅ = {4, 5, 9, 10}.

=

д). Выберем какое-нибудь одно покрывающее дерево

Номера вершин совпадают с номерами индексов элементов множества X, образующих данное дерево.

G₁

Символ дерева α(G₁) = (2, 3, 4)

Дерево в корневой форме имеет вид

Код дерева γ(G₁) = (00110011).