Как только в прорыв вошли свежие силы Стратегического резерва и повернулись спиной к дубраве, ловушка захлопнулась – в дело пошел Засадный полк.

Домашнее задание: построить орграф и определить гамильтонов путь в задачах:

1) «в каком порядке одеваться бойцу- новобранцу, чтобы не получить наряды вне очереди при утреннем построении»;

Ф – галифе; М – подсумок; Г – гимнастерка; Р – ремень; Ш – скатка из шинели;

П – портянки; С – сапоги; К – «калаш».

Г < М; Г < Р; Р < Ш; П ç< С; Ф < П; Ф < Р; Ф < С; Ф « Г; П < К; Г < Ш; Р < М

Ш < К; М < Ш; … ?

2) «на основе анализа действий противостоящих сторон при протекании сражения на Куликовом поле представить результат анализа в виде символьной записи аналогичных (как в задаче 1) неравенств, и применив методические правила (в том числе и из Приложения) построить алгоритм победы русских войск».

Литература

1. Иваницкий Г.Р. Ритмы развивающихся сложных систем, Математика/кибер­нетика, Новое в жизни, науке, технике, Вып.9, Издательство «Знание», 1988.

2. К.Берж. Теория графов, ИЛ, М., 1962.

3. О. Оре, Графы и их применения, “Мир”, М., 1965.

4. Шведовский В.А. Поиск формулы рангового упорядочения факторов комплексного повышения уровня сплоченности в рабочем коллективе // Комплексный подход к коммунистическому воспитанию, ИСИ АН СССР – ССА, М., 1977.

5. А.Кофман, Р.Фор. Займемся исследованием операций, «МИР», М., 1966.

Приложение. Описание алгоритма Фаулкса [5, стр. 246].

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

A < B B ç< C C < D E < D F < D

A < D B < D F < E

A«F B«E

B«F

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

A B C D E F

A
B
C
D
E
F

Этой матрице соответствует следующий ориентированный граф, на котором и надо искать гамильтонов путь. Прежде всего, исследуем граф на наличие строго однозначной начальной или конечной вершины каждого гамильтонова пути. Таковой оказывается вершина D, - см. ниже Рис.4.6.

B

C

A

D

F

E

Рис.4.6. Ориентированный граф, соответствующий списку вышеприведенных отношений.

Свойство завершения гамильтоновых путей на этом графе в вершине D выражается наличием 1 во всем столбце D выше приведенной матрицы. Строка на ней для D содержит 0 за исключением 1, расположенной на главной диагонали матрицы.

Может быть и симметричная ситуация, т.е. вся строка состоит из 1, а весь столбец, исключая пересечение со строкой, состоит из 0, - в этом случае соответствующая вершина графа означает начало гамильтоновых путей.

В случаях установления концевых вершин гамильтоновых путей матрица графа допускает упрощение вычеркиванием пар соответствующих столбцов и строк для концевых вершин. В нашем случае после вычеркивания столбца и строки для вершины D получаем М^¢:

A B C E F

Как легко увидеть из сопоставления матриц и соответствующих графов 1 на пересе­че­нии n –ой строки с m – ым столбцом означает наличие пути из вершины n в вершину m длиной в одну дугу.

Чтобы узнать, существуют ли из вершины n в вершину m длиной в не менее двух дуг, поступают следующим образом. Образуют последовательные произведения элементов n –ой строки на последовательные элементы m – ого столбца, например, строки А на столбец С. Тогда получится:

а) 1 * 0 = 0; б) 1 * 1 = 1; в) 0 * 1 = 0; г) 0 * 0 = 0; д) 1 * 1 = 1.

Из выше приведенной матрицы следует, что прямого пути длиной в одну дугу из А в С не существует. Из рассмотрения орграфа, отвечающего этой матрице, устанавливаем, что существуют прямые пути из А в В и из В в С, т.е. существует путь из А в С, но длиной 2. Других путей – через вершины Е или F - мы не обнаружили.

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

Å	А	В	АÅВ

Применяя закон булевого сложения к полученному выше перемножению элементов А –строки на С – столбец, получаем:

0 Å 1 Å 0 Å 0 Å 1 = 1

Точно также вычисляем все остальные элементы матрицы (М^¢)² и в итоге получаем матрицу (М^¢)² :

A B C E F

A
B
C
E
F

Итак, в этой матрице 1 в строках означают наличие пути в соответствующую столбцу вершину длины меньшей или равной 2, а 0 означают их отсутствие. Разглядывая матрицу, мы снова устанавливаем и в этом редуцированном графе наличие концевой вершины – С, что позволяет и далее упрощать граф, вычеркивая соответствующие строки и столбцы.

Новая матрица (М^¢¢)² : A B E F

A
B
E
F

Точно также, как мы искали пути длины меньшей или равной 2, найдем пути длины меншей или равной 3, вычисляя (М^¢¢)³:

A B E F

A
B
E
F

Матрица (М^¢¢)³содержит только единицы, что доказывает наличие путей длины меньшей или равной 3 между всеми вершинами орграфа А, B, E, F, взятыми по две. Обычно, когда вычисляют матрицы, возведенные в степень n, то действует правило останова:

(М^¢¢)ⁿ⁺¹ = (М^¢¢)ⁿ

ибо это означает, что в М не существует пути, длина которого превышает n. Двигаясь назад по шагам редукции, получаем в итоге гамильтонов путь:

АFEBCD.

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

Представьте ход сражения в виде отдельных боевых операций или боев, например, БСП - бой сторожевого полка, ВСРМК - ввод стратегического резерва монгольской конницы, ВЗП - ввод запасного полка, БППР - бой полка правой руки, БПЛР - бой полка левой руки и т.д. Тогда запись течения сражения представляется в виде временных неравенств между боями:

БСП <ВЗП - бой сторожевого полка происходит раньше ввода в сраже­ние запасного полка; БППР <ВЗП; БСП <БППР; ВСРМК |< ВЗП; БППР <ВСРМК; БПЛР <ВЗП; БСП <БПЛР; БСП <ВСРМК и т.д.

Вопросы для самопроверки:

- Объясните, как вы понимаете "проклятие перебора".

- Нарисуйте 3-х вершинные знаковые графы неустойчивых, напряженных отношений.

- В чем смысл теоремы Картрайта - Хайдера - Харари?

- Охарактеризуйте общие свойства матрицы графа отношений взаимных симпатий и антипатий в группе из n субъектов.

- В чем смысл теорем Кенига и Дирака?

- Для чего служит операция возведения квадратной матрицы ориентированного графа в n - ую степень?