Об однородных матроидах, соответствующих блок-схемам | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/2

Об однородных матроидах, соответствующих блок-схемам

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

On homogeneous matroids corresponding to block-schemes.pdf На множестве M определён матроид, если некоторые его подмножества названы независимыми (остальные - зависимыми), причём удовлетворяются аксиомы матрои-да; так, в терминах циклов - минимальных (по включению) зависимых подмножеств из M - аксиом всего две: 1) нет цикла в цикле, т.е. если C, D - циклы и C С D, то C = D; 2) если C1 = C2 - циклы и x Е C1 П C2, то C1 U C2 \\ {x} содержит цикл [1-4]. Матроид называется связным, если для любых двух его элементов существует содержащий их цикл. Простым (или комбинаторной геометрией) называется матроид, в котором нет одноэлементных и двухэлементных циклов. Под однородностью матро-ида понимается одинаковость мощностей его циклов, равная n, где, возможно, не все n-элементные множества - циклы. При этом если все n-элементные подмножества - циклы, то такой матроид называется пороговым (равномерным) [5]. Матроид является разделяющим тогда и только тогда, когда для любых x = y существует разделяющий их цикл C, т. е. x Е C, y Е C. Любое максимальное независимое подмножество B, содержащееся в M, называется базой матроида M; дополнение цикла матроида - ко-гиперплоскостью C = M \\ C. Блок-схема D(v, b, r, k, A), согласно [6], - такое размещение v различных элементов по b блокам, что каждый блок содержит точно k различных элементов, каждый элемент появляется точно в r различных блоках и каждая пара различных элементов появляется в A блоках. Блок-схема с k = 3 вполне естественно называется системой троек. При этом параметры должны удовлетворять аксиомам 3b = rv, 2r = A(v - 1). Система троек с A =1 называется системой троек Штейнера. Условие v = 1, 3 (mod 6) необходимо и достаточно для существования штейнеровской системы троек. Утверждение 1. Если каждый цикл однородного разделяющего связного матроида является его гиперплоскостью, то ему соответствует блок-схема. Доказательство. Пусть M = (E, C) - связный разделяющий однородный мат-роид с мощностью n ^ 4 циклов C G C, такой, что n* = |E| - |C| = |E| - n = 4. Для каждой когиперплоскости H*, т.е. гиперплоскости двойственного матроида M* = (E,H*), имеем |H*| = |E \\ C| = 4, H* G H*. Пусть H* G H*, H2* G H*, H* = H2*. Предположим, что пересечение любых различных гиперплоскостей матроида M* не более чем одноэлементно. Пусть H* П H* = {e}, d G H* U H* (отметим, что ввиду n ^ 4, n* = 4, |E| = n + n* ^ 8 такой элемент d существует), тогда по второй аксиоме гиперплоскостей существует гиперплоскость H* G H*, такая, что {e,d} С H*. По предположению H* П H* = {e} = H* П H2*. В силу разделимости матроида M каждый его элемент e принадлежит не менее чем двум когиперплоскостям. В самом деле: если a = e, то существует такой цикл Ca, что a G Ca и e G Ca, т.е. e G Ha* = E \\ Ca; взяв b = e, b G H, найдём цикл Cb, такой, что b G Cb, e G Cb, т. е. e G H* = E \\ Cb, причём H* = H*, так как b G H*, но b G H*. Ввиду произвольности элемента d, в силу предположения получаем разбиение множества E \\ {e} множествами H* \\ {e}. Поскольку в качестве e можно взять любой элемент множества E, получаем блок-схему с параметрами v = |E|, k = n* = 4, A = 1, v - 1 v - 1 vr v(v - 1) r = ^^-г = -, b = - = -. Итак, в этом случае получаем систему A(k - 1) 3 k 12 четвёрок Штейнера. Каждая пара различных элементов в M* независима, так как M* простой, и поэтому существует единственная содержащая эту пару гиперплоскость H*. Следовательно, ранг гиперплоскостей в M* равен двум, а любое трёхэлементное множество - либо цикл, если оно входит в некоторую четвёрку, либо база, если не входит ни в какую четвёрку. Значит, ранг r* матроида M* равен трём. Предположим, что пересечение любых двух различных гиперплоскостей матрои-да M * не более чем двухэлементно. Пусть H* П H2 = {e, f}, e = f .В силу связности матроида M для любых двух различных его элементов e и f существует содержащий их цикл C. Поскольку M - связный и разделяющий, то M* простой; значит, {e,f} - независимое множество в M* и его можно дополнить до гиперплоскости H* = E \\ Ci, где C1 - цикл в M. Пусть b G H*, тогда {e, f, b} -независимое множество в M* и его можно дополнить до гиперплоскости H2 = H*, только если ранг гиперплоскостей равен трём. Следовательно, ранг M* равен четырём. Допустим, что {a, b, c} - трёхэлементный цикл. Тогда он лежит в плоскости ранга два (так как M* простой), которая должна быть пересечением гиперплоскостей, что противоречит предположению. Значит, все трёхэлементные подмножества независимы и каждое из них является базой единственной (в силу предположения) гиперплоскости в M*, которая сама поэтому представляет собой цикл. Отсюда каждое четырёхэлементное подмножество - либо цикл в M*, если оно является четвёркой (т. е. гиперплоскостью в M*), либо база в M*, если не является. Поэтому каждое пятиэлементное подмножество зависимо (и само является циклом, если не содержит четвёрку). Предположим, что имеется пересечение двух гиперплоскостей матроида M* по трёхэлементному множеству, |H* П H*| = 3. Тогда для C = E \\ Hi* (i = 1, 2) имеем |Ci ф C2| = 2 и поэтому каждое n-элементное подмножество (n + 1)-элементного множества F = (C1 U C2) является циклом. Если F не замкнуто (т. е. не является плоскостью матроида M), то существует a Е E \\ F и цикл C Е C, такой, что C \\ F = {a}, но тогда, очевидно, и в множестве {a} U F каждое n-элементное подмножество является циклом. Обозначим {a, b, с} = E \\ F; в силу разделимости матроида M существует цикл, содержащий b, но не содержащий с, однако тогда и в множестве {a, b}U F каждое n-элементное подмножество - цикл. В силу связности матроида M найдётся цикл, соединяющий оставшийся элемент с с множеством {a, b} U F, откуда замыкание множества F совпадает с носителем E матроида M, причём каждое n-элементное его подмножество есть цикл, а это означает равномерность матроида M. Для того чтобы матроид M не был равномерным, необходимо, чтобы F было его плоскостью. Однако в силу разделимости матроида M существует цикл Ca, такой, что a Е Ca, b Е Ca. Ввиду замкнутости F необходимо с Е Ca; аналогично - найдётся цикл C'a, такой, что a Е C'a, с Е C'a, но b Е C'a. Это означает, что F - гиперплоскость матроида M, и поэтому E \\ F есть цикл двойственного матроида M*. Значит, цикл {a, b, с} есть плоскость (как пересечение гиперплоскостей) в M* ранга два (так как M* простой) и поэтому гиперплоскости матроида M* имеют ранг равный трём. Пусть {bi, b2, b3} - база произвольной гиперплоскости H*, не являющейся циклом матроида M. Поскольку |H*| = 4, имеется единственный цикл, скажем, {b1, b2, h}, при H* = {b1, b2, b3, h}. Однако тогда для любого элемента x Е E, x Е H* имеем: множества {b1,b2,x}, {b1,b3,x}, {b2,b3,x} независимы, так как множество {b1,b2,b3,x} независимо и поэтому является базой матроида M*. Зафиксируем x = bo. Тогда для любого у Е {b0,b1,b2,b3} = B* найдётся единственный цикл C*, такой, что C* \\ B* = {у}, и при у = h необходимо b0 Е C*. Поскольку мощность гиперплоскости матроида M не может быть меньше n, если он не равномерный, то мощность её дополнения не может быть больше четырёх. Отсюда |C*| ^ 4, в случае равенства C* -гиперплоскость матроида M* и поэтому его дополнение - цикл матроида M, являющийся также и его гиперплоскостью. ■ Утверждение 2. Если матроид связный и разделяющий, то двойственный ему матроид простой. Доказательство. Пусть матроид M = (E, C) связный, |E| ^ 2; тогда двойственный матроид M* = (E, H*) не имеет одноэлементных циклов. Действительно: если {e} -цикл в M* (т.е. коцикл в M), то H = E \\ {e} = 0 - гиперплоскость в M. Однако для любого h Е H существует, ввиду связности, цикл C, содержащий и e, и h. При этом |C| > 1, |C \\ H| = |{e}| = 1, откуда e принадлежит гиперплоскости H - противоречие. Пусть матроид M разделяющий, |E| ^ 3. Тогда M* не имеет двухэлементных циклов. Действительно: если {e, f} -двухэлементный цикл в M*, то H = E\\{e,f} = 0 - гиперплоскость в M. В силу того, что M разделяющий, существует цикл, содержащий e, но не содержащий f, и существует цикл, содержащий f, но не содержащий е. Эти циклы не могут быть одноэлементными, т. е. {е} и {f}, по первой аксиоме циклов. Следовательно, существует цикл C, такой, что |C| > 1 и, без ограничения общности, е £ C, f £ C. Но тогда |C\\H| = |{е}| = 1, откуда е принадлежит гиперплоскости H - противоречие. ■ Таким образом, вариантом однородного неравномерного матроида, которому не соответствует блок-схема, может быть только реализация случая с возможностью пересечения его когиперплоскостей по трёхэлементному множеству. Утверждение 3. Однородный связный разделяющий матроид с мощностью циклов n = 5 является равномерным. Доказательство. Пусть M = (E, C); при |E| = 5 матроид не разделяющий, а при |E| = 6 он, очевидно, равномерный, так как тогда любые два различных цикла пересекаются по четырёхэлементному множеству и поэтому любое пятиэлементное подмножество их объединения, равного E, является циклом. Аналогично при |E| = 7: если E = {a,b} U C, где C - цикл, не содержащий ни а, ни b, то в силу разделимости существует цикл Ci, содержащий а, но не содержащий b, и тогда |Ci П C| = 4, откуда во множестве {а} U C каждое пятиэлементное подмножество есть цикл. В силу связности существующий цикл, содержащий {а,Ь}, пересекается с любым циклом, содержащим b, но не содержащим а, по четырёхэлементному множеству, откуда вытекает равномерность матроида M. Эти же рассуждения применимы при | E| = 8. Пусть теперь |E | ^ 9, е £ E - произвольный элемент матроида, D £ C - произвольный его цикл, не содержащий е. Тогда в силу связности этот цикл может быть представлен в виде D = (Ci U C2) \\ Je(Cl,C12), где Ci, C2 -циклы, содержащие е, Je(Ci, C2) = П{C : е £ C С (Ci U C2)}. Допустим, существует такой цикл D, что нет циклов, содержащих е и не пересекающихся с D по четырёхэлементному множеству. Отсюда |Ci П C2| < 4, и из |D| = |Ci| = |C2| = n = 5 вытекает, что |Ci П C2| > |Je(Ci,C2)| ^ 2. Поэтому |Ci П C21 = 3, |Je(Ci,C2)| = 2. Пусть Je(Ci, C2) = {е, f}, Ci П C2 = {е, f, g}. Тогда D = (Ci 0C2) U{g} и существует такой цикл C С (CiUC2), что {е, f} С C, g £ C. Отсюда следует, что |(Ci®C2)ПC| = 3. Однако тогда либо |Ci П C| = 4, либо |C2 П C| = 4. Пусть, без ограничения общности, |CiПC| = 4. Тогда в шестиэлементном множестве (Ci U C) каждое пятиэлементное множество есть цикл, в том числе C = (D П (Ci U U C)) U {е}. Однако ясно, что |C' П D| = 4 вопреки предположению о D и е. Итак, от противного утверждение доказано. ■ Представленный подход может быть применён к решению более сложных задач обобщения связи блок-схем и однородных матроидов.

Ключевые слова

однородные матроиды, схемы разделения секрета, блок-схемы, циклы, homogeneous matroids, secret sharing schemes, block-schemes, cycles

Авторы

ФИООрганизацияДополнительноE-mail
Медведев Никита ВладимировичУральский государственный университет путей сообщениякандидат технических наук, доцент кафедры информационных технологий и защиты информацииitcrypt@gmail.com
Титов Сергей СергеевичУральский государственный университет путей сообщениядоктор физико-математических наук, профессорsergey.titov@usaaa.ru
Всего: 2

Ссылки

Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. 288 с.
Welsh D. J. A. Matroid Theory. London: Academic Press, 1976.
Парватов Н. Г. Совершенные схемы разделения секрета // Прикладная дискретная математика. 2008. №2(2). С. 50-57.
Beimel A. and Livne N. On matroids and non-ideal secret sharing // TCC 2006. LNCS. 2006. V. 3876. P. 482-501.
Marti-Farre J. and Padro C. Secret sharing schemes on sparse homogeneous access structures with rank three // Electronic J. Combinatorics. 2004. No. 11(1). Research Paper 72. 16p.
Холл М. Комбинаторика. М.: Мир, 1970.
 Об однородных матроидах, соответствующих блок-схемам | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/2

Об однородных матроидах, соответствующих блок-схемам | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/2