Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 32
Текст из файла (страница 32)
Если С вЂ” произвольная матрица, суммы элементов строк которой равны нулю, можно доказать тождество бе!(х1+ у,1 — гС) = — хо бе!((х/х)1 — С), х+пр „ прибавляя столбцы от 2-го до и-го к первому, вынося за скобки (х + пр)/х, вычитая из столбцов со второго по и-й первый столбец, умноженный на р/х, а затем вычитая столбцы со второго по и-й из столбца 1.
Следовательно, принимая х = а — па, у = о, х = Ь, а = 1 и Ь = — 1, мы находим, что С имеет стороны О,п — а п,п — ап (В частности, этот результат согласуется с упражнением 104 (с), если С' — пустой граф К ) сделано для ьрърькиИапаса,ого ОТВЕТЫ К УПРАЖНЕНИЯМ 133 (Ь) Отсортируйте (с4,...,а,', , а,'~,...,а,", ,).(Для разнообразия в очень простой случай.) (с) Здесь С = С + 6, так что в соответствии с частями (а) и (Ь) сторонами С являются (О, и' + и", и" + а'„..., и" + а'„„и' + а,",..., и' + а'„'„, ) . (В частности, С представляет собой К лн если С' = К и С" = К„, следовательно, сторонами К,„являются (О, (и — 1) т, (т — 1) ° п,т+ и).) (д) С (С) = 1„' З С (С") + С (С') З 1„", где Х„обозначает единичную матрицу размером и х и, а символ З вЂ” произведение Кронекера двух матриц.
Сторонами С (С) являются (а' + а~в' ) О < у < и', О < й < и" ); если А и  — произвольные матрицы, собственными значениями которых являются соответственно (Лм..., Л ) и (дм..., д„), то собственными значениями А З Х„, + Х,„З В будут тп сумм Лв + ~М. Доковотавьсгпоо: выберем Б и Т так, что В АВ и Т ВТ вЂ” треугольны. Затем воспользуемся матричным тождеством (А ® В) (С З О) = АС З ВХУ, чтобы показать, что (ВЗТ) (АЗ1„+Х' ЗВ)(ВЗТ) = (В АВ) ЗХ„+ Хм З (Т ВТ).
(В частности, многократное применение этой формулы показывает, что сторонами и-мерного куба являются ((о) О, (",) 2,..., („") 2п), а формула (57) следует иэ упражнения 104 (Ь).) (е) Если С вЂ” однородный граф степени И', его сторонами явлнются о, = 4' — ЛХ+и где Л| > ° > ˄— собственные значения матрицы смежности А = (ео). Матрицей смежности С' явлнется А' = Вт — ~П,'„где В = (Ь;.) — матрица ннциденций размером и х и' с элементами Ь; = (Ребро 1 касается вершины 1], а и = и'И'/2— количество ребер.
Матрицей смежности С является А = ВВт — 21„. Мы имеем ха Де1 (хХ' — Втв) = х'и бег, (х1 — ВВт); это тождество следует из того факта, что коэффициенты бес (хХ вЂ” А) можно выразить через 1гасе (А") для й = 1, 2,..., с использованием тождеств Ньютона (см. упражнение 1.2.9-10). Так что сторонами С являются стороны С', а также и — и' сторон, равных 24'. [Этот результат получен в работе Е.В, Ъаййотвйу, В1Ьпзкй' Мак Ейигпа), 6 (1965), 44-49; см.
также Н. Васйв, %мвепвсйаХНХсйе Ее1гвсйг1Хв дег Тесйп!всйеп НосйвсйпХе Вшепаи, 13 (1967), 405-412.) (1) А = А'ЗА", так что сторонами являются (с~'а'+ 4"а~ — а'а~в ~ 0 < у < и', 0 < <й<н"), (к) А(С) = 1,',ЗА" +А'ЗХ,",+А'ЗА" = (1,', + А') З(Х„"+ А") — 1„дает стороны, равные ((о" + 1) а' + (и' + 1) а~в — аа~~ ) 0 < у < и', 0 < й < и" ). 106. (а) Если а — сторона пути Р„, то имеется ненулевое решение (хо, хм..., х„+1) уравнений ахь = 2хв — хь 1 — хны для 1 < й < и, причем хо = х1 и х„= х„эь Если положить хь = сов(2Й вЂ” 1) д, то мы получим хо = х1 и 2хв — хь 1 — хьы — — 2хь— — (2сов 26) хв; следовательно, 2 — 2 сов 29 = 4 в1пэ 9 будет стороной, если выбрать 9 так, чтобы х„= х„ем и так, чтобы все х не были нулями. Таким образом, сторонами Рв Явлаютсн оо " о( -Ц .
Поскольку с (Р„) = 1, нз упражнения 104 (Ь) должно получаться а1... а„| = и; следовательно, ('-"') = П П('- ° ) Хтм в=1 сделано для мгвлк$пХапаса.огя 7.2.1 134 ОТВЕТЫ К УПРАЖНЕНИЯМ (Ь, с) Аналогично: если а является стороной цикла С„, существует ненулевое решение указанных уравнений, такое, что х„= хв. В этом случае мы испытываем хь = сов 2йд и находим решения при д = рг/и, где 0 < у < (и/2). В то же время хь = в!п йд дает оствльиые линейно независимые решения для (п/2) < у < п. Следовательно, сторонами С„являются пд„, пд„,..., и!вп д>„, и мы получаем с(Р,„х С„) =п П П (аз~+и!дь)„), с(С х С„) = тп П П (!г(дд! +о(гц~.) Пусть ~'„(х) = (х+ о!„)... (х+ п(„0„) и д„(х) = (х+ съ,)...
(х+ о(д„— д>„). Эти полииомы имеют целые коэффициеяты; действительио, /„(х) = (/„-! (х/2+ 1) и д„(х) = 2(Т„(х/2+ 1) — 1)/х, где Т„(х) и С„(х) — полииомы Чебышева, определяемые как Т„(совд) = совой и (/„(совд) = (ьйп(я+1)д)/вшд. Вычисление с(Р х Р„) можно свести к вычислению определители размером т х т, поскольку оя является результаитом /„, (х) и /„( — х) (см. упражнение 4.6.1 — 12).
Аивлогичвгх -„'с(Р х С„) и — '„с(С х С„) представляют собой результаиты /„,(х) и д„( — х), а также д (х) и д„( — х) соответствеияо. Пусть а„(х) = )14 „/в(х)"; таким образом, а! (х) = 1, ад (х) = х + 2, ав (х) = (х + 3) (х + 1), ав = хд+4х+2, ав (х) = (хд + 5х + 5) (хд + Зх + 1), ав (х) = = хв + 4х + 1 и т.д. Рассматривая так называемые характеристические полияомы, можно показать, что а„(х) является иеприводимым яад целыми числами при четном и, а в остальиых случаях представляет собой произведение двух иепривпдимых полияомов одной и той же степени. Аналогично: если 4, (х) = Дщ„дв (х)"~"~ ~, то Д, (х) при и > 3 является квадратом иеприводимого полииома.
Эти факты поясняют наличие достаточно малых простых множителей в результате. Например, иаибольший простой множитель в с(Р х Р„) при и! < и с 10 равеи 1 009; ов встречается только в результаите ав (х) и ад (-х), который равен 662913 = З~ . 73 1009. 107. Для п = (1,...,5) имеется (1,1,2,6,21) иеизоморфиых графов; однако иам нужно рассмотреть только случаи с < ! (д) ребрами в силу упражпеиия 105 (а). Оставшиеся случаи при и = 4 представляют собой свободные деревья: звезда, являющаяся дополнением К! + Кв со сторонами 0,1,1,4, и Р4 со сторонами 0,2— — ь/2,2,2+ !/2 согласно упражиепию 106.
При п = 5 существует три свободных дерева: звезда со сторонами 0,1,1,1,5; Рв со сторонами 0,2 — ф,З вЂ” ф,1+ ф,2+ 4; а также — со сторонами О,г!,1,юд,гв, где (г!,гз,гв) ж (0.52,2.31,4.17) — корни уравнения хв — 7хд + 13х — 5 = О. Н иакоиец, имеется пять случаев с одним циклом: (Х представляет собой К! ~ (Кд+ Кд), так что его сторовами являются 0,1,1,3,5; Св имеет егоровы 0,3 — ф,З вЂ” ф,2+ ф,2+ ф; стороиами р — являются О,г!,гд,З,гв; у его дополиеиия с ~- стороны представляют собой 0,5 — гв,2,5 — гд,б — г!, у Д стороны— О, (5 — !/ГЗ)/2„3 — ф,2+ ф, (5+ !/13)/2.
108. Пусть дан ориентированный граф В с вершинами (Ъ!,..., 1(,), и пусть ен— количество дуг от У! к $', Определим С (Х3) и его стороны, как и ранее. Поскольку матрица С(11) ие обязательно симметричиа, действительность сторон больше ие гараптироваиа. Но если а представляет собой сторону, то стороной является и комплексно сопряженное значение а; если мы упорядочим стороны в оютветствии с их действительиыми частями, то, как и ранее, получим ад = О.
Формула сделано для вдълкиИана1ц,ого 7.2.1 ОТВЕТЫ К УПРАЖНЕНИЯМ 135 с(0) = о1...о„1/п остается верной, если рассматривать с(Р) как среднее количество ориентированных остовных деревьев, взятое по всем возможным корням Ь . Очевидно, что сторонами транзитивного турнира Т„, лугами которого являются 1'; -+ У при 1 < 1 < у < п, являются О, 1,..., и — 1; очевидны так же и стороны его подг рафа в. Выводы в частях (а)-(д) ответа к упражнению 105 остаются без изменений. Например, рассмотрим К1 ~ Тя, сторонами которого являются 0,2,3,4. Этот ориентированный граф Р имеет (2,4,6,12) остовных деревьев с четырьмя возможными корнями, и с (Р) действительно равно 2 3 4/4.
Обратите также внимание, что ориентированный граф — мс'-ь является своим собственным дополнением и имеет те же стороны~ что и Тя. Ориентированные графы допускают также другое семейство интересных операций: если Р' и Р" являются ориентированными графами на непересекающихся множествах вершин У' и У", рассмотрим добавление а дуг е' — сл и Ь дуг св — о', где я' е У' и сл е 1'". Манипулируя определителями так же, как н в упражнении 105 (а), можно показать, что получающийся в результате ориентированный граф имеет стороны (О,ап" + (т',ап" + о(,...,ап" + о'„, „Ьп'+ о",,...,Ьп'+ о'„'„,). В частном случае а = 1 и Ь = 0 можно ввести удобное обозначение для получающегося графа: Р' — Р"; так, например, Т„= Кг — Т„ь Ориентированный граф К„, — К„,— К„с п1+пя+ +п вершинами имеет стороны (О,п в,...,пз.
вя, (п1 — 1) в1), где вв = пь+ +и Очевидно, что сторонами ориентированного пути С)„от У1 до У„являются О, 1,..., 1. Ориентированный цикл О„имеет стороны (О, 1 — ы,... 1 — ы" 1), где ы = япнуч Также есть красивый результат для ориентированного графа, в котором дуги соответствуют вершинам исходного графа: стороны графа .0' получаются из сторон графа Р простым добавлением ть — 1 копий числа оь (1 < Ь < и), где тв — входящая степень вершины Уы а оь — ее исходящая степень. (Если гв = О, мы удаляем одну сторону, равную оы) Соответствующее доказательство похоже (хотя и проще) на доказательство из упражнения 2.3.4.2-21.
ХХспяорическое приввечание: результаты упражнений 104 (Ь) и 105 (а) основаны на работах А.К. Ке1тапя, Агяотаяйа 1 Те1ете1йашйа, 26 (1965), 2194 — 2204; 27, 2 (ЕеЬгпагу 1966), 56-65 (перевод на английский язык в Апяотаноп апс( Нешояе СопЯго!, 26 (1965), 2118-2129; 27 (1966), 233-241. Мирославу Фидлеру (М1гоя1ат Р1еб)ег) (Сяесй. Магй.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
