Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 164
Текст из файла (страница 164)
920 Ответы к упралгнениям Раздел 15.3. 1. а) 1011100010010111110100100010; б) 001011010110101; в) бес14ей; г) 1ааиез. 3. Вес кода 1 равен 127. Вес кода 2 равен 112. Вес кода 3 равен 136. Выбираем код 2. 5. а) б) а = О, Ь = 10, с = 110, т = 111; в) вес равен 41; г) 110111010; д) 100111; е) саг; ж) ЬагЬ. 7. а) б) а = 01, д = 00, е = 11, й = 1000,т = 1001, з = 101; в) вес равен 92; г) 11100101101111001; д) 000110011000111001; е) гаКей; ж) деагег. 9.
а) б) а = 100; с = 1010; е = 01; 1 = 111; д = 1100; 6 = 10110; т = 10111; з = 1101; Г = 00; в) вес равен 118. Ответы к упражнениям 921 И. а) 6)а = 100; Н = 0111; е = 111; ! = 00001; д = 0110; Ь = 000001; 1 = 10111; т = 1010; п = 0001;о = 1101; и = 010; э = 1100; ! = 10110; и = 001; гл = 000000; в) вес равен 547; г) 1111001100101101101000011011000000111111 00001000110000010111 0000001111100101101101000011011000000111 11010110111010001 д) 110000000011110010110111010. 13. Рассмотрим два элемента для кодирования.
Коды совпадают, пока к элементам ведет один путь. Если эти пути расходятся на и-ом ребре, то коды отличаются в и-ом двоичном разряде. Им пути должны разойтись до того, как один путь достигнет листа. В противном случае они бы достигли одного листа и остановились. Следовательно, ни один элемент кода не может быть начальной строкой другого элемента кода, и код — префиксный. Р а 76.4.
6) х ч-аЬс; 9. а) в) аЬ+ сх. 6) + х еаЬс+ сс1; в) аЬ+ с х сЫ+ +. 1. а) аЫсе; 3. а) г!асЬ|ед!уЬЬг; 5. а) НеасЬдуЬУ!Ьги1; 7. а) х 6) ЬасНе; б) дУИсаЬеЬ1гй1; б) Ьдег!саЬ/!УЬ!ии в) аг!есЬ. в) аьсаеа!!ЬЬд. в) НаЬсе1д!тпЬЗЧЬ. 922 Ответы к упражнениям 11. а) в) аде~+ — + хдй+ Ц+ х+. б) + х а + Ь вЂ” с) + еУ х +дЬ + 11; 13. а) в) аб+ с — Н х еУдй + е — +. б) + х — +аЬсН вЂ” ех) +дй; 15. 17 Отввты я упражнениям 923 Ь Г Раздел 1б.б. 1. а) "о б) Ы' 3 з 5 в) "а "з тз тз "з 3. а) б) тн тп 23. (д). 2$. Для каждой арифметической операции количество предшествуюших ей чисел на два или больше превышает количество предшествующих ей арифметических операций, и последний символ должен быть арифметической операцией. 27.
После того как вершина Ь была обработана на обоих деревьях, на шаге 4 вызывается алгоритм ИБД для обработки на обоих деревьях левого сына вершины Ь. На обоих деревьях это вершина с, и на обоих деревьях у вершины с нет сыновей. ИБД возврашается в обоих деревьях к вершине Ь, и на шаге 5 вызывается ИБД для обработки правого сына вершины Ь. Когда на шаге 2 будет 1зо = Р, алгоритм установит, что деревья не изоморфны. 924 Ответы к упражнениям в) оо "го огг б) 5.
а) 7 в) б) 7. а) оо "г "г в) "о "г ог "з Ответы к упражнениям 925 9. а) 6) оо Д уз оз в) "о о~ з з 11. а) 6) "о "о 4 о о 7 о о в) о ! о о 3 у о о 3 г 13. оз точка — сочленения; оооооз, оооооз, оошоз, ооотоо — компоненты двусвязности 1б. Если ооо1оз оь 1 — цикл и если начать в вершине оо, то дерево поиска в ширину будет состоять из двух простых путей, оошог и сота |оь зтк з., поэтому оно будет иметь вид . озшоооь ооь-зоь-з .. Дерево поиска в глубину будет иметь вид иоо1оз оь Имеется Ь деревьев. В каждом одно из Ь ребер удалено. 17.
Пусть (а,Ь) — ребро графа. Если это не разрезающее ребро, то после удаления (а,Ь) граф остается связным, Следовательно, у графа, не содержащего (а,Ь), имеется остовное дерево. Если (а, Ь) — разрезаюшее ребро, то существуют такие вершины оо и ты что любой путь из оо в ш содержит ребро (а, Ь). Поскольку оо и о1 принадлежат любому остовному дереву и дерево связно, то на дереве должен существовать путь из ио в оы который должен содержать ребро (а, Ь). Следовательно, ребро (а, Ь) принадлежит всем остовным деревьям графа С.
19. Остовное дерево, полученное поиском в глубину для К„, — это простой путь вида о1ез оь или в любом другом порядке. Поскольку из любой вершины можно попасть в любую другую вершину, то при поиске в глубину каждая вершина будет в какой-то момент выбрана. Если при поиске в ширину вершина ш выбрана как начальная, то другие вершины являются сыновьями этой вершины, поскольку все являются смежными к ней. 21. Пусть Е' — разрезаюшее множество графа С. Если Е' удалено из графа, то граф перестает быть связным, и существуют такие вершины а и Ь, что путь из а в Ь отсутствует. Следовательно, в графе С любой путь из а в Ь должен содержать ребро из Е'.
Для любого остовного дерева графа С вершины а и Ь принадлежат дереву. Поскольку остовное дерево связно, то существует путь из а в Ь. Но этот путь должен содержать ребра из Е'. 23. пх2" 926 Ответы к упражнениям 25. Предположим, что граф С имеет п + 1 вершин. Следовательно, Т и Т' — оба имеют по и ребер.
Предположим, что они имеют )с общих ребер, так что каждое дерево имеет и — )с ребер, не принадлежащих другому дереву. Пусть С' — граф, который содержит и ребер дерева Т' и и — )с — 1 ребер дерева Т, не принадлежащих Т'. Граф С' содержит и+ и — 'и-1 = 2п — )с — 1 ребер. При формировании остовного дерева и — 'и — 1 ребер могут быть удалены из цепи. Ни одно из ребер дерева Т, не может быть удалено, поскольку в цепи всегда имеется ребро, не принадлежащее Т,.
Поэтому в остовном дереве остаются все ребра дерева Т, и одно ребро из Т'. 27. а) 1,1,0,2,2,6,6; б) 2,2,3,4,5,4,5; в) 2.,2,3,4,5,4,5; г) О, 1, 1, 1, О, 3, 1 1, 4, 14, 4, 3, О, 5, 15, 5. б) 29. а) Уг в) в) 24. б) 8; 31. а) 4; Раздел 15.6. 1. а Отееты к упремнениям 927 3.
Реэдел 16.1. 1. а) д) !). г) 10; в) 10 б) 5 (5,2) — не Р6 9. (а). 11. (а4). 928 Ответы к упражнениям Раздел 16.2. 1. а) б) в) а г) а ° г 1) Для каждого вновь отмеченного а, б А отметить все Ь~, для которых существует ребро ива; в Ь,, знаком г, если они уже не отмечены целым числом. 2) Если некоторое Ь, отмеченное знаком УЬ, теперь отмечено целым числом, то паросочетание расширено. Если никакое Ь, не является вновь отмеченным, то паросочетание максимизировано, 3.
Да. 5. Да. 7. Алгоритм (А,ВгМ): Отметить все а б А, для которых имеется ребро, инцидентное к а, в паросочетании М, знаком «. Отметить все Ь б В такие, что не существует ребро, инцидентное к Ь, в паросочетанни М, знаком тл. Ответы к упражнениям 929 3) Для каждого вновь отмеченного 6, б В, если существует а; такое, что существует ребро из а; в 6; в паре, отметьте его знаком У. 4) Вернуться к шагу (1). Раздел 16.3.
1. (!) (а), (б), (в); (й) (б), (в), (е); (ш) (а), (в), (г), (е), (ж); (!ч) (а), (б), (в), (г), (д), (е), (ж); (ч) (а), (в), (г), (е), (ж) (ч!) (б), (в), (г), (д), (е), (ж); (чй) (а), (б), (в), (г), (д), (е), (ж). 930 Ответы к упражнениям Раздел 17.1. 1. а) (аЬа,аса, ада); 6) (с, аЬс, аабс, аЬЬс, ааЬЬс, ас, Ьс, аас, Ьбс, аааЬЬЬс); в) (ас,ад,бс, Ы); г) (а, аЬ, аЬЬ, аЬЬЬ, Л, сг(, сг(сд, сЫсдсд, сдсдсг)сг(, аЬЬЬЬ); д) (аг(, абсд, абсбсд, абсбсбсг(, абсбсбсд, абсбсбсбсг(, абсбсбсбсбсд, абсбсбсбсбсбсд, абсбсбсбсбсбсбсбсд). 3. а) а(Ьысыд); 6) (аыЬ)(Ьыс); в) аЬаЬ*; г) (аЬ)'; д) а(ЛыЬыаыаЬ)Ь.
$. а) (аыс)" Ь(аыс)*Ь(аыс)*; б) а'Ьа'Ьа'са* са'ча'Ьа са* Ьа'са' ыа*са'Ьа'Ьа*са*ы ыа*са'са'Ьа'Ьа ыа са Ьа'са' Ьа'хна Ьа са' са Ьа', в) (аыЬыс)'Ь( аыЬыс)*Ь(аыЬыс)', г) а(а гбх с)'Ь(ах'Ьх'с) с(ач'Ьчс)'га(а гЬнс) с(а'гЪ|гс)'Ь(ах'Ьх'с)', д) аа*ЬЬ'сс 7. (6), (в), (д). 9. Однозначно декодируемые коды (а), (6) (в) (г) Суффиксные коды (а), (в), (д).
11. а) код не является однозначно декодируемым, т.к. в 111011 за 11 следует 1011 и за 1110 следует 11; 6) однозначно декодируемый префиксный код; в) код не является однозначно декодируемым, т.к. в 10101010 за 10101 следует 010 и за 1010 следует 1010; г) код однозначно декодируемый. Предположим, что существует два различных способа комбинирования кода для образования одной и той же строки.
Конечное слово кода одной строки должно быть заключительной подстрокой конечного слова кода другой строки. Но тогда слово кода, предшествующее самому короткому слову, должно заканчиваться на О, что невозможно; д) однозначно декодируемый префиксный код. 13. (а), (6). 15. (а), (б), (г). 17. Нет, 110011,1001 является кодом, который является суффиксным и префиксным, но инфиксным не является. 19.
Никакой. 21. (6). 23. Нет. 25. Пусть ю и ю' — элементы ключевого кода. Существует элемент алфзвита, который принадлежит ю и не принадлежит и/. Существует также элемент алфавита, который принадлежит ю' и не принадлежит ю. Следовательно, ни одна из строк не может быть начальной или конечной строкой другого элемента кода. Раздел 17.2. 1. (6), (в), (г). 3. а'Ь(аа*Ь) . 6.
(аыЬа) Ответы к уорежненияи 931 а ь с 4 ь с а ,ь а ь 932 Ответы к упражненияи Раздел 17.8. 1. а в ь в ь в ь А В А В А В А 1 ь ь Аав Аа Аа Б. аЬ(аЬ)*. 7. Ь'а Ь*а (Ь аЬ'аЬ )'. Раздел 18.2. 1. (с) ~ 1 1 1 0 1 0 О 3 а)С~= 1 1 0 1 0 1 0 1 О 0 1 0 О 1 б) 1111110, 0101101, 1001100, 1010011; в) 111, 110, 010, 011; г) дз, нет, нет, нет. ~О 1 1 1 0 01 В.а)Са= 1 0 1 О 1 0 1 1 0 0 0 1 б) 001101 011000 111101 101000 100101 110000 101001 111100 000010 000001 101111 111010 101100 111001 001001 011100; 100100 000000 100000 010000 001000 000100 100011 010101 001110 110110 011011 101101 111000 000011 110101 101110 010110 111011 110011 000101 011110 100110 001011 101011 011101 000110 111110 010011 100111 010001 001010 110010 011111 100001 010111 001100 110100 011001 100010 010100 001111 110111 011010 000111 110001 101010 010010 111111 Ответы к упражнениям 933 в) вместо 011001 должно стоять 011011; 111000 — правильно; вместо 110111 должно стоять 110110; вместо 101100 должно стаять 101101.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
