Уральский государственный университет путей сообщения (Екатеринбург) Работа посвящена исследованию однородных матроидов, т.е. таких, которые имеют циклы одинаковой мощности. Рассмотрены некоторые плоскости таких матроидов. Установлена их связь с блоксхемами. Дано частичное описание матроидов коранга три, а так же поставлены задачи для дальнейшего исследования. Ключевые слова: однородные структуры доступа; схемы разделения секрета; матроиды; циклы.
3
Некоторые свойства однородных матроидов В представленном ниже подходе к описанию однородных матроидов большую роль играют арифметические соотношения между параметрами характеризующих его объектов.
Пусть M = (E; C) – связный разделяющий матроид на множестве E с семейством циклов C. Пусть N = jEj > n, и пусть M – однородный, т.е. все его циклы C имеют мощность n:
C 2 C ) jCj = n: Если a; b 2 E, a 6= b, то, в силу того, что M – разделяющий, существует цикл C0 такой, что a 2 C0, b 2= C0. В силу того, что M – связный, существуют такие два цикла C1, C2, что C1 6= C2, b 2 C1, b 2 C2 и Поскольку имеем
jDe(C1; C2)j = j(C1 [ C2) n Je(C1; C2)j ¸ j(C1 [ C2) n (C1 \ C2)j = jC1 © C2j: Следовательно, De(C1; C2) может быть минимальным по включению (и, значит, циклом) только если n = jDe(C1; C2)j ¸ jC1 © C2j.
Пусть F – максимальное по включению подмножество в E, в котором каждое n-элементное подмножество является циклом. Можно считать, что jF j ¸ n.
Утверждение 2. Множество F является подпространством матроида M .
Доказательство. От противного, если F не замкнуто, то существует e 2 E n F , лежащий в замыкании
F , т.е. существует такой цикл C1, что feg = C1 n F . Возьмем любой элемент d 2 F n C1. Тогда C2 =
fdg[(C1\F ) ½ F , и, поскольку jC2j = n, то по предположению C2 является циклом. Значит, C1©C2 = fe; dg,
и поэтому любое n-элементное подмножество в fe; dg [ (C1 \ C2) является циклом, т.е. любой элемент x
Из (
C0 = Db(C1; C2) = (C1 [ C2) n Jb(C1; C2); Jb(C1; C2) = \fC : b 2 C ½ (C1 [ C2)g:
C0 = (C1 \ C0) [ (C2 \ C0):
(
Утверждение 1. В связном разделяющем однородном матроиде для любых двух различных элементов a; b и любого цикла C, содержащего a, но не содержащего b, существует цикл C0, содержащий b и такой, что Пусть e 2 E – любой элемент и C1 6= C2 – два содержащих его различных цикла. Согласно определению jC \ C0j ¸ dn=2e = bn + 1=2c: Je(C1; C2) = \fC : e 2 C ½ (C1 [ C2)g:
Je(C1; C2) ½ (C1 \ C2); в C1 n feg можно заменить на любой элемент d 2 F n C1, и при этом множество feg [ (C1 n fxg) [ fdg также будет циклом. Отсюда вытекает, что любое n-элементное подмножество в feg [ F есть цикл, что противоречит максимальности F .
Поскольку M – не пороговый (не равномерный), то F 6= E. Для каждого a 2 E n F обозначим через k(a) минимальную мощность множества C0 nF по всем таким циклам C0 2 C, что a 2 C0. Согласно утверждению 1 имеем
k(a) · n ¡ dn=2e Поскольку F – подпространство матроида, имеем 1 < k(a).
Пусть k – минимальное такое число, т.е. k = min k(a); a 2 E n F . Из предыдущего ясно, что 2 · k · n ¡ dn=2e. Если k(a1) = k, т.е. на элементе a1 2 E n F этот минимум достигается, то существует такой цикл C0, что C0 n F = fa1; :::; akg, jC0 n F j = k. По утверждению 1 имеем C0 \ F 6= ®. Дополняя это множество C0 \ F до подмножества C ½ F мощности n, можем считать C0 = fa1; :::; ak; f1; :::; fn¡kg, C = ff1; :::; fn¡k; :::; fng 2 C. Поскольку никакое подмножество в fa1; :::; akg мощности (k ¡ 1) не равно (C00 n F ) ни для какого C00 2 C, то любое такое подмножество вместе с любым (n ¡ 1)-элементным подмножеством в F является независимым и, следовательно, есть база некоторого подпространства F 0. Ясно, что F ½ F 0 и rankF 0 = (k ¡ 1) + (n ¡ 1) = n + k ¡ 2. Следовательно, в любом (n ¡ 1)-элементном подмножестве множества F существует единственное его (n ¡ k)-элементное подмножество D такое, что fa1; a2; :::; akg [ D – цикл (достаточно для этого в базу F 0 включить элементы a2; :::; ak). Введем во множестве C = ff1; :::; fng ½ F следующее бинарное отношение: u ´ v тогда и только тогда, когда в C n fug и в C n fvg такое подмножество D одно и то же. Легко проверяется рефлексивность, симметричность и транзитивность этого отношения, т.е. это – отношение эквивалентности. Соответствующее ему разбиение множества C имеет, очевидно, одинаковые мощности классов эквивалентности, а именно n ¡ (n ¡ k) = k, т.к. мощность каждого такого D равна (n ¡ k).
Следовательно, fa1; :::; akg задает разбиение любого n-элементного подмножества C ½ F на kэлементные подмножества, дополнение каждого из которых до C, объединенное с fa1; :::; akg, есть цикл. Отсюда вытекает Утверждение 3. Мощность циклов n делится на k. Теперь допустим, что jF j ¸ n + 1. Взяв G ½ F , jGj = n + 1, видим, что A [_B есть база в F 0, где A – любое такое подмножество в fa1; :::; akg, что jAj = k ¡ 1; B – любое такое подмножество в G, что jBj = n ¡ 1; [_ – обозначает объединение непересекающихся множеств.
Следовательно, для любых двух различных элементов x; y 2 G, x 6= y, существует единственный цикл Cxy = fa1; :::; akg[_ Dxy, где Dxy ½ G n fx; yg = Bxy, jDxyj = n ¡ k.
Рассмотрим случай минимального значения k = 2. По утверждению 3 в этом случае n четно. Здесь
jDxyj = n ¡ k = n ¡ 2, так что Dxy получается удалением из G еще одного, кроме x и y, однозначно
определенного по ним элемента z:
(
2. В силу единственности Dxy каждая пара x; y различных элементов содержится точно в одной тройке (¸ = 1).
3. Более того, для разных x1 6= x2 ни один смежный класс разбиения множества G n fx1g не совпадает ни с одним смежным классом разбиения множества G n fx2g, т.к. иначе имелись бы два цикла C1 и C2 с C1 © C2 = fx1; x2g, откуда вытекало бы, что каждое n-элементное подмножество в C1 [ C2 – есть цикл, в том числе циклы C0 и C00 такие, что C0 n F = fa1g, C00 n F = fa2g что противоречит замкнутости F . Следовательно, число таких троек равно n(3n+21) .
Из этих свойств вытекает, что полученное¢ семейство троек образует блок-схему [10] с параметрами: (n + 1) – количество элементов; (n+1)n – количество блоков (троек);
6 3 – количество элементов в блоке (в тройке); r = n2 – количество блоков (троек), содержащий любой данный элемент; ¸ = 1 – каждая пара различных элементов содержится точно в одном блоке (в тройке). Итак, получаем блок-схему D(n + 1; (n+1)n ; n2 ; 3; 1) (см. раздел 15.4 в [10]), т.е. систему троек Штейнера.
6 Такие тройки существуют, как известно, при n ´ 0(mod 6) или n ´ 2(mod 6). Таким образом, однородные матроиды оказываются связанными с блок-схемами. 4
Обобщение конструкции В [11] дано описание однородных матроидов коранга три. При этом утверждение доказано в не явном предположении, что существует не более одной линии, проходящей через точку b, не лежащей на данной линии, и не пересекающейся с ней. Ниже дано уточненное изложение этого вопроса.
Определение линии bc: x 2 bc тогда и только тогда, когда во всех циклах, не содержащих ни b, ни c, нет и x.
Рассмотрим матроид, в котором любой цикл содержит элементы либо a, либо b, либо c, либо пару их, либо все три. (Значит, fa; b; cg – кобаза). Из непороговости вытекает, что мощность m антициклов ¸ 3.
Пусть A1, A2 – циклы, такие, что a 2 A1, a 2 A2 (b 2= Ai, c 2= Ai), где (i = 1; 2). Тогда если A1 6= A2, то в (A1 [ A2) n fag есть цикл A, причем a 2= A, b 2= A, c 2= A (противоречие с вышеописанным предположением). Следовательно, существует единственный цикл A такой что a 2 A, b 2= A, c 2= A. Аналогично – для элементов b, c матроида M и циклов B, C. Если a1, a2 таковы, что не существуют циклов, не содержащих fa1; b; cg или fa2; b; cg, то Ai (i = 1; 2) – единственный цикл, такой, что ai 2 Ai, b 2= Ai, c 2= Ai (i = 1; 2). Если A1 \ A2 6= ®, то при A1 6= A2 эта единственность нарушается для любого a 2 A1 \ A2 по второй аксиоме циклов. Если же A1 \ A2 = ®, то цикл A1 не содержит fa2; b; cg, и A2 не содержит fa1; b; cg вопреки предположению. Итак, существует единственный цикл A, не содержащий ни b, ни c, и поэтому можно определить лишь bc = A.
Поэтому bc = A, т.е. для каждой линии (вне которой есть хотя бы одна точка) существует единственный цикл, дополнением которой он является.
Утверждение 6. Вне каждой линии есть точка. Доказательство: В противном случае не существовали бы три точки a, b, c.
Предположим, как было указано выше, что для любой точкивне любой данной линии, существует не более одной линии, содержащей эту точку и не пересекающейся с данной линией.
Следствие 1. N = jM j = n + jbcj для любых точек b 6= c и определяемой ими линии bc. Следствие 2. Если w 2 uv, u 6= v 6= w 6= u, то u 2 vw, v 2 uw, как дополнение единственного цикла. Итак, циклов (и антициклов) всего
CN2 CN2¡n =
N (N ¡ 1) (N ¡ n)(N ¡ n ¡ 1) : Пусть m = N ¡ n есть мощность антициклов, т.е. количество точек на каждой линии. Тогда пары точек u 6= v и a 6= b определяет одну и ту же линию, когда они обе ей принадлежат, и таких пар на линии всего Cm2. А всего пар различных элементов матроида – CN2 . Поэтому количество всех линий как антициклов равно
CCNm22 =
N (N ¡ 1) = m(m ¡ 1)
N (N ¡ 1) (N ¡ n)(N ¡ n ¡ 1) : Зафиксируем точку b и линию ac, b 2= ac. Тогда, поскольку для каждой точки x на линии ac получаем (m ¡ 1) точку на линии bx (кроме b), итого получаем (поскольку все эти линии разные для разных x, т.к. иначе было бы b 2 ac = x1x2) всего m(m ¡ 1) + 1 точек. Если этими точками исчерпываются все элементы матроида, то N = m2 ¡ m + 1, и линий всего (m2 ¡ m + 1)(m2 ¡ m) m(m ¡ 1) = m2 ¡ m + 1 ("проективный случай" проективная плоскость порядка (m ¡ 1)).
Итого получаем N = [m(m ¡ 1) + 1] + (m ¡ 1) = (m + 1)(m ¡ 1) + 1 = (m2 ¡ 1) + 1 = m2 ("аффинный случай" – аффинная плоскость порядка m), а линий всего
N (N ¡ 1) = m(m ¡ 1) m2(m2 ¡ 1) m(m ¡ 1) = m(m + 1): Случай 1. Далее произведем проверку аксиом проективной плоскости, взяв линии в качестве прямых. Аксиома 1. Две различные точки определяют единственную прямую. Доказательство следует из разделимости матроида. Аксиома 2. Две прямые пересекаются в единственной точке.
Пусть однородный матроид M мощности jM j = N = m2 ¡ m + 1, где m – мощность линий (антициклов), и a, b, c – его элементы, не содержащиеся в одном антицикле. По описанному выше построению все точки (элементы матроида) исчерпываются точками линий, соединяющих точку b с точками ac.
Пусть L1 = C1, L2 = C2 – две разные линии, дополнения циклов C1 и C2, C1 6= C2. Ясно, что если линии пересекутся в двух или более точках, то они совпадут (см. первую аксиому плоскости). Если же они не пересекутся, L1 \ L2 = ®, то C1 [ C2 = M .
Пусть w 2 M – любой элемент, C – цикл, содержащий w. Тогда линия L = C не проходит через w и содержит m точек. Линии, проходящие через w и через различные точки линии L, различны, и их всего m штук. Точек на всех этих линиях, как было вычислено выше, всего N = m2 ¡ m + 1. Следовательно, этими точками исчерпываются все элементы матроида, и других линий, проходящих через w, больше нет. Итак, доказано: Утверждение 7. Через любую точку w проходят ровно m линий. Всего пар различных линий
CN2 =
N (N ¡ 1)
2
=
(m2 ¡ m + 1)(m2 ¡ m)
2
=
(m2 ¡ m + 1)m(m ¡ 1)
2
:
щенные идеальные схемы, разделяющие секрет, и матроиды. Проблемы передачи информации,
33(
About secret sharing schemes and homogeneous matroids
Ural State University of Railway Transport (Yekaterinburg, Russia)
Ural State University of Railway Transport (Yekaterinburg, Russia)
Abstract. This research is devoted to homogeneous matroids, which have equal power of circuits. Some flats of such matroids are considered, as well as their connection with block-schemes. A partial description of homogeneous matroids of corank three is given. The authors set tasks for further research.
Keywords: homogeneous access structure, secret sharing schemes, matroids, circuits.