В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 57
Текст из файла (страница 57)
Достаточность. Рассмотрим класс,Ж связных гиперграфов Н, каждый нз которых удовлетворяет условию Хелли, а реберный граф Ь(Н) является триангулированным. Доканеем, что существует реализация любого гиперграфа Н рк 'ре деревом. ср Рвс. 71.2 312 Очевидно, что если хотя бы одно из пересечений е е;й Гг(етг7', 1, 1=1, В) непусто, то непусто и () еее е =-1 а значит, любые )е попарно смежных ребер удовлетворяют условию Хелли.
Поэтому остается рассмотреть случай„ когда существуют три различные вершины и = — )'и и ш )рг, арсе )Рг. Введем следуюгцпе обозначения: Р~ — (и, и)-цепь, Рг — (и, и)-цепь, Ре — (и, ю)-цепь в графе Т. Так как Т вЂ” дерево, то р'Р, П )РРг й 1'Рг Ф И (иначе граф Т содержал бы цикл). В то же время всякое ребро е; (1= 1, й) содержит не менее двух вершин из (и, и, ир), и реализацией е; является дерево Ть Поэтому всякое дерево Т,(1= = 1, /с) содержит все вершины одной из цепей Рп Рг, Рг. Отсюда имеем й е= уР, П уР, П уРа~ а Доказательство проведем индукцией по числу ребер гиперграфа. Для гиперграфов с одним ребром утверждение очевидно. Пусть' гиперграф Н =()т, Ю) ~к Ж имеет т ~ 2 ребер (~д'~ = т) и реализация деревом любого гиперграфа из дй с меньшим числом ребер существует.
Поскольку граф Е(Н) =(д', Е) триангулированный, то в нем по теореме 62.4 существует снмплициальная вершина ео, т. е. множество вершин ео 0 У(ео) является кликой в Ь(Н). Этой вершине в гиперграфе Н соответствует ребро ео, все смежные ребра которого обозначим через ен ег, ..., е„. Так как они соответствуют вершинам У(ео) графа 1 (Н), то для любых 1= 1, й, 1= 1, й справедливо соотношение е,Пе,ФИ Поскольку гиперграф Н удовлетворяет условию Хелли, то существует вершина г, е= П еь Теперь рассмотрим г=.г новый гнперграф Н' =(И, е '), где И = У~(во~по), Ю = = (е': е' = е~(еоЪо), в~го, еФ во).
Итак, Ю'! = ~8'!— — 1 = т — 1. Поскольку ребра е„е„..., ео содержат вершину ио, а остальные ребра гиперграфа Н' остались прежними (е' = е), то гиперграф Н' также удовлетворяет условию Хелли. По той же причине граф Ь(Н ) изоморфен графу, полученному из Е(Н) путем удаления вершины, соответствующей ребру ео, т.
е. Й(П') — триангулированный граф. Следовательно, Н' ~п М. Поскольку ~Ю'~ = т — 1, то по индуктивному предположению существует реализация гнперграфа Н =()т, Р') деревом Т'. Очевидно, что реализация гнперграфа Н деревом Т получается из дерева Т' путем добавления ~евино~ новых вершин н соединения их с вершиной ио. 0 Гиперграф Н, изображенный на рис. 71.1, удовлетворяет условиям теоремы 71.1, поэтому существует его реализация деревом; это дерево 6 представлено на том же рисунке.
Говорят, что гиперграф Н удовлетворяет ослабленному условию Хелли, если для любого мнояоества попарно смежных ребер (еь ег, ..., е,) гкперграфа Н существуют две такие вергпины и, и ~к ИН, что е; П (и, и) т'- Ы для каягдого 1=1, Й. Следующие две теоремы приведем без доказательства. Т е о р е м а 71.2. Если гинерграф Н удовлетворяет ослабленному условию Хелли и его реберный граф Е(Н) 313 триангулированный, то существует реализация Н планарным графом. Теорема 71.3. Ьсли реберный граф гиперграфа Н является планарным, то существует реализация Н планарным графом. В рассмотренных выше реализациях одно и то же ребро реализующего графа может участвовать в реализации нескольких ребер гнперграфа.
Естественно возникают задачи построения таких реализаций гиперграфа, в которых зто запрещено. Пусть задан гиперграф Н=((т, Ю), ет =(ен ез, ..., е ). Строгой реализацией гиперграфа Н называется любой граф 6, удовлетворяющий следующим условиям: 1) (т6 = (тН; 2) существует такое разбиение множества Е6 ребер графа 6 на подмножества Еь Ьз, ..., Е„, что граф, индуцированный множеством Е„является реализацией ребра е, гиперграфа Н.
Конечно, всякая строгая реализация гиперграфа является его реализацией. Па рис. 71.1 граф 6" является строгой реализацией гнперграфа Н, а граф 6 не является такой реализацией (почему?). Следующий пример показывает, что гиперграф может не иметь строгой реализации.
П р и м е р. Рассмотрим гиперграф Н =(т', Ю), где (ин из оз~ оз)~ Ь ((оь озв оз)з (ин озв о4)ю (ин оэ~ оз)~ (оз, оз, озИ. Если бы существовала строгая реализация зтого гиперграфа, то она должна была бы иметь не менее 2 4 = 8 ребер, что невозможно для графа с четырьмя вершинами. Чтобы сформулировать критерий существования строгойреалнзациигиперграфа Н =()т,Ю),Ю = (еь ез, ..., е„), воспользуемся одним фактом из теории матрондов. Обозначим через 6; полный граф с множеством веры шин е; и положим Е = Е(Н) = 0 Е6;. Рассмотрим г=1 на множестве Е т таких матроидов Мь Мз, ..., М, что М~ — циклический матроид графа 6о Пусть р~ — ранговая функция матроида М~((=1, т).
Ясно, что р (Е) = ~еб— — 1. Очевидно, что существование строгой реализации гиперграфа Н = ( т', со ) равносильно существованию попарно непересекающихся баз В~ ~ М1((= 1, пз). Последнее усло- 344 вне, в свою очередь, выполняется тогда и только тогда, т когда ранг матроида М = () Ме не меньше, чем 1=1 Х Рг(Е) = лз () в'~ 1) Теперь, применив теорему 24.1, е=г г=г получим следующий критерий существования строгой реализации. Теорема 71.4.
Строгая реализация гипврграфа Н= =(У, ю) с т ребрами существует тогда и только тогда, когда для любого 'множества А шЕ выполняется неравенство ш ш ( А ( > ~л~~ ( вг ( — и — ~~з рг (Е А), г=г Отметим, что для построения строгой реализации гиперграфа существует аффективный алгоритм. УПРАЖНЕНИЯ 1. Покрытием гинерграфа Н называется такое множество вершин П ш 7Н, что П (( е Ф 8 для любого ребра е ш д'К.
Покрытие называется наименьшим, если число вершин в нем наименьшее среди всех покрытий гиперграфа. Число вершин в наименьшем покрытии гиперграфа Н обозначается через бе(Н). Покажите, что: 1) для гиперграфа Н порядка и справедливо равенство иа(Н) + бе(Н) = и; 2) множество вершин Н ш УН является покрытием гипергразра Н тогда н только тогда, когда множество УН',,Н независимо; 3) множество вершин (Г = УН является наименыпим покрытием гиперграфа Н тогда и только тогда, когда множество УН~,Б является наибольшим независимым множеством в Н. 2. Докажите, что реализация гиперграфа Н планарным графом оуществует, если кенигово представление К(Н) этого гиперграфа является планарным графом.
Приведите пример, когда такая реализация гиперграфа существует, хотя его кенигово представление — не планарный граф. 3. Пусть Н = (У, д') — гипеграф Удалением ребра ее ш Н типерграфа Н назовем операцию перехода к гиперграфу Н' = = (У, Н'), где д*' = д',еь Стягиванием ребре е, ш В' гине))графа Л назовем операцию перехода к гиперграфу Н" = (У", Ю'), где У" = (У'~ее) () еь го — новая вершина (ео Ф У), и" = д'1 () Нь Ю,=(е'. е'=(е'~ее) Ось ешв'~,еь ейеоФЯ), де=(е: е() () ее= Е, е ш Х~е,) Введением еершиньь э, ш У в ребро ее гипергрзфа Н назовем опорацию перехода от Н к гиперграфу Н' = (У', д"), где У' = 7 () еь д' = (Ю'1еа) () е*, ее = еа () ео.
Пусть существует такая вершина эе ш У, что Ю(эе) = е ш Ю', (ее( ) 1, Тогда угалекиеи вершины эе назовем переход от гнперграфа Н к Н" = (1'", Н"), где У" = У~ре, де = (д'~ее) () е*, е* = = со~ге 315 Докюкитс слсдуюп1ис утверждения: 1) если существует реализация гиперграфа Н планарным гра- фом, то супжствует такая жо реализация н гиперграфа Й полу- ченного из Н вЂ” удалепи~ м тпобото р< бра, — стягиванием любого ребра, -- введепоеьг вгрппщы в любое робро, — упалепи~ ч варнавы; 2) если существует плапарпый граф, который является реа- лизацией гипсрграфа Н, полученного из Н стягиванием каждого ребра некоторого подмножества ребер М' щ ЮН, то существует реа- лизация плапарпым графом гиперграфа, полученного нв Н стяги- ванием любого подмножества ребор е е ~ Е', Е" ед ХН. ть В про дыдуп1сй задаче опроделспы операции введения и уда- ления вершины стспони 1. Пусть г, — вершина гнперграфа Н = = ((т, Ь') степени большой, чом 1, т.
е, д'(ее) = (еь ет, ..., еа), й ) 1, причем )е~) ) 1 (1 =- 1, й). Определим операцию удаления такой вершины г, из Н как переход от гппорграфа Н к гиперграфу В = (Р, д'), где 1' = У'тга, д' = (4'М(еа)) () д',д" = () ец ез = з= — 1 = е~'~ею (1 = — 1, й). Приведите пример гинерграфа Н, для ноторо- го существует реализация плапарным графом, но не существует такой реализации гиперграфа, полученного иа Н удалением верши- ны стспепн болсо чем 1.
5. Покажите. что из существования роализации гиперграфа Н планарным графои пе следует существование таких реализаций всех сто порожденных подгиперграфов. 6. Дока>ките утверждение: для того чтобы гипеграф Н был й-раскрашиваемым, необходимо и достаточно, чтобы существовала реалнзация гипсрграфа Н, являющаяся й-раскрашиваемым графом. 7. Докажито утверждение: если существует строгая реализация гпперграфа Н = ()т, д'), то для всякого подмножества д': — Ю вы- полняется неравенство ) е ) ( ) ЕК (4*') ) + ( 8" ), екав гдо К(Р') — объединение полных графов, построенных на каждом из множеств е щ Л'. Докажите, что обратное утверждение 1) неверно; 2) верно, если )е) ( 3 для лзобого ребра е гиперграфа Н. 8. Докажите, что строгая реализация свяаного гиперграфа деревом существует тогда и только тогда, когда гиперграф не содерящт циклов. 9, Пайднто нообходнмоо и достаточное условие существования строгой реализации гиперграфа простым циклом.
Глава ХП Алгоригилы В предыдущих главах упоминались задачи теории графов, имеющие важное практическое значение. Особый интерес для приложений представляют алгоритмические аспекты таких задач. На практике важно уметь с помощью ЭВМ находить в графе наибольшее паросочетапие и наибольшее независимое множество, строить гамильтонов цикл или гамильтонову цепь, выделять связные или двусвязные компоненты и т. п. Иначе говоря, надо иметь соответствующие алгоритмы, а в конечном счете и программы для ЭВМ. Нетрудно (хотя порой и это требует некоторых усилий) для каждой из упомянутых задач разработать алгоритм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
