Реализации гиперграфа

Пусть задан гиперграф Н = (V, E). Реализацией гиперграфа Н называется любой граф G, удовлетворяющий следующим условиям:

1) VG = VH;

2) любое ребро графа G содержится в некотором реб­ре гиперграфа Н;

3) для любого ребра е € E порожденный подграф G(e) является связным.

Реализацией ребра е € E гиперграфа Н является лю­бой связный граф G_e, для которого VG_e = e. Поэтому

всякая реализация гиперграфа является объединением не­которых реализаций всех его ребер.

На рис. 71.1 изображены гиперграф Н и две его реа­лизации G’ и С",

Задачи построения реализации гиперграфов часто воз­никают в электронике при проектировании и изготовлении интегральных схем. Элементы такой схемы, как правило, разбиты на группы. При изготовлении схемы элементы каждой группы должны быть соединены проводниками. Таким образом, можно считать, что спроектированная схема задается с помощью гиперграфа, а изготовленная — с помощью графа, являющегося реализацией заданного гиперграфа. При этом соединять элементы можно произ­вольным способом, лишь бы получающийся в результате граф обладал заданными свойствами, например, был де­ревом, планарным или гамильтоновым графом и т. д. Следует отметить, что, как правило, задачи построения подобных реализаций являются очень сложными для ал­горитмического решения.

Сначала рассмотрим реализацию гиперграфа деревом. Для этого введем определения.

Реберным графом гиперграфа Н =(V, E) называется граф L(Н) = (E,E), множество вершин которого совпа­дает с множеством ребер E гиперграфа Н, при этом две вершины графа L(H) смежны тогда и только тогда, ког­да смежны соответствующие им ребра гиперграфа Н. Та­ким образом, L (Н)— граф пересечений ребер гипер­графа Н.

Говорят, что множество {e₁, e₂,..., e_r} попарно смеж­ных ребер удовлетворяет условию Хелли, если

или,другими словами, если существует по крайней мере одна общая вершина, инцидентная каждому ребру e_i

Если любое множество попарно смежных ребер гипер­графа Н удовлетворяет условию Хелли, то говорят, что гиперграф Н удовлетворяет условию Хелли.

Теорема 71.1. Реализация связного гиперграфа Н деревом существует тогда и только тогда, когда Н удов­летворяет условию Хелли, а реберный граф L(H) триан­гулированный.

Необходимость. Пусть для гиперграфа Н су­ществует его реализация деревом Т. Сначала покажем, что Н удовлетворяет условию Хелли. Доказательство про­ведем индукцией по мощности множества попарно смеж­ных ребер гиперграфа Н.

Два смежных ребра, конечно, удовлетворяют условию Хелли. Преположим, что любое множество попарно смеж­ных ребер в количестве к — 1 > 2 удовлетворяет условию Хелли, и рассмотрим множество {e₁, e₂,..., e_r} попарно смежных ребер гиперграфа Н. По индуктивному предположению

Очевидно, что если хотя бы одно из пересечений V_i ∩ V_j (i ≠ j, i,j = 1, 3) непусто, то непусто и ∩ e_i, а значит, любые k попарно смежных ребер удовлетворяют условию Хелли. Поэтому остается рассмотреть случай,, когда существуют три различные вершины и ≡ V₁, v € V₂ и w € V₃. Введем следующие обозначения: P₁ —(и, v) -цепь, P₂ —{v, w} -цепь, P₃ — (и, w) -цепь в графе Т. Так как; Т — дерево, то VP₁ ∩ VP₂ ∩ VP₃ ≠ ¢ (иначе граф T содер­жал бы цикл). В то же время всякое ребро e_i (i =1, k) содержит не менее двух вершин из {и, v, w}, и реализа­цией e_i является дерево T_i. Поэтому всякое дерево T_i (i = 1, k) содержит все вершины одной из цепей P₁, P₂ , P₃ Отсюда имеем

т. е. множество {e₁, e₂,..., e_r} удовлетворяет условию Хел­ли. Следовательно, гиперграф удовлетворяет условию Хелли.

Теперь методом от противного покажем, что реберный граф L(H) = (E, E) является триангулированным. Пусть в L.(H) существует порожденный простой цикл С={e₁, e₂,..., e_p, e₁}, р ≥ 4. Тогда этому циклу в Н соответствуют ребра e₁, e₂,..., e_p, такие, что смежными сре­ди них являются лишь пары ребер е₁ и е₂ , е₂ и е₃, …., е_p и е₁ (рис. 71.2), а это значит, что при реализации ребер e₁, e₂,..., e_p появится цикл. Однако это противоречит тому, что реализация Т гиперграфа Н являет­ся деревом.

Достаточность. Рассмотрим класс H связных гиперграфов H, каждый из которых удовлетворяет условию Хелли, реберный граф L (Н) является триангулированным. Докажем, что существует реализация любого гиперграфа l € H деревом.

Доказательство проведем индукцией по числу ребер типерграфа. Для гиперграфов с одним ребром утвержде­ние очевидно. Пусть гиперграф H = (V, E) € H имеет т ≥ 2 ребер (|E|=т) и реализация деревом любого гиперграфа из H с меньшим числом ребер существует. По­скольку граф L (Н) = (E, Е) триангулированный, то в нем потеореме 62.4 существует симплициальная вершина e₀, т. е. множество вершин e₀ U N(e₀) является кликой в L(H). Этой вершине в гиперграфе Н соответствует ребро e₀, все смежные ребра которого обозначим через e₁, e₂,..., e_k. Так как они соответствуют вершинам N(e₀) графа L(H), то для любых i = 1, k, j = 1, k справедливо соотношение e_i ∩ e_j ≠ ¢.

Поскольку гиперграф H удовлетворяет условию Хелли, то существует вершина v₀ € ∩ e_i. Теперь рассмотрим

новый гиперграф Н' = (V’, E’), где V’ = V \(e₀ \ v₀), E' = {е': е' ≡ e \ (e_o \ v_o), e € E, е ≠ e₀). Итак, |E'| = |E| - 1 = т - 1. Поскольку ребра е'₁, е'₂ ,..., е'_k содержат вершину v_o, а остальные ребра гиперграфа Н' остались прежними (е’ = е), то гиперграф Н' также удовлетворяет условию Хелли. По той же причине граф L(H') изоморфен графу, полученному из L(H) путем удаления верши­ны, соответствующей ребру во, т. е. L(H’) — триангулиро­ванный граф. Следовательно, Н' € H.

Поскольку |E'| = т — 1, то по индуктивному предположедию существует реализация гиперграфа Н' = (V’,E') деревом Т'. Очевидно, что реализация гиперграфа Н деревом Т получается из дерева Т' путем добавле­ния | e_o \ v_o | новых вершин и соединения их с верши­ной v_o.

Гиперграф Н, изображенный на рис. 71.1, удовлетворя­ет условиям теоремы 71.1, поэтому существует его реали­зация деревом; это дерево G' представлено на том же ри­сунке.

Говорят, что гиперграф Н удовлетворяет ослабленному условию Хелли, если для любого множества попарно смежных ребер {e₁, e₂,..., e_k } гиперграфа Н существуют две такие вершины и, v € VH, что е_i ∩ (и, v) ≠ ¢ для каждого i=1,k.

Следующие две теоремы приведем без доказатель­ства.

Теорема 71.2. Если гиперграф Н удовлетворяет ослабленному условию Хелли и его реберный граф L(H)

триангу линованный, то существует реализация Н планарным графом.

Теорема 71.3. Если реберный граф гиперграфа В является планарным, то существует реализация Н планарным графом.

В рассмотренных выше реализациях одно и то же ребро реализующего графа может участвовать в реализации нескольких ребер гиперграфа. Естественно возникают задачи построения таких реализаций гиперграфа, в которых это запрещено.

Пусть задан гиперграф

строгой реализацией гиперграфа Н называется любой граф G, удовлетворяющий следующим условиям:

1) VG = VH;

2) существует такое разбиение множества EG ребер графа G на подмножества E₁, E₂,…, E_m, что граф, индуцированный множеством E_i, является реализацией ребра E_i гиперграфа Н.

Конечно, всякая строгая реализация гиперграфа является его реализацией.

На рис. 71.1 граф G" является строгой реализацией гиперграфа Н, а граф G' не является такой реализацией (почему?). Следующий пример показывает, что гиперграф может не иметь строгой реализации.

Пример. Рассмотрим гиперграф Н =(V, E), где V= {v₁,v₂ ,v₃ , v₄},E = {{v₁,v₂ ,v₃}, {v₁,v₂ ,v₄},{v₁,v₃ ,v₃₄},{v₂,v₃ ,v₄}}. Если бы существовала строгая реализация этого гиперграфа, то она должна была бы иметь не менее 2 * 4 = 8 ребер, что невозможно для графа с четырьмя вершинами.

Чтобы сформулировать критерий существования строгой реализации гиперграфа Н =(V, E), E = {е₁,е₂ ,..., е_т}, воспользуемся одним фактом из теории матроидов.

Обозначим через G_i полный граф с множеством вер­шин е_i и положим Е = Е(Н)= U EG_i. Рассмотрим

на множестве Е т таких матроидов М₁, М₂,..., М_т, что M_i — циклический матрои д граф а G_i Пусть p_i — ранговая функция матроида M_i(i =1, m). Ясно, что p_i(E) =| e_i | — 1. Очевидно, что существование строгой реализации гиперграфа Н =(V, E) равносильно существованию попарно пепересекающихся баз В_i € M_i (i =1, m). Последнее условие, в свою очередь, выполняется тогда и только тогда,когда ранг матроида М =U M_i не меньше, чем

Теперь, применив теорему 24.1,получим следующий критерий существования строгой реа­лизации.

Теорема 71.4. Строгая реализация гиперграфа Н =(V, E) с m ребрами существует тогда и только тогда, когда для любого множества А € Е выполняется нера­венство

Отметим, что для построения строгой реализации гиперграфа существует эффективный алгоритм.

Глава XII

Алгоритмы

В предыдущих главах упоминались задачи теории гра­фов, имеющие важное практическое значение. Особый интерес для приложений представляют алгоритмические-аспекты таких задач. На практике важно уметь с помощью ЭВМ находить в графе наибольшее паросочетание и наи­большее независимое множество, строить гамильтоно» цикл или гамильтонову цепь, выделять связные или дву-связные компоненты и т. п. Иначе говоря, надо иметь соответствующие алгоритмы, а в конечном счете и про­граммы для ЭВМ.

Нетрудно (хотя порой и это требует некоторых уси­лий) для каждой из упомянутых задач разработать алго­ритм, реализующий перебор всех возможных вариантов-Такой подход, однако, как правило, неприемлем из-за чрезвычайно большого числа этих вариантов. Поэтому ну­жен не просто алгоритм, а алгоритм, в некотором смысла эффективный, причем эффективность алгоритма важна уметь оценивать a priori. Этой цели служит анализ алго­ритма.

Итак, под решением задачи «в алгоритмической поста­новке» мы будем понимать разработку и анализ соответ­ствующего алгоритма.