Гиперграф

Пример гиперграфа: [math]\displaystyle{ V = \{v_1, v_2, v_3, v_4, v_5, v_6, v_7\} }[/math], [math]\displaystyle{ E= \{e_1,e_2,e_3,e_4\} }[/math] [math]\displaystyle{ =\{\{v_1, v_2, v_3\}, \{v_2,v_3\}, }[/math] [math]\displaystyle{ \{v_3,v_5,v_6\},\{v_4\}\} }[/math].

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

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

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

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

Литература

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