Ширина гиперграфа

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

Ширина H , обозначаемая w( H ), представляет собой наименьший размер подмножества E , которое закрепляет E. [ ^2]
Ширина соответствия H , обозначаемая mw( H ), представляет собой максимум среди всех соответствий M в H минимального размера подмножества E , которое закрепляет M . ^[3]

Так как E содержит все паросочетания из E , для всех H : w( H ) ≥ mw( H ).

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

Примеры

Пусть H — гиперграф с множеством вершин V = {A,B; a,b} и множеством ребер:

Е = { {А,а}, {Б,б}, {А,б}, {Б,а} }

Ширина H составляет:

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

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

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

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

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

w( H ) > r тогда и только тогда, когда для каждого набора из r вершин в L( H ) существует вершина, не смежная ни с одной из них.
mw( H ) > r тогда и только тогда, когда для каждого набора из r вершин в L( H ) существует вершина, не смежная ни с одной из них, и, кроме того, существует независимое множество I в L( H ), которое содержит вершину, не смежную ни с одним из таких множеств.

Число доминирования графа G , обозначаемое γ ( G ), является наименьшим размером множества вершин, которое доминирует над всеми вершинами G . Ширина гиперграфа равна числу доминирования или его линейному графу: w( H ) = γ (L( H )). Это происходит потому, что ребра E являются вершинами L( H ): каждое подмножество E , которое закрепляет E в H, соответствует множеству вершин в L( H ), которое доминирует над всеми L( H ).

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

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

О других концепциях, называемых «шириной» в теории графов, см. Ширина (значения)#Теория графов .

Ссылки

^ Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов». Журнал теории графов . 35 (2): 83– 88. doi :10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN 1097-0118.
^ ab Мешулам, Рой (2001-01-01). «Комплекс клик и сопоставление гиперграфов». Combinatorica . 21 (1): 89– 94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.
^ Ахарони, Рон (1 января 2001 г.). «Гипотеза Райзера для трехдольных трехграфов». Комбинаторика . 21 (1): 1–4 . doi : 10.1007/s004930170001. ISSN 1439-6912. S2CID 13307018.
^ Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах». Комбинаторика . 27 (3): 253–267 . doi :10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.

[:4-1] Ахарони, Рон; Хакселл, Пенни (2000). «Теорема Холла для гиперграфов». Журнал теории графов . 35 (2): 83– 88. doi :10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN 1097-0118.

[:7-2] Мешулам, Рой (2001-01-01). «Комплекс клик и сопоставление гиперграфов». Combinatorica . 21 (1): 89– 94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

[:6-3] Ахарони, Рон (1 января 2001 г.). «Гипотеза Райзера для трехдольных трехграфов». Комбинаторика . 21 (1): 1–4 . doi : 10.1007/s004930170001. ISSN 1439-6912. S2CID 13307018.

[:1-4] Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах». Комбинаторика . 27 (3): 253–267 . doi :10.1007/s00493-007-2086-y. ISSN 1439-6912. S2CID 43510417.