Рёберный граф гиперграфа

Рёберный граф гиперграфа — это граф, множество вершин которого является множеством гиперрёбер гиперграфа, а два гиперребра смежны, если они имеют непустое пересечение. Другими словами, рёберный граф гиперграфа — это граф пересечений семейства конечных множеств. Понятие является обобщением рёберного графа обычного графа.

Вопросы о рёберных графах гиперграфов часто являются обобщениями вопросов о рёберных графах обычных графов. Например, гиперграф, все рёбра которого имеют размер k, называется k -униформным (2-униформный гиперграф — это обычный граф). В теории гиперграфов часто естественно требовать k-униформность. Любой обычный граф является рёберным графом некоего гиперграфа, но если зафиксировать размер ребра k (число точек множества, принадлежащего ребру), не всякий граф является рёберным графом какого-либо k-униформного графа. Основная задача — описать рёберные графы для каждого k ≥ 3.

Гиперграф называется линейным, если любая пара гиперрёбер имеет в пересечении максимум одну вершину. Любой граф является рёберным графом не только некоторого гиперграфа, но и некоторого линейного гиперграфа.

Рёберные графы k-униформных гиперграфов, k ≥ 3

Байнеке описал рёберные графы обычных графов путём перечисления 9 запрещённых порождённых подграфов (смотрите статью о рёберных графах). Никакого описания посредством запрещённых порождённых подграфов не известно для рёберных графов k-униформных гиперграфов для любого k ≥ 3 и Ловас показал, что не существует такого описания в виде конечного списка для k = 3.

Краус описал рёберные графы обычных графов в терминах покрытия кликами (Смотрите Рёберный граф). Глобальное описание краусовского типа для рёберных графов k-униформных гиперграфов для любого k ≥ 3 дано Бержем.

Рёберные графы k-униформных линейных гиперграфов для k ≥ 3

Глобальное описание краусовского типа для рёберных графов k-униформных линейных гиперграфов для любого k ≥ 3 дано Найком, Рао, Шрикханде и Сингхи. В то же время они нашли конечное число запрещённых порождённых подграфов для линейных 3-униформных гиперграфов с минимальной степенью вершины не меньше 69. Метельский и Тышкевич и Якобсон, Кезди, Лехель улучшили эту границу до 19, а Скумс, Суздаль и Тышкевич сократили это значение до 16. Метельский и Тышкевич также доказали, что для k > 3 не существует подобного списка для линейных k-униформных гиперграфов, какое бы ограничение на степень не накладывали.

Сложность поиска описания линейных k-униформных гиперграфов заключается в том, что имеется бесконечно много запрещённых порождённых подграфов. Чтобы дать пример, для m > 0 возьмём цепочку из m графов-алмазов, так чтобы алмазы имели общие вершины второго порядка, и добавим некоторые висячие вершины, как показано на рисунке, чтобы получить одно из семейств минимальных запрещённых подграфов.

Имеется ряд интересных описаний для рёберных графов линейных k-униформных гиперграфов, данных разными авторами, при ограничениях на минимальную степень вершин или минимальную степень рёбер. Минимальная степень ребра для описания рёберных графов k-униформных линейных гиперграфов для любого k ≥ 3, не меньшая k³-2k²+1 в работе Найка, Рао, Шрикханде и Сигхи, уменьшена до 2k²-3k+1 в работах Якобсона, Кезди, Лехела и Зверовича.

Сложность распознавания рёберных графов линейных k-униформных гиперграфов без ограничений на минимальную степень (или минимальную степень рёбер) неизвестна. Для k = 3 и минимальной степени по меньшей мере 19 распознавания возможно за полиномиальное время). Скумс, Суздаль и Тышкевич уменьшили минимальную степень до 10.

Есть много нерешённых задач и гипотез в работах Найка и др., Якобсона и др., Метельского и др. и Зверовича.

Литература

