Домашнее задание: построить орграф и определить гамильтонов путь в задачах:
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 - мы не обнаружили.
Важно отметить, что если мы хотим получить алгоритм установления подобных путей в отношении связывания всех вершин со всеми, то мы должны матрицу М¢ возвести в квадрат, при этом вместо арифметической суммы при получении соответствующего элемента матрицы (М¢)2 как в обычном матричном произведении будем проставлять булеву сумму. Таблица булевого суммирования для удобства приведена ниже.
| Å | А | В | АÅВ |
Применяя закон булевого сложения к полученному выше перемножению элементов А –строки на С – столбец, получаем:
0 Å 1 Å 0 Å 0 Å 1 = 1
Точно также вычисляем все остальные элементы матрицы (М¢)2 и в итоге получаем матрицу (М¢)2:
A B C E F
| A | |||||
| B | |||||
| C | |||||
| E | |||||
| F |
Итак, в этой матрице 1 в строках означают наличие пути в соответствующую столбцу вершину длины меньшей или равной 2, а 0 означают их отсутствие. Разглядывая матрицу, мы снова устанавливаем и в этом редуцированном графе наличие концевой вершины – С, что позволяет и далее упрощать граф, вычеркивая соответствующие строки и столбцы.
Новая матрица (М¢¢)2: A B E F
| A | ||||
| B | ||||
| E | ||||
| F |
Точно также, как мы искали пути длины меньшей или равной 2, найдем пути длины меншей или равной 3, вычисляя (М¢¢)3:
A B E F
| A | ||||
| B | ||||
| E | ||||
| F |
Матрица (М¢¢)3 содержит только единицы, что доказывает наличие путей длины меньшей или равной 3 между всеми вершинами орграфа А, B, E, F, взятыми по две. Обычно, когда вычисляют матрицы, возведенные в степень n, то действует правило останова:
(М¢¢)n+1 = (М¢¢)n
ибо это означает, что в М не существует пути, длина которого превышает n. Двигаясь назад по шагам редукции, получаем в итоге гамильтонов путь:
АFEBCD.
Методическое замечание к выполнению домашнего задания.
Представьте ход сражения в виде отдельных боевых операций или боев, например, БСП - бой сторожевого полка, ВСРМК - ввод стратегического резерва монгольской конницы, ВЗП - ввод запасного полка, БППР - бой полка правой руки, БПЛР - бой полка левой руки и т.д. Тогда запись течения сражения представляется в виде временных неравенств между боями:
БСП < ВЗП - бой сторожевого полка происходит раньше ввода в сражение запасного полка; БППР < ВЗП; БСП < БППР; ВСРМК |< ВЗП; БППР < ВСРМК; БПЛР < ВЗП; БСП < БПЛР; БСП < ВСРМК и т.д.
Вопросы для самопроверки:
- Объясните, как вы понимаете "проклятие перебора".
- Нарисуйте 3-х вершинные знаковые графы неустойчивых, напряженных отношений.
- В чем смысл теоремы Картрайта - Хайдера - Харари?
- Охарактеризуйте общие свойства матрицы графа отношений взаимных симпатий и антипатий в группе из n субъектов.
- В чем смысл теорем Кенига и Дирака?
- Для чего служит операция возведения квадратной матрицы ориентированного графа в n - ую степень?
