Что такое булев куб

3.2. Булев куб и его свойства

Булев вектор может применяться для моделирования операций на конечных множествах. Пусть – некоторое универсальное множество в рамках решаемой задачи. Элементы множества для удобства помечены числовыми индексами. Если , то множеству А ставится в соответствие n— мерный булев вектор , в котором , если и в противном случае. Такая строка бит называется характеристическим вектором множества А. При этом, операции на множествах имитируются соответствующими логическими операциями на характеристических векторах.

Для размерности n операции над векторами производятся покоординатно. Логическая сумма двух векторов – вектор, координаты которого являются логическими суммами соответствующих исходных векторов. Аналогично определено произведение.

Между множеством всех подмножеств множества U и булевым кубом , где можно установить взаимнооднозначное соответствие, при котором операции объединения множества соответствует операции логического сложения (их характеристических векторов), операции пересечения множеств соответствует операция логического умножения их характеристических векторов, а операции дополнения – операция отрицания. Пустому множеству соответствует нулевой вектор, а универсальному – единичный.

Пример. Пусть , и . Характеристическими векторами множеств А, В, , и соответственно будут: . Полученные векторы позволяют легко выписать элементы множеств: .

Номером булевого вектора называется число его двоичного представления. Например, булев вектор а из предыдущего примера имеет номер 10101.

Два булевых вектора называются соседними, если их координаты отличаются только в одном разряде (т.е. они отличаются только одной координатой).

Булев куб размерности 1

Булев куб размерности 2

Булев куб размерности 3

3.3. Понятие отношения

Для выражения взаимодействий и связей между элементами множеств в математике используется понятие отношения.

n – местным (n – арным) отношением R на множествах называется любое подмножество прямого произведения этих множеств, то есть . Другими словами, элементы этих множеств связаны отношением R тогда и только тогда, когда n упорядоченных чисел .

Отношение называется n – местным на множестве А.

При отношение R задает фиксированный элемент множества А. При отношение R представляет собой подмножество множества А и называется унарным отношением или свойством. При отношение R называется бинарным или соответствием. При отношение тернарное и т. д.

В математике чаще всего используются бинарные отношение (соответствия). В дальнейшем рассматриваются в основном только такие отношения и при этом слово “бинарные” опускается.

Пусть А и В – два множества. Соответствием или (бинарным) отношением из множества А в множество В называется подмножество R прямого произведения , т.е. . Если aA, bB, находятся в отношении, то пишут: (a,b)R или R(a,b), а также в инфиксной форме aRb. При этом говорят, что b соответствует a при соответствии R или b находится в отношении R с a. Если R=, то отношение называют пустым. Отношение называют полным. Для любого множества А определяется тождественное отношение — .

Принадлежность элементов а и b отношению R наглядно можно представить в следующем виде

Областью определения (DomR) соответствия R, называется множество элементов aA, для каждого из которых, найдется хотя бы один элемент bB, такой, что aRb.

Областью значения (ImR) соответствия R называется множество элементов bB, для каждого из которых, найдется хотя бы один элемент aA, такой, что aRb.

Соответствие R называется всюду определенным, если DomR=A, в противном случае – частично определенным. Соответствие называется сюръективным, если ImR=B.

Для каждого aA, множество элементов bB таких, что aRb называется образом элемента aA относительно R и обозначается im_Ra.

Прообразом элемента bB относительно R, называется множество элементов aA, таких, что aRb. Прообраз обозначается: coim_Rb

В общем случае отношения (соответствия) могут быть заданы любым из двух способов, которые используются для задания множеств, т.е. перечислением элементов отношения или указанием их характеристических свойств.

Отношения, определенные на конечных множествах , могут быть заданы:

Матрицей [R] размерности , элементы которой т.е. строки этой матрицы помечаются элементами из A, а столбцы – элементами из B, а на пересечении строки a_i со столбцом b_i стоит единица (1), если aRb; и нуль (0), — в противном случае. Тогда для выше приведенного примера имеем матрицу

Булевы функции и булев куб

В дискретной математике большую роль играют конечные функции. Конечной функцией называют отображение одного конечного множества в другое. Важный класс таких функций образуют булевы функции.

Булева функция (от переменных) — это произвольное отображение вида

т.е. булева функция определена на множестве всех n-элементных (при ) последовательностей (или n-компонентных кортежей) нулей и единиц и принимает два возможных значения: 0 и 1.

С понятием булевой функции тесно связаны понятия булевой константы и булева переменного. (В литературе по теории булевых функций традиционно употребляется термин "булева переменная" (в женском роде).)

Булева константа — это индивидная константа с областью значений . Таким образом, существуют две булевы константы: 0 и 1. По определению принимается, что каждая булева константа есть также булева функция от 0 переменных (что вполне аналогично определению нульарной операции).

Булево переменное — это индивидное переменное с областью значений , т.е. это переменное, которое может принимать только два значения: 0 и 1 (подобно тому, как действительное переменное принимает произвольное действительное значение, а комплексное переменное — произвольное комплексное значение). Тогда с использованием понятия булева переменного мы можем задать булеву функцию (6.1) записью , в которой каждое булево переменное , и функция / принимают два возможных значения: 0 и 1. Переменные называют при этом переменными булевой функции . Фиксируя значение каждого переменного , получаем кортеж из множества , называемый набором значений переменных , и соответствующее ему значение функции , которое будет значением переменного , сопоставленным заданным значениям переменных .

Подчеркнем, что, если специально не оговорено противное, в выражении все переменные предполагаются попарно различными, т.е. пробегающими каждое независимо от других множество .

Понятию булевой функции можно придать иной смысл, понимая элементы множества как истинностные значения, а именно понимая единицу как "истину", а нуль как "ложь". Такие истинностные значения могут быть, как мы знаем, сопоставлены каждому высказыванию. Тогда булева функция есть некоторое правило, позволяющее каждому фиксированному набору истинностных значений, т.е. набору значений булевых переменных, сопоставить то или иное истинностное значение. Так может быть вычислено, например, истинностное значение сложного высказывания, составленного по определенным правилам из простых высказываний. Подобного рода сложные высказывания составляются с помощью логических операций: "или", "и", "если . то . " и т.п. Указанная логическая интерпретация булевой функции позволяет понять, почему булево переменное часто называют логическим переменным (традиционный термин: "логическая переменная"), а булеву функцию — логической функцией (или функцией алгебры логики).

Кроме того, согласно определению, булева функция от переменных есть отображение n-й декартовой степени множества в множество , т.е. не что иное, как n-арная операция на множестве . Тем самым логическая интерпретация булевой функции согласуется с ее алгебраической интерпретацией: булева функция есть операция (в алгебраическом смысле этого слова) на множестве истинностных значений. Тогда и понятие логической операции, которое было введено ранее, оказывается частным случаем общего понятия операции.

Будем обозначать через множество всех булевых функций (для всех возможных значений числа переменных), а через — множество всех булевых функций от переменных (для фиксированного ). Из определения следует, что .

Итак, областью определения любой булевой функции от переменных является множество , т.е. булев куб размерности . Элементы булева куба называют n-мерными булевыми векторами (или наборами). Число всех элементов булева куба составляет является носителем булевой алгебры (это же обозначение часто будем использовать и для соответствующего булева куба). Но в любой булевой алгебре определяется, как известно, естественное отношение порядка так, что для произвольных соотношение выполняется тогда и только тогда, когда .

Употребляются также термины: единичный куб размерности , n-мерный единичный куб; вместо слова "куб" говорят также "гиперкуб".

Согласно общему принципу распространения отношения порядка на декартово произведение множествам. 4.5), для произвольных двух наборов и из имеет место тогда и только тогда, когда для каждого , то есть .

Другими словами, тогда и только тогда, когда или , а для каждого . Если существует хотя бы одно , то имеет место строгое неравенство . В частности, если существует ровно одно такое доминирует над набором , так как ясно, что в этом случае нельзя найти такой набор , что .

Пример 6.1. В булевом кубе причем второй из этих наборов доминирует над первым, а третий — над вторым (но, естественно, третий уже не доминирует над первым, а лишь строго больше его). Наборы же и — несравнимые элементы, так как первая компонента второго набора больше первой компоненты первого набора, но зато вторая компонента первого набора больше второй компоненты второго набора. Подчеркнем также, что описанное сравнение наборов возможно только для фиксированной размерности и никак нельзя сравнивать наборы разных размерностей.

Булевый порядок

Рассмотренное отношение порядка на

Другой способ наглядного изображения булева куба основан на том, что диаграмма Хассе любого конечного упорядоченного множества , тогда и только тогда, когда доминирует над компонент отличны от нуля (множество всех таких наборов для фиксированного , будем называть булевой n-сетъю или просто булевой сетью, если упоминание о размерности опускается. Так как булев куб имеет наименьший элемент — нулевой набор и наибольший элемент — единичный набор, то каждая булева сеть имеет единственный вход (помеченный нулевым набором) и единственный выход (помеченный единичным набором).

На рис. 6.2 приведено изображение булева куба

Помимо булева порядка полезно также ввести на булевом кубе другое отношение порядка, которое мы будем называть лексикографическим порядком, используя обозначение (для произвольного фиксированного ). По определению,

Каждая из сумм в неравенстве (6.2) есть не что иное, как представление некоторого натурального числа (включая и нуль) в двоичной системе счисления (при числе разрядов, равных фиксированной размерности ). На каждый булев вектор можно смотреть как на такое представление (двоичный код) натурального числа, и лексикографический порядок на булевом кубе множества (при условии, что числа заданы в двоичной системе счисления). Более строго: упорядоченное множество изоморфно подмножеству с естественным числовым порядком.

Заметим, что отношение лексикографического порядка является, в отличие от булева порядка, отношением линейного порядка.

Пример 6.2. Набор как двоичный код числа лексикографически больше набора , служащего двоичным кодом числа 3, но при этом указанные наборы не сравнимы по отношению булева порядка.

Однако лексикографический порядок при изучении булевых кубов играет вспомогательную роль. В частности, при изображении булевых кубов (в виде диаграмм Хассе или в виде сети) принято располагать вершины каждого k-слоя в лексикографическом порядке (по возрастанию — слева направо или сверху вниз). Везде в дальнейшем, рассуждая о булевом кубе как об упорядоченном множестве, мы имеем в виду булев порядок.

Грань булева куба

Гранью булева куба размерности — размерность булева куба, называют множество наборов, имеющих не менее и из множества . Тогда грань, обозначаемая как , есть множество всех таких . При этом кортеж номеров называют направление ем грани . Если число , полагая, что второй набор доминирует над первым. Любая вершина булева куба считается гранью размерности 0.

Можно показать, что число всех граней размерности .

Пример 6.3. В четырехмерном булевом кубе . Эта грань состоит из восьми наборов:

На рис. 6.1 выделены все ребра булева куба

Грани булева куба, имеющие одно и то же направление, называют параллельными. Две параллельные грани и называют соседними, если один из наборов и доминирует над другим. На рис. 6.1 грани и соседние, равно как и грани (ребра) и . Но ребра и не являются соседними.

Нетрудно догадаться, что каждая грань размерности , столькими способами, сколько существует разных n-мерных граней в кубе размерности способами. Так, одномерный куб четырьмя способами — как одна из его четырех одномерных граней (т.е. как одно из его четырех ребер, см. рис. 6.1).

Договоримся впредь записывать конкретные наборы (элементы булева куба соответствующей размерности) без скобок и запятых, т.е. будем писать не , а переменных для фиксированного . Поскольку каждая булева функция отображает множество из равна Замечание 6.1. Поскольку булева функция от переменных является в то же время и n-арной операцией на множестве , то при существуют две нульарные операции: 0 и 1, которые есть не что иное, как нуль и единица двухэлементной булевой алгебры.

Научный форум dxdy

Пожалуйста, объясните, что такое $N$ -мерные булев куб , $\pm1$ -куб и соответствующие симплексы ?
В каких областях математики наиболее полно развита их теория? Где об этом можно подробно прочесть?
$N$ -мерные булев куб

Это $$\< 0;1\>^N$» /> — граф на множестве векторов длины <img decoding=$ и нулями и единицами. Используется в аналитической геометрии, для решения задач булева линейного программирования (NP-задачи на графах) и еще много где.
$\pm1$ -куб

$N$ — мерный симплекс — полный граф на $N+1$ линейно независимых точках в $N$ -мерном пространстве (при $N=0$ — точка, при $N=1$ — отрезок, при $N=2$ — треугольник, при $N=4$ — треугольная пирамида и т.п.). Извините за кривое определение. Вообще, их начинают изучать в аналитической геометрии, а потом где только не используют.
$\pm 1$ -симплекс —
$\pm1$ -куб

Вот, вчера наткнулся, среди прочего

Информационные процессы, Том 8, № 4, 2008, стр. 201-204.
МАТЕМАТИЧЕСКИЕ МОДЕЛИ, ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ
«О квадратичных формах, равных единице на большом множестве вершин n-мерного куба»
Селиверстов, Любецкий

Последний раз редактировалось Sonic86 05.10.2011, 10:27, всего редактировалось 1 раз.

Ааа, тогда понятно.
Я с перепугу подумал, что это размерность такая.

— Ср окт 05, 2011 07:27:13 —

Да обычный куб, образ при гомотетии булева $N$ -мерного куба смотря, что авторы в нем откопали.

Читать:

Как найти ключ по значению в словаре питон

Сейчас я попробую сформулировать.

В -мерном случае вершины куба имеют координаты: $(0,0,0),\ (1,0,0),\ (0,1,0),\ (1,1,0),\ (0,0,1),\ (1,0,1),\ (0,1,1),\ (1,1,1)$
а вершины его грани построенной на первых дух ортах: $(0,0,0),\ (1,0,0),\ (0,1,0),\ (1,1,0)$

Пусть размерность $N=4$ .
Вершины грани гиперкуба построенной на первых трех ортах будут иметь координаты (к координатам вершин куба добавится в четвертой позиции): $(0,0,0,0),\ (1,0,0,0),\ (0,1,0,0),\ (1,1,0,),\ (0,0,1,0),\ (1,0,1,0),\ (0,1,1,0),\ (1,1,1,0)$
Тогда через любые из этих вершин можно провести прямую (или правильно будет сказать — гиперплоскость размерности $N-1$ ?), это верно? Например, через точки имеющие ровно ненулевые координаты — $(1,1,0),\ (1,0,1),\ (0,1,1)$

Пусть размерность $N$ произвольна.
Как пронумеровать подмножества вершин грани содержащие по $N-1$ вершине, каждая из которых имеет ровно ненулевые координаты?

Можно ли выписать эти подмножества (или, хотя бы, вершины) не выковыривая их по одной из всего множества сочетаний из $N-1$ по ?

Нельзя ли использовать, например, то свойство, что все такие вершины принадлежат одной грани, а их радиус-векторы имеют одинаковую длину и значит их кратчайший обход можно совершить по дуге окружности?

Как пронумеровать подмножества вершин грани содержащие по $N-1$ вершине, каждая из которых имеет ровно ненулевые координаты?

В лоб. Вектору $\bar x = (x_1. x_n), x_j \in E$ можно поставить в соответствие число $$a(\bar x) = \sum\limits_<k=0>^n x_k2^<k-1>$» />, номер вектора — это номер элемента в упорядоченном списке <img decoding=$ . Причем условие $\sum\limits_k x_k = 3$ не требуется — это работает для любого числа единиц в векторе.
Можно ли выписать эти подмножества (или, хотя бы, вершины) не выковыривая их по одной из всего множества сочетаний из $N-1$ по ?

Последний раз редактировалось serval 05.10.2011, 12:58, всего редактировалось 3 раз(а).

Последний раз редактировалось Sonic86 05.10.2011, 13:13, всего редактировалось 1 раз.

Нет. Не поняли Вы меня.
Чтобы Вам увидеть закономерность в расположении упорядоченных векторов длины $n$ с $k$ единичками, Вам нужно самому взять например $n=6,k=3$ и ручками выписать все эти вектора, посмотреть на них и увидеть закономерность. После того, как Вы ее увидите, Вы сможете выписывать их сами или программно или даже через формулу для любых $n,k$ без полного перебора всех векторов.

Я имел ввиду, что если этот объект и есть, то это не дуга и не многоугольник (это плоские объекты) — нужно их называть соответствующими словами, указывающими на их $N$ -мерность.

Я пробовал. Как раз для случая $N=6$ пытался придумать алгоритм пересчета (вроде пересчета всех сочетаний) — и затруднился. Поэтому и обратился с вопросом.

Пусть будет гипердуга
Можно я не буду лепить к каждому термину эту приставку? А то получается коряво. Просто будем понимать, по аналогии с гиперкубом, что все объекты имеют соответствующую размерность.
Но тут я запутался. С одной стороны, через $N-1$ такую точку можно провести прямую, а с другой — все они лежат на дуге окружности. где я ошибся? Или это шутки многомерия?
Я пробовал. Как раз для случая $N=6$ пытался придумать алгоритм пересчета (вроде пересчета всех сочетаний) — и затруднился. Поэтому и обратился с вопросом.

Так там всего 20 векторов, на листочек влазит. Просто выпишите их хоть перебором и отсортируйте. Если так трудно — используйте Excel или возьмите $n=4,k=2$ .
Попробуйте выписать из рекуррентных соображений: т.е. вектор длины 6, у него 1-й элемент, либо 1, либо 0 — по этому признаку множество векторов разбивается на 2 класса, причем 1-й класс — это множество всех векторов длины 5 с 2-я единичками (размерность уменьшилась!), а 2-й класс — это множество всех векторов длины 5 с 3-я единичками (размерность уменьшилась снова!). Это соответствует рекуррентной формуле $C_n^k = C_<n-1>^<k-1>+C_<n-1>^k$» /> — слагаемые — это мощности классов. Пишите результат здесь. Это просто.
Последний раз редактировалось serval 05.10.2011, 16:15, всего редактировалось 1 раз.
Вот эти векторы для <img decoding= :

$(1,1,1,0,0,0)$
$(1,1,0,1,0,0)$
$(1,0,1,1,0,0)$
$(0,1,1,1,0,0)$
$(1,1,0,0,1,0)$
$(1,0,1,0,1,0)$
$(0,1,1,0,1,0)$
$(1,0,0,1,1,0)$
$(0,1,0,1,1,0)$
$(0,0,1,1,1,0)$
$(1,1,0,0,0,1)$
$(1,0,1,0,0,1)$
$(0,1,1,0,0,1)$
$(1,0,0,1,0,1)$
$(0,1,0,1,0,1)$
$(0,0,1,1,0,1)$
$(1,0,0,0,1,1)$
$(0,1,0,0,1,1)$
$(0,0,1,0,1,1)$
$(0,0,0,1,1,1)$

Последний раз редактировалось ИСН 05.10.2011, 15:47, всего редактировалось 2 раз(а).

Алгоритм матричного отображения графа на булев куб Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Закревский Аркадий Дмитриевич

Рассматриваемая в настоящей статье задача имеет важные приложения в теории и практике проектирования дискретных устройств. Именно к ней в значительной степени сводится минимизация числа переключений элементов памяти при схемной реализации конечного автомата. В статье излагается формальный матричный метод решения этой задачи, разработанный на базе предложенного ранее визуального метода и ориентированный на компьютерную реализацию.

Текст научной работы на тему «Алгоритм матричного отображения графа на булев куб»

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

2011 Управление, вычислительная техника и информатика № 3(16)

ДИСКРЕТНЫЕ ФУНКЦИИ И АВТОМАТЫ

АЛГОРИТМ МАТРИЧНОГО ОТОБРАЖЕНИЯ ГРАФА НА БУЛЕВ КУБ

Ключевые слова: граф переходов, матрица смежности, булев куб, матрица куба, кодирование состояний, отображение ребер.

Важной проблемой современной теории и практики автоматизированного проектирования дискретных устройств является задача энергосберегающего кодирования состояний автомата, реализуемого логической схемой. Она формулируется следующим образом. Автомат задается неориентированным графом переходов О с т вершинами. Информация об ориентации переходов при этом не учитывается, поскольку она оказывается несущественной. Требуется оптимальным образом разместить вершины графа в булевом пространстве М = <0, 1>п, размерность которого п равна целому, ближнему сверху к т, и которое можно рассматривать

как п-мерный булев куб. За критерий оптимальности примем число ребер графа, отображенных на ребра булева куба. В результате этого отображения инцидентные ребру графа вершины окажутся на соседних элементах пространства М, т.е. на булевых п-векторах, различающихся ровно в одной компоненте.

В работе [1] был предложен эвристический визуальный метод решения этой задачи, названный методом квадратов. Он основан на использовании графического изображения графа и карты Карно и заключается в построении последовательности конфигураций из ребер и квадратов, образующих фрагменты гиперкуба. Квадратом называется четырехреберный цикл в графе.

Ниже описывается оригинальный комбинаторный алгоритм решения этой же задачи на базе матричных представлений, ориентированный на компьютерную реализацию.

1. Представление данных

Рассматриваемый в предлагаемом алгоритме граф переходов представляется симметричной булевой матрицей смежности Є размером т х т. Элемент этой матрицы giJ = 1, если и только если вершины і и / связаны некоторым ребром -обозначим это ребро через (і-/). Другими словами, соответствующие этим вершинам состояния автомата связаны некоторым переходом. Очевидно, что giJ =gj'.

Положим, что gi 1 = 0, поскольку переходы состояний в себя при решении рассматриваемой задачи не учитываются.

Например, показанный на рис. 1 граф переходов автомата с 11 состояниями представляется следующей матрицей смежности:

Рис. 1. Граф переходов

1 2 3 4 5 6 7 8 9 10 11

0 0 1 0 0 1 0 1 0 0 0 1

0 0 0 1 0 1 0 0 1 0 1 2

1 0 0 0 0 1 1 0 1 0 0 3

0 1 0 0 1 0 0 1 0 0 0 4

0 0 0 1 0 0 0 0 0 1 1 5

1 1 1 0 0 0 1 0 0 1 0 6

0 0 1 0 0 1 0 0 1 0 0 7

1 0 0 1 0 0 0 0 1 0 0 8

0 1 1 0 0 0 1 1 0 0 0 9

0 0 0 0 1 1 0 0 0 0 1 10

0 1 0 0 1 0 0 0 0 1 0 11

Два ребра графа назовем параллельными, если они не содержат общих вершин и принадлежат оба некоторому квадрату. Это условие легко проверяется в визуальном методе — достаточно посмотреть на граф. В методе, предлагаемом в настоящей статье, оно представляется более формально, в терминах матрицы смежности.

Два ребра графа (і-/) и (к-1), задаваемые матричными элементами giJ и gk 1, параллельны, если матрица смежности Є принимает значение 1 также на элементах gi1 и gk3. Другими словами, эти ребра параллельны, если все четыре элемента матрицы, расположенные на пересечении строк gi и gk со столбцами £ и gI, принимают значение 1.

В этом случае они принадлежат квадрату, который удобно задать выражением (і, /, к, I), в котором смежные вершины представлены соседними или крайними членами. Кроме ребер (і-/) и (к-1) в квадрат входит также пара I——-к

параллельных ребер (/, к) и (I, і) (рис. 2). , ,

т-> /їх Рис. 2. Квадрат (і, /, к, I)

В данном примере (рис. 1) параллельными оказываются ребра (4-5) и (11-2), принадлежащие отмеченному

на рисунке квадрату, равно как и ребра (5-11) и (2-4). Они представляются четырьмя матричными элементами, на пересечении строк 4 и 11 со столбцами 2 и 5. Это элементы g4 2, g4 5, g¡¡2 и g¡¡ 5. Они отмечены в матрице курсивом. А квадрат в целом представляется выражением (4-5-11-2).

Заметим, что перечисление вершин квадрата можно начинать с любой вершины и в любом направлении. Из этого следует эквивалентность следующих обозначений данного квадрата:

Структуру булева куба, на который требуется спроектировать граф переходов, представим переменной булевой матрицей В размером п на 2п, строки которой соответствуют булевым переменным хь х2, . хп, а столбцы — элементам булева

пространства этих переменных, т.е. вершинам булева куба. Назовем ее матрицей куба.

Перед выполнением алгоритма отображения все элементы матрицы куба имеют значение 1. Например, при п = 4 эта матрица имеет следующий начальный вид:

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 X!

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 х2

0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 х3

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 х4

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 1 1 х2

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 х3

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 х4

Элементы булева пространства (вершины булева куба), соответствующие столбцам матрицы Ь/, пронумерованы и показаны сверху, а булевы переменные, соответствующие ее строкам Ьі — справа. Ребра куба представлены соответствующими парами элементов матрицы В; значение й/ говорит о том, что /-й вершине куба инцидентно ребро, ориентированное по переиенной хі. Например, в матрице отмечены полужирным четыре ребра, инцидентные вершине 0 — это ребра (0-1), (0-2), (0-4) и (0-8). При выполнении алгоритма некоторые элементы матрицы В меняют свое значение с 1 на 0, что свидетельствует об использовании ребер булева куба в ходе реализации алгоритма отображении ребер графа в булево пространство.

2. Алгоритм отображения

Предлагаемый алгоритм заключается в последовательном выборе ребер графа (единичных элементов матрицы Є) и отображении их в булево пространство М = <0, 1>п (п-мерный булев гиперкуб) путем кодирования соответствующих пар вершин булевыми векторами с п компонентами.

На первом шаге выбирается некоторое ребро, для которого находится параллельное ему. В рассматриваемом ниже примере из нескольких подходящих ребер всегда выбирается ребро с минимальным номером. Например, в рассматриваемом графе первыми выбираются ребро (1-3) и параллельное ему ребро (7-6). Вершины первого из них кодируются соседними кодами — различающимися значением в одной компоненте. Операцией смены значений другой компоненты из этих кодов получаются коды вершин другого ребра.

Так, вершины 1 и 3 кодируются векторами 0000 и 0001, а вершины 7 и 6 — векторами 0010 и 0011. Эти ребра образуют квадрат (1-3-7-6), куда входят также ребра (3-7) и (6-1). Таким образом, в результате этой четыре ребра графа (1-3), (3-7). (7-6) и (6-1), образующие найденный квадрат, отображаются на соответствующие ребра булева куба: (0-1), (1-3), (3-2) и (2-0). Соответственно корректируется матрица В. Отображенные ребра отмечаются в матрице Є.

Проиллюстрируем эту операцию новым значением матрицы В. Сверху матрицы В показаны вершины графа, проектируемые на вершины булева куба, пред-

ставленные столбцами матрицы. Справа показано, как из кодов вершин ребра (1-3) получаются коды вершин параллельного ему ребра (7-6) Звездочкой отмечена компонента с изменяемым значением.

На каждом из последующих шагов алгоритма выбирается одно из отображенных ребер и находится параллельное ему свободное ребро графа (с пока не закодированными вершинами). Коды его вершин получаются из кодов соответствующих вершин отображенного ребра, сменой значений одной компоненты, так, чтобы они были новыми (ранее не встречались). В результате кодируются две новые вершины и отображаются три ребра.

Опишем эти операции более подробно.

Выбор отображенного ребра. Рассматривается некоторое отображенное ребро (і, /) графа, отмеченное в матрице Є . Обозначим через Ь* и Ь/ столбцы матрицы В, соответствующие кодам вершин і и / (например, Ь1 = [1100]т). Если конъюнкция этих столбцов не содержит единиц (Ь і Л Ь/ = 0), не существует свободного ребра, параллельного ребру (і, /), следовательно, надо выбрать другое из отображенных ребер. Их можно перебирать в порядке нумерации.

Нахождение параллельного ему среди свободных ребер. Обозначим через N множество незакодированных вершин, а через Я/ и Су соответствующие этим вершинам подмножества строк и столбцов матрицы Є. Допустим, что выбрано отображенное ребро (р-д). Рассмотрим в множестве Я/ некоторую строку gk, содержащую единицу в /-й компоненте = 1). Если конъюнкция векторов gi и gk принимает значение 1 в некотором столбце I из множества С/, находится свободное ребро (к-1), параллельное ребру (р-д). В противном случае рассматривается другая строка из Я^.

Кодирование вершин и отображение ребер. Коды вершин к и I получаются соответственно из кодов вершин / и і сменой значения младшей из компонент, удовлетворяющих следующему условию: одноименная компонента в векторе Ь 1 л Ь* должна быть равна единице. Из этого условия, в частности. следует, что данная компонента имеет одинаковое значение в кодах вершин / и і .

В соответствии с этими правилами выполняются последующие шаги алгоритма. На каждом из них выбирается свободное ребро, параллельное одному из отображенных, и кодируются его вершины. Результат представляется новым значением матрицы куба В. Процесс кодирования вершин показан справа от этой матрицы.