Ширина гиперграфа - Width of a hypergraph

В теория графов, есть два связанных свойства гиперграф которые называются его «шириной». Учитывая гиперграф ЧАС = (V, E), мы говорим, что множество K краев булавки другой набор F ребер, если каждое ребро в F пересекает некоторый край в K.[1] Потом:

  • В ширина из ЧАС, обозначим w (ЧАС), является наименьшим размером подмножества E это булавки E.[2]
  • В подходящая ширина из ЧАС, обозначается mw (ЧАС), является максимальным по всем совпадения M в ЧАСиз подмножества E это булавки M.[3]

С E содержит все совпадения в E, для всех ЧАС: w (ЧАС) ≥ mw (ЧАС).

Ширина гиперграфа используется в Теоремы холловского типа для гиперграфов.

Примеры

Позволять ЧАС - гиперграф с множеством вершин V = {A, B; a, b} и набор ребер:

E = {{A, a}, {B, b}, {A, b}, {B, a}}

Ширина ЧАС находятся:

  • w (ЧАС) = 2, так как E закреплен, например набором {{A, a}, {B, b}}, и не может быть закреплен каким-либо меньшим набором.
  • мвт (ЧАС) = 1, так как каждое совпадение может быть закреплено одним ребром. Есть два соответствия: {{A, a}, {B, b}} закреплено, например на {{A, b}}, а {{A, b}, {B, a}} закреплено, например автор: {{A, a}}.

Характеристики

В граф дизъюнктности из ЧАС, обозначим D (ЧАС), это граф, в котором каждое ребро в H является вершиной в D (ЧАС), и каждые два непересекающихся ребра в ЧАС смежны в D (ЧАС). В совпадения в ЧАС соответствуют клики в D (ЧАС). Мешулам[2] охарактеризовал ширину гиперграфа ЧАС с точки зрения свойств D (ЧАС). Для любого положительного целого числа р:

  • w (ЧАС) > р тогда и только тогда, когда D (ЧАС) удовлетворяет свойству P (р, ∞), что означает, что каждый набор р вершины в D (ЧАС) есть общий сосед. Это потому, что w (ЧАС) > р если только ЧАС не имеет размера р, тогда и только тогда, когда для каждого подмножества р края ЧАС есть ребро, которое не закреплено им, если и только если каждое подмножество р края ЧАС имеет общего соседа в D (ЧАС).
  • мвт (ЧАС) > р тогда и только тогда, когда D (ЧАС) удовлетворяет свойству P (р, 0), что означает, что каждый набор р вершины в D (ЧАС) имеют общего соседа, а кроме того, существует клика C в D (ЧАС), который содержит общего соседа каждого такого множества.

В линейный график из ЧАС, обозначим L (ЧАС), это граф, в котором каждое ребро в H является вершиной в L (ЧАС), и каждые два пересекающихся ребра в ЧАС смежны в L (ЧАС). Соответствия в H соответствуют независимые множества в L (ЧАС). Поскольку L (ЧАС) является дополнением к D (ЧАС) приведенная выше характеристика может быть переведена на L (ЧАС):

  • w (ЧАС) > р тогда и только тогда, когда для каждого набора р вершины в L (ЧАС) есть вершина, не смежная ни с одной из них.
  • мвт (ЧАС) > р тогда и только тогда, когда для каждого набора р вершины в L (ЧАС) есть вершина, не смежная ни с одной из них, а кроме того, существует независимое множество я в L (ЧАС), который содержит вершину, не смежную ни с одним таким множеством.

В число господства графа грамм, обозначенный γ(грамм), является наименьшим размером множества вершин, доминирующего над всеми вершинами грамм. Ширина гиперграфа равна числу доминирования или его линейному графику: w (ЧАС) = γ(L (ЧАС)). Это потому, что края E - вершины L (ЧАС): каждое подмножество E это булавки E в ЧАС соответствует множеству вершин в L (ЧАС), доминирующая над всеми L (ЧАС).

В число доминирования независимости графа грамм, обозначенный iγ(грамм), является максимальным по всем независимые множества А из грамм, из наименьшего множества доминирующих А.[4] Соответствующая ширина гиперграфа равна числу доминирования независимости или его линейному графу: mw (ЧАС) = iγ(L (ЧАС)). Это потому, что каждое совпадение M в ЧАС соответствует независимому множеству яM в L (ЧАС), и каждое подмножество E это булавки M в ЧАС соответствует набору, который доминирует яM в L (ЧАС).

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

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

  1. ^ Ахарони, Рон; Хакселл, Пенни (2000). "Теорема Холла для гиперграфов". Журнал теории графов. 35 (2): 83–88. Дои:10.1002 / 1097-0118 (200010) 35: 23.0.CO; 2-В. ISSN  1097-0118.
  2. ^ а б Мешулам, Рой (01.01.2001). «Кликовый комплекс и соответствие гиперграфа». Комбинаторика. 21 (1): 89–94. Дои:10.1007 / s004930170006. ISSN  1439-6912.
  3. ^ Ахарони, Рон (01.01.2001). «Гипотеза Райзера для трехчастных 3-графов». Комбинаторика. 21 (1): 1–4. Дои:10.1007 / s004930170001. ISSN  1439-6912.
  4. ^ Ахарони, Рон; Бергер, Эли; Зив, Ран (2007-05-01). «Независимые системы представителей в взвешенных графах». Комбинаторика. 27 (3): 253–267. Дои:10.1007 / s00493-007-2086-у. ISSN  1439-6912.