Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 50
Текст из файла (страница 50)
Аналогично, для трех переменных, где значения р, д и г даны по порядку, получаем таблицу г г г г Вспоминая теперь, что в случае карты Карно таблица скручена так, что два края рассматриваются как смежные, приходим к выводу, что две вершины являются смежными, если они смежные как вершины куба порядка 3.
Рассматривая карту Карно для четырех переменных и присваивая переменным значения р, 9, г и а по порядку, аналогичным образом получаем г г г г Вспоминая, что в случае карты Карно таблица скручена так, что два края рассматриваются как смежные, и смежными являются также верх и низ таблицы, снова приходим к выводу, что две вершины являются смежными в таблице только тогда, когда они смежные как вершины куба порядка 4. Используя приведенный выше метод, построим последовательность вершин для Й + 1-мерного куба, используя последовательность вершин й-мерного куба следующим образом: 1) Поместить 1 перед каждой вершиной в последовательности вершин ймерного куба. Вершины, которые были смежными в й-мерном кубе, с приставленной единицей остаются смежными в й + 1-мерном кубе.
2) Поместить О перед каждой вершиной в последовательности вершин 1- мерного куба. Вершины, которые были смежными в й-мерном кубе, с приставленным нулем остаются смежными в й+ 1-мерном кубе. 3) Поместить последовательность, построенную в (2), вслед за последова- тельностью, построенной в (1). Нами предложен метод для построения вершин гиперкубов, причем для п = 1, 2, 3 и 4 можно использовать карты Карно, чтобы показать, когда вершины являются смежными. При п > 4 для образования вершин можно использовать приведенные выше шаги (1)-(З). Предположим, что имеется вращающийся диск, разделенный на секторы, и серия щеток или лазерных лучей, возвращающих информацию о том, на какой РАДЕЛ б.7. Голерхубы и ход Грея 293 угол диск успел повернуться на текущий момент. Если двоичные строки, которыми пронумерованы соседние секторы, существенно различны в том смысле, что при переходе от одного сектора к другому многие цифры в ннх изменяются, то устройство, считывающее эту информацию непосредственно в процессе вращения, может выработать число, совершенно не похожее ни на одно из чисел.
В данном случае желательно пронумеровать секторы так, чтобы двоичные строки, нумерующие соседние секторы, различались только одной цифрой. В общем случае, однако, вершины в приведенном выше списке не являются смежными. Можно, тем не менее, изменить ситуацию, внеся незначительные исправления в приведенной выше части (2). Для формирования списка вершин й + 1-мерного куба, до того как помещать О перед элементами списка для /смерного куба, реверсируем список вершин для к-мерного куба, т.е. порядок вершин в списке изменим на обратный.
Например, при формировании списка вершин 2-мерного куба помещаем 1 перед столбцом для 1-мерного куба: Затем меняем порядок элементов в столбце: Наконец, помещаем О перед каждым элементом, имея в итоге 1 1 1 О О О О 1 Чтобы получить вершины 3-мерного куба, помещаем 1 перед приведенным выше списком для 2-мерного куба и помещаем О перед реверсированным списком для 2-мерного куба. В итоге для 3-мерного куба получаем 1 1 1 1 1 О 1 О О 1 О 1 О О 1 О О О О 1 О О 1 1 Легко доказать, что приведенная процедура всегда будет давать последовательность вершин для й-мерного куба, которую назовем й-списком.
В таком /ссписке (1) каждая вершина последовательности является смежной для следующей вершины и (2) первая вершина последовательности является смежной к последней вершине последовательности. Используя индукцию, начнем с констатации 294 ГЛДОА б. Графы, ориентированные графы и деревья 1) Поместите 1 перед каждой вершиной в й-списке й-мерного куба. Вершины, смежные в й-мерном кубе, с приставленной впереди 1 остаются смежными в Й+ 1-мерном кубе. 2) Поместите О перед каждой вершиной в реверсированном й-списке й-мерного куба.
Вершины, смежные в и-мерном кубе, с приставленным впереди О остаются смежными в /с+ 1-мерном кубе. 3) Разместите последовательность, сформированную в (2), после последовательности, сформированной в (1). 4) Каждая последовательная пара вершин в 2+1-мерном списке 2+1-мерного куба является смежной. Первая вершина Й + 1-списка также является смежной к последней вершине списка. Например, 3-спнсок и реверсированный 3-список представляют собой, соответственно, О 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 состоят в следующем: РАЗДЕЛ 6.7. Гиперкубы и код Грея 295 получаем 1 1 1 1 1 1 1 О 10 О 1 О О О 1ООО 010 О О О ОО10 ОООО 0001 О 1 О 1 010 О 0110 О 1 1 1 Таким образом, мы построили код Грея для п = 4.
Ранее упоминалось соединение компьютеров в конфигурацию сетки или решета. Под сеткой понимают граф, вершины которого заданы массивом размерности пт х и, и для которого две вершины, соседствующие в одной и той же строке или столбце массива, являются смежными как вершины графа. Возможно лн для т < 2" и и < 2' построить подграф 1+1-мерного куба, т.е. сетку размера гп х яр Это уже делалось при построении карт Карно. Указанное легко сделать, обозначая строки согласно первым гп элементам кода Грея для к и обозначая столбцы согласно первым и элементам кода Грея для й Элемент на позиции (1,1) сетки есть метка 1-ой строки, за которой следует метка З-го столбца.
Таким образом, если необходимо построить сетку 3 х 7, то она будет иметь вид Здесь (г,З)-ый элемент сетки является (г, ))-ым элементом таблицы. Проведенные рассмотрения доказывают следующую теорему. ТЕОРЕМА 6.70. Каждая сетка размера гп х п представляет собой подграф 1+ З- мерного куба, где нт < 2* и и < 2'.
Предоставляем читателю доказать следующую теорему. ТЕОРЕМА 6.71. Каждый гиперкуб для и ) 1 является двудольным графом, в котором непересекающиеся множества вершин состоят из множества тех вершин, которые изображаются строками, содержащими четное число единииц, и множества вершин, которые изображаются строками, содержащими нечетное число единиц. 296 ГПАВА б. Графы, ориентированные графы и деревья ° УПРАЖНЕНИЯ 1. Найдите диаметр следующих графов: а) К„ б) Кщ„ в) г) чг чг ч, 2.
Найдите диаметр следующих графов: а) б) г) в) (1, (0,00) (1,0, 1) 1) (1, (0,1,0) (1,1,1) 0,1,1) д) 4-гиперкуб. 3. Постройте код Грея для 5. 4, Постройте код Грея для 6. 5. Постройте сетку 4 х 5. 6. Постройте сетку 3 х 8, 7. Постройте сетку 5 х 6. 8. Докажите теорему 6.71. Каждый гиперкуб для и > 1 является двудольным графом, в котором непересекающиеся множества вершин состоят из мно- РНЗИЕЛ В.7. Гиперкубы и код Грея 297 жества тех вершин, которые изображаются строками, содержащими четное число единиц, и множества вершин, которые изображаются строками, содержащими нечетное число единиц.
9. Докажите, что если т = 2' и и = 2', то построенная сетка т х и обладает свойством, что соответствующие вершины в первой и последней строке сетки являются смежными, и соответствующие вершины в первом и последнем столбце являются смежными. РАЗДЕЛ 7. Я Решето Эратосфена 299 1, г, 3, 4, 5, 6, 7, В, 9,1О,П,12,13,14,15,16,17,18,19,20, 21,22, 23,24, 25,26,27,28, 29,30, 31,32,33,34, 35,36, 37,38,39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, БО, Б1, 52, 53, 54, 55, 5Б, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 7Б, 76, 77, 78, 79, ВО, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100 Теперь отмечаем все числа, кратные простому числу 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
