XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 59
Текст из файла (страница 59)
5.11. Установить, является ли ориентированный граф, изображенный на рис. 5.49, связным. Найти все его компоненты и бикомпоненты. 370 6. ТЕОРИЯ ГРАФОВ Рис. 6.60 Рис. 6.49 5.12. Конденсация ориентированного графа С = (У, Е) есть ориентированный граф 6' = (У/р, Е~, где р — отношение взаимной достижимости (см. задачу 5.10), а для любых и', е'б Р', в'~е', (и', и') ЕЕ'4Ф(Зи Еи'),(Зе бе'), (и, е) Е Е. Доказать, что С вЂ” бесконтурный граф тогда и только тогда, когда С изоморфен своей конденсации С'. 5.13.
Найти все ориентированные графы с двумя вершинами, являющиеся гомоморфными образами ориентированного графа, изображенного на рис. 5.50. 5.14. Установить, является ли конденсация ориентированного графа (см. задачу 5.12) его гомоморфным образом. Построить примеры. Указание: выяснить, может ли конденсация ориентированного графа содержать петли. 5.1б. Доказать, что ориентированный граф связный тогда и только тогда, когда в нем есть путь, проходящий через все вершины. Останется ли это утверждение справедливым, если потребовать, чтобы существовал простой путь? 5.16. Пусть у: У -+ У вЂ” биекция множества вершин ориентированного графа С = (У Е) в себя. Сопоставим ей матрицу Я с элементами =и*); 1 ! ~0, иначе.
371 Вопросы и задачи Доказать: а) Я 1 = Я (т.е. Я вЂ” ортогональнзл матрица); б) если у — автоморфизм графа С, то матрица смежности В' автоморфного образа у(0) есть В' = Я ВЯ. 5.17. Доказать, что если неориентированный граф Й-регулярный, т.е.
степени всех его вершин одинаковы и равны Й, то число Й есть собственное число матрицы смежности графа. т Указание: доказать, что вектор х = (1, 1, ..., 1) размерности и = ~У~ есть собственный вектор матрицы смежности Й-регулярного графа С. 5.18. Написать алгоритм нахождения множества предшественников Г 1(э) для каждой вершины графа по спискам смежности. Оценить сложность алгоритма. 5.19. Что является компонентами связности в ориентированном дереве? 5.20.
Найти остовное дерево наименьшего веса для неориентированного графа с десятью вершинами, заданного следующим сциском ребер с метками (вершина, вершина, метка): (1"1> 1>2> 1)> (е2> ез> 5)> (1>3> 1>4> 4)> (94> 1>з> 8)> (1>з> еб> 3)> (еб> 1>в> 5)> (1>в> 99> 11)> (99> 1>10> 8), (е10, 91> 7), (92, е10, 5), (92, ет, 8), (ез, ет, 7), (ез, из, 3), (94, е10 4) (еб ет 6), (ев ет, 12), (99 ет 9) 5.21.
Найти условия, необходимые и достаточные для единственности остовного дерева наименьшего веса. 5.22. Доказать, что сеть является простой, если любой подграф, порожденный множеством всех вершин, достижимых из некоторого корня, является деревом. Верно ли обратное? 372 5.
ТЕОРИЯ ГРАФОВ 5.23. Используя алгоритм Демукрона, найти порядковую функцию сети, заданной следующими матрицами смежности: б) 5.24. Составить подробное описание алгоритма вычисления порядковой функцяи сети, который в случае, если входной граф есть сеть, работает как алгоритм Демукрона, если же иначе, то сообщает о наличии в графе контуров и останавливается.
5.25. Эдлероеььм нпилом в неориентированном графе называется цикл, в котором каждое ребро графа проходится ровно один раз. Доказать, что связный неориентированный граф имеет эйлеров цикл тогда и только тогда, когда степень каждой его вершины четная. 5.26. Доказать, что ориентированный граф не содержит контуров тогда и только тогда, когда при поиске в глубину иэ некоторой вершины (независимо от ее выбора) множество обратных дуг пусто. 5.27. Доказать, что в связном ориентированном графе найдется вершина, при поиске в глубину из которой глубинный остовный лес является деревом. Верно ли обратное? У к а з а н и е: используйте результат задачи 5.15. 5.28.
Найти все возможные глубинные остовные леса, получающиеся при поиске из вершины е1: 00001000000 10000000000 10000000100 00100010000 00000000000 01000011100 01000001000 00000000110 00000000010 00000000000 10100100000 00100000 10111110 00011000 00001010 00000011 10100000 00000001 00000000 373 Воввосм и задачи а) для неориентированного графа с 10 вершинами и множеством ребер л> = ((еь 02) > (оь 03) > (02> 03) > (02> 08) > (04 > 051> 105> еб) > (Еб> 07) > 1>05 > 07) > (07 > 08) > (7>8> 09) > ~09> 010) > (08> 010) ) > б) для ориентированного графа с 10 вершинами и множеством дуг г> = ((7>Ь 7>2)> (0Ь 1>3), (03> 02)> (02> 04)> (02> 010)> (04> 05)> (Е5> Еб)> (07> Еб)> (07> 05)> (07> 08)> (08> 09)> (09> 010)> (010> 08)).
У к а 3 а н и е: рассмотреть различные порядки расположения вершин в списках смежности. 5.20. Выполнить поиск в глубину для неориентированных графов, юображенных на рис. 5.47, ю различных стартовых вершин. 5.30. Выполнить поиск в ширину из вершины 02 для ориентированного графа из задачи 5.28. 5.31. Выполнить поиск в ширину ю вершины 05 для ориентированного графа, изображенного на рис.
5.38. После остановки алгоритма продолжить поиск ю вершины 08. Сравнить стоимости прохождения со значениями порядковой функции сети, приведенными на рисунке. 5.32. Для ориентированных графов, заданных множеством дуг с указанием меток (вершина, вершина, метка), решить задачу транзитивного замыкания (в полукольце В) и задачу вычисления кратчайших расстояний (в полукольце В+): а) (7>ь 7>г, 8), (оь еь 2), (еь 03 5) (02, оь 3) (2>з 02 2) б) (эь 02> 2), (еь 04> 10), (02> 03> 3), (ез> 05, 4), (05 04 5), (02> 7>4> 7)> (04> 03> 6)> в) (1>ь эг, 10), (еь 04> 5), (02> еь 6); (02> ез> 7), (ог, 04> 2), (02> 05> О)> (оз> ез, 8), (ез, 04> 10), (08> ез, 5), (оь 7>5> 4), (08> иг, 7), (05> еь 8)> (05> 03> 4)> 374 5.
ТЕОРИЯ ГРАФОВ г) (еь 63, 2), (еь ез, 3), (63, ез, 6), (ез, ез, 5), (ез, е4, 6), (63! 65у 2) (64 651 3) (651 64р 4) (езф 64! 1)) (67~ е51 5)у (65> 67! 4), (67, 63, 6); д) (еь 63, 1), (ег, ез, 3), (ез, 64, 4), (65, 64, 5), (65, 65, 1), (66~ 611 1)~ (еь 67~ 2)1 (62~ 67~ 1)~ (64~ 67~ 1)~ (67~ 63~ 2)~ (67~ 65~ 1), (671 651 1); 5.33. Ориентированный граф задан матрицей смежности, содержащей метки соответствующих ребер: 0 7 8 9 10 0 0 8 9 10 0 -2 0 9 10 0 -4 -3 0 10 0 -7 — 6 -5 0 Решить задачу о кратчайпп1х путях для данного ориентированного графа, обратив внимание на то, что метки некоторых дуг равны 0 или отрицательны. Выяснить, применим ли здесь алгоритм Флойда — Уоршела — Клини.
Можно ли изменить метки дуг таким образом, чтобы алгоритм Флойда — Уоршела — Клини стал неприменимым? 5.34. Установить, можно ли использовать алгоритм Флойда — Уоршела — Клини для вычисления стоимости путей наиболыпей длины во взвешенном графе.
Сформулировать ограничение на граф, при котором такое использование возможно. 6. В~ЛЕВЫ а ~НКЦИИ 6.1. Понятие булевой функции. Булев куб В дискретной математике большую роль играют конечные функции. Хоненноб бтункциеб называют отображение одного конечного множества в другое. Важный класс таких функций образуют булевы функции. Булееа функция (от и переменных) — это произвольное отображение вида У:(0,1)"-~(О,Ц, (6.1) *В литературе по теории булевых функции традиционно употребллетсл термин „булеаа переменнал" (в женском роде). Но так как в данном комплексе учебввкоа првнлт термин „переменное" (среднего рода), мы июнем везде „булеао переменное".
т.е. булеза функция определена на множестве всех и-элементных (при и > 0) последоватпельностпеб (или и-компонентных корптежеб) нулей и единиц и принимает два возможных значения: 0 и 1. С понятием булевой функции тесно связаны понятия булевой константы и булеза переменного'. Булева констпантпа — это индивиднал констпантпа с областью значений (0,1).
Таким образом, существуют две булевы константы: 0 и 1. По определению принимается, что каждая булева константа есть также булеза функция от 0 переменных (что вполне аналогично определению нульарноб операции). Булеео перелеенное — зто индивидное переменное с областью значений (О, Ц, т.е.
это переменное, которое может принимать только два значения: 0 и 1 (подобно тому, как действительное переменное принимает произвольное действительное 376 Е. БУЛЕВЫ ФУНКЦИИ значение, а комплексное переменное — произвольное комплексное значение). Тогда с использованием понятия булеза переменного мы можем задать булеву функцию (6.1) записью у = = Дхм..., х„), в которой каждое булево переменное х;, 1 = 1, и, и функция У принимают два возможных значения: О и 1. Переменные хм ..., х„называют при этом переменными булевой фуннефни ~.
Фиксируя значение ол е (О, Ц каждого переменного х;, получаем кортеж се = (о~, ..., а„) из множества (О, Ц", называемый набором значений переменных хм ..., х„, и соответствующее ему значение функции у" (се1,...,о„), которое будет значением переменного у, сопоставленным заданным зна чениям переменных хм ..., х„. Подчеркнем, что, если специально не оговорено противное, в выражении у = )'(х1,...,х„) все переменные предполагаются попарно различными, т.е. пробегающими каждое независимо от других множество (О, Ц. Понятию булевой функции можно придать иной смысл, понимая элементы множества (О, Ц как истннностные значения, а именно понимая единицу как „истину", а нуль как „ложь". Такие истинностные значения могут быть, как мы знаем, сопоставлены каждому высказыванию.
Тогда булеза функция есть некоторое правило, позволяющее каждому фиксированному набору истинностных значений, т.е. набору значений булевых переменных, сопоставить то или иное истинностное значение. Так может быть вычислено, например, истинностное значение сложного высказывания, составленного по определенным правилам из простых высказываний. Подобного рода сложные высказывания составляются с помощью логических операвей: „или", „и", „если ..., то ..." и т.п.
Указанная логическая интерпретация булевой функции позволяет понять, почему булеза переменное часто называют логическим переменным', а булеву функцию — логической функцией (или функцией алгебры логики). 'Ч~задиииоииый термин: „логическая перемеииея". 6.1. Поилтие булевой фувккии. Буков куб 377 Кроме того, согласно определению, булева функция от н переменных есть отображение н-й декартовой степени множества (О, Ц в множество (О, Ц, т.е. не что иное, как н-арнал онераиия на множестве (О, Ц. Тем самым логическая интерпретация булевой функции согласуется с ее алгебраической интерпретацией: булеза функция есть операция (в алгебраическом смысле этого слова) на множестве истинностных значений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
