Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 73
Текст из файла (страница 73)
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. Ух аз ание. Возможны следующие наборы степеней вершин у графа Сгт (4, 3, 3, 2) и (3, 3, 3, 3). 2.18. Рис. 6.1: те(С) = 3, ~'(С) = 3. Рис. 6.3: ц(С) = 3, те'(С) = 4. Рис. 6.5, а: с(С) = 3, тс'(С) = 3. Рис.
6.5, б: х(С) = 3,;~'(С) = 3. Рис. 6.6, а: зс(С) = 3, у'(С) = 4. Рис. 6.6, б: с(С) = 2, те'(С) = 4. Рис. 6.6, а: у(С) = 4, у'(С) = 5. 2.19. Ц К(В") = 2, ~~'(В") = и. 2) у(К„) = и; если и нечетно, то у'(К„) = и, если же и четное, то у~(К ) = и — 1. 3) тс(К,„,„) = 2, ~'(К,„) = шах(тп, и) = и.
2.21. Указание. Применить индукцию по числу вершин. 2.22. У к а з а н и е. Можно применить индукцию по числу вершин. 2.23. Указание. Применить индухдию по числу вершин. 3.1. а) 0101001011. 6) 00010010111011. в) 0000101110010111. г) 0000110100101111, д) 0010110100010111. 3.2. См.
рис. 0.6.1. 3.3. Ц, 4), 6) Ла. 2) Нет, нарушено свойство 2. 4) Нет, нарушено свойство 1. 5) Нет, нарушено свойство 2. 3.4. Ц Классы разбиения имеют внд Кт = (от, от)., Кг = зтог, оз, Нз). 3.5. Провести индукцию по числу ребер. 3.6. Ц Число деревьев с и ребрами не превосходит числа кодов, которые являются двоичными векторами длины 2и. 2) Учтено, что число единиц в коде дерева равно числу нулей. 3) Учтено, что первая координата кода есть О, а последняя 1. 362 Ответы, указания, решенця 3.8 — 3.10. Провести индукцию, опираясь на индуктивное определение корневого дерева. 3.11. а) г(Т) = 2, Ю Т) = 2, Гэ(Т) = 3. 6) г(Т) = 1, 11(Т) = 2, тг(Т) = 4. в) г(Т) = 1, КТ) = 3, Г//Т) = 5. 3.13. Следует из задачи 3.12, 5).
3.14. Указание. Провести индукцию по величине радиуса дерева. 3.15. Ц Например, простой цикл длины 21 + 1. 3.16. Ц См. рис. 0.6.2. 2) 15. 3.17. Ц На рис. 6.16, б, г разложение е-типа; на рис. 6.16, а, д разложение р-типа; на рис. 6.16, е, е — разложение Н-типа. 2) На рис. 0.6.3, а представлена внешняя сеть Г/(а, Ь) е-расщепления гъ/ /, -''— - '/ з — г/ а б е г д Рис.
0.6.2 Рис. 0.6.3 сети Г(а, Ь), изображенной на рис. 6.16, а. На рис. 0.6.3, б, е, г представлены внутренние сети е-расщепления. 3.19. Ц Например, (2/ 5), (3/ Ц. 2) (1/ 5), (3/ 4). 3) Например, (2/ 6). 4) (1, 5). 5) 11, 5). 3.20. Ц Первое из неравенств вытехает из того, что в неразложимой, сильно связной сети каждая внутренняя вершина имеет степЕнгэ не меньшую 3, а каждый полюс имеет степень, не меныпую 2. Второе неравенство следует из того, что неразложимая и-вершинная сеть не имеет кратных ребер, а следовательно, число ребер меньше, чем у полного графа с и вершинами. 3.21. Через разделяющую вершину проходят все цепи. Поэтому она не может зависеть ни от какой неэквивалентной ей вершины. 3.22.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
