Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 73
Текст из файла (страница 73)
У него 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. Через вершину е, смежную с полюсами а, Ь, проходит цепь из ребер (а, э), (е, Ь). Эта цепь не проходит через какую-либо другую внутреннюю вершину СЕти. 363 Гл. РВ Графы и с/паи 3.23. 1) Да. Рассмотреть суперпозицию, где внешней сетью является сеть Г' (ш > Ц, а внутренние име/от вид Ге (к > 1). 2) Ла. Рассмотреть суперпозицию, где внешняя сеть есть сеть типа Г" (ш > 1), а внутренние имеют вид Го (ь > 1). 3) Па.
Рассмотреть суперпозицию, где внешняя сеть есть Н-сетгн а внутренние сети имеют вид Г'„' (к > Ц. 3.26. Неверно. См., например, сотен граф которой является полным и-вершинным (и > 3) графом. 3.2Т. л — 1. При выборе в В" в качестве полюсов вершин, находящихся на расстоянии 2, 3, ..., п, получаем неразложимые, попарно неизоморфные сети.
3.28. 1) Неверно, см. рис. 0.6.4/ а. 2) Неверно, см. рис, 0.6.4, б. 3) Верно. 4) Па, достаточно. 6) См. рис. 0.6.4, о. 3.3рь 1) Если нри удалении некоторой вершины из сети последняя становится несвязной, то удаляемая вершина является разделяющей. Таких вершин в Н-сети нет. 2) Верно. 3.31. Указание. Показать, что каждая внутренняя вершина полученной сети минимальная., и использовать ответ к задаче 3.24. 3.32. См, рис, 0.6.5. З.ЗЗ. См. рис, 0.6.6. 3.38. Рангом оеришны о сети Г(а, Ь) назовем расстояние о от а. Ребро сети, соединяющее вершину ранга г — 1 с вершиной ранга г, назовем а Ь а 6 а Рис. 0.6.4 Рис. 0.6.5 Рис. 0.6.6 ребром уровня г.
Заметим, что удаление всех ребер одного уровня, не превосходящего 1, делает сеть несвязной. Поэтому число ребер одного уровня не меньше 1. Число уровней в сети длины 1 не меньше 1. Отсюда вытекает утверждение. 364 Ответы, указания, решения Глава УП 1.1. Ц, 3), 4), 6) Код С не обладает свойстном префикса. 2), 5) Код обладает свойством префикса. 1.2. Ц Код не является однозначно декодируемым. Неоднозначно декодируемое слово: 01122 01. 2)., 4), 5), 8) Кол однозначно декодируемый. 3 0010001001. 6) 01101100112100. 7) 010210112 ) 1.3. Ц, 2), 4) Р является кодом одного сообщения. 3), 8) Р не является кодом сообшения.
5) — 7) Р является кодом более чем одного сообшения. 1.4. Ц Р е ш е н и е. Пусть С(А) множество двоичных разложений чисел из А; С(А) = (1, 101, 110, 111, 1100, 1101, 1000Ц. Вычеркнув из С(А) слова 1 и 110, получим префиксный код. Вычеркиванием меньшего числа слов обойтись нельзя. Таким образом, для задачи а) В = А)(1, 6). 2) а) В = А)(1, 3, 6, 8); б) В = А)(Ц. 3) а) В = А1(2, 6, 7, 8, 9); б) В = А)(2, 7). 4) а) В = А)(1, 2, 5); б) В = А)(1, 2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
