Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 73
Текст из файла (страница 73)
в) Т(Р) = 101гОг1. 4) а)-в) К данному слову не применима. 5) а) К слову 1г не применима. 6) Т(Р) = 1з. в) Т(Р) = 1 . 1 2. 1) Одна из возможных машин залается такой программой: уз1дг 1Л. 2) Программа одной из таких машин: дгОдгОВ, дг1уг1В. 3) Программа одной из таких машин: угОдгОЯ, дг1дг1Я. 1'ж )г. Эпемепшы гпеорип ипгоришиов 357 4) Одна из возможных машин задается следующей программой: узОдгОЛ, Ф1дг1й, узОугОЛ.
1.3. Ц а) доЦ01]г, 2) 6) 1]10]~уо1. 3) 6) 10до1 01. 4) а) 1'Овдо1. 5) а) 1гОг1до01. в) ]10]гОда1г. 1.4. 3) Программа одной такой машины имеет вид узОуг07' уйу40Л дз1ув1Л двОдзОЛ дгОдзОЛ, дзОузОВ даОдг15 дв1дв17 уг1уг15 дзгдз1Л дгОдв07 дзОдоОЛ дзОувуй дг1уг17 1.5.
2) Пусть доз, ..., уо„, (~п, > Ц все заключительные состояния заданной машины Тьюринга. Нужную машину можно построить так: заменяем каждую команду вида д,одаг~Ю (о, Б символы внешнего алфавита, 77 Е 1Б, То Л)) на командУ д,одг)г77, где д,' новое состоание (длк каждого состояния уо, свое). 1.6. Для построония машины Т достаточно добавить ш дополнительных (новых) состояний у], ..., д,„и «пополнить» программу машины Т, например, такими командами; дзодзоБ, ..., д,„од,„оБ, где о . - какой-то фиксированный символ из внешнего алфавита. 1.7. Таких машин 15.
1.8. Ц Одна из возможных программ: дг1дг07о дгОда1Б, дг1уг15. 2) Одна из подходящих программ: дзОузОЛ, уз1уо1Л. 5) Одна из возможных программ: дгОдг1Л, дг01з1Л,, д~Одыг1Л.. ; ди — гбдгг1Л, дг~0до1Б, Ф1дг1Л, дг1дз1Л. °, д 1д +г1Л, ° °, дг~ — г1дг~1Л. 1.9. Ц а) Композиция ТгТ к 1 0 1 не применима. 2) а) (ТгТг)(Р) = 1]10]']01]з1. 3) 6) (Т,Тг)1Р) = 1'01г02'1'-, 1.10. Ц а), б) Указанная итерация к словам вида 1зк и 1зз ы (й > Ц, не применима. в) Итерация применима к любому слову вица 1~в+а (й > Ц, и в результате получается слово 1.
3) Итерация к данным словам применима, результат слово 1г'~в~'. 1.11. Ц Т(Р) = 10 1. 2) 6) Т(Р) = 1'0101в01'01. 1.12. 2) пТг ]дга ] Тз ]узо аз ]ТгТвТз ] г,з г г з 3) оТз]дзо ]Те]два Тг(Р) = ТгТзТзТзТ4] ]Та ]ТгТзаг. з г г г з 1.13. Ц Т(Р) = 1*01'~". 2) Т(Р)=1', если х>у>1, Т(Р)=1о, если р>х=1, и Т(Р)= =1" 01" '"',если у>х>2. 1.14. 6) Функция определена только при х = О., 1.
Одна из возможных программ такова: дгОуо1Б, д~1дг1Л, дгОдг1Л, дг1дз1Л, дз1дз1Б. 12) Указание. Функция определена только на следующих парах значений аргументов: (О, Ц, (О, 2), (1, Ц и (2, )7), где Л > 1. 1.15. 3) Функдия определена только нри х = 2, 3. Одна из возможных программ: дгОда1Б, дг1дгОЛ, угОугОБ, дг1дзОЛ, дзОдзОБ, дз1дзОЛ, двОдг1Ь, д41двОЛ, дзОд41й, уз1дз1Б.
1.16. Ц Дх)=хе-1, ~(х,р) =х-~у-е1. 3) Дх) =О, ~(х, у) =уф1. 6) 1(х) нигде не определена, 1(х, у) = р. 358 Ответы, указания, решения 1.17. Если машины начинают работу с самой левой единицы кода числа х, то вычисляются следующие три функции; х, х — 1 и нигде не определенная. 1.18. Ц Подходящая программа: дгОдз177, дг1дгИй дгОдгОЙ, д 1дг171, дз0940В, дз1д41В, д40до18. 1.19. Ц а) Ленному 1-кратному коду соответствует решетчатый код, расположенный на двух решетках, со следующей парой слов: 1 и 11. Значит., надо построить машин) Т, удовлетворяющую условию: начав работу на первой единице слова 1 0'1гг, она выдает слово 1101 (решетчатый код набора (О, Ц), Подходящая программа: дгОдгОЯ, дг1дгОй„дгОдгОН., дг1дзОЙ, дз0941п, дз1дзОге, д40де1ге, деОдеОК, д«0до1Б.
2.1. 4) 7(х) = их 7(0) = и 0 = О, 7(х -Ь Ц = Цх, 7(х)) = гг(х+ Ц = = их -Ь и. = 1(х) -> и = з(з ... в(1'(х))...). Значит, оэ Мх, у) = (в " (у) " ) = 1гг(х: ( е(у) " )) 7) Указание. Пля требуемого примитивно рекурсивного описания функции х ° у на «первом этапе» нужны функции у(х) = 0(х) и 1г(х, у, г) = х+1,,(х, у, г). «Второй этап» связан с описанием функции 1г(х, у, з). 2.2. Ц 7(х, у) = х(у+ Ц.
2) 1(х, у) = х+ (у — ' Ц. 4) 7" (х, у) = 3'то1о 'У . 5) 7'(х, у) = об у -Ь (х — (у — ' ц) в8 у. 7) Д(х, у) = (2х) в8у+ (у — ' Ц в8 ((у — ' Ц вЂ” 'х). 8) 7"(х, у) = в8 х в8у-Ь х в8(у — 'Ц. 2.3. 3) шах(х, у) = (х — ' у) + у. 8) Указание. 1(х) = ~ а, . в8 [х — г[ 4- с . П в8 [х — г[. =о =о 9) Указание. Д(х) = х Х(х), где 1Е(х) = х — '2[х/2) .-. характеристическая функция множества нечетных чисел.
10) 1" (х) = в8(х — 'т [х/т)). 1Ц Указание. [зггх-Ь1 = [тех) 4-дг(х), где дг(х) =в8(([ьгх)-~Ц вЂ” '(х + Ц). 2.4. 7) а) Указание. 1г(х) получается из примитивно рекурсивной 7(х у) = ~~' в8[х — а'[ отождествлением переменных х и у. =.о б) Указание. уг(х-1- Ц = уг(х)-> уз(в+2), где уз функция из задачи а). 2.5.
Ц в8[хг — 3[ — 1. 2) хг — 2. 3) х~ + 2. 5) (хг — Ц,12. 6) ((хг -~- Ц.вбхг)/2. 9) (6хг — 4) в8хг. 10) (хг — хг) -~-(хг — хг). 12) (ейхг) . (2хг -~- Ц7в8(2 — 'хг). 359 Га. г7, Графы и сесин 14) 1о8 (х1/(2хг + Ц) пРи г = 1; (хг — 2 ')/2" т~ пРи г = 2. 15) (хг — Ц/зб(3 — ' х1). 2.6. Ц 2 — 'хг. 2) 2хг. 3), 4) Такой функции нет.
5) хг г-2хг. 6) Зхг -~-хг. 7) хг . (хг -~-2). 8) хг (1 — 'хг). 2.7. Ц д,,юх — ' Ц/2]) = (2х 4- Ц збх. 4) р, (х л— [х/3]) = (З[х/2]+ Ц вЂ” '2 з8 (х х— 2[х/2]). 5) Р ([ъ'хг]) = [багха] + зб(х — '[згх]~). 6) р*(х х— [тих])' = х+ [(х+ Ц!2]г. 2.8. 2) ф( ) = 1. 3) Функция 1(х) должна быть не определена при х = О. 4) ф(х) всюду определена и принимает каждое значение из множества (О, 1, 2,... ]. 2.9. Ц Не может. 2) Не могут. 2.13.
Ц Не следует. Если же машины Тг и Тг правильно вычисляют примитивно рекурсивные функции уг и фг (соответственно), то их композиция ТгТг вычисляет (причем «правильным образом>) функцию гг(г г (х)). 2) Не спранедливо. 2.14. Да, вытекает. 2.16. 2)-8) Указание. Лостаточно построить соответствуюшую суперпозицию над множеством, содержшцим заданную функцию и подходящие функции из совохупности (О, 1, 2х, хг). Например, для функции из задачи 5) имеем ф(х 1 ) = ф(х). Затем надо провести рассуждение от противного. 2.17.
Указание. Построить машину Тьюринга, вычисляюшую следуюшее обшерекурсивное доопределение функции 1(х): / ф(х), осли в точке х функция ф(х) определена, ф(х) = ( х, если в точке т функция 1(х) не определена. 2.18. Ц Полной системой не является. 2), 3) Полная система.
Глава Ы 1.2. Ц Указание. Такой граф один. У него 5 вершин и 8 ребер. 2) Указание. Таких графов 3. 1.3. Указание. Таких графов 11. 1.5. 2) Указание. Таких графов 9. 1.6. Лва. 1.7. Лва. 1.8. Ц Не сушествует. 1.9. Имеется 5 допустимых наборов степеней вершин. 1.11. Указание. Набор степеней вершин у одного из таких п-вершинных графов имеет вид (1, 2, ..., 'и — 1, [гг/2]). 1.12.
Лля маршрутов четной длины утверждение неверно. 1.13. 2) Указание. Рассмотреть граф, состоягцнй из двух изолированных вЕршин. 360 Ответы, указания, решения 1.16. Общего ребра может не быть. 1.20. 4) Так как в нетривиальном самодополнительном графе С имеются несмежные вершины (ибо он отличен от полного графа), го Р(С) ) 2. Палее, из задачи 1.19, 3) следует, что если Р(С) 3 4, то Р(С) ( 3. Но С самодополнительный граф. Значит, он изоморфен С, а поэтому неравенство Р(С) ) 4 выполняться не может. 1.21.
У к а з а н и е. В задачах Ц вЂ” 3) удобнее строить дополнения искомых графов. 1) 9 графов. 3) 11 графов. 4) 5 графов. 1.24. Указание. Из теоремы Кбнига следует, что данный граф двудольный. 1.27. У к а ванне. Воспользоваться тооремой Эйлера (см. задачу 1.Ц. 1.28. 2) Указание. Лля каждого п, ) 2 существует только одно такое дерево. 1.29.
2) Указание. Таких деревьев 4. 4) Указание. Таких деревьев 3. 1.30. 6 деревьев. 1.31. Такой граф один. Указание. Используя результат из задачи 1.19., 2), можно оценить сверху число вершин у тахого графа. 1.34. На рис. 6.1, 6.3 и 6.4 изображены пары изоморфных графов. Указание. Полезно рассмотреть дополнения этих графов. 1.35. 1) Могут быть не изоморфными.
1.36. 1) В каждом из графов, изображенных на рис. 6.6, существует подграф, гомеоморфный Кю 2) В графе Петерсена (см. рис. 6.6, а) и в графе, изображенном на рис. 6.6, в,. подграфов, гомсоморфных графу Кв, нет. В графе, представленном на рис. 6.6, б, сугцествует подграф, гомеоморфный Кз. 1.38. 2) Можно применить индукцию цо числу вершин в псевдографе. 1.39. 1) 4 орграфа. Односторонне связных четыре.
Сильно связный один. 2) 4 орграфа. Сильно связных два. 3) 9 орграфов. Слабо связных четыре, односторонне связный один. 1.40. 1) 6 псевдографов. Сильно связный один. 2) 10 псевдографов. Слабо связных восемь, сильно связных два. 3) 3 псевдографов. Односторонне связный один. 1.41. 1) 6 графов. 2) 12 графов. 3 ) 9 графов.
1.42. 2) 4 турнира. 1.43. Лва турнира. 1.44. 1) 4 дерева. 2) 9 деревьев. 3) 15 деревьев. 1.47. Можно применить индукдию по числу дуг. 1.48. 2) Нельзя. 1.55. Можно применить индукцию по числу дуг. 1.58. Указание. Применить индукцию по числу вершин. 1.59. 1) Указание. Применить индукцию по к. 1.62. Ух аз ание. Лля турнира с п вершинами иы ..., и,. выполняются равонства ~~ дв(и,) = и е)т(и,) -~-4 (и,) = п — 1 (г = 1, ..., и).
2 =з 361 Га, тй Графы н остин 2.1. Ц Каждый из рассматриваеътых графов содержит подграф, гомеоморфный графу Кз,з. 2) Каждый из графов, изображенных на рис. 6.6, а, а, содержит подграф, гомеоморфный графу Кз,з. У графа, приведенного на рис. 6.6, б, есть подграф, гомеоморфный Кз. 2.2. а) Прн всех п > 2. 6) Только при и = 2. 2.4. Таких графов четыре. 2.6. 3) Указание. Оценка для числа граней имеет вид бф ( 2т. 4) Указание.
Зля получения противоречия оценивать число граней нужно достаточно тонко: ф = фз 4- ф>.т, где фз число граней, ограниченных циклами длины 3, а ф>т число остальных граней; Зфз + 4ф>4 ( 2ти. 2.7. Ц а), б) 2 вершины. 2) а) 3 ребра. 6) 4 ребра. в) 2 ребра. 2.8. Ц Не существует. 2) Существует. 2.9. 6. Указание. Рассмотреть граф, получающийся из Кз после удаления одного ребра. 2.10. Ц Не существует. 2) Указание. Таких графов два. 2.11. Ух аз ание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
