Двудольный гиперграф - Bipartite hypergraph

В теория графов, период, термин двудольный гиперграф описывает несколько родственных классов гиперграфы, все из которых являются естественными обобщениями двудольный граф.

Свойство B и 2-окрашиваемость

Основная статья: Свойство B

Гиперграф ЧАС = (V, E) называется 2-цветный если его вершина установлена V можно разделить на два набора, Икс и Y, так что каждое гиперребро пересекает оба Икс и Y. Эквивалентно вершины ЧАС может быть двухцветным, так что ни одно гиперребро не будет одноцветным. Каждый двудольный граф грамм = (Икс+Y, E) 2-раскрашиваем: каждое ребро содержит ровно одну вершину Икс и одна вершина Y, так например Икс может быть окрашен в синий цвет и Y может быть окрашен в желтый цвет, а края не являются одноцветными.

Свойство 2-окрашиваемости было впервые введено Феликс Бернштейн в контексте заданных семей;[1] поэтому его еще называют Свойство B.

Точная 2-окрашиваемость

Гиперграф называется двудольный если его вершина установлена V можно разделить на два набора, Икс и Y, такое, что каждое гиперребро содержит ровно один элемент Икс.[2][3]


Чтобы увидеть, что этот смысл сильнее, чем двукратность, пусть ЧАС - гиперграф на вершинах {1, 2, 3, 4} со следующими гиперребрами:

{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }

Этот ЧАС можно раскрашивать в 2 цвета, например, перегородкой Икс = {1,2} и Y = {3,4}. Однако это не совсем-2-раскрашивание, поскольку каждый набор Икс с одним элементом имеет пустое пересечение с одним гиперребром, и каждое множество Икс с двумя или более элементами имеет пересечение размером 2 и более, по крайней мере, с двумя гиперребрами.

Каждый двудольный граф грамм = (Икс+Y, E) раскрашивается ровно-2.

Теорема холла о браке был обобщен с двудольных графов на точно 2-раскрашиваемые гиперграфы; видеть Теоремы холловского типа для гиперграфов.

п-относимость и радужная окраска

Учитывая целое число п, гиперграф называется п-равномерно, если все его гиперребра содержат ровно п вершины. An п-равномерный гиперграф называется п-частный если его вершина установлена V можно разделить на п такие подмножества, что каждое гиперребро содержит ровно один элемент из каждого подмножества. [4] Альтернативный термин радужный.[5]

Чтобы увидеть это п-частность сильнее точной-2-окрашиваемости, пусть ЧАС - гиперграф в вершинах {1, 2, 3, 4} со следующими гиперребрами;

{ {1,2,3} , {1,2,4} , {1,3,4} }

Этот ЧАС 3-равномерная. Он точно-2-раскрашивается перегородкой Икс = {1} и Y = {2,3,4}. Однако он не является трехчастным: в каждом разделе V на 3 подмножества, по крайней мере одно подмножество содержит две вершины, и, таким образом, по крайней мере одно гиперребро содержит две вершины из этого подмножества.

Сравнение с другими представлениями о двудольности

Есть и другие естественные обобщения двудольных графов. Гиперграф называется сбалансированный если он по существу двухцветный и остается по существу двухцветным после удаления любого количества вершин (см. Сбалансированный гиперграф ).

Свойства двудольности и равновесия не подразумевают друг друга.

Двусторонность не предполагает баланса. Например, пусть ЧАС - гиперграф с вершинами {1,2,3,4} и ребрами:

{ {1,2,3} , {1,2,4} , {1,3,4} }

Он двудольный по перегородке Икс={1}, Y= {2,3,4}. Но не сбалансирован. Например, если удалить вершину 1, мы получим ограничение ЧАС к {2,3,4}, который имеет следующие гиперребра;

{ {2,3} , {2,4} , {3,4} }

Он не является 2-раскрашиваемым, поскольку в любой 2-раскраске есть по крайней мере две вершины одного цвета, и, следовательно, по крайней мере одно из гиперребер одноцветное.

Другой способ увидеть это ЧАС не сбалансирован, так как содержит цикл нечетной длины C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), и нет край C содержит все три вершины 2,3,4 C.

Баланс не предполагает двупартийности. Позволять ЧАС быть гиперграфом:[нужна цитата ]

{ {1,2} , {3,4} , {1,2,3,4} }

он может быть 2-раскрашен и остается 2-раскрашиваемым после удаления из него любого количества вершин. Однако он не двудольный, так как для того, чтобы иметь ровно одну зеленую вершину в каждом из первых двух гиперребер, мы должны иметь две зеленые вершины в последнем гиперребре.

Смотрите также

Рекомендации

  1. ^ Бернштейн, Ф. (1908), "Zur theorie der trigonometrische Reihen", Лейпц. Бер., 60: 325–328.
  2. ^ Ахарони, Рон; Кесслер, Офра (1990-10-15). «О возможном распространении теоремы Холла на двудольные гиперграфы». Дискретная математика. 84 (3): 309–313. Дои:10.1016 / 0012-365X (90) 90136-6. ISSN  0012-365X.
  3. ^ Аннамалай, Чидамбарам (21 декабря 2015 г.), "Поиск идеальных пар в двудольных гиперграфах", Материалы ежегодного симпозиума ACM-SIAM по дискретным алгоритмам 2016 г., Proceedings, Society for Industrial and Applied Mathematics, pp. 1814–1823, Дои:10.1137 / 1.9781611974331.ch126, ISBN  978-1-61197-433-1
  4. ^ Ахарони, Рон (1985-12-01). "Соответствия постоялым дворам-графам". Графы и комбинаторика. 1 (1): 303–304. Дои:10.1007 / BF02582958. ISSN  1435-5914. S2CID  19258298.
  5. ^ Гурусвами, Венкатесан; Ли, Ыуунг (2018-06-01). "Сильные результаты о несовместимости на сбалансированных радужно-раскрашиваемых гиперграфах". Комбинаторика. 38 (3): 547–599. Дои:10.1007 / s00493-016-3383-0. ISSN  1439-6912. S2CID  53566425.