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

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

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

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

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

Примеры

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

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

Ширина H :

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

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

Граф дизъюнктности графа H , обозначаемый D( H ), представляет собой граф, в котором каждое ребро в H является вершиной в D( H ), а каждые два непересекающихся ребра в H смежны в D( H ). Паросочетания в H H соответствуют кликам в D( ) . Мешулам ^{[ 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 H , обозначаемый L( H ), представляет собой граф, в котором каждое ребро в H является вершиной в L( ) , а каждые два пересекающихся ребра в 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 соответствует независимому множеству в _IM L( H каждое подмножество E , которое закрепляет M в H, соответствует множеству, которое доминирует IM _{), а} в 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 .
^ Jump up to: ^а ^б Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов» . Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .
^ Ахарони, Рон (1 января 2001 г.). «Гипотеза Райзера для трехдольных трехграфов» . Комбинаторика . 21 (1): 1–4. дои : 10.1007/s004930170001 . ISSN 1439-6912 . S2CID 13307018 .
^ Ахарони, Рон; Бергер, Эли; Зив, Ран (1 мая 2007 г.). «Независимые системы представителей во взвешенных графах» . Комбинаторика 27 (3): 253–267. дои : 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] Jump up to: ^а ^б Мешулам, Рой (1 января 2001 г.). «Комплекс клик и сопоставление гиперграфов» . Комбинаторика . 21 (1): 89–94. дои : 10.1007/s004930170006 . ISSN 1439-6912 . S2CID 207006642 .

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

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]