Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 163
Текст из файла (страница 163)
29. Пусть 7; С(Е, У) — С'(Е', У') — изоморфизм. Если граф С двудольный, то У = А О В; при этом не существует ребро между вершиной из А и вершиной из В. Если существует ребро е' между 7"(а) б 7"(А) и /(Ь) б з'(В), то е' = Де), где е — ребро между а и 6. Но это противоречит предположению, что граф С двудольный. Следовательно, граф С' двудольный.
31. По определению, каждая вершина графа С принадлежит его дополнению. Таким образом, пересечение графа С и его дополнения содержит все вершины графа С. Ни одно из ребер графа С не принадлежит его дополнению. Следовательно, пересечение графа С и его дополнения не содержит ни одного ребра графа С.
Значит, пересечение графа и его дополнения представляет собой граф, состоящий только из вершин графа С и не содержащий ребер. 33. Пусть е — разрезающее ребро графа С и С вЂ” граф С с удаленным оебром е. Пусть С' — граф С' с удаленным ребром 7'(е). Пусть / — изоморфизм из С в С'. По определению разрезающего множества, существуют вершины а,6, которые не связаны в С. Поэтому они принадлежат различным компонентам графа С. Следовательно, как показано в предыду- щЕМ уПражНЕНИИ, 7(а) И Г(Ь) ПрИНадЛЕжат раЗЛИЧНЫМ КОМПОНЕНтаМ Графа С', И Граф С' несвязный. Вполне очевидно, что 7(е) — разрезающее ребро графа С'. 35. В матрице смежности графа имеется единица, если в матрице смежности его дополнения имеется нуль. 37.
Пусть аг,аз,аз,...,а„ вЂ” вершины графа С, и Р— перестановочная матрица размерности и х и. Пусть ш = (1, О, О,..., О) представляет аг, оз = (О, 1, О,..., О) представляет аз и о, = (0,...,0,1,0,...,0) представляет а„ где 1 находится на 1-ом месте. Аналогично, пусть мч = (1,0,0,...,0), представляет аы ыз = (О, 1,0,...,0), представляет аз и ш, = 912 Ответы к упражнениям (О,...,0,1,0,...,О) представляет а„где 1 находится паз-ом месте. Определим У(а,) = Ь,, если Ри, = нн.
Предположим, что Яа,) = Ь, и У(аь) = Ьь Тогда Р„= 1 и Ргь = 1 Рассмотрим произведение РВР', где  — матрица смежности графа С. Пусть Т = ВР', Тогда, посколькУ Р„', = Ргь = 1, то В,ьРь, = Тт ПУсть В' = РТ. ПосколькУ Рсн = 1, то В,', = Р„Тн, поэтому число в)-ой строке и в 1-ом столбце матрицы В' равно Вм, и ребро между Ь~ и Ь1 существует тогда н только тогда, когда существует ребро между а, и аь. Следовательно, С и С' изоморфны. Обратно, если они изоморфны, то матрицы В и В', определенные выше, являются матрицами смежности для соответствующих графов. 39. Разрезающие множества включают ((а,Ы),(а, Ь)), ((д,е),(д,а)), и ((У,д),(У,1)). Раз- резаюшими ребрами являются (Ь,с), (е, У), (ЕУ).
41. Пусть е = (о,о') входит в цикл ио'ш .оь го и пусть а,Ь вЂ” вершины графа С. Если имеется путь из а в Ь, который не включает е, то путь нз а в Ь существует, если ребро е удалено. Если е не входит в путь, то заменим ребро ио' путем соь 1. шо', и путь ива в Ь по-прежнему существует. Обратно, допустим, что е = (о, о') не является разрезаюшим ребром. В этом случае, если ребро е удалено, то по-прежнему имеется путь соь 1 .шо' из о в о', и еоь 1 шо'о является циклом. 43.
Если С,(ьн Р,) состоит из единственного ребра е, то не сушествует простой цикл графа С, содержащий е, поэтому е — разрезаюшее. 4$. Если воспользоваться определением объединения, которое дано в определении 14.14, то вполне очевидно, что любой граф С, является подграфом объединения ()", А,. Также, согласно этому определению, если любой граф С, принадлежит графу С", то каждое ребро и каждая вершина любого из графов С. принадлежат С".
Следовательно, каждое ребро и каждая вершина объединения графов С, принадлежат С". Таким образом, определение объединения, которое дано в определении 14.14, удовлетворяет определению, данному в задаче. Два определения эквивалентны, если сушествует только один граф, удовлетворяющий определению, данному в задаче. Но если имеются два графа С' и С", удовлетворяюшие определению, то С' -с С" и С" с С', поэтому С" = С'. Раздел 14.3. 1. а) да, граф нарисован так, что линии не пересекаются; б) нет, граф содержит Кз,з как подграф; в) нет, граф содержит Кз как подграф; г) да, граф можно изобразить как д) да, граф можно изобразить как б) нет, граф содержит Кз,з как подграф.
3. а) да, граф можно изобразить как е Ь Ответы л упрвжненцям 913 в) да, граф можно изобразить как г) да, граф можно изобразить как Ь а с — в д) да, граф можно изобразить как б. Если имеется 12 вершин степени 3, то степень вершин равна 36, поэтому имеется 18 ребер. Поскольку о — е + 1 = 2, то 12 — 18 + з' = 2 и Х = 8. 7. а)4; б) 6; в) 2/с. 9. Поскольку граф с 4 вершинами не может содержать граф, гомеоморфный подграфу, гомео.
морфному Кз или Кз,з, то он должен быть планарным. С другой стропы, легко показать, что граф К4 планарный. Поскольку любой граф с 4 вершинами — подграф графа К4, он является планарным. 11. Будем использовать индукцию по количеству ребер дерева.
Очевидно, что любое дерево с одним ребром — планарное, Предположим, что любое дерево, имеюшее к ребер, планарное. Пусть Т вЂ” дерево, имеюшее й+1 ребер. Любое дерево имеет вершину степени 1. Выберем такую вершину и удалим ее и ребро, инцидентное к ней. Оставшееся дерево по индуктивному предположению является планарным. Удаленное ребро и вершина могут быть снова добавлены так, что ребро не пересечет ни одно из других ребер.
Следовательно, дерево Т вЂ” планарный граф. Раздел 14.3. в) 1. а) Е, Е Е Е Е Ес Е, 914 Отеегпы к упрелгнениям г) г д) Е Ег 3. а) 2; б) 3; в) 4; г) 3; д) 4. Б. К,„содержит множество т вершин и множество и вершин. Ребра имеются только между двумя множествами, Поэтому можно раскрасить одно множество одним цветом, а второе множество — другим. 7.
а) Л(Л вЂ” 1)(Л вЂ” 2)г; б) л(л — ц (л — г); г) л(л-ц(л-г)', в) Л(Л вЂ” 1)(Л 2)г(Л 3) Раздел 14.4. 1. а) асдуедЬа; в) а6161дседа; б) а61есда; д) не существует. б) абсдеу; г) не существует; в) УдседаЬум 3. а) аЬсде; г) едасд166; д) адбсеудЛ. $. Если граф С имеет гамильтонов цикл, то любое ребро является частью цикла. Но разрезающее ребро не может быть ребром, входящим в цикл. Следовательно, С не содержит разрезающее ребро. Пусть (а,Ь) — разрезающее ребро и компоненты С1 и Сг — компоненты, имеющие гамильтоновы циклы, например, ашигоз оь га и Ьи(огиз о',6. Тогда и1сгоз оь-1або',огсз о', — гамильтонов путь. 7. Ь д) Л(Л вЂ” 1)(Л вЂ” 2)г.
9. Если планарный граф изоморфен своему двойственному графу, то количество граней равно количеству вершин. Поскольку о — е + 1 = 2, топ — е + и = 2 и е = гп — 2. Раздел 14.Б. 1. а) б) ««(7,5) «11,0) «/ 14,5) Юг) «(9,7) «(0,0) ;(5,2) г) а) 1 (4,1) з(2,0> , (б,З> «е(0,0) «(7,2) «(5,2) «,(З,З) о «,(5,5) ,(о,о> ;(1,о) б) 3. а) ««(4,6) .(5,8> «(о,о> «,(2 О> «з(««о> ;(7,5);(з,о);(0,0) ,«о) "«« ,(О,О) ° ° з(4,11 1 ° «(15,4) 1«(5,2) б «з(8,2) б « (5,1) з ;(о,о> ° 2 1 б' ,л «,(5,1) Э Ответы к упразкнениям 919 в) г) «,(3,2) ««(5,2) «,(з,а) «,<з,о) (б,а) « (е,о) ;(о,о) «(б,г) п<з,а) г «5(ап « (2,0) 5 ,(5,2) д) ,<ззп Раздел 15.1 3, а) 63 вершины, 32 листа и 31 внутренняя вершина; б) 141 вершина, 81 лист и 60 внутренних вершин; в) 511 вершин, 256 листьев и 255 внутренних вершин; г) 85 вершин, 64 листа и 21 внутренняя вершина; д) 10 вершин, 1 лист и 9 внутренних вершин.
Б. а) (!) 5, (й) 2 ((й) 4, (<ч) 2, (ч) И, (ч() е,а; б) (!) 5, (й) 4 (гй) 2, ((ч) 2, (ч) д, (ч!) е, д; в) (!) 4, (й) 3 (И) 1, ((ч) 1, (ч) Ы, (ч)) е,д; г) (!) 6, (й) 5 (гй) 3, ((ч) 3, (ч) д, (ч() е,д; д) 0) 4, (й) 1 (й!) 3, (<ч) 1, (ч) «К, (Ш) а,е, д. 7.
а) сбалансированное; б) сбалансированное; 9. а) 7; б) 127. 11. а)! = 2". Поэтому !оба! = 1о822" = Ь; б) поскольку количество листьев меньше или равно 2", когда дерево полное, то в) сбалансированное. 2л ) ! .. !ода 2" > !охг! и )г )!Од ! поскольку ! — возрастающая функция 916 Ответы к упражнениям и равно 2" только в том случае, Ответы к упражнениям 917 в) и=2 — 1; л.ы ,и+1 = 2 +'; !ок (и + 1) = 6 .!. 1; и Ь !Оаг(и + 1) 1 г) поскольку полное дерево имеет максимальное количество вершин; и<2 э' — 1, г.и+1<2 эг, !Окг(и+1)<6+1 и 6 > !ойг(и+ 1) — 1. поскольку ! — возрастающая функция; поскольку ! — возрастающая функция поскольку элементы полурешетки являются идемпотентами = (аа)(ии ) = поскольку решетка ассоциативна и коммутативна Р = аиаи = = а(и)а(о ). Раздел И.З.
1. а) ь в) б) г -/~, 13. Предположим, что граф С вЂ” дерево, Пусть ребро (а,Ь) добавлено к дереву. Поскольку дерево было связным, уже существовал путь аигигиз иь 26 из а в Ь. Таким образом, аиг огиз . оь-26а является циклом. Предположим, что добавление ребра (а,Ь) создает два цикла, аигигоз иь 26 и аи',огиз...о,'„,Ь, тогда ащигиз иь 266о', .изиго',а уже является циклом, что противоречит предположению, что С вЂ” дерево.
Предположим, что граф С не является деревом. Тогда он уже содержит цикл. Предположим, что ребро (а,Ь) добавлено в О. Путь из а в 6 уже существовал, поскольку граф С связный. Теперь имеются два пути ива в Ь, поэтому (а,Ь) — часть цикла, но не часть исходного цикла, поэтому в графе С с добавленным ребром теперь имеется, по крайней мере, два цикла. 1Б. Утверждение ошибочное. На дереве лист не является разрезающей вершиной.
17. С содержит эйлеров цикл. 19. Нужно показать, что а(ои') = а(и)а(и'). а(ио ) = а(ои ) = 918 Ответы к упражнениям б) 3. а) в) /'», / »» /'» 5. Цепь. 7. вь ав Хасйвю А. уаьюоь м кю ~ Узв Вьнь льь а ь е а аее ан ь и т.в «и Твивя Ответы к упражнениям 919 б) 13. а) г / г / г г г) в) д) I . 15. Процедура Поиск (а, и) Если а=с, то Положить Найдено = да; Если а < г, то Если г имеет левого сына и, то вызвать Поиск(а,и); Положить Найдено = нет; Если а > г, то Если г имеет правого сына гл, то вызвать Поиск(а, ю) Положить Найдено = нежн Конец процедуры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
