Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 101
Текст из файла (страница 101)
Найдите разложение соответствующей производящей функции, чтобы определить, сколько кодов из десяти цифр в каждом можно образовать из цифр О, 1 и 2, если а) цифра 0 должна встречаться в коде хотя бы дважды; б) цифра 1 может встречаться не более трех раз, а цифра 2 — не более четырех раз; в) цифра 1 может встречаться четное, а цифра 0 — нечетное число раз. 2. Двенадцать воздушных шаров должны быть привязаны к 12 фонарным столбам по маршруту парада. Найдите разложение соответствующей производящей функции для определения количества способов развешивания красных, синих, желтых и зеленых шаров при условии, что а) использован хотя бы один шар каждого цвета; б) использовано не более 4 красных, 3 желтых, 7 зеленых и 6 синих шаров; в) использовано не более 2 красных шаров, не более 3 зеленых шаров, от ! до 5 зеленых шаров и четное количество синих шаров. 3.
Найдите производящую функцию последовательности факториалов О!,1!,2!, 3).... 4. Найдите производящую функцию, описывающую количество способов раскрашивания 8 х 8-клеточной шахматной доски, используя красный, белый и синий цвета, при условии, что четное количество клеток — красные. 5. Используя производящую функцию, определите количество чисел, состоящих из и цифр, все цифры в которых нечетные, а цифры 1 и 3 присутствуют в них не менее одного раза.
6. Воспользуйтесь производящей функцией для нахождения количества чисел, состоящих из и цифр, все цифры которых нечетные, при условии, что все цифры присутствуют хотя бы один раз, а цифра 5 появляется четное число раз. 7. Воспользуйтесь производящей функцией для нахождения количества способов размещения 30 человек в 3 комнатах гостиницы, если в каждой комнате находится хотя бы по одному человеку. 8. Воспользуйтесь производящей функцией для нахождения количества способов размещения 30 человек в 3 комнатах гостиницы, если в каждой комнате находится четное количество людей. РАЗДЕЛ 13.5.
Экспоненциапьные проиэводяц1ие функции ббб 9. Используйте производящую функцию для определения количества способов размещения 25 объектов четырех типов по порядку, если количество объектов первого типа — четное, количество объектов второго типа — нечетное, и хотя бы по одному объекту третьего и четвертого типа. 10.
Используя производящую функцию, определите, сколько существует способов распределения 9 кусков торта между 4 детьми при условии, что каждый ребенок из первых двух получает кусок торта. 11. Найдите производящую функцию для вычисления количества упорядочений монет стоимостью 1 цент, 5 центов, 10 центов и 25 центов, которые в сумме дадут и центов. 12. Покажите, что !т †', = — зкспоненциальная производящая функция, описывающая количество способов выбора некоторого, возможно пустого, подмножества из !с объектов.
Распределите их по п ящикам, учитывая порядок в подмножестве. !3. Найдите экспоненциальную производящую функцию, описывающую количество способов разбиения числа п на й частей, учитывая порядок. 14. Используя метод индукции, докажите теорему 13.24. е"* = (е*)" для любого неотрицательного целого числа и. 15. Докажите теорему !3.28. х хз хз а) е* — 1= — + — + — + 1! 2! 3! х+ — к .2 А 6 2 2! 4! 6! вк е-е х хз хз хт в) 2 1! 3! 5! 7! РАЗДЕЛ 14.1. Алгебраические сесбсглеа графов 557 Таким образом, изоморфизм, по сути, является переименованием вершин и ребер графа Ъ', которое сохраняет свойство гомоморфности, так что если вершины и и и инцидентны ребру е графа С, то вершины Ди) и Х(и) инцидентны ребру Г(е) графа С'.
Инварианты изоморфизмов приведены в задачах. Вполне очевидно, что практически все свойства графов инвариантны относительно изоморфизма. Отсюда следует, что простейший способ показать неизоморфность двух графов — установить свойство, которым обладает один граф и не обладает другой. ОПРЕДЕЛЕНИЕ 14.6. Если граф С1$',Е) содержит ребро е = (им из) и граф С'($"',Е') получен из графа С(КЕ) добавлением новой вершины и в множество Ъ' и заменой ребра (им из) ребрами (ими) и (и,из), то граф С'(Ъ", Е') называется расигиренигм графа С(К, Е). Если графы Сы Сз, Сз,... С„таковы, что С,~г является расширением графа С„то граф С„назовем производным от графа Сг.
Если граф С'1$", Е') — расширение графа С(К Е), то посредине одного из ребер множества Ъ' появляется вершина, а исходное ребро делится на два новых ребра, которые соединяют вершины, инцидентные исходному ребру, и новую вершину. ОПРЕДЕЛЕНИЕ 14.7. Графы С и С' называются гомеоморфкыми, если существует граф С" такой, что оба графа, С и С', являются производными от графа С". ПРИМЕР 14.8. Граф, изображенный на рис. 14.1, является расширением графа, изображенного на рис. 14.2.
Р-, И.г Рис. 14.1 ПРИМЕР 14.9. Граф, изображенный на рис. 14.3, является производным от графа, изображенного на рис. 14.4. 668 П1ЯВД 14. Некоторые специальные вопросы теории графов Рис. /4.З Рис. 14.4 ПРИМЕР 14.10. Граф, изображенный на рис. 14.5, является производным от гра- фа, изображенного на рис. 14.6. Рис. 14.б Рис.
14.б ПРИМЕР 14.11. Граф, изображенный на рис. 14.7, является гомеоморфным графу, изображенному на рис. 14.8. Ь Ь Рис. 14.8 Рис. 14.7 Приведенные ниже определения введены, главным образом, для рассмотрения планарных графов в следующем разделе. Они демонстрируют, каким образом свойства графов остаются инвариантными для отношений между графами. Если граф С'(Ъ", Е') — расширение графа С(КЕ), то новая добавленная вершина имеет степень 2.
Степени других вершин не изменились. Отсюда вытекает следующая теорема. ТЕОРЕМА 14.12. Если графы С и С' — гомеоморфны, то у них одинаковое количество вершин нечетной степени. Из данной теоремы и теорем 6.45 и 6.49 непосредственно вытекает следующая теорема.
ТЕОРЕМА 14.13. Если графы С и С' гомеоморфны, то граф С имеет эйлеров цикл (собственный путь) тогда и только тогда, когда граф С' имеет эйлеров цикл (собственный путь). Если С' — подграф графа С, то это обозначается как С' с С. РАЗДЕЛ 14. 1. Апгеораические свойстве грефог 669 ОПРЕДЕЛЕНИЕ 1416. Пусть С = С(й, Е) — граф и СыСз,Сз,...,С„подграфы графа С.
Подграфы Сы Сз, Сз,..., С„являются попарно непересекающимися, если С; г) С = И для всех 1 < г < т' < и. Доказательство приведенных ниже теорем предоставляется читателю. ТЕОРЕМА 1417. Если Сг и Сз — различные компоненты графа С, то С, и Сев попарно непересекающиеся.
ТЕОРЕМА 14.18. Граф С является объединением попарно непересекающихся компонент. ОПРЕДЕЛЕНИЕ 14.20. Подграф С'(~', Е') является остоеным графом для графа С = (Ъ; Е), если Ъ" = Ъ'. ПРИМЕР 14.21. Для заданного графа, изображенного на рис. 14.9, а Ь с У рис (4,9 660 ГЛАВА 14. Некоторые специальные вопросы теории графов графы, изображенные на рис. 14.10-14.12, — остовные графы.
Ю [[1 Рис. 14.10 Рис. 14.Н Рис. 14.12 В то же время графы, изображенные на рис. 14.13-14.15, остовными не являются. Рис. 14.14 Определение остовного дерева дано в главе 6 и приводится здесь для удобства изложения. В главе 6 было показано также, что каждый связный граф имеет остовное дерево. ОПРЕДЕЛЕНИЕ 14.22.
Дерево называется остовным деревом графа С, если оно является остовным графом графа С. Доказательство приведенных ниже теорем предоставляется читателю. ТЕОРЕМА 14.23. Если ТЯЕ') — остовное дерево графа С = (КЕ), то для любого цикла оои1озозиг,...ио, по кРайней меРе, одно из РебеР пРинадлежит Š— Е'.
Предположим, что компания создает коммуникационную сеть (рис. 14.16). Нью-Йорк Лос Майами Хьюстон Атланта Рис. 14.1б Для компании важно знать, сколько городов окажутся не связанными между собой, если удалить некоторые линии. В частности, сколько линий требуется удалить, чтобы города оказались не связанными. М Ы е Рис. 14.13 М ~4 е с Рис. 14.!Б 0 РАЗДЕП В4гн Алавораичвскив свойства графов 561 ОПРЕДЕЛЕНИЕ 14.24.
Множество ребер С связного графа С = (17,Е) называется разрезающим множеством, если удаление ребер из множества С нарушает связность графа, а удаление собственного подмножества множества С оставляет граф связным. Если множество С состоит из одного ребра, то это ребро называется раэрезающим ребром. Иной способ описания разрезающего множества — это определение его как минимального множества ребер, удаление которых нарушает связность графа. ПРИМЕР 14.25. Для графа, изображенного на рис. 14.17, ез и ев — разрезающие ребра. Уг г Рис. !4.17 ПРИМЕР 14.26. Для графа, изображенного на рис.
14.18, Циыиз),(и*ив)) и Циз, из), (ив, ит)) — разрезающие множества. Рис. !4.7о Доказательства приведенных ниже теорем предоставляются читателю. ТЕОРЕМА 14.27. Если Т(Ъ;Е') — остовное дерево графа С = (17,Е) и С— разрезающее множество графа С, то Сг1 Е' ~ о.
ТЕОРЕМА 14.28. Ребро е графа С является разрезающим ребром графа С тогда и только тогда, когда оно не входит в цикл графа С. Другая важная задача: сколько городов лишится связи, если коммуникационная сеть выйдет из строя в определенном городе (города представлены вершинами). Вопрос сводится к следующему: тйто произойдет, если удалить вершину графа"? ОПРЕДЕЛЕНИЕ 14.29. Вершина а 6 17 связного графа С = (17,Е) является разрезающей вершиной, или точкой сочленения, если удаление этой вершины и инцидентных ей ребер приводит к нарушению связности графа.
662 ГЛА8А 14. Некоторые спвцивпьныг вопросы теории графов ОПРЕДЕЛЕНИЕ 14.30. Граф С('г', Е) называется двусвязным, если не содержит точек сочленения. ТЕОРЕМА 14.31. Вершина а графа С = (К Я) является точкой сочленения тогда и только тогда, когда существуют различные вершины е и ю такие, что каждый путь из е в ю проходит через а.
ДОКАЗАТЕЛЬСТВО. Сначала докажем достаточность. Предположим, что каждый путь из вершины е в ю проходит через вершину а. Тогда, если вершина а удалена, то не существует более пути из вершины е в ю, и граф С становится несвязным. Следовательно, вершина а — точка сочленения. Для доказательства необходимости в утверждении теоремы используется метод доказательства от противного. Предположим, что для каждой пары различных вершин е и ю существует путь, который не проходит через а. В этом случае при удалении вершины а для всех е,ю Е Ъ' всегда остается путь из вершины е в ю, и граф С остается связным.
Следовательно, вершина а не является точкой сочленения. ПРИМЕР 14.32. В графе, изображенном на рис. 14.19, вершины ез, ег и ег— разрезаюшие вершины. Рис. 14.!9 ТЕОРЕМА 14.33. Для связного графа С = ('й, Е) определим отношение В на Е: е~Вез, если е~ = ез или в графе С существует простой цикл, содержащий еь и ез в качестве ребер. Тогда отношение В является отношением эквивалентности. ДОКАЗАТЕЛЬСТВО. Свойства рефлексивности и симметричности очевидны. Предположим, что еьВез и езВез.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
