Гиперграф

Гипергра́ф — обобщение графа, в котором каждым ребром могут соединяться не только две вершины, но и любые подмножества вершин.

С математической точки зрения, гиперграф представляет собой пару <math>(V, E)</math>, где <math>V</math> — непустое множество объектов некоторой природы, называемых вершинами гиперграфа, а <math>E</math> — семейство непустых (необязательно различных) подмножеств множества <math>V</math>, называемых рёбрами гиперграфа.

Гиперграфы применяются, в частности, при моделировании электрических цепей.

Трансверсалью гиперграфа является множество <math>T \subseteq V</math>, содержащее непустое пересечение с каждым ребром. Такая трансверсаль будет минимальной, если никакое её подмножество само не является трансверсалью гиперграфа.

Литература

• В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Глава XI: Гиперграфы // Лекции по теории графов. — М.: Наука, 1990. — С. 298—315. — 384 с. — ISBN 5-02-013992-0.
• И. А. Головинский Методы анализа топологии коммутационных схем электрических сетей // Электричество. — 2005. — № № 3. — С. 10—18.
• В. А. Евстигнеев, В. Н. Касьянов. [pco.iis.nsk.su/grapp2/html/ReqtypetNamegipergraf.htm Толковый словарь по теории графов]. — Новосибирск: Наука, 1999.
• А. А. Зыков Гиперграфы // Успехи математических наук. — 1974. — № 6 (180).
• Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990. 216 с.

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

– Ты ему вскружила совсем голову, зачем? Что ты хочешь от него? Ты знаешь, что тебе нельзя выйти за него замуж.
– Отчего? – не переменяя положения, сказала Наташа.
– Оттого, что он молод, оттого, что он беден, оттого, что он родня… оттого, что ты и сама не любишь его.
– А почему вы знаете?
– Я знаю. Это не хорошо, мой дружок.
– А если я хочу… – сказала Наташа.
– Перестань говорить глупости, – сказала графиня.
– А если я хочу…
– Наташа, я серьезно…
Наташа не дала ей договорить, притянула к себе большую руку графини и поцеловала ее сверху, потом в ладонь, потом опять повернула и стала целовать ее в косточку верхнего сустава пальца, потом в промежуток, потом опять в косточку, шопотом приговаривая: «январь, февраль, март, апрель, май».
– Говорите, мама, что же вы молчите? Говорите, – сказала она, оглядываясь на мать, которая нежным взглядом смотрела на дочь и из за этого созерцания, казалось, забыла всё, что она хотела сказать.
– Это не годится, душа моя. Не все поймут вашу детскую связь, а видеть его таким близким с тобой может повредить тебе в глазах других молодых людей, которые к нам ездят, и, главное, напрасно мучает его. Он, может быть, нашел себе партию по себе, богатую; а теперь он с ума сходит.
– Сходит? – повторила Наташа.
– Я тебе про себя скажу. У меня был один cousin…
– Знаю – Кирилла Матвеич, да ведь он старик?
– Не всегда был старик. Но вот что, Наташа, я поговорю с Борей. Ему не надо так часто ездить…
– Отчего же не надо, коли ему хочется?
– Оттого, что я знаю, что это ничем не кончится.
– Почему вы знаете? Нет, мама, вы не говорите ему. Что за глупости! – говорила Наташа тоном человека, у которого хотят отнять его собственность.
– Ну не выйду замуж, так пускай ездит, коли ему весело и мне весело. – Наташа улыбаясь поглядела на мать.
– Не замуж, а так , – повторила она.
– Как же это, мой друг?
– Да так . Ну, очень нужно, что замуж не выйду, а… так .
– Так, так, – повторила графиня и, трясясь всем своим телом, засмеялась добрым, неожиданным старушечьим смехом.
– Полноте смеяться, перестаньте, – закричала Наташа, – всю кровать трясете. Ужасно вы на меня похожи, такая же хохотунья… Постойте… – Она схватила обе руки графини, поцеловала на одной кость мизинца – июнь, и продолжала целовать июль, август на другой руке. – Мама, а он очень влюблен? Как на ваши глаза? В вас были так влюблены? И очень мил, очень, очень мил! Только не совсем в моем вкусе – он узкий такой, как часы столовые… Вы не понимаете?…Узкий, знаете, серый, светлый…