Elementy_teorii_grafov_2

	2	15		1	3	12		11		14
			2		1		5		6		0
	0		5				4		2		9
37.	23		9		2				4		6
					5	13		14
		10					2
				10			6		5
38.		1	8		313		3		313
			915				5
		3		4		4	12			4
39.				5	3			3		2
	1614			2		612		411		515
	20		9	11			4		2		5
	3		6		2		5		4		9
40.	2		0	19					6		2
			9			12		11
					6				3
			0		4		6		2
41.			2				5		4
		11			713		211		315
		3	12			6		4		4
		9		3		2				5
						1		1
	16			4		5		6		2
						41

			9	16		15		19
					5		2		3
			8				1
			0		2		5		4
			1		4		6		2
43.		12			1		2	10
			9		5	13		14
									3
		10		10			5		5
44.					2				4
		1	8	4	312		313		3
		3				3		2	15
45.			13		3	2		6		4
	1611			6		412		5		214
	0		2	11			5	15			9
	2		6						2		0
46.	23		4		2		4		9		6
		11		11		19		12
					342		7
			2		4		4		5
			0		2				6
			9				6

		12		15		13		11
	3		2		4		2		4
							6		6
48.	16		4		2		5
	9	0	3		519		116		1
			15			4		2
	12			2		8		3
		9		2		3		5
		8		6		2		4
49.				1		5	10
		9	14		13
						2		5
				3		5		3
50.	10			5		6		0
	3	8		315		313		3
		12			4		6	13
	1		3		5		1
	16		4		2		2		4
51.							5		6
	9	13		15		13		11
									4
	3		3		4		2
	4						6		1
	16		4		2		5		6
					43

азработк(проектированиедискретныху преобразователевычислительнойдискретных. техникиДискретныйсвязана с

åê

тель это устройство,обладающее некоторымпреобразователей)числом вх дов и вы-

хированиемдов (см. рис. 12).

x

x

x

n

1

2.. .

z

z

.. . z

p

1

2

èñ. 12

На вх ды подаются сигналы, принадлежащие некоторому конечно-

му мн жеству X = fx

; : : :; x

n

g. Например, входными словами могут

1

áû ü двоичные к ды, десятичные к ды или любые символьные слова.

Устройство преобразу

их в вых дные сигналы Z = fz

; : : : ; z

g. Âðå-

мя преобразования мало

1

p

им м жно пренебречь. Сеть обозначается

êàê

(fx

; : : : ; x

n

g; fz

; : : : ; z

g).

1

1

p

являются ари метико

Примерами дискретных

огическоеункция

процессора или его части. В этом случае сигна-

ëû

ат множествупреобразователейf0; 1g Вх дом могут быть 2 n-разрядных

регистра,принадлежвыхстройстводом n-разряднûé ðегистр.

...

F

èñ.

i

13

проектирова

вание акого устройства можно свести

ниюПроекнек òîðîй сети, вершины к

пр дставляют собой некоторые

прос ейшие преобразоват

ли, называемыå

элемен

тами. Такой элемент

имеет n вхоторойдов и 1 выхункциональнымид. Его обозначение при-

водится на

. 13.

При проектированииðèñ дискретного преîбразователя необходимо создать сеть вершинами в виде ункци нальных элементов и с ду-

44

ментов. При составлении сложных сетей используютс 3 операции со

ния более простых:

0

00

, ïðè ê

âõ äàìè

Объединение сетей =

[

сетей являетс

объединение входов составляющих сетейобъединениявых -

дами объединения сетей являются оторомвых ды составляющих сетей

(ñì. ðèñ. 14).

n0

n00

. .

.

. .

.

0

00

p0

èñ.

14

p00

элемент

, при отором ni выходов

Fi ê ñåòè 0

(n p) ñåòè 0 ñò

я входами

ункцио ального эле н-

Присоединениета F

ановятсрезультате этого соединения сеть иìååò

i

p ni +полученная1 вых д (см. рис. 15).

i

. . .

n

0

...

n

F

èñ

.i 15

асщепление выхода, при котором один из выходов расщепялется

íà 2 (ñì. ðèñ. 16).

.

n

... .0 ..

èñ. 16

45

базис сети из ункциональных элеме тов. Одним из распространен-

ных является базис эл ментов отðèöания, конъюнкции и дизъюнкции

для сигналов из мíîæåñòâà {0,1} (ñì. ðèñ. 17).

y

x

x

y

x

z^= x ^ y

z_=

x _ y

z = x

èñ. 17

ассмотрим пример пðоектирования дискретного преобразователя

с ункцией

z = x

1

+ x

mod 2:

СДНФ этой укции z = x

x

x

x2 . По этой ДНФ проектируем сеть

1

2

1

2

дискретного преобразоватеëÿ (ðèñ. 18).

x2

x1

^

_

^

z

èñ. 18

Так что любую булеву ункцию можно записать виде СДНФ (или

ÑÊÍÔ)

потому можно реализовать преобразование этой ункции в

âèäå ñåòè

указанным базисом ункциональных элементов.

Любой сети (fx

; : : :; x

n

g; fz ; : : : ; z

g) можно сопоставить систе-

1

1 46

p

				< 1		1
Теперь ясно, как				: z::::::::::::::::p = fp(x1;::::::::::::::: ; xn)
					â		сеть. Но следует учитывать слож
ость получа мойспроектирот рàя определяется оличеством ункцио
à üíûõ ýëåìåнтовсети,их сложностью. П этому вопросы минимизации
Что можно взять(минимизациbв к честве ункциональных элементов? Оказы
булевых ункций							числа	пераций) являются актуаль
íûìè.
вается, справедлив акой акт:
для реализации любой					мы булевых уравнений необходимо и до
анее мы доказывали, чтосистестема f^;								; g	яполной		ìíî-
статочно, чтобы система булевых ункций была по										.
жестве всех булевых ункций,											начестве
						потому можявляетсбыть взята в
Имеются различные алгоритмы минимизации.										о трудоемкость
				элементов.
аких алгоритункциональныхов, ак правило, экспоненциальна,Однаккак они связа-
системыны перебором.
Пример синтеза сети из ункциональных элементов рассмотрен в
разделе 5.2.
5	Задание 9			назначениях, заданную булевой матрицей раз-
1. ешить задачу
мерности n m			возможностей n работников для m работ:
a) указать условия, при которых может существовать решение -
	чи о назначениях; построить транспортную сеть для указанной
	задачи о назначениях;
b) описать сведение задачи о назначениях к задаче о наибольшем
)	потоке;	лгоритм решения задачи о наибольшем потоке для за-
	описатьдачи назначениях;						47

e) шемрешенияåñëè потокнаибольшийзадаполучитьназначениях,потокматрицудовлетвортоназначенийрешениюóсловиям; противномзадачисуществованияслучае

найти узкое место, которое не позволяет решить задачунаиболь-

значениях.

ìíî

æ

2. Для заданной ункции множества вых дных сигналов

вх дных сигналов дискретного преобразователя разработать

ñествавозможно меньшей сложностью (числом ункциональных эле-

еть из системы ункциональных элементов f^;

;

g этого

строй

ментов).

задан ую у кцию с целью определен я мно

a) проан

жествà âõ äíûõ

выходных с гíàëîâ è

ия ункций каж-

представилизироватькаждую булеву ункцию системы в виде ДНФ илè

дого вых дного сигнала

çàâèсимости отполучевх дных сигналов;

b) разработ

систему булевых ункций для выходных сигналов

)

ÊÍÔ;

каждую булеву ункцию системы из ДНФ или

преобразоватьКНФ ормулу, содержащую наименьшее число операций си-

стемы f^;

;

g;

при возмо

d) ыявить повторяемость вида булевых

ания отдельных бл

ункцийв для подсистем ункцийсоединения этих блоков

сти разбить систему

на подсистемы

целью проектиржно-

e) ïîñ

åòü èç

ункциональных элементов для заданного дис-

â

ïðè ï

мощи вышеописанных операций для сетей;

креобщуюн го сетьу тр йства;

f) определить сложность построенной сети из ункциональных эле-

ментов.

48

к задаче о наибольшем потоке

следующей бу

левПримерй матрицей1. ешитьR возмозадачужностейназначераб тниковях, заданную(строки)

ðàáîт (столбцы) сведением к задаче

î

наибольшем потпокевыполнениюее реше-

íèåì:

R =

1

0

1

1

1

1

0

0

0

0

1

1

A. Корректность задачи о

назначениях

определяется следующими

условиями:

1

n = m число раб тников (n = 5) ра но числу работ (m = 5).

2. Äëÿ

ников число

которые они

в совокупн сти умеют выполнять, не меньше числа

îâ;

для любого дмножества работ

число

îâ,

оторые их

могут выполнять,

меньше числа работ. Эти условияработникпосред

ственно трудно

проверяемы поэтому если за

ֈ

имеет реше-

ние, то условия

если нет, то найдетс

узкое место

группа работников, для которых не хватаетработник, которые они

могут выполнять, а т кж

группа работ, для выполнения кото-

рых работников

выполнены,хв тает.

Ищется булева матрица назначений N, для которой:

1)

каждой строке

ит ровно 1 единица (назначение на работу, со

ответствующую столбцу), которая соответствует такому же эле-

2)

менту матрицы R;

в каждом столбце стоит ровно 1 единица (назначение работни-

êà, ñîî

строке), которая соответствует такому же

элемен ветствующегоматрицы R.
Построим транспортную сеть следующим образом (рис. 19):
	49

3

2.

4.

ê

работы J

j

(j

= 1; : : :; 5) введем вершину x

j+5

; введем

вершиной x

Âõâõаждойñåòèx соединимx0 âûõ äкаждойz.

i

(i = 1; : : : ; 5) дугой про-

пускной0

способности

1.

Соединим аждую вершину x

j+5

(j = 1; : : : ; 5) с выходом z дугой

пропускной способности 1.

вершиной x

j = 1; : : :; 5)

Соед ним вершину x

(i = 1; : : :; 5)

дугой пропускной способности 1,

åñëè

r

ij

= 1

(соответственно

матрице возможностей R).

j+5

i

				èñ. 19		назна		н ях к задаче		íàè-
	B. Проведем сведение данной задачи
б льшем		е для построенной тра спîртн й с т . Для этого								нужно
п казать, чòî			задачи о íàç			÷åíèÿõ строи			я поток для
ýòîé транспортнойрешению он являåòñÿ					íà			à	àêæå, ÷òî ïî
í		потокусети,если его значение '					ибольшим,= n = m строится
	Пусть матрица N .= fn g(i 2 1; 5;				jz		2 1; 5) является решением
задачиибольшемуназначениях (в			аждой строке и в к ждом столбце ровно 1
			ij
единица). Определим ункцию ' на дугах трàнспортной сети следу-
ющим образом:				50