Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 49
Текст из файла (страница 49)
° УПРАЖНЕНИЯ 1. Найдите матрицы инцидентности следующих графов; а) б) е! Уз е, Уз У ! з ез ез е, У! Уз у г) в) Уз 7 Уз е 2. Найдите матрицы инцидентности следующих графов: а) б) У, Уз Уз У ! 286 ГЛАВА б. Графы, ориентированные грвфы и деревья в) г) е ег 5г 3. Найдите матрицы смежности для графов из упражнения 1. 4. Найдите матрицы смежности для графов из упражнения 2. 5. Для заданной матрицы инцидентности 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 1 1 0 О 1 1 0 О 0 0 0 0 0 0 1 1 1 найдите соответствующий граф.
6. Для заданной матрицы инцидентности 1 О 1 0 1 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 О 0 0 0 1 0 0 0 0 О 0 0 0 найдите соответствующий граф. 7. Для заданной матрицы смежности 0 0 1 0 О 0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 1 найдите соответствующий граф.
8. Для заданной матрицы смежности 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 О 0 1 0 О 0 0 1 1 0 0 0 0 0 1 0 0 0 0 О 1 0 0 1 0 0 1 0 0 0 0 0 0 О 0 0 1 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 РЯЗДЕЛ б.б. Матрицы инцидентности и смежности 287 найдите соответствующий граф. 9. Для графа, показанного на рис. 6.76, а) найдите матрицу смежности; б) используя матрицу смежности, найдите в) используя матрицу смежности, найдите 10.
Для графа, показанного на рис. 6.77, а) найдите матрицу смежности; б) используя матрицу смежности, найдите в) используя матрицу смежности, найдите все пути длины 2; все пути длины 3. все пути длины 2; все пути длины 3. "! Рис, б.7б Рис. б.77 11. Для графа, показанного на рис. 6.78, а) найдите матрицу смежности; б) используя матрицу смежности, найдите в) используя матрицу смежности, найдите 12.
Для графа, заданного на рис. 6.79, а) найдите матрицу смежности; б) используя матрицу смежности, найдите в) используя матрицу смежности, найдите все пути длины 2; все пути длины 3. все пути длины 2; все пути длины 3. Рис. б.78 Рис. б.79 13. Используя тот факт, что транзитивное замыкание 14. Используя тот факт, что транзитивное замыкание А = А ч Аог ч Аоз 7Аем ',7 ч Ао", определите отношения, представленного графом на рис.
6.80. А = А ч А ~~'7АО~ ы Аем ч . ''~Аш", определите отношения, представленного графом на рис. 6.81. 288 ГЛАВА б. Графы, ориенширааанные графы и деревья !" "г ез ег Рис. 6.8/ Рис. 6.80 15. Используя тот факт, что А те транзитивное замыкание графом на рис. 6.82. 16. Используя тот факт, что А те транзитивное замыкание графом на рис. 6.83.
— А ~/ АО2 ~/ АОз ~/ АО4 ~/ . ~/ АОн определи. отношения, представленного ориентированным = А У АО2 ~/ АОз ч АО4 / .. ~/ АО определи- отношения, представленного ориентированным Ь "г Рис. 6.83 Рис. 6.82 17. Используя алгоритм Уоршолла, шения, представленного графом 18. Используя алгоритм Уоршолла, шения, представленного графом Рис. 6.86 Рис. 6.84 19. Используя алгоритм Уоршолла, определите транзитивное замыкание отношения, представленного графом на рис. 6.86. 20. Используя алгоритм Уоршолла, определите транзитивное замыкание отношения, представленного ориентированным графом на рис.
6.87. е, ег ез ег определите транзитивное замыкание отно- на рис. 6.84. определите транзитивное замыкание отно- на рис. 6.85. РА37)ЕЛ 6.б. Матрицы инцидантности и смамности 289 Ь Рис. б.87 Рис. 8.8б 21. Используя алгоритм Уоршолла, определите транзитивное замыкание отношения, представленного ориентированным графом на рис. 6.88. 22. Используя алгоритм Уоршолла, определите транзитивное замыкание отношения, представленного ориентированным графом на рис. 6.89. Рис.
8.88 Рис. 8,89 23. Матрицы инцидентности для мультиграфов можно определить таким же способом, как и для обыкновенных графов. Как по матрице инцидентности можно судить о том, имеют ли два ребра мультиграфа общие вершины? (Такие ребра называются кратными.) 24. Если рассматривается матрица инцидентности для мультиграфа, дает ли сумма элементов строки, обозначенной данной вершиной, степень данной вершины? Что означает сумма элементов строки? 26. Используя индукцию, докажите теорему 6.63. Пусть С вЂ” (ориентированный) граф с вершинами из, иа, из,..., и„и матрицей смежности А. Из вершины и; в вершину иу тогда и только тогда существует путь длины й, где 1 < й < и, когда А~~и = 1. 26.
Используя индукцию, докажите теорему 6.64. Пусть С вЂ” (ориентированный) граф с вершинами иы из, из, ..., и„и матрицей смежности А. Из вершины и, в вершину и тогда и только тогда сушествует т путей длины к, где 1< 9 <п, когда А';, =гп. 27. Используя теорему 6.63, докажите теорему 6.65. Пусть С вЂ” (ориентированный) граф с вершинами иы иа, из, ..., и„и матрицей смежности А. Если А = А и Ас а '7 Ашз ~7 Агм ~~...'иАш", то А, = 1 тогда и только тогда, когда имеется путь из вершины и; в вершину иу. 28.
Опишите матрицу смежности для дерева. 29. Опишите транзитивное замыкание для дерева. 290 ГЛАВА б. Графы, ориентированные графы и дврввья 6.7. ГИПЕРКУБЫ И КОД ГРЕЯ ОПРЕДЕЛЕНИЕ 6.68. Расстоянием между двумя вершинами графа называется длина самого короткого пути между этими двумя вершинами. ОПРЕДЕЛЕНИЕ 6.69. Диаметром графа называется наибольшее расстояние между двумя любыми его вершинами.
Во многих случаях вместо использования одиночных процессоров, способных выполнять только одну программу, несколько процессоров соединяется для выполнения программ в параллельном режиме. При этом обеспечивается обмен информацией между процессорами, и различные программы выполняются одновременно. Одним из способов связи компьютеров есть соединение их сериями в кольцо. Указанный метод обладает тем недостатком, что для передачи информации от одного процессора к другому потребуется прохождение ее через значительное число процессоров. В самой неблагоприятной ситуации информация должна будет пройти через половину процессоров. Незначительное улучшение дает использование сетки, или прямоугольного массива процессоров, когда они помещены в каждой точке сетки.
Пример такой сетки показан на рис. 6.90. ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° ° Рис. б.90 Таким способом достигается лишь некоторое улучшение, так как прохождение информации через значительное число процессоров остается необходимым. В случае сетки 4 х 5, показанной выше, может возникнуть необходимость прохождения информации через восемь процессоров, включая конечные процессоры. В общем случае сетки ги х и возможна ситуация прохождения информации через т + и — 1 процессор. Намного лучшей конфигурацией является гиперкуб. В частности,и-гиперкуб может быть использован для соединения вплоть до 2" компьютеров. Граф и- гиперкуба строится рекурсивно следующим образом.
Для и = 1 одну вершину представляем посредством 1, а другую — посредством О, так что получаем граф, изображенный на рис. 6.91. 1 Рис. 6.9! Таким образом, вершины графа состоят из всех строк длины 1, содержащих 0 и 1. Для и = 2 вершины представляем посредством 11, 10, 01 и 00, так что получаем граф, изображенный на рис. 6.92. Таким образом, вершины представлены строками длины 2, содержащими 0 и 1.
Для и = 3 вершины представлены посредством 111, 110, 101, 100, 011, 010, 001, 000, так что получаем граф, изображенный на рис. 6.93. РАЗДЕП В.7. Гиперкубы и код Грея 291 (1, (00,0) (1,0, 1) 1) (0,1) (1,1,1) 0,1,1) Рис. 6.92 Рис. 0.93 Таким образом, вершины этого графа описывают строки длины 3, состоящие из О и 1. Заметим, что две вершины являются смежными, если одна переходит в другую при замене одного символа в строке.
В главе ! при построении таблиц истинности был составлен список всех возможных комбинаций утверждений. Если использовать систему обозначений булевой алгебры и заменить Т на 1 и Р на О, то обнаружим, что образованы вершины гиперкубов порядка 1, 2, 3 и 4, которые в сокращенном виде можно записать следующим образом: Что означает для этих точек быть смежными, уже было определено для п = 2, 3 и 4.
Рассмотрим следующую карту Карно: И 1О О1 ОО Нас интересует, какие блоки являются смежными. Если опять заменить Т на 1, Р на О и придать первой переменной значение р, а второй переменной— значение о, тогда внутренние значения в таблице покажут, где находятся соседние 292 ГЛЯ8А 6. Графы, ориентированные графы и оерееья блоки. Следовательно, каждая вершина является смежной к другой вершине, если они смежные как вершины куба порядка 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
