close

Вход

Забыли?

вход по аккаунту

?

Неизоморфные бинарные матроиды.

код для вставкиСкачать
УДК 510
НЕИЗОМОРФНЫЕ БИНАРНЫЕ МАТРОИДЫ
© 2011 С. А. Гизунов
докт. техн.. наук, профессор,
e-mail: gsa_sci@rambler.ru
Курский НИИ Министерства обороны РФ
На основе результатов исследования свойств некоторых алгебраических структур,
порожденных морфизмами в категории матроидов и их отображений, предложен алгоритм
построения всех неизоморфных бинарных матроидов заданных на конечном множестве.
Ключевые слова: матроид, изоморфизм, цикловая структура, лифт.
M1, M 2 ∈M ( S ) с точки зрения
их цикловых структур означает, что на множестве S существует взаимно однозначное
соответствие π , такое, что для любого цикла C = ( c1 ,..., ck ) ∈ R M матроида M 1,
1
множество π (C ) = (π (c1 ),..., π (ck )) будет циклом матроида M 2 . Понятно, что,
говоря об изоморфизме матроидов M 1 и M 2 , автоматически здесь и далее будем
предполагать, что rM ( S ) = rM ( S ) = r ( S ) . Семейство циклов R M произвольного
1
2
матроида M ∈M ( S ) , как и любое семейство подмножеств заданного множества S ,
Изоморфизм матроидов одинакового ранга
однозначно
Г (S, R
описывается матрицей инцидентности, или двудольным графом
, вершинами которого являются элементы множества S и циклы из
M)
семейства
R
ребром,
с
M
a∈S
C ∈R M ,
, и элемент
циклом
M1, M 2 ∈M ( S )
инцидентен, или соединен в графе
если
изоморфны
соответствующие графы
тогда
Г (S, R
M1
)
a ∈C .
и
и
Таким
только
Г (S, R
M2
тогда,
).
образом,
когда
Г (S, R M )
матроиды
изоморфны
Отсюда следует, что в
изоморфных матроидах совпадает не только общее количество циклов и количество
циклов заданной длины, но и количество циклов, инцидентных любому элементу
a ∈ S . В то же время это условие для изоморфизма матроидов необходимое, но не
достаточное.
Для
любого
матроида
введем
обозначение
M ∈M ( S )
R
M
( r, A) = {C ∈ R
M
A⊆C
что множество всех циклов длины
с множеством
UR
M
| C | = r}, 1 ≤ r ≤ rM ( S ) + 1. Тогда очевидно,
r в R M (обозначим его через R M (r) ) совпадает
и
( r, a ) .
a∈S
Для любого подмножества
A⊆ S
построим целочисленный вектор вида
ΩM ( A) = {| R M (1, A) |, | R M (2, A) |,..., | R M ( rM ( S ) + 1, A) |}.
(1)
МАТЕМАТИЧЕСКИЕ НАУКИ
ΩM ( A) может быть нулевым, например, для подмножеств
A , таких, что | A | > rM ( S ) + 1.
Для любого r,1 ≤ r ≤ rM ( S ) + 1, количество циклов длины r в семействе
rM ( S ) +1
1
R M равно | R M ( r ) | = ∑ | R M ( r, a ) |, а ∑ | R M ( r, a ) | есть общее
r a∈S
r =1
количество циклов, инцидентных вершине a ∈ S в графе Г ( S , R M ) .
Как уже отмечалось, если взаимно однозначное отображение π на множестве
порождает
изоморфизм
матроидов
то
S
M1, M 2 ∈M ( S ) ,
r
для
всех
допустимых
значений
и
| R M1 ( r ) | = | R M 2 ( r ) |
Понятно, что вектор
r ( S ) +1
∑ |R
r =1
M1
( r, a ) | =
r ( S ) +1
∑ |R
r =1
M2
( r, π ( a )) |
для всех элементов
одних этих условий для изоморфизма матроидов
M1
и
M2
a∈S ,
однако
недостаточно. В
частности, должно совпадать и общее количество различных элементов a ∈ S ,
принадлежащих циклам из семейств
R M ( r ) и R M ( r ) , то есть
1
2
|{a ∈ S a ∈ C и C ∈ R M1 ( r )}| = |{b ∈ S b ∈ D и D ∈ R M 2 (r )}| , для всех
значений r , 1 ≤ r ≤ r( S ) + 1.
Утверждение 1. Матроиды M1, M 2 ∈M ( S ) изоморфны тогда и только
тогда, когда на множестве S существует взаимно однозначное отображение π ,
такое, что Ω M ( A) = Ω M (π ( A)) для любого подмножества A ⊆ S .
1
2
Доказательство. Для изоморфных матроидов M1, M 2 ∈M ( S ) равенство
векторов (1) очевидно.
Пусть цикл C ∈ R
M1
(r)
для некоторого
r, 1 ≤ r ≤ rM1 ( S ) + 1.
Так как
циклы не могут содержаться друг в друге как подмножества, то из равенства
Ω M (C ) = Ω M (π (C )) следует, что | R M ( r, C ) | = | R M ( r, π (C )) | = 1.
1
Отсюда,
2
с
π (C ) ∈ R
учетом
1
определения
множества
R
2
M2
( r, π (C )) ,
получаем,
что
( r ) . Изоморфизм матроидов одинакового ранга, таким образом, следует
из того факта, что данное включение справедливо для любых циклов C ∈ R M ( r ) и
1
значений параметра r , 1 ≤ r ≤ rM ( S ) + 1. W
1
Для
любого
подмножества
обозначим
через
A⊆ S
A( m) = {B ⊆ A | B | = m} совокупность всех его подмножеств мощности
С
учетом
этого
обозначения
пусть
далее
m,1 ≤ m ≤ | A |.
M2
Ученые записки: электронный научный журнал Курского государственного университета. 2011. № 2 (18)
Гизунов С. А. Неизоморфные бинарные матроиды
Ω M1 ( m ) = {Ω M1 ( A) A ∈ S (m)}
и
Ω M1 ( m )
и
целочисленных векторов
Ω M1 ( m ) ≅ Ω M 2 ( m ) ,
элементов множества S .
обозначать
Ω M 2 ( m ) = {Ω M 2 ( B) B ∈ S (m)}.
ΩM2 ( m)
Семейства
будем называть эквивалентными и
если они совпадают с точностью до перестановки
Условие эквивалентности, в свою очередь, означает выполнение двух
следующих условий.
Во-первых, совокупность подмножеств S (m) разбивается на классы
эквивалентности вида
S (m) = SM(1)1 (m) + ... + S M( tm1 ) (m) = S M(1)2 (m) + ... + S M( tm2 ) (m)
(2)
| SM( i 1) (m) | = | SM( i )2 (m) |
для всех
так, что с точностью до нумерации
i,1 ≤ i ≤ tm ,
когда
и равенство
Ω M1 ( A) = Ω M 2 ( B )
выполняется тогда и только тогда,
A ∈ S M( i 1) (m) и B ∈ S M( i )2 (m) для некоторого i,1 ≤ i ≤ tm .
Во-вторых, существует взаимно однозначное соответствие
элементов
S,
такое, что, если
A ∈ S M( i 1) (m) ,
то
πm
на множестве
π m ( A) ∈ S M( i ) (m)
2
для всех
i,1 ≤ i ≤ tm .
Утверждение
2.
Матроиды
M1, M 2 ∈M ( S )
rM1 ( S ) = rM 2 ( S ) = r ( S )
изоморфны
Ω M1 ( m ) ≅ Ω M 2 ( m )
m,1 ≤ m ≤ r( S ) ,
для всех
тогда
и
одинакового
только
тогда,
ранга
когда
и соответствующие перестановки
π m непротиворечивы как взаимно однозначные соответствия на множестве S .
Доказательство. Достаточно показать, что на множестве элементов S
существует перестановка π , такая, что Ω M ( A) = Ω M (π ( A)) для всех
1
2
A ⊆ S , | A | ≤ r( S ) . Однако в условиях утверждения этот факт
индукцией по m,1 ≤ m ≤ r( S ) , следует из непротиворечивости перестановок π m ,
определенных на всем множестве S . W
подмножеств
Из утверждения 2 как следствие можно предложить отличный от метода
перебора алгоритм проверки матроидов M1, M 2 ∈M ( S ) одинакового ранга на
изоморфизм.
Для m = 1 , очевидно, S (1) = S и разбиение (2) имеет вид
S = S M(1)1 + ... + S M( t11) = S M(1)2 + ... + S M( t12) .
(3)
МАТЕМАТИЧЕСКИЕ НАУКИ
Так как в разбиении (3) множества элементов, принадлежащих разным классам,
не пересекаются, то графы Г ( S , R M ) и Г ( S , R M ) будут изоморфными только
1
тогда, когда изоморфны подграфы
2
(i )
M1
Г (S , R
M1
)
Г ( S M( i )2 , R
и
M2
)
для всех
i,1 ≤ i ≤ t1. Другими словами, любую перестановку π1, удовлетворяющую условиям
(t )
(1)
утверждения 2, можно представить следующим образом π 1 = (π 1 ,..., π 1 1 ) , где
π1(i ) : SM(i 1) ↔ SM(i )2 , i = 1, t1 .
Далее, для m = 2 перестановки π 2 , удовлетворяющие условиям утверждения
2,
будут
существовать
только
(i )
M1
(i )
M2
{Ω M1 ( A) A ∈S (2)} ≅ {Ω M 2 ( B) B ∈ S (2)}
тогда,
для
когда
i ,1 ≤ i ≤ t1 .
всех
Соответствующие разбиения (2) имеют вид
S M(i 1) (2) = S M(i 1,1) (2) + ... + S M(i 1,t2 ) (2)
и
.
(4)
( i ,t2 )
S M(i )2 (2) = S M(i ,1)
(2)
+
...
+
S
(2)
M
2
2
Очевидно, что должно совпадать не только количество биграмм в
соответствующих классах разбиений (4), но и количество различных элементов в них.
Другими словами, перестановки π 2 должны быть такими, чтобы соответствия
{a ∈ A A ∈SM(i ,1 j ) (2)} ↔ {b ∈ B B ∈ S M(i ,2j ) (2)}
i,1 ≤ i ≤ t1,
для всех
и
j,1 ≤ j ≤ t2 .
были взаимно однозначными
π1
При этом перестановки
непротиворечивы только тогда, когда для любого
i,1 ≤ i ≤ t1
и элемента
π2
и
a ∈ S M( i 1)
выполняются равенства
|{ A ∈ SM(i ,1 j ) (2) a ∈ A}| = |{B ∈ SM(i ,2j ) (2) π 1(i ) (a) ∈ B}|, j = 1, t2 .
Другими словами, элементы множеств
S M( i 1)
и
S M( i )2 , i = 1, t1 ,
должны
встречаться в классах разбиений (4) одинаковым образом. Отсюда следует, что
(1)
перестановка π 1 = (π 1
перестановок, так, что
,..., π 1( t1 ) )
в
общем
случае
разбивается
на
t1 ⋅ t2
π 2 = (π 1(1,1) ,..., π 1(1,t ) ,..., π 1( t ,1) ,...,π 1( t ,t ) ) .
2
Следовательно, так же как и для
1
1 2
m = 1, графы Г ( S , R
M1
)
(5)
и
Г (S, R
M2
)
изоморфны только тогда, когда изоморфны подграфы, определенные на подмножествах
множества
S , соответствующих перестановкам π 1( i , j ) , где i = 1, t1, j = 1, t2 .
Ученые записки: электронный научный журнал Курского государственного университета. 2011. № 2 (18)
Гизунов С. А. Неизоморфные бинарные матроиды
Очевидно, что если графы изоморфны, то данный итерационный алгоритм
непротиворечив для всех m,1 ≤ m ≤ r( S ) . В противном случае либо векторы
Ω M1 ( m )
ΩM2 ( m)
для некоторого m .
и
не эквивалентны, либо перестановки
π m−1 и π m
противоречивы
Подчеркнем, что проверять на непротиворечивость перестановки π m−1 и π m
имеет смысл только для тех значений параметра m , для которых существуют
подмножества
A ⊆ S (m)
с ненулевыми значениями векторов
Ω M1 ( m )
и
ΩM2 ( m)
в
соответствующих классах разбиений (2). Например, если количество различных
элементов в классах разбиений (4) не превышает двух и перестановки π 1 и π 2
непротиворечивы, то проверка на изоморфизм заканчивается для значения m = 2 , вне
зависимости от величины r( S ) . Действительно, в этом случае на множестве S
существуют перестановки
π2
вида (5), такие, что подграфы, определенные на
S (2) , изоморфны.
Следовательно, чтобы установить изоморфизм матроидов M1, M 2 ∈M ( S ) ,
достаточно проверить условие π 2 (С ) ∈ R M для всех циклов C ∈ R M и только
2
1
соответствующих
подмножествах
из
семейств
S (1)
и
таких перестановок π 2 .
Пусть π – взаимно однозначное соответствие на множестве S , тогда для
любого матроида M ∈M ( S ) через π ( M ) будем обозначать матроид, изоморфный
матроиду
M.
Предположим далее, что матроиды
элементарным отображением
Ф
M ⎯⎯
→H ,
M , H ∈M ( S )
связаны
порожденным модулярным фильтром
ФM = Ф(R H − R M ) . Покажем, что тогда и изоморфные матроиды
π ( M ),π ( H ) ∈M ( S ) связаны элементарным отображением, порожденным
модулярным фильтром Фπ ( M ) = Ф(π ( R H ) − π ( R M )) . Действительно, ввиду
взаимной
однозначности
соответствия
справедливо
равенство
π,
π (R H -­‐ R M ) = π (R H ) − π (R M ) , и, с учетом свойств изоморфных матроидов,
если цикл D∈R H -­‐ R M , то цикл π ( D) ∈π (R H ) -­‐ π (R M ) . Поскольку для
изоморфных матроидов каждой флате A∈ℑM однозначно соответствует флата
π ( A) ∈ℑπ ( M ) , то из вышесказанного следует, что если фильтр ФM - модулярный
фильтр матроида M , то фильтр Фπ ( M ) также является модулярным фильтром
матроида π ( M ) . Таким образом, мы получаем следующий результат.
Утверждение 3. Пусть матроиды M , H ∈M ( S ) и матроид H –
элементарный фактор матроида M . Тогда в любом изоморфном матроиду M
матроиде π ( M ) всегда найдется элементарный фактор π ( H ) , изоморфный
матроиду H .
МАТЕМАТИЧЕСКИЕ НАУКИ
Таким образом, если для любого матроида M ∈M ( S ) можно было бы
отличным от перебора методом построить цикловую структуру всех его элементарных
факторов, то с помощью описанного выше алгоритма можно было бы построить, а
значит, и перечислить все неизоморфные матроиды заданного ранга в множестве
M ( S ) . В работе [2] было отмечено, что такой процедуры в общем случае не
существует, как не существует и отличного от реализации метода перебора алгоритма
построения всех лифтов произвольного матроида. Далее мы покажем, что конкретно
для бинарных матроидов данная проблема разрешима как для лифтов, так и для
элементарных факторов матроидов из множества N ( S ) . Более того, с помощью G факторизации можно, используя описанный выше алгоритм, построить цикловую
структуру всех бинарных матроидов и, следовательно, всех неизоморфных матроидов
из множества N ( S ) .
Для любых бинарных матроидов
G -фактором матроида M
матроида H .
(см. [3]),
M , H ∈N ( S ), если матроид H является
то матроид M будем называть G -лифтом
Напомним, что любым матроиду N ∈M ( S ) и базе
соответствует семейство фундаментальных циклов вида
C N ( B) = {CN (b* , B) ∈ R
B ∈B
N
однозначно
b* ∈ S − B}.
N
(6)
Рассмотрим схему вида
M
b
Ф
⎯⎯
→
Ф*
M * ←⎯
⎯
где
и
M , H ∈N ( S )
матроиды
M * , H * ∈N ( S )
–
бинарные
и
H
b
,
(7)
H*
и
связаны
дуальные
к
элементарными
ним
матроиды
отображениями,
ФM и ФH* * .
B0 ∈B H , подмножества
порожденными соответствующими модулярными фильтрами
Теорема 1. В условиях схемы (7) для любых базы
D0* ⊆ B0* = S − B0 ∈B
ФH* * = Ф( FH * ( D0* )) ,
H*
,
такого,
и элемента
что
d 0* ∈ D0*
модулярный
множество
фильтр
B0 + d 0* ∈B
M
, и
соответствующее семейство фундаментальных циклов имеет вид
C M ( B0 + d0* ) = {CH (b* , B0 ) ∈ R
*
*
0
*
*
H
b* ∈ B − D0*} +
0
*
(8)
*
0
+{CH (b , B0 ) ⊕ CH (d , B0 ) b ∈ D − d }.
0
Ученые записки: электронный научный журнал Курского государственного университета. 2011. № 2 (18)
Гизунов С. А. Неизоморфные бинарные матроиды
Доказательство.
Рассмотрим
*
C H ( B0 ) = {CH (b , B0 ) ∈ R
*
H
семейство
*
0
b ∈B }
фундаментальных
матроида
H ∈N ( S ) .
циклов
Так как, по
M * является G -фактором матроида H * и
= Ф( FH * ( D0* )) , где подмножество D0* ⊆ B0* , то
предположению, в схеме (7) матроид
модулярный фильтр
ФH* *
СH (b* , B0 ) ∩ D0* = 1,
если
b* ∈ D0* ,
и
СH (b* , B0 ) ∩ D0* = 0 ,
если
b* ∈ B0* − D0* . В условиях утверждения и согласно теореме 5[4] матроид
M ∈N ( S ) является в схеме (7) G -лифтом матроида H ∈N ( S ) , и из теоремы
*
*
*
*
3[4] получаем, что CH (b , B0 ) ∈ F M , если b ∈ D0 , и CH (b , B0 ) ∈ R M ∩ R H ,
*
*
*
*
а значит, и CH (b , B0 ) ∈R M , если b ∈ B0 − D0 , что соответствует первому
слагаемому в (8).
CH (d 0* , B0 ) ∈ F M для любого элемента d 0* ∈ D0* .
*
*
А так как d 0 ∉ B0 , то и множество B0 + d 0 ∈ F M , а поскольку
rM ( S ) = rH ( S ) + 1, то множество B0 + d 0* ∈B M . Пусть элемент d * ∈ D0* − d 0* .
Тогда в матроиде M
существует единственный фундаментальный цикл
*
*
CM (d , B0 + d 0 ) для элемента d * в базе B0 + d 0*. При этом обязательно
d 0* ∈ CM (d * , B0 + d 0* ) , ибо в противном случае имеет место равенство
CM (d * , B0 + d 0* ) = CH (d * , B0 ) , что противоречит условию CH (d * , B0 ) ∈ F M .
*
*
Так как циклы CH ( d , B0 ), CH ( d 0 , B0 ) ∈C H ( B0 ) , то либо двоичная сумма
CH (d 0* , B0 ) ⊕ CH (d * , B0 ) ∈ R H , либо CH (d 0* , B0 ) ∩ CH (d * , B0 ) = ∅ и
CH (d 0* , B0 ) ⊕ CH (d * , B0 ) = CH (d 0* , B0 ) + CH (d * , B0 ) . В любом случае
Отсюда также следует, что
(CH (d 0* , B0 ) ⊕ CH (d * , B0 )) ∩ D0* = 2.
Следовательно,
в
соответствии
с
теоремой 3 [4], учитывая единственность фундаментальных циклов, либо цикл
CM (d * , B0 + d 0* ) = CH (d 0* , B0 ) ⊕ CH (d * , B0 ) ∈ R M ∩ R H ,
CM (d * , B0 + d 0* ) = CH (d 0* , B0 ) + CH (d * , B0 ) ∈ R M − R H ∩ R
либо
M
W
Из теоремы 1 и полученных в [4] результатов, таким образом, следует, что для
бинарных матроидов, в отличие от общего случая, можно отличным от метода
перебора конструктивным образом построить цикловую структуру всех G -лифтов
бинарных матроидов из множества N ( S ) .
Результаты подсчета количества неизоморфных матроидов, полученные методом
перебора, известны для небольших значений параметра n , n ≅ 10 (см., например, [5]).
МАТЕМАТИЧЕСКИЕ НАУКИ
Исходя из этих подсчетов, количество неизоморфных бинарных матроидов ранга
⎛ ⎛ n ⎞ ⎞
n − k можно оценить величиной O ⎜ ⎜ ⎟ ⎟ .
k
⎝ ⎝ ⎠ ⎠
Теорема 2. Для построения всех неизоморфных бинарных матроидов из
множества N ( S ) существует основанный на процедуре G -факторизации алгоритм
трудоемкостью
3
O ( S 3 S ) арифметических операций.
Доказательство. Рассмотрим бинарный матроид
факторизацию канонического отображения
B( S ) → M
M ∈N
S −k
(S )
G-
и
вида
Фk
Ф1
Ф2
B( S ) = M 0 ⎯⎯
→ M 1 ⎯⎯
→ ...M k −1 ⎯⎯
→ Mk = M .
Пусть
S = {1,2,..., n}.
(9)
Для построения всех неизоморфных матроидов
Mk
ранга n − k с использованием процедуры G -факторизации вида (9) опишем
алгоритм, состоящий из следующих этапов.
1) Для каждого матроида M k −1 из массива неизоморфных матроидов ранга
2 n − k +1 − 1
Dk ⊆ B , где база B ∈B M k −1 , и
строятся цикловые структуры матроидов M k , как G -факторов неизоморфных
матроидов M k −1, порожденных модулярными фильтрами Ф ( FM ( Dk )) .
k −1
2) По цикловой структуре G -фактора M k , в свою очередь, строится семейство
векторов
вычисляются
значения
параметров
{ΩM k (a ) a ∈ S} и
|R M k ( r ) |,1 ≤ r ≤ n − k + 1.
n − k +1
задается
подмножеств
3) Полученные на этапе 2 значения параметров сравниваются с уже
имеющимися соответствующими значениями параметров для ранее построенных
неизоморфных G -факторов M k . В случае их несовпадения цикловая структура, а
также соответствующее семейство векторов {Ω M
(a ) a ∈ S} вместе с упомянутыми
выше значениями параметров добавляются в массив неизоморфных G -факторов M k .
k
4) Если на этапе 3 значения параметров совпадают, то используется описанный
выше алгоритм проверки на изоморфизм для всех m, 2 ≤ m ≤ n − k + 1. Если на
каком-либо этапе алгоритма построений матроид
Mk
не считается изоморфным, то
процедура записи в массив неизоморфных G -факторов повторяется.
Согласно утверждениям 2 и 3, в результате работы такого алгоритма будут
построены все неизоморфные бинарные матроиды M k ранга n − k .
Основная трудоемкость алгоритма сосредоточена на этапе 4, который связан со
сравнением
(n − k + 1)
чисел для проверки соответствующих векторов
эквивалентность. Ранее отмечалось, что чем больше
m,
Ω(Mmk)
на
тем меньше подмножеств
Ученые записки: электронный научный журнал Курского государственного университета. 2011. № 2 (18)
Гизунов С. А. Неизоморфные бинарные матроиды
A ∈ S (m) , принадлежащих соответствующим классам разбиений, для которых
(m)
вектора Ω M не нулевые. Поскольку для m = 2 количество проверок на этапе 4) не
k
⎛ n ⎞ ⎛ n + 1⎞
n + ⎜ ⎟ = ⎜
⎟ , то количество упомянутых сравнений можно
2
2
⎝ ⎠ ⎝
⎠
2
оценить величиной O ( n ) .
больше величины
Таким образом, если предположить, что этап 4 выполняется для всех
неизоморфных матроидов M k −1, то общая трудоемкость при построении всех
мощности
S = n,
S
⎛
⎛ n ⎞ n −k +1 ⎞
O ⎜ n 2 (n − k + 1) ⎜
⎟ .
⎟ 2
k
−
1
⎝
⎠
⎝
⎠
n − k,
неизоморфных бинарных матроидов ранга
не превышает величины
определенных на множестве
Соответственно, трудоемкость построения всех неизоморфных бинарных матроидов из
множества
3
S
N ( S ) оценивается величиной O( S 3 ) . W
Эта оценка позволяет сделать вывод о том, что с помощью основанного на
процедуре G -факторизации канонических отображений алгоритма можно построить в
явном виде цикловую структуру всех неизоморфных бинарных матроидов из
множества N ( S ) для множества S достаточно большой мощности. Подчеркнем, что
проблема построения всех неизоморфных матроидов, в том числе и всех неизоморфных
бинарных матроидов для значений параметра n > 10 , считается, согласно
дополнению к переизданной в 2006 году монографии Оксли [5], нерешенной. Известно
только, что при n → ∞ количество неизоморфных бинарных матроидов стремится к
величине
1 n
N k (S ) ,
∑
n ! k =0
N k (S )
где
- число бинарных матроидов ранга
k,
подсчитанное по формуле (5) [4].
Ниже приведены результаты подсчета по описанному выше алгоритму
количества всех неизоморфных бинарных матроидов из множества N ( S ) для
| S | = n и n ≤ 14 .
k /n 1 2 3 4
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
1
1
2
1
1
3
3
1
1
4
6
4
1
5
6
7
8
9
10
11
12
13
14
1
5
10
10
5
1
1
6
16
22
16
6
1
1
7
23
43
43
23
7
1
1
8
32
77
106
77
32
8
1
1
9
43
131
240
240
131
43
9
1
1
10
56
213
516
705
516
213
56
10
1
1
11
71
333
1060
1988
1988
1060
333
71
11
1
1
12
89
507
2108
5468
7664
5468
2108
507
89
12
1
1
13
109
751
4064
14724
29765
29765
14724
4064
751
109
13
1
1
14
132
1088
7641
39006
117169
173035
117169
39006
7641
1088
132
14
1
МАТЕМАТИЧЕСКИЕ НАУКИ
Всего
2
4
8
16
32
68
148
342
848
2297
6928
24034
98854
503137
Заметим, что поскольку матроид дуальный к бинарному матроиду также
бинарен, то количество в том числе и неизоморфных матроидов рангов k и n − k в
множестве N ( S ) должно совпадать. Вместе с тем подчеркнем, что описанный выше
алгоритм последовательно строит неизоморфные матроиды
Mk
ранга
n − k по
n − k + 1,
построенным ранее неизоморфным матроидам
M k −1 ранга
безотносительно к их возможной дуальности к уже построенным матроидам. Другими
словами, совпадение в приведенной таблице соответствующих значений является
дополнительной проверкой корректности реализации данного алгоритма.
Библиографический список
1. Гизунов С. А., Лямин В. Н. Сечения матроидов // Ученые записки: электронный
журнал Курского государственного университета. 2010. № 2. URL: http://scientificnotes.ru/pdf/014-2.pdf (дата обращения: 13.03.2011).
2. Гизунов С. А., Лямин В. Н. Псевдоматроиды, порожденные отображениями
матроидов.
3. Гизунов С. А., Лямин В. Н. Полуматроиды, порожденные G -отображениями
бинарных матроидов.
4. Гизунов С. А., Гречкин А. О., Лямин В. Н. G-факторизация канонических
отображений.
5. Oxley J. G. Matroid Theory. N.Y.: Oxford Univ. Press, 1992. 532 p.
Ученые записки: электронный научный журнал Курского государственного университета. 2011. № 2 (18)
Документ
Категория
Без категории
Просмотров
3
Размер файла
4 927 Кб
Теги
бинарных, матроид, неизоморфные
1/--страниц
Пожаловаться на содержимое документа