-Поиск по дневнику

Поиск сообщений в zhurnalist

 -Подписка по e-mail

 

 -Статистика

Статистика LiveInternet.ru: показано количество хитов и посетителей
Создан: 26.11.2010
Записей:
Комментариев:
Написано: 18

Сборка гиперкуба

Дневник

Вторник, 04 Января 2011 г. 20:24 + в цитатник
На первом шаге получаем четыре одномерных гиперкуба, изображенных на рис. 21.1. Максимальное значение имеет вес w23 = 3. Поэтому в первую очередь ребром соединяются вершины q2 и q3. Затем ребрами соединяются вершины q1 с q6, q4 с q5 и q7 с q8.


• q2 • q1 • q4 • q7

q3 • q6 • q5 • q8 •
Рис. 21.1. Результат первого шага построения гиперкуба

Чтобы из четырех одномерных гиперкубов получить два двухмерных, надо добавить четыре ребра. Для этого выбираются такие ребра, чтобы сумма их весов была максимальна. Сначала строится один гиперкуб, для которого выбираются два ребра с максимальной суммой весов. Затем точно так же собирается второй гиперкуб. На рис. 21.2 показаны варианты выбора ребер для получения первого двухмерного гиперкуба.
q2 • • q3 q2 • • q3 q2 • • q3 q2 • • q3

q1 • • q6 q6 • • q1 q4 • • q5 q5 • • q4
w12  w36 = 2 w26  w13 = 3 w24  w35 = 2 w25  w34 = 4

q1 • • q6 q1 • • q6

q4 • • q5 q5 • • q4
w14  w56 = 2 w15  w46 = 0
Рис. 21.2. Варианты сборки двухмерного гиперкуба
Вершины q7 и q8 здесь не участвуют, так как все инцидентные им ребра имеют нулевой вес и сумма их весов заведомо не максимальна. Максимальной суммой весов обладает четвертый вариант. Для второго гиперкуба все варианты одинаковы.

На рис. 21.3 изображены два двумерных гиперкуба, из которых надо собрать один трехмерный гиперкуб, добавив четыре ребра. Варианты такой сборки представлены на рис. 21.4. Сумма весов ребер показана ниже каждого изображения варианта сборки.

Метки:  

 Страницы: [1]