Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 158
Текст из файла (страница 158)
Продолжать шаг (3), пока асе скобки не будут удалены. Раздел 5.6. 1. 1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 10000, 10001, 10010, 10011, 10100, 10101, 1011010111. 3. а) 101101; 6) 1010110; в) 11110011; г) 11000010; д) 100111000. 5. а) 11; б) 26; в) 36; 7. а) ЗР; 6) 74; в) 178; 9. а) 74; 6) 755; в) 1274; 11. а) 10111.111; 6) 101011.11; г) 1011110.1100; д) 110100.010011. 13. а) 14.75; 6) 10.625; г) 3.4375; д) 13.3125. 15. а) 24.А; 6) А1.С8; в) 250.28; г) 754.8В7)7; д) 147Е.59.
17. а) 92.2265625; в) 1199.767578125; д) 5070.821289062. 19. а) 5.А; 6) 37.54; в) 1В6.6Р8; г) ЗАЕ.36С; д) ЗВ4.228. 21. а) 101100.01001011; в) 101011111000.010010001100; д) 1100000101001010.001011010100. 884 Ответы к упражнениям г) РС44. г) Р970. г) 35ЬЗ. г) РР31. Раздел Б.8. 1. в) — 1; г) — 234. 3. — 1. 5. Если А — перестановочная матрица, то в каждой строке и в каждом столбце этой матрицы только один элемент равен 1, а все остальные равны О. Пусть В = АА'.
Пусть А, — строка матрицы А и пусть в 4-ой строке А,» = 1. Если А' — У-ый столбец в транспонированной матрице А', то ВО = 1 тогда и только тогда, когда А,'„= 1. В противном случае В„= О. Но А'„; = А,ы поэтому ВО = 1 тогда и только тогда, когда А,» = 1. Но поскольку имеется только одна 1 в каждой строке и столбце, то это имеет место, только если з = з. Следовательно, В, = 1 тогда и только тогда, когда Г = У, поэтому  — единичная матрица. в) 15 Раздел 6.Е 6) путь, не простой путь, длина 6; г) путь, не простой путь, длина 8. 6) цикл, не простой, длина 8; г) цикл, простой, длина 6. 1.
в) путь, простой путь, длина 5; в) путь, не простой путь, длина 7; 3. а) не цикл, г) 7. Компонента представляет собой наименьший подграф такой, что если точка, изображающая палочку, принадлежит графу и палочка касается другой палочки, то вершина, изображающая вторую палочку, и ребро между ними принадлежат подграфу. Иными словами, это граф, представляющий совокупность палочек, лежащих одна поверх другой. Раздел б.2. 1. а) И = 1а,б,с,д,е). Вершина а имеет степень входа 2 и степень выхода 1, вершина Ь— степень входа 1 и степень выхода 1, вершина с — степень входа 2 и степень выхода 1, вершины д н е — степень входа 0 и степень выхода 1, вершины д и е — источники; б) И = 1а,Ь,с,д,е).
Вершины а, Ь, Ы и с имеют степень входа 0 и степень выхода 1. 3. в) 01001001; в) 11011011; 5. в) 00100110; в) 10111111; 7. а) 01000111; в) 11101000; 9. а) 8РС6; 6) 54ЕО; 11. а) 010Е; 6) ГС83; 13. а) С5СО; б) Г6С9; 15. в) 04АА; б) 15ВР; 17. -2147483648 го 2147483647. 6) 10011011; г) 11110010, 6) 01111110; г) 11000101. 6) 01011101; г) 00000110. в) 05ЕЕ; в) РГЕГ; в) ЕР7С; в) Р4В1; Ответы к упражнениям 885 Вершина е имеет степень входа а и степень выхода О.
Вершины а,64 и с — источники. Вершина е — сток; в) Ъ' = (а, Ь,с, Ы,е, Д. Вершина а имеет степень входа О и степень выхода 2. Вершины Ь, с и И имеют степень входа 1 и степень выхода 2. Вершина е имеет степень входа 1 и степень выхода 1. Вершина У имеет степень входа 5 и степень выхода О.
Вершина а— источник, а вершина У вЂ” сток. г) 1' = (а,б,с,д,е). Вершина а имеет степень входа 2 и степень выхода 1. Вершины Ь, И и е имеют степень входа 1 и степень выхода 1. Вершина с имеет степень входа 1 и степень выхода 2. 3. а) Ые — — ~~е Нв ве Ив~~с Ые ве ° с ° с ° с ае — и'вЬ а» вЂ” ьвЬ аве =.вЬ ав' эЬ в) г) ь б.
а) б) совпадают с построенными в (а) в) а Ь 888 Ответы к упражнениям г) 7. Ориентированным циклом называется ориентированный путь, который начинается и за. канчивается в одной и той же вершине. 9. Орграфы (а), (б), (г) — связные, граф (б) — сильно связный. 11. Орграфы (а), (в), (г) — связные, граф (в) — сильно связный. Раздел 6.4. 1. а) фронтальная ж б) фронтальная задняя с ж левая правая з левая правая с задняя с ж к з ж г) фронтальная з к в) фронтаЛьная з задняя ж левая правая к ж задняя с левая правая ж д) решение отсутствует. Раздел 6.6.
1. (а). 3. (в). Б. (а), (в). 7. (б). 9. Предположим, что граф С связный и ровно две его вершины имеют нечетную степень. Раздел 6.3. 1. (а), (б) и (д). 3. (а); (б) и (в). 5. Поскольку каждая компонента С, — дерево, то от = е, + 1. Следовательно, для каждого целого дерева имеем 2, т ит = т... 4(е, + 1), поэтому и = е + т. 7. а) нв,ит, ив, иэ, 'б) ио, из, ив', в) ит, г) 2; д) ив, ит', е) 3; ж) оз, ив, иъ, ют, из, иэ, э) нет, ио имеет степень выхода 3.
9. Воспользуемся индукцией по количеству вершин. Если И и = 1, то е = О. Таким образом, теорема верна, если и = 1. Предположим истинность утверждения теоремы для и = /с, Пусть Т вЂ” дерево с )в+ 1 вершинами. Удалим лист и инцидентное ему ребро. Теперь дерево имеет к вершин. Следовательно, по индуктивному предположению, для этого дерева о = е+ 1. Если возвратить на место лист и ребро, то количество вершин и количество ребер увеличится на один. Поэтому для дерева с )в+ 1 вершинами по-прежнему будем иметь о = е+ 1.
Ответы к упражнениям 887 Раздел 6.6. 1. а) е! в! 1 вз 1 вз 0 ве 0 в. 0 б) е! в! 1 вз вз 0 ве 0 вз 0 ве 0 вт 0 вз 0 г) е! в! 0 вз 1 вз 0 ве 0 вз 1 ег ез ее ез ее о о ! ! о 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 1 0 1 ее еъ ее о о о 1 1 0 0 0 0 О1О о оп 1 0 1 0 0 0 о о е7о еы ею о о о 0 0 0 1 0 0 1 1 0 о о о о о о 0 0 1 0 1 1 Ед ЕЗ 1 0 0 0 0 0 о о 1 1 0 1 0 0 0 О Ет ЕЗ Ед о о 0 0 0 1 0 1 о о о 0 1 0 о о о 0 1 1 0 0 0 в) е! ез 971 0 вз 1 взо 1 чО О взо 0 ез ее ез ед 0 1 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 ее е- ее о о 0 0 0 0 1 1 1 0 1 0 1 0 ез ез 0 1 1 0 0 1 1 0 0 0 ет ез ед 0 1 1 0 0 1 о о о 1 0 0 1 1 0 е79 о 1 ) а 0 3.
а) в! вз 970 1 вз1 0 взо 1 в41 0 вз1 0 б) в! в! 0 вз 1 вз 1 ве 0 1 ве 0 вт 0 вз 0 вз ве вз 0 1 1 1 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 вз вз 1 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 Вт ВЗ 0 0 0 0 1 0 0 1 1 0 0 1 0 1 1 0 Пусть а и Ь вЂ” вершины нечетной степени. Если между о и Ь ребро отсутствует, добавим его. Теперь каждая вершина имеет четную степень, поэтому новый граф имеет эйлеров цикл.
В этом цикле следует проходить и ребро (а,6). Например, проходя цикл, мы движемся от а к Ь. Если начать с этого ребра и пройти цикл, то легко заметить, что если ребро удалить, начать путь в вершине Ь и пройти его, следуя циклу, то получим эйлеров путь из Ь в а. Если между а и Ь имеется ребро, удалим его. Новый граф имеет эйлеров цикл, если он по-прежнему связный. Пусть эйлеров цикл начинается и заканчивается в вершине а. Если мы пройдем этот цикл, а затем проследуем вдоль удаленного ребра от а к 6, то получим эйлеров путь ото к Ь. Если новый граф перестал быть связным, то он имеет эйлеров цикл для компоненты, содержащей вершину а, который начинается и заканчивается в вершине о, а также для компоненты, содержащей вершину Ь, который начинается и заканчивается в вершине Ь. Пройдем эйлеров цикл от а к а, удаленное ребро от а к Ь, затем пройдем эйлеров цикл от Ь к Ь.
В результате получим эйлеров путь от а к Ь. Предположим, что граф С имеет эйлеров путь. Пусть, например, он начинается в вершине а и заканчивается в вершине Ь. После первого ребра пути, выходящего из а, для каждого ребра пути, который ведет в а, должно существовать ребро, выходящее из а. Поэтому вершина а должна иметь нечетную степень. Аналогично, вершина Ь должна иметь нечетную степень. В любых других вершинах, для любого ребра пути, который ведет в эту вершину, должно существовать ребро, которое выходит из этой вершины. Поэтому вершина имеет четную степень.
11. Если граф сильно связный, то для любой его вершины в, несомненно, любая другая вершина достижима из вершины в, и в достижима из любой другой его вершины. Обратно, пусть имеется вершина в, обладающая указанным свойством. Пусть а и 6 — произвольные вершины. Поскольку существует путь из а в в и путь из в в 6, то существует путь из а в 6, поэтому рассматриваемый граф сильно связный. 888 Ответы к упражнениям В) и1 и1 О и2 1 из О и4 1 и- О Г) и1 и2 310 1 О из 1 ! 341 1 из! 1 из и4 из 1 1 1 1 1 1 О О О и2 из и4 из Ото О1!О О О О О!Об Аз = 9. А= О О О 1 О и1 и2 из и4 иъ 2-реберные из из в и1,из,из, из О О 1 1 О О О 1 1 О 1 1 О О 1 1 1 О О 1 О О 1 1 1 1 1 О О 1 1 1 О О 1 О О 1 1 О О О 1 1 О 1 1 О О 1 О О 1 1 О О О 1 1 О 1 1 О О 1 1 1 О О 1 О О 1 1 1 11.
а) б) в) 13. 43 = ((и1, и1), (и1,и2), (и1,из), (и2,и1), (и2, и2), (и2,из), (из,и1), (из,и2), (из,из), (и4,и4), (иъ, иъ), (и4, и5), (из, и4)) 15. АхА. 17. В = ((и1, и1), (и!,и2), (и1,из), (и2,и1), (и2,и2), (и2, из), (из,и!), (из,и2), (из,из), (и4,и4), (иъ и5) (и4 иъ) (и5 и4)) ° 19. А х А. 21. 23 = ((и1, из), (и1, из),(и4,и4), (и4, из), (из, и4), (из,из)). 28. Ребрам соответствуют одинаковые столбцы. 28. По определению матрицы смежности, теорема верна, когда и = 1. Предположим, что она верна для и = !4. Следовательно, й-путь из вершины и, в вершину и существует тогда и и1 и2 из и4 О 1 1 О 1 О 1 О 1 1 О О О О О О О О О 1 из и1 в и1,из,из и1 и1 1 и2 1 из 1 и4 О иъ О из в и1 иъ О О О О 1 и4, из из во и2 из и4 1 1 О 1 1 О 1 1 О О О 1 О О О и2,из, нз и4 В Ответы к упражнениям 889 только тогда, когда Ао" = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
