Введение в прикладную комбинаторику, Кофман А. (984071), страница 33
Текст из файла (страница 33)
211. Рис. 210. раз; через У' — свойство: через вершины А, С, В, Е путь проходит в точности один раз, а через вершины В, Е путь проходит в точности два раза, 255 Так как для пути со свойством У' не выполняется условие 3) (см. начало 5 41), то он не является У'-латинской последовательностью. Легко видеть, что пути со свойством У являются У-латинскими последовательностями. Перечислив их, мы можем отобрать из них пути со свойством У'.
Соответствующие выкладки для отыскания путей со свойством У приведены на стр. 256 до )~М'рф) включительно. Их следует продолжить до )) М ))<'), так как путь со свойством У содержит не более восьми вершин. Это показывает, что для нахождения путей с заданным свойством ~', не являющихся Ц'-латинскими последовательностями, следует подобрать (когда это возможно) свойство гг так, чтобы: а) пути со свойством Я' были ьУ-латинскими последовательностями и б) среди путей со свойством ~ содержались все пути со свойством Д', а затем перечислить сб-латинские последовательности. Можно поступить и иначе. Возьмем, например, граф 6=(Е, Г) с Е=)А, В, 6,.0, В, Р) (см. рис.
210) и заменим его графом 6'=(Е', Г) Е'= (А, Во В„С, О, Е, Ры Р,), в котором В, и Ва (Р, и Р,) инцидентны тем же вершинам в О', что и В(Р) в О, а В, и В, (Р, и Р,) соединены двумя противоположно ориентированными дугами (рис. 211). Достаточно теперь найти элементарные пути графа О', а затем положить В, = Вз= В, Р, =Рз=Р. УПРАЖНЕНИЯ 45А. Перечислить: а) пути длины 7 графа а) из упражнения 44Б, проходящие не более од. ного раза через А, В, С, Е, Р и не более двух раз через ГЛ б) пути минимальной длины графа г) из упражнения 44Б, проходящие по одному разу через Х~ и Ха, по два раза — через Хь и Хе и ие проходящие через Хм в) пути, проходящие в точности один раз через Х~ и Хз, в точности два раза через Хз и Хг и не проходящие через Хз, для графа, дополнительного к графу г) из упражнения 44Б. 45Б.
Перечислить пути длин 1, 2, ..., 1О графа: ГА=(А,В1, ГВ=(В,С), ГС (С,В), ГВ=(В). Бывестн общую формулу для подсчета путей длины и такого графа й 46. Перечисление факторов графа Фактором графа 6 = (Е, Г) называется частичный граф (Е, Ь) такой, что полустепени исхода и захода каждой его вершины равны 1. Таким образом, фактор графа составляется из непересекающихся контуров таких, что в совокупности они со.
держат все вершины графа и каждая встречается один раз. Например, на рис. 2!3 и 214 изображены факторы графа па рис. 212. Гамильтонов контур представляет собой фактор. 257 Фактор является элементом класса эквивалентности, определенного в 5 16. В том же параграфе мы указали, как пересчитать эти классы. Здесь же мы займемся перечислением их элементов, сопоставляя перестановкам возможные факторы заданного графа. Метод латинской композиции позволяет перечислить факторы графа, отыскивая элементарные контуры. Рассмотрим свойство У: последовательность является либо элементарным путем, либо элементарным контуром.
В обозначениях, введенных ранее, (46.1) Для единообразия будущих обозначений положим 11 М 1гс1 = 11 М ~11". Г х Рис. 212. Рис 213. Рис 2!4. На главной диагонали матрицы 11 М 1йс1 представлены все элементарные контуры длины 2; 11 М!1П1 обозначает 11 М~|1И1 без главной диагонали. Составим матрицу 1~ М ИМ с М и1с1 ° с М~ со1 (46.2) на главной диагонали которой будут представлены элементарные контуры длины 3.
Аналогично из 11М~~",1 получаем )~М11П1 и составляем 11 м 1114) = 11 м !!13) ° 11 м' 11и 1 н т. д. Таким образом, исключаемые главные диагонали дадут нам все элементарные контуры. Найдем таким способом факторы графа на рис. 212 (см, стр. 259 — 261). аз Приходим к следующим элементарным контурам: вЦМЦпн (В, В), (й, О), в Ц М Ц',": (В, С, В), (Е, Е, Е), вЦ М Ц< >: (А, С, В, А), (А, С, Е, А), (В, Е, Е, О), вЦМЦ[40 (В Е В С В) (С Е Е В С) в Ц М Ц"! (А, С, В, Е, Е, А), вЦМЦ!и.
(А С В Е В Г А) (46.9) Рис. 2!5 Рис. 2!б. Классы подстановок на множестве 6 элементов: (6, О, О, О, О, 0), (4, 1, О, О, О, 0), (3, О, 1, О, О, 0), (2, О, О, 1, О, 0), (2, 2, О, О, О, 0), (1, 1, 1, О, О, 0), (1, О, О, О, 1, 0), (О, 3, О, О, О, 0), (О, 1, О, 1, О, 0), (О, О, 2, О, О, 0), (О, О, О, О, О, !) (46.10) Учитывая (46.9), получаем для класса (1, 1, 1, О, О, О): 1 фактор [(О, В), (Е, Е, Е), (Л, С, В, Л)], для класса (1, О, О, О, 1, 0): 1 фактор [(О, В), (А, С, В, Е, Е, А)], „для класса (О, О, 2, О, О, 0): 1 фактор [(Л, С, В, А) (В, Е, Е, В)], для класса (О, О, О, О, О, !); 1 фактор [(А, С, В, Е, О, Е, А)]. (46. 11) Два первых фактора представлены иа рис.
213 и 2Н, а два последних на рис, 215 и 216, УПРАЖНЕНИЯ 46А. Перечислить факторы графов: 46Б. Пересчитать и перечислить перестановки, запретные положения зле. ментов которых указаны сотами; Л В С Р и г" 1 з 3 4 5 6 т а1 й 47. Перечисление рассечений Рассечением графа Сг = (Е, Г) называют такую совокупность элементарных путей или элементарных контуров, что: !) два пути рассечения не имеют общих вершин; 2) каждая вершина графа принадлежит одному из путей рассечения. Например, на рис. 218 и 219 представлены рассечения графа на рис.
217. Среди различных путей рассечения графа будем различать; элементарные контуры — их обозначаем символом се;; элементарные пути ненулевой длины — их обозначаем символом пути нулевой длины — их обозначаем символом т„. Для получения рассечений графа достаточно составить матрицы ~~ М ~~<г1, дающие элементарные пути, и матрицы |~ М 11Г1, дающие элементарные контуры, 263 .-' с Рис. 219 Рис. 217.
Рис. 218 г Н Рис. 220, П р и м е р. Перечислим рассечения графа на рис. 217 (если они существуют), состоящие из элементарного контура длины 3 и элементарного пути длины 2. Нам, следовательно, нужно рассмотреть матрицы ]] М]][" (см. (46.3)) и ]] М]]' ' (см. (43.2) ). Контуры ои длины 3; (А,С,В,А), (А,С,Е,А), (О,Е,Е,О), Возьмем, например, (А, С, В, А) и, исключая строки и столбцы А, В, С в ]]М]])з>, получаем пути длины 2: (Р, Е, Е), (О, С, Е), (Е, О, Е) и (Е, Е, О). Но (О, С, Е) нам нужно выбросить, так как он содержит С.
Итак, получаем рассечения; [(А, С, В, А), (О, Е, Е)], [(А, С, В, А), (Е, О, Е)], [(А, С, В, А), (Е, Е, О)]. Поступая аналогично с (А, С, Е, А), а затем с (О, Е, Е, О), по- лучаем рассечения: [(А, С, Е, А), (В, Е, О)], [(О, Е, Е, О), (А, С, В)],[(0, Е, Е, О), (В, А, С)],[Р, Е, Е, О), (С, В, А)], Таким образом, получили семь рассечений, которые представлены на рис. 220. УПРАЖНЕНИЯ 47А.
Перечислить рассечения графов из упражнения 46А. 47Б. Перечислить рассечения графов из упражнения 46А, не являющиеся факторами. 47В. Перечислить рассечения графа г) из упражнения 445. 47Г. Дать способ пересчета рассечений графа, используя способ пересчета перестановок в пикловой записи. 8 48. Другие методы и задачи перечисления (48.1) (48.2) (48.3) ') Это понятие введено в работе Женю и (Р.
Сея пуз), Сопипеп1апез аиг 1е 1апяане А)яо1, Яеупе Смцгез, № 5, !962, 29 — 53. При изложении мы следуем в основном Д е р н и а м у 117]. 265 Понятие груды'). Понятие латинской композиции можно видоизменить, что приводит к понятию, полезному при рассмотрении ряда комбинаторных задач. Пусть сс = (а„ а!, ..., а„) — последовательность элементов множества Е.
Такую последовательность будем называть словом на Е, а число ее членов Х(а) = и + 1 — его длиной. Если Ь ен Е и аг = Ь, то говорят, что г — «место появления Ь в а», а также, что «Ь появляется в и». На множестве слов М введем внутренний закон композиции, называемый сцеплением; а=(ащ аы ..., а„), ]]=(Ьо, Ь|, ..., Ь„), а * Р = (ао а „..., а, Ьо, Ьи ..., Ь„), тогда р называют «левым сомножителем я», а у — «правым со- множителем я». Например, пусть я = (Ь, а, с, с, а, Ь, а) — слово на Е = (а, Ь, с,а!).
Слова (Ь, а, с), (Ь, а), (Ь) — правые сомножители, а (Ь, а), (а) — левые сомнол» жители я. Рассмотрим граф на рнс. 221. За слова примем последовательности его с дуг, являющиеся путями. Пустое слово Л вЂ” путь из О дуг. Если для l путей я = (ас, а!, ..., а„) и = (Ь„ Ь, , Ь ) ввести сцепление: а*р=(а,, а„..., а„, Ьа Ь! Ь )* если правая часть — путь, (48.5) рис 22! а «8 = Л, если правая часть в (48.5)— не путь, (48.6) то этот закон будет определен всюду и мы приходим к латин- ской композиции. Определим теперь понятие груды.
Грудой на множестве Е называют такую конечную последо- вательность А = (яе, я!, ..., я«), я; ен (М, е), ( = О, 1, 2, ..., д,что: 1) яс=я,=Л, 2) для 1= 1, 2, ..., с) выполняется одно из условий: я; !— левый сомножитель я, с ).(я!) = ),(я! !)+ 1, я; — левый сомно- житель яс, с ).(я! !) = ).(я!)+ 1.
Элементы груды называются ее состояниями, а последний элемент слова яс — пиком ') со- стояния яь Пример. Пусть (48.7) Е = (а, Ь, с, а), а,=а Ь, а,=а«Ь«с, я,=а, а„=Л, а, =. а е Ь, пе аз=а, а,=а, а,=а»с, (48.8) или ас=Л, а,=а, аз=а*Ь, аз — — а*Ь»с, а«=а«Ь*сай, аз=а»Ь*с, аз=а«Ь, я,=а, аз=Л. Структура (М, е) — моноид, если закон е всюду определен и ассоциатнвен.
Пустую последовательность Л будем считать принадлежащей М и называть «пустым словом». Она является нейтральным элементом в (М, е), в противоположность латинскому закону композиции, определенному в $41. Пусть я, р, у, 8 — такие слова, что а=р»Ь«у! (48.4) ') В работах [331 и [!71 вместо «пика» используется слово «вершииа» (зотше!), 266 Последовательности А~ = (Л, а, а э Ь, а е Ь ч с, а ь Ь, а, а э с, а, Л), (48.10) А, = (Л, а, а * Ь, а ч Ь * с, а ь Ь ь с * с(, а * Ь э с, а ь Ь, а, Л) (48.11) — груды.
Элементы с и а — пики соответственно состояний а ~ Ь ~ с и а Л не обладает пиком. Для каждого элемента хан Е, появляющегося в слове груды, определим его вход и его выход. а) Предположим, что а; 1 — левый сомножитель он и х(он) = 7 (он 1)+1; тогда существует такой х~ Е, что ан = = а; 1:-:х. Этот индекс ! называют входом х. б) Предположим, что а; — левый сомножитель а~ ~ и 7.(он 1) = 7 (он)+ 1; тогда существует такой хан Е, что а;, = = а;.;х, Этот индекс ! называют выходом х.
Элемент х может обладать несколькими входами и выходами. Например, в (48.8): 1 — вход а, 2 — вход Ь, 3 — вход с, 4 — выход с, 5— выход Ь, 6 — вход с, 7 — выход с, 8 — выход а (а и Ь обладают каждыи одним входом и одним выходом, с обладает двумя входами и выходами). В (48.9): 1 — вход а, 3 — вход с, 5 — выход й; каждый из элементов а, Ь, с и с( обладает одним входом и выходом. Если каждый элемент х ~ Е, появляющийся в слове груды, обладает одним и только одним входом (следовательно, одним и только одним выходом), то груду называют простой.
Слово груды, имеющее наиболыпую длину, называют ее аьшотой. Груда, построенная на дугах графа. Пусть 6 = (Е, Г) =- = (Е, !э') — граф. Построим граф 6' =(Е() (й), Г') =(ЕЦ (й), В'), где И вЂ” новая вершина, Г'Гс=Е, Г'Хс =ГХ,, Х, ев Е, Будем последовательно строить простую груду, элементами состояний которой являются дуги графа 6'. Возможны следующие случаи, а) а; ~ = Л . Тогда либо сс; 1 — последнее состояние груды, либо существует такая вершина Хан Е, что никакая дуга с концом Х не обладает входом, меньшим с, и мы можем образовать состояние аь используя дугу от )г к Х (! будет ее входом).
б) (! — 1) — вход и. Тогда, если существует дуга со входом, не меньшим 1, начало которой совпадает с концом и, то мы можем образовать состояние аь либо используя эту дугу (! будет ее входом), либо выбрасывая и (! будет выходом и); если такой дуги не существует, то у нас остается лишь последняя возможность. в) (! — 1) — выход дуги и и а~ ~ ~ Л. Тогда, если существует дуга со входом, не меньшим й начало которой совпадает с началом и, то мы можем образовать состояние иь либо используя 267 эту дугу (з будет ее входом), либо выбрасывая пик состояния аз, (з — выход пика); если такой дуги нельзя найти, то у нас остается последняя возможность. Таким образом, мы придем к простой груде, состояния которой — пути в 6' с навалом в Я.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