• L. W. Beineke Beitrage zur Graphentheorie / H. Sachs, H. Voss, H. Walther. — Leipzig: Teubner, 1968. — С. 17—23.
• C. Berge Hypergraphs: Combinatorics of Finite Sets. — North-Holland, 1989.. Переведено с французского
• J. C. Bermond, M. C. Heydemann, D. Sotteau Line graphs of hypergraphs I // Discrete Mathematics. — 1977. — Т. 18. — С. 235—241. — DOI:10.1016/0012-365X(77)90127-3.
• M. C. Heydemann, D. Sotteau Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976). — 1976. — Т. 18. — С. 567—582.
• J. Krausz Démonstration nouvelle d'une théorème de Whitney sur les réseaux // Mat. Fiz. Lapok. — 1943. — Т. 50. — С. 75—85.. На венгерском
• L. Lovász Beitrage zur Graphentheorie und deren Ansendungen. — 1977. — С. 313.
• M. S. Jacobson, Andre E. Kézdy, Jeno Lehel Recognizing intersection graphs of linear uniform hypergraphs // Graphs and Combinatorics. — 1997. — Т. 13. — С. 359—367.
• Yury Metelsky, Regina Tyshkevich On line graphs of linear 3-uniform hypergraphs // Journal of Graph Theory. — 1997. — Т. 25. — С. 243—251. — DOI:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K.
• Метельский Ю.М., Тышкевич Р.И. Реберные графы линейны: З-униформных гиперграфов // Докл. АН Беларус. — 1996. — С. 26—30..
• Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi Combinatorial mathematics, optimal designs and their applications (Proc. Sympos. Combin. Math. and Optimal Design, Colorado State Univ., Fort Collins, Colo., 1978). — 1980. — Т. 6. — С. 275—279.
• Ranjan N. Naik, S. B. Rao, S. S. Shrikhande, N. M. Singhi Intersection graphs of k-uniform linear hypergraphs // European J. Combinatorics. — 1982. — Т. 3. — С. 159—172. — DOI:10.1016/s0195-6698(82)80029-2.
• P. V. Skums, S. V. Suzdal', R. I. Tyshkevich Edge intersection of linear 3-uniform hypergraphs // Discrete Mathematics. — 2009. — Т. 309. — С. 3500—3517. — DOI:10.1016/j.disc.2007.12.082.
• Igor E. Zverovich A solution to a problem of Jacobson, Kézdy and Lehel // Graphs and Combinatorics. — 2004. — Т. 20. — С. 571—577. — DOI:10.1007/s00373-004-0572-1.
• Vitaly I. Voloshin Introduction to Graph and Hypergraph Theory. — Nova Science Publishers, Inc., 2009.

Отрывок, характеризующий Рёберный граф гиперграфа

– Здесь то слава богу, – сказал адъютант, – но на левом фланге у Багратиона ужасная жарня идет.
– Неужели? – спросил Пьер. – Это где же?
– Да вот поедемте со мной на курган, от нас видно. А у нас на батарее еще сносно, – сказал адъютант. – Что ж, едете?
– Да, я с вами, – сказал Пьер, глядя вокруг себя и отыскивая глазами своего берейтора. Тут только в первый раз Пьер увидал раненых, бредущих пешком и несомых на носилках. На том самом лужке с пахучими рядами сена, по которому он проезжал вчера, поперек рядов, неловко подвернув голову, неподвижно лежал один солдат с свалившимся кивером. – А этого отчего не подняли? – начал было Пьер; но, увидав строгое лицо адъютанта, оглянувшегося в ту же сторону, он замолчал.
Пьер не нашел своего берейтора и вместе с адъютантом низом поехал по лощине к кургану Раевского. Лошадь Пьера отставала от адъютанта и равномерно встряхивала его.
– Вы, видно, не привыкли верхом ездить, граф? – спросил адъютант.
– Нет, ничего, но что то она прыгает очень, – с недоуменьем сказал Пьер.
– Ээ!.. да она ранена, – сказал адъютант, – правая передняя, выше колена. Пуля, должно быть. Поздравляю, граф, – сказал он, – le bapteme de feu [крещение огнем].
Проехав в дыму по шестому корпусу, позади артиллерии, которая, выдвинутая вперед, стреляла, оглушая своими выстрелами, они приехали к небольшому лесу. В лесу было прохладно, тихо и пахло осенью. Пьер и адъютант слезли с лошадей и пешком вошли на гору.
– Здесь генерал? – спросил адъютант, подходя к кургану.
– Сейчас были, поехали сюда, – указывая вправо, отвечали ему.
Адъютант оглянулся на Пьера, как бы не зная, что ему теперь с ним делать.
– Не беспокойтесь, – сказал Пьер. – Я пойду на курган, можно?
– Да пойдите, оттуда все видно и не так опасно. А я заеду за вами.
Пьер пошел на батарею, и адъютант поехал дальше. Больше они не видались, и уже гораздо после Пьер узнал, что этому адъютанту в этот день оторвало руку.
Курган, на который вошел Пьер, был то знаменитое (потом известное у русских под именем курганной батареи, или батареи Раевского, а у французов под именем la grande redoute, la fatale redoute, la redoute du centre [большого редута, рокового редута, центрального редута] место, вокруг которого положены десятки тысяч людей и которое французы считали важнейшим пунктом позиции.
Редут этот состоял из кургана, на котором с трех сторон были выкопаны канавы. В окопанном канавами место стояли десять стрелявших пушек, высунутых в отверстие валов.
В линию с курганом стояли с обеих сторон пушки, тоже беспрестанно стрелявшие. Немного позади пушек стояли пехотные войска. Входя на этот курган, Пьер никак не думал, что это окопанное небольшими канавами место, на котором стояло и стреляло несколько пушек, было самое важное место в сражении.
Пьеру, напротив, казалось, что это место (именно потому, что он находился на нем) было одно из самых незначительных мест сражения.
Войдя на курган, Пьер сел в конце канавы, окружающей батарею, и с бессознательно радостной улыбкой смотрел на то, что делалось вокруг него. Изредка Пьер все с той же улыбкой вставал и, стараясь не помешать солдатам, заряжавшим и накатывавшим орудия, беспрестанно пробегавшим мимо него с сумками и зарядами, прохаживался по батарее. Пушки с этой батареи беспрестанно одна за другой стреляли, оглушая своими звуками и застилая всю окрестность пороховым дымом.
В противность той жуткости, которая чувствовалась между пехотными солдатами прикрытия, здесь, на батарее, где небольшое количество людей, занятых делом, бело ограничено, отделено от других канавой, – здесь чувствовалось одинаковое и общее всем, как бы семейное оживление.
Появление невоенной фигуры Пьера в белой шляпе сначала неприятно поразило этих людей. Солдаты, проходя мимо его, удивленно и даже испуганно косились на его фигуру. Старший артиллерийский офицер, высокий, с длинными ногами, рябой человек, как будто для того, чтобы посмотреть на действие крайнего орудия, подошел к Пьеру и любопытно посмотрел на него.
Молоденький круглолицый офицерик, еще совершенный ребенок, очевидно, только что выпущенный из корпуса, распоряжаясь весьма старательно порученными ему двумя пушками, строго обратился к Пьеру.
– Господин, позвольте вас попросить с дороги, – сказал он ему, – здесь нельзя.
Солдаты неодобрительно покачивали головами, глядя на Пьера. Но когда все убедились, что этот человек в белой шляпе не только не делал ничего дурного, но или смирно сидел на откосе вала, или с робкой улыбкой, учтиво сторонясь перед солдатами, прохаживался по батарее под выстрелами так же спокойно, как по бульвару, тогда понемногу чувство недоброжелательного недоуменья к нему стало переходить в ласковое и шутливое участие, подобное тому, которое солдаты имеют к своим животным: собакам, петухам, козлам и вообще животным, живущим при воинских командах. Солдаты эти сейчас же мысленно приняли Пьера в свою семью, присвоили себе и дали ему прозвище. «Наш барин» прозвали его и про него ласково смеялись между собой.
Одно ядро взрыло землю в двух шагах от Пьера. Он, обчищая взбрызнутую ядром землю с платья, с улыбкой оглянулся вокруг себя.
– И как это вы не боитесь, барин, право! – обратился к Пьеру краснорожий широкий солдат, оскаливая крепкие белые зубы.
– А ты разве боишься? – спросил Пьер.
– А то как же? – отвечал солдат. – Ведь она не помилует. Она шмякнет, так кишки вон. Нельзя не бояться, – сказал он, смеясь.
Несколько солдат с веселыми и ласковыми лицами остановились подле Пьера. Они как будто не ожидали того, чтобы он говорил, как все, и это открытие обрадовало их.
– Наше дело солдатское. А вот барин, так удивительно. Вот так барин!
– По местам! – крикнул молоденький офицер на собравшихся вокруг Пьера солдат. Молоденький офицер этот, видимо, исполнял свою должность в первый или во второй раз и потому с особенной отчетливостью и форменностью обращался и с солдатами и с начальником.
Перекатная пальба пушек и ружей усиливалась по всему полю, в особенности влево, там, где были флеши Багратиона, но из за дыма выстрелов с того места, где был Пьер, нельзя было почти ничего видеть. Притом, наблюдения за тем, как бы семейным (отделенным от всех других) кружком людей, находившихся на батарее, поглощали все внимание Пьера. Первое его бессознательно радостное возбуждение, произведенное видом и звуками поля сражения, заменилось теперь, в особенности после вида этого одиноко лежащего солдата на лугу, другим чувством. Сидя теперь на откосе канавы, он наблюдал окружавшие его лица.
К десяти часам уже человек двадцать унесли с батареи; два орудия были разбиты, чаще и чаще на батарею попадали снаряды и залетали, жужжа и свистя, дальние пули. Но люди, бывшие на батарее, как будто не замечали этого; со всех сторон слышался веселый говор и шутки.