А. Кофман и Р. Фор. Займемся исследованием операций (стр. 34 )

			B	C	D	E	F	G	H
	B	1	1	1	1	1	1	1
М′[8]=	C		1		1			1
D	1	1	1	1	1	1	1
E				1			1
F	1	1	1	1	1	1	1
G		1		1		1	1
H				1			1

Для вычисления М[8] нет надобности сохранять столбец и строку A в М[4]; мы получаем М′[8], относительно которой легко заметить, что она в точности равна соответствующей части М[4].

В этих условиях мы должны, согласно алгорифму Фаулкса[75], прекратить наши операции. Перестановкой строк и столбцов матрицу М[4] можно представить в форме М[4]; это означает, что задача порождает пять упорядоченных подграфов.

			A	B	C	D	E	F	G	H
		A	1	1	1	1	1	1	1	1
		B	0	1	1	1	1	1	1	1
М[4]=	C	0	1	1	1	1	1	1	1
D	0	1	1	1	1	1	1	1
E	0	0	0	0	1	1	1	1
F	0	0	0	0	0	1	1	1
G	0	0	0	0	0	0	1	1
H	0	0	0	0	0	0	1	1

Это множество обладает одним и только одним гамильтоновым путем[76], которым является путь ADBFGCEH. Последнее означает, что наш друг Фреголи обладает одним и только одним способом одеться, как денди. Этот способ состоит в том, чтобы одеваться в таком порядке: галстук, жилет, носки, ботинки, пиджак, пальто, перчатки.

Некоторые аналогичные задачи могут привести к нескольким решениям; так, если бы в приведенном примере мы имели D F, то существовало бы дополнительное решение ABDFGCEH.

Хотя мы описали алгорифм Фаулкса на столь забавном примере, ясно, что он может быть также использован при решении гораздо более серьезных задач.

Задачи о назначении в промышленности, например, могут носить такой же комбинаторный характер: речь может идти о выполнении некоторого числа операций на различных машинах; при этом на порядок этих операций могут быть наложены условия с помощью связей типа <, или |<. Когда имеется много машин и много операций, единственность решения встречается

Рис. 16.2.

Рис. 16.3.

редко. В этих условиях остается выбрать, согласно определенному критерию (в качестве которого могут выступать затраты или длительность процесса), лучший из возможных порядков, даваемых решениями задачи.

Алгорифм Фаулкса

Рассмотрим шесть операций: А, В, С, D, E, F, между которыми существуют следующие соотношения:

А < В В |< С С <D Е < D F < D

A < D В < D F < E

A F B E

B F

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

A B C D E F A 1 1 0 1 0 1 B 0 1 1 1 1 1 C 0 0 1 1 0 0 D 0 0 0 1 0 0 E 0 1 0 1 1 0 F 1 1 0 1 1 1

Рис. 16.4.

Исследование графа, изображенного на рис. 16.4, показывает, что точка D есть безусловно конечная точка каждого гамильтонова пути (если таковой существует), ибо никакая дуга не имеет эту точку своим началом, тогда как дуга, исходящая из любой другой точки, достигает точки D.