Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 13 )

После удаления 1-ой строки и 5-го столбца выполняется аналогично процедура выбора 2-го назначения.

							Сi1		Ci2		Сj
							-		-		-
	4	11	7	6			4		6		2
С =	3	5	6	7			3		5		2
	4	7	6	10			4		6		2
	5	5	7	6			5		6		1
С1j	3	5	6	6	-
С2j	4	5	7	7	-
с	1	0	1	1	-

И опять риск оценивается значением «два». Выбираем первый по счету вариант назначения, соответствующий этому значению, а именно: С21=4.

Тогда, s=s+C21= 3+4=7. Далее процесс продолжается аналогично.

В результате получим следующий план:

	0	0	0	0	1
	1	0	0	0	0
X* =	0	1	0	0	0
	0	0	1	0	0
	0	0	0	1	0

s=3+4+5+6+4=24 (слагаемые соответствуют шагам алгоритма).

3.  Методические указания для подготовки к аттестующим тестам

Цель тестирования – аттестация знаний, полученных на лекциях по двум основным темам «Дискретной математике»: теории графов и теории сетей.

a.  Тест № 1 «Экстремальные числа графа»

Рассмотрим решение основных задач теста на следующем примере.

Дан неориентированный связный простой (без кратных ребер и петель) граф G(X, U) на шести вершинах (n=6) и десяти ребрах (m=10), количество компонент связности p=1.

Цикломатическое число неографа s(G) указывает на количество независимых циклов в графе и определяет сколько ребер надо удалить из графа, чтобы превратить его в остовное дерево, для несвязного графа с p>1 – в лес остовных деревьев.

s(G) = m(G) – n(G) + p(G) = 10 – 6 + 1 = 5

Следовательно, в данном графе надо удалить 5 ребер. Порядок удаления – произвольный, но при условии сохранения связности, например, так:

X4	X3

 

Хроматическое число графа g(G) определяет минимальное количество цветов, которое необходимо при раскраске вершин графа. Так как операция раскраски вершин помечает одним цветом только несвязанные между собой вершины, то для данного графа g(G) = 4, что соответсвует, например, такой раскраске вершин:

Число внутренней устойчивости (или число независимости, или число неплотности) графа a0 (G) – это максимальное количество вершин в графе, не смежных между собой. Другими словами, это число равно мощности наибольшего внутренне устойчивого множества (НВУМ) вершин в графе.

Для нашего графа поиск НВУМ даст 4-ре решения: {X1,X3}, { X1,X4},

{ X2,X6}, { X5,X6}. Поэтому a0 (G)=2.

Заметим, что между хроматическим числом и числом внутренней устойчивости есть прямая связь: при минимальной раскраске вершины НВУМ получат одинаковый цвет.

Число внешней устойчивости (или число вершинного покрытия) b0 (G) – это минимальное число вершин, образами которых являются все другие вершины этого графа. Другими словами, это число равно мощности наименьшего внешне устойчивого множества вершин в графе.

Для нашего графа это множество { X5,X6}, в котором образами вершины Х5 являются вершины Х1, Х2, Х3 и Х4. Поэтому b0 (G)=2.

Кликовое число (или число плотности) графа j0 (G) определяется числом вершин в наибольшем полном подграфе (НПП), т. е. кликой с максимальным числом вершин. В нашем графе можно выделить три клики: 4-вершинный полный подграф на множестве {Х2, Х3, Х4, Х5} и два 3-вершинных полных подграфа на множествах {Х1, Х2, Х5} и {Х3, Х4, Х6}.

Здесь: НПП – это подграф на множестве {Х2, Х3, Х4, Х5} и j0 (G)=4.

Число паросочетания графа a1 (G) определяется числом ребер в наибольшем паросочетании графа (паросочетание – это множество несмежных ребер). Для нашего примера a1 (G)=3 и определяется следующим наибольшим паросочетанием (ребра выделены жирными линиями):

Число реберного покрытия графа b1 (G) определяется числом ребер в наименьшем реберном покрытии (реберное покрытие – это множество ребер, которое покрывает все множество вершин этого графа). Учитывая бинарность графов, следует помнить, что b1 (G) ³ n/2. Для нашего примера есть решение, соответствующее минимальной оценке b1 (G) = 3. Это решение, например, {(X1, X2), (X3, X5), (X4, X6)}.

Метрические характеристики графа определяются понятием расстояния между вершинами. К таким характеристикам относятся диаметр, радиус и центр графа.

Расстояние между вершинами Хi и Хj в связном неографе G(X, U) определяется количеством ребер в минимальном маршруте, связывающем эти две вершины - d (Xi, Xj).

Диаметр графа d(G) определяется максимальным расстоянием между вершинами в графе.

Максимальное удаление (или эксцентриситет) от вершины Хi – r(Xi) определяется максимальным расстоянием этой вершины до любой другой вершины в графе.

Радиус графа r(G) определяется минимальным эксцентриситетом в этом графе.

Центр графа – это множество вершин, для которых r(Xi) = r(G).

Для нашего графа определим расстояния между вершинами и их эксцентриситеты:

Xi	1	2	3	4	5	6
r (Xi)	3	2	2	2	2	3

Тогда: d(G) = 3, r(G) = 2.

Центром графа будет множество вершин {Х2, Х3, Х4, Х5}

b.  Тест № 2 «Сети Петри»

Пусть дана сеть Петри С = <T, P, I, О, m0 >:

T ={t1, t2, t3, t4} – множество переходов, m=4.

P ={p1, p2, p3 } - множество позиций, n=3.

I – входная функция, устанавливающая соответствие T ® P.

О - выходная функция, устанавливающая соответствие P ® T.

m0 = (1,2,0)- вектор начальной маркировки сети С.

Кратность входной позиции pk - это число # ( pk, I( ti )), которое показывает сколько раз позиция pk встречается в множестве I( ti ), например: # ( p1 , I( t1)) = 1, # ( p2 , I( t2 )) = 2.

Кратность выходной позиции pk - это число # ( pk, О( ti )), которое показывает сколько раз позиция pk встречается в множестве О( ti ), например: # ( p1 , О( t1)) = 1, # ( p2 , О( t2 )) = 0.

Петля – это контур, состоящий из одной и той же позиции pk для события ti. Для данной сети таким контуром является { (p1 ,t1 ), (t1, p1)}.

Покрывающее дерево – это ориентированное корневое дерево, вершинам которого соответствуют достижимые из m0 маркировки m, а дугами являются разрешенные переходы ti, определяющие отношения непосредственного следования:

ma [ ti > mb,

где ma , mb - начало и конец дуги, помеченной символом ti.

Для обозначения расширенной маркировки используем символ «w» и построим покрывающее дерево для нашей сети Петри:

Корневая вершина

На основании построенного покрывающего дерева можно дать следующие определения для данной сети Петри:

№	свойство	определение	основание
1.	ограниченность	неограниченная	В покрывающем дереве присутствует w.
2.	безопасность	небезопасная	Количество маркеров в ряде позиций превышает k=1.
3.	сохраняемость	несохраняющаяся	Нет такого целого числа, которому бы равнялость общее количество маркеров.
4.	живость	неживая	В покрывающем дереве присутствуют терминальные вершины, соответствующие тупиковым маркировкам.

ЛИТЕРАТУРА

Введение в методы оптимизации. - М.: Наука, 1977. Хопкрофт Дж., Ульман Дж. Построение и анализ Вычислительных алгоритмов: Перевод с англ. - М.: Мир, 19с. Ашманов программирование. - М.: Наука, 1981. Горбатов дискретной математики: Учебн. пособие для студентов вузов. - М.: Высш. шк., 19с., ил. , ,, Тышкевич по теории графов - М.: Наука. Гл. ред. физ.-мат. лит., 19с. Зыков конечных графов. - Новосибирск: Наука, Сибирское отд-ние, 19с. Котов Петри. – М.: Наука. Гл. ред. физ.-мат. лит., 19с. Теория графов. Алгоритмический подход: Перевод с англ. - М.: Мир, 1с. Алгоритмы оптимизации на сетях и графах: Пер. с англ. - М.: Мир, 19с. , Осипова дискретной математики : Учеб. пособие. - М.: Изд-во МАИ, 19с.: ил. Новиков математика для программиста. / Учебник для вузов. СПб: Питер, 2004. – 301с.: ил. Теория графов. - 2-ое изд. - М.: Наука, Главная редакция физико-математической литературы, 1980, 336с. Комбинаторные алгоритмы. Теория и практика: Пер. с англ. - М.: Мар, 19с. Методы решения оптимизационно-графовых задач в САПР: Методические указания к лабораторным и индивидуальным работам по дисциплине «Математическое обеспечение САПР». Пенза 1995. Методы решения задач математического программирования: Методические указания к лабораторным и индивидуальным работам по дисциплине «Оптимизация САПР». Пенза 1995.