Двудольный гиперграф
В теории графов термин «двудольный гиперграф» описывает несколько родственных классов гиперграфов , каждый из которых является естественным обобщением двудольного графа .
Свойство B и 2-раскрашиваемость
[ редактировать ]Самое слабое определение двудольности также называется 2-раскрашиваемостью . Гиперграф H = ( V , E ) называется 2-раскрашиваемым, если его множество вершин можно разделить на два множества, X и Y , так что каждое гиперребро пересекает как X, так и Y. V Эквивалентно, вершины H могут быть двухцветными, так что ни одно гиперребро не будет одноцветным. Каждый двудольный граф G = ( X + Y , E ) раскрашивается в 2 цвета: каждое ребро содержит ровно одну вершину X и одну вершину Y , поэтому, например, X можно покрасить в синий цвет, а Y можно покрасить в желтый цвет, и ни одно ребро не будет одноцветным.
Свойство 2-раскраски было впервые введено Феликсом Бернштейном в контексте семейств множеств; [1] поэтому его также называют Свойством B.
Точная 2-цветность
[ редактировать ]Более строгое определение двудольности таково: гиперграф называется двудольным если его множество вершин V можно разделить на два множества, X и Y , так что каждое гиперребро содержит ровно один элемент X. , [2] [3] Любой двудольный граф также является двудольным гиперграфом.
Каждый двудольный гиперграф раскрашивается в 2 цвета, но двудольность сильнее, чем в 2-раскраску. Пусть H — гиперграф на вершинах {1, 2, 3, 4} со следующими гиперребрами:
{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }
Этот H раскрашивается в 2 цвета, например, с помощью разбиения X = {1,2} и Y = {3,4}. Однако оно не является двудольным, поскольку каждое множество X с одним элементом имеет пустое пересечение с одним гиперребром, а каждое множество X с двумя и более элементами имеет пересечение размера 2 и более хотя бы с двумя гиперребрами.
Теорема Холла о браке была обобщена с двудольных графов на двудольные гиперграфы; см. теоремы типа Холла для гиперграфов .
n -раздельность и радужная раскраска
[ редактировать ]Более сильное определение: для данного целого числа n гиперграф называется n -однородным, если все его гиперребра содержат ровно n вершин. n - однородный гиперграф называется n -частичным , если его множество вершин V можно разбить на n подмножеств так, что каждое гиперребро содержит ровно один элемент из каждого подмножества. [4] Альтернативный термин — раскрашиваемый радугой . [5]
Каждый гиперграф n- частности является двудольным, но n-дольность сильнее двудольности. Пусть H — гиперграф на вершинах {1, 2, 3, 4} со следующими гиперребрами;
{ {1,2,3} , {1,2,4} , {1,3,4} }
Этот H 3-однороден. Он двудольный по разбиению X = {1} и Y = {2,3,4}. Однако оно не трехдольное: в каждом разбиении V на 3 подмножества хотя бы одно подмножество содержит две вершины, а значит, хотя бы одно гиперребро содержит две вершины из этого подмножества.
Трехчастный гиперграф часто называют «трехчастным гиперграфом». Однако двудольный гиперграф — это не то же самое, что двудольный гиперграф; это эквивалентно двудольному графу .
Сравнение с другими понятиями двудольности
[ редактировать ]Существуют и другие естественные обобщения двудольных графов. Гиперграф называется сбалансированным , если он по существу раскрашивается в 2 цвета и остается по существу раскрашиваемым в 2 цвета при удалении любого количества вершин (см. Сбалансированный гиперграф ).
Свойства двудольности и сбалансированности не предполагают друг друга.
Двусторонность не означает баланса. Например, пусть H — гиперграф с вершинами {1,2,3,4} и ребрами:
{ {1,2,3} , {1,2,4} , {1,3,4} }
Он двудольный по разбиению X = {1}, Y = {2,3,4}. Но не сбалансирован. Например, если удалить вершину 1, мы получим ограничение H на {2,3,4}, которое имеет следующие гиперребра;
{ {2,3} , {2,4} , {3,4} }
Он не раскрашивается в 2 цвета, поскольку в любой 2-раскраске есть как минимум две вершины одного цвета, и, следовательно, хотя бы одно из гиперребер одноцветное.
Другой способ увидеть, что H не сбалансирован, состоит в том, что он содержит цикл нечетной длины C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), и ни одно ребро C не содержит все три вершины 2,3,4 из C .
Баланс не подразумевает двусторонность. Пусть H — гиперграф: [ нужна ссылка ]
{ {1,2} , {3,4} , {1,2,3,4} }
он раскрашивается в 2 цвета и остается раскрашиваемым в 2 цвета при удалении из него любого количества вершин. Однако оно не двудольное, так как для того, чтобы в каждом из первых двух гиперребер было ровно по одной зеленой вершине, нам необходимо иметь две зеленые вершины в последнем гиперребре.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Бернштейн, Ф. (1908), «К теории тригонометрических рядов», Лейпц. Бер. , 60 : 325–328 .
- ^ Ахарони, Рон; Кесслер, Офра (15 октября 1990 г.). «О возможном распространении теоремы Холла на двудольные гиперграфы» . Дискретная математика . 84 (3): 309–313. дои : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
- ^ Аннамалай, Чидамбарам (21 декабря 2015 г.), «Нахождение идеальных совпадений в двудольных гиперграфах», Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2016 года , Труды Общества промышленной и прикладной математики, стр. 1814–1823, doi : 10.1137/1.9781611974331.ch126 , hdl : 20.500.11850/224679 , ISBN 978-1-61197-433-1
- ^ Ахарони, Рон (1 декабря 1985 г.). «Соответствия inn-частные-графы». Графы и комбинаторика . 1 (1): 303–304. дои : 10.1007/BF02582958 . ISSN 1435-5914 . S2CID 19258298 .
- ^ Гурусвами, Венкатесан; Ли, Ыйун (01 июня 2018 г.). «Сильные результаты неаппроксимируемости на сбалансированных гиперграфах, раскрашиваемых в радугу». Комбинаторика . 38 (3): 547–599. дои : 10.1007/s00493-016-3383-0 . ISSN 1439-6912 . S2CID 53566425 .