Булевы функции и графы

[cyb12]

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

[arseniiv]

cyb12 в сообщении #688953 писал(а):

Вопрос - а сколько таких графов может получиться в результате (имеется в виду попарно не изоморфных) для всех функций от $n$ переменных?

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

-- Чт фев 28, 2013 01:19:58 --

А дальше можно рассмотреть симметрии гиперкуба и попробовать теорему Редфилда—Пойа. Кажется, это то самое.

[cyb12]

Ну да, вы правы, избавиться от функций просто. Но вот с применением теоремы Пойа, похоже, будут трудности.

[arseniiv]

Вот группы симметрий: http://groupprops.subwiki.org/wiki/Sign ... tric_group.