Введение в прикладную комбинаторику, Кофман А. (984071), страница 32
Текст из файла (страница 32)
Метод латинской композиции ') Конечная последовательность (Хг,, Хг,, ..., Х; ) вершин графа 6 = (Е, Г) называется латинской последовательностью со свойством .У, или Я-латинской последовательностью, еслиг 1) она является путем, 2) она обладает свойством У', ') В вту главу нам пришлось внести ряд существенных исправлений. (Приве перев.) ') Метод разработан автором. По вопросам, касающимся гамильтоновых путей и контурсв, автор консультировался с Мальгра1пкем; см. 11етпе ггап.
Са)зе бе кеса«гойе орегапоппепе, 1-ег 1гкпеыге, 1963, Рй 26, 243 3) любой ее отрезок длины )2 также обладает этим свойством. Пусть з! = (Х!,, Х!, ..., Хе, Ха) и зт = (Хт, Хй, ..., Х! ) (41.1) — две У-латинские последовательности. Введем бинарную операцию ') (Х;,, Хс,..., Х!, Ха, Хт, Х),, ..., Х) ), если Ха = Х! и получающаяся последовательность У-латинская; О (пустая последовательность), если по крайней мере одно из этих условий не выполняется.
(41.2) Если принять, что З обладает свойством У, то У-латинскне последовательности графа ст образуют группоид относительно закона композиции н, для которого з!" 8= 0 (4 1.3) (41.4) (41.5) Ожз,=о, Ые Я=З. (4 !.7) (41.8) (4 1.9) (41.10) (41.11) (41.12) ') Мы называем зту операцию латинской композицией, а некоторые авторы — сцеплением (сопсасепа!юп), как в 134). 244 Основные свойства этого группонда следующие. 1) Этот группоид ассоциативен, т. е. он моноид, или полу- группа; в самом деле, для любых его элементов з!, зв, зз (з! * зв) е зз з! * (за * зз) (4!.6) 2) Существуют как правые, так и левые нейтральные эле- менты, которые не единственны. Имеем з! =(Х!,, Хс, ..., Хс, Ха), з, = (Ха), з! е з = (Хс, Х!, ..., Х!, Хе) = з!, т. е.
зв — элемент, нейтральный справа. Аналогично з, =(Х!), зт=(Х! Х! Х;, ..., Хт), э! аз!=(Х!, Х!и Хт, ..., Х; ), т. е. з! — элемент, нейтральный слева. 3) Этот моноид не обладает нейтральным ') элементом, и не существует обратных элементов. 4) Все элементы моноида регулярны как слева, так и справа: зз = аззч=ь гз! * зз = з! * зз~ (41. 13) аз = зз4$ зз * з4 зз * з4. (41.14) 5) Моноид, очевидно, не коммутатнвен. Для упрощения введем обозначение: если з, * зз= 8, (41.15) то (41.
16) э, э з,=з, ° зз', где з,' — последовательность з, без первой вершины. Обозначим через Схгхь = (з!, зз, ° ° ° эв ° . °, за) (41.17) подмножество Р-латинских последовательностей с р+ 1 вершинами, начинающихся Х; и оканчивающихся Хы Аналогично Схьх. = (1!, зз, ..., зэ, ..., гр). (41.18) Определим произведение Сах,.хь *Сх х = = ((э!*1,), (з, е!з), ..., (аз*!!), ..., (зя, 1,), ..., (з„, 1)) (41.19) (одинаковые элементы учитываются по одному разу).
Как и в (41.16), можно записать (41.20) где Сх„х, = (1!, !з, ..., Г„..., !В) (41.21) — подмножество, состоящее из последовательностей 1„1„..., 1р, у которых удалены первые вершины. Выпишем последовательно л л Сх,'.х, = Ц (Сх,'х, *Сх,'х,) = О ~Схзхь ФСхьих,), (41.22) ь=! ь=! п л Сх!х = Ц (Сх~х е Сх!!х ) = О (Сх~х ФСх х )), (41.23) з=! ь=! л з Сх,х = О (Схс'~х * Сх'х ) = О (Сх~х Е Схдьпх.), (41.24) з=! з=.! в л Сх!х = О (Сх",.хь * Ст~х,.) = Ц (Сх х„~ ° Схьх ), (41.25) ь=! ь=! где п = ! сг !.
') Известно, что нейтральный элемент является одновременно нейтраль. ным слева н нейтральным справа; когда он существует, он едннствен 2245 Для любых целых положительных г и з имеем и ч Сх+х! = О (Сх,.х * Сх„х ) = О (Сх~х «Сх х )). (41 26) х=! х=! Исходя из (41.22) — (41.25), введем матрицы, которые назовем латинскими: 1<М 1<'"> = <! М ~~'" е ~~ М'!~о', (41.27) где на пересечении >-й строки и >ьго столбца матрицы <<МЦ"+ стоит л Сх,'.х" ,= О (Сх,'.х„° Схл',х>), (41.28) х=! а на пересечении й-й строки и 1-го столбца матрицы 1~М'~~о стоит Сх х .
~<«> Таким образом, мы можем описать процесс перечисления всех У-латинских последовательностей графа. й 42. Перечисление путей Рассмотрим свойство .У: «последовательность есть путь». Пусть ~! М ~~<<> — латинская матрица для путей длины 1 и >! М' ~~<<> — соответствующая матрица для путей длины 1 с удаленными первыми вер>пипамн. КомпозиА цня ~~М~!<'>а~~М'~!<'> дает !!М~<<'>, т. е. латинскую матрицу для путей длины 2. Последовательно получаем ~~М~( '®()М'~1~ '=!>М~! ', <! М <1<з! ° )< М' <)и! = <! М <<">, (42.1) >>М~!" и ° <<М'~~"'=~~М~<<">, т. е. перечисление всех путей длины 1, 2, ..., г, ... Перечисление путей длины 1, 2, 3 для графа па рис. 206 приведено на стр.
247. Если интересоваться путями фиксированной длины г, то их можно получить композицией. Например, <<М!!«> получается композицией ~!М>><з> и <>М'<<<'>; ПМ!><'> — из ~/МП<4> и ~)М'~!<>> или из ~!М~~<з> и ~~М1~<з> и т. д. 246 ф 43. Перечисление элементарных путей Рассмотрим свойство У: «последовательность есть элементарный путь», т. е.
последовательность представляет собой размешение без повторения нз а вершин по г (~-выборку без повторения). Е д) А в ; З г 1 Рис. 207, 248 (~ Е) А Г в з 1 ; ью Е) А ; »Ю е) в » ; ~,З а) А Т огда имеем а) е ЗЗ= 3, ° а'„если 3, ° з, '— элементарный путь, (43.1) Я в противном случае. Все элементарные пути графа на рис. 206 приведены на стр. 250, 251. Так как в графе с шестью вершинами не сушествует элементарного пути длины больше 5, то матрица ~(М()И) пуста. Гамильтоновы пути этого графа (элементарные пути длины 5) представлены на рис. 207. УПРАЖНЕНИЯ 4ЗА. Перечислить все пути, длины которых не превосходят числа вершин, для следующих графов: 1 3 3 4 3 6 7 А В С Р Е г" б) 43Б.
Для указанного графа перечислить пути, удовлетворяющие услоьиям: а) пути длины 4, не содержащие вер- шины В; 6) пути длины 3, не содержащие дуги (В, С); в) пути длины 1( 6, не содержащие дуг (В, С) и (Е, Е); г) пути четной длины; д) пути, проходящие через А; е) пути, проходящие через (А, Р). 4ЗВ. Перечислить контуры длин, не превосходящих 1, для следующих графов: а) граф а) из упражнения 43А, 1 = 4; б) граф б) из упражнения 43А, 1 = 3; в) граф б) из упражнения 43А, 1 = 4; г) граф из упражнения 43Б, 1=2. 43П Перечислить перестановки пяти букв А, В, С, Р, Е, в которых ника- кие две согласные не стоят рядом.
4ЗД. Рассмотрим прадерево: Г (А) = (В, С), Г (В) = (О, Е), Г (С] = (Р, 6), Г (О) = (Н, У, У), Г (Е) = Я, Г (Р) = (К, Ц, Г(6) =(М, Н), Г(Н) =Р, ГРЛ =(Р), Г(У) =<Р], Г(К) =Я', Г(Ь) =Ят Г(ги) =Я, Г(Н] =Я. Перечислить пути, начинающиеся в корне А и оканчивающиеся в верши- нах без потомков. Упростить метод латинской композиции для таких графов.
43Е. Перечислить пути, длины которых не превосходят 6, соединяющие вершины А и Е графа а) из упражнения 4ЗА. 43Ж. Перечислить пути, соединяющие вершины С и У, для графа без контуров: ГА=(У,К), ГВ =(А, 6», ГС=(В, В, Н], ГН = (Е), ГЕ = [Р], ГР = (У), Г6=(У), ГН=(Е,Р,6), ГУ =Я, ГУ = (У), ГК = (У). Для сокращения вычислений упростить представление с помощью латин- ской матрицы. $44.
Перечисление элементарных контуров Заметим, что элементарный контур (А, Х;Р Х<Р ..., Хг ы А) длины уг становится элементарным путем, если удалить нз него первую вершину; за У примем свойство: «быть элементарным А путем». Латинская матрица ]] М'))<о ° ° <) М']]<н отличается от латинской матрицы )) М)]<о ° )) М'])<н тем, что из путей в клетках матрицы ]] М )]<о удалены первые вершины. Подмножество С,г<" ~=ОС;а;~ФС;~ую (44,1) <р В ь совпадает с подмножеством С<у<"+" матрицы )] М'(('~", если г' Ф у. Если <=у, то Суу+н= Ы для любого у, но Е в<ген Рис.
208. Сн может содержать латинскую последовательность. Каждая такая по- следовательность оканчивается Х, и представляет собой элементарный путь. Из наших рассмотрений вытекает, что, приписав Х; к ней слева, получим элементарный контур длины и + з. Таким образом, для получения элементарных контуров графа длины р = г + з(р ( л) достаточно найти элементы главной диагонали матрицы () М")]г™ =)) М'])<о ° )) М'))", (44.
2) которую, например, можно представить так: )] М )] ](М )) ° )) М )1 . (44.3) При У+и= и, где п — число вершин графа, элементы главной диагонали матрицы )) М"))<г+з> представляют собой гамиль- 252 ~~М'~~ч)= ~~М~!)Я ° ~~ М'~~"), 5 М" ))в = 5 М' ~) ' ° )) М' 1~' ', находим Сй)а. Имеем (44,4) (44.5) А е с т) е 7 о 17 44ж6] 0) П )м)( Е Л В С Р Е Р С Н )44. 7) )г) и .шв 1м))=)м)) ° )м)) = В во сов осввл овввл овсвл овсов всввл лсгвл всввл 444 г) ввснл А В С О В Р С Н снсвл с )44.4] и нвс л нсввл «л 253 тоновы контуры графа, а все С», ) =~1, пусты, так как граф не )с) содержит элементарных путей длины и. Так как через каждую о)л) вершину проходит любой гамильтонов контур, то все С)) равны между собой, и достаточно найти одно из них. П р и м е р (рис.
208). Очевидно, что для нахождения гамильтоновых контуров этого графа достаточно выписать элементы одной клетки на главной диагонали матрицы )) М"))Рв). Учитывая (44.1) и Из (44.8) и (44.9) получаем первую строку и первый столбец матрицы || М' ~~<4). Перемножив их, выписываем все гамильтоновы контуры: АНВСОЕСЕА АНСВЕБЕВА АВОСГЕВНА АВОЕСН СЕА (44.10) Эти контуры изображены на рис. 209.
Е Рис. 209 УПРАЖНЕНИЯ 254 44А. Найгн элементарные контуры графов а) и б) из упражнения 43А и графа из упражнения 43Б. 446. Рассмотрим графы: А А А А А А в С В В С Ю С С С С С гз Ю г) г? Ю Е Е Е Е Е Е Е Е Е Е С? б) С.) г) Перечислить: 1) гамильтоновы пути графов а), б), а), г); 2) гамильтоновы контуры графов а), б), е), г); 3) простые пути графов а) и г); 4) пути графа а) длины, л1еньшей или равной 6; 5) контуры графа а) длины, меньшей или равной 6.
44В. Рассмотрим соты из упражнений 21А и 2!В. Заштрихованные клетки обозначают запретные ячейки. !) Перечислить различные подстановки для а) из упражнения 21А. 2) То же для г) из упражнения 21А 3) То же для ж) из упражнения 21А. 4) То же для а) из упражнения 21В. Можно лн здесь упростить перечис. ление? Как? В 45. Перечисление последовательностей с повторением Рассмотрим граф сг(Е, Г) на рис. 21!). Обозначим через Вз свойство: через вершины А, С, В, Е путь проходит не более одного раза, а через вершины В, Е путь проходит не более двух А А Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
