В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 56
Текст из файла (страница 56)
Кроме того, будем считать, что изолированных вершин гиперграф не содержит. Гиперграф называется й-раскрашиваемым ('к-цветным), если для него существует правильная раскраска в й цветов. Хроматическое число у,(Н) — это наименьшее число цветов, достаточное для правильной раскраски гиперграфа Н. Если т(Н) = к, то гиперграф Н называется й-хроматическим. Очевидно, что разбиению множества т'Н на независимые множества Яи Яз, ..., Я„соответствует правильнан раскраска вершин гиперграфа Н )з цветами. Верно, конечно, и обратное утверждение. Теорема 70.1. Для любого гиперграфа Н порядка п справедливы неравенства Х(Н)ао(Н)> п, 2Уп ( т(Н)+ ао(Н) ( п+ 1, где ао(Н) — число независимости зиперзрафа Н, > Рассмотрим разбиение множества т'Н на независимые множества Яи Яз, ..., Ям где )з = т(Н).
Тогда будем иметь и = ~ч" ! Яз ) ( ка, (Н ) = )( (Н) а, (Н). о=1 Отсюда сразу получаем т(Н)+ ао(Н) ~ 2Уп. Далее, пусть Я вЂ” наибольшее независимое множество вершин гиперграфа Н. Окрасим все вершины из Я в один цвет и используем п — ~Я~ = п — ао(Н) других цветов для окрашивания всех вершин из р~я в разные цвета.
В результате получаем т (Н)+ ао(Н) ~ и+ 1. < Важное место в теории графов занимают верхние оценки хроматического числа в терминах степеней вершин. При естественном определении степени вершин сохраняет силу теорема Брукса. При другом определении, которое мы дадим ниже, получается более тонная оценка хроматического числа, полученная И. Томеску. Так же, как и для графов, через Ь(Н) будем обозначать наибольшую из степеней вершин гиперграфа Н: й(Н) = шах ! а (о) ~. оаон Абсолютным гииерграфом будем называть гиперграф, для любых двух вершин и и о которого существует ребро е = ио. Оказывается, справедлива следующая теорема, являющаяся обобщением теоремы Брукса (з 54).
Теорема 70.2 (Л. Ловас, 1968 г.). Если Н вЂ” связный гииерграф, отличный от абсолютного, и съ(Н)~ З,то д(н) л(н). Порядком дя(о) вершины о гиперграфа Н называется мощность наибольшего подмножества д" шЖН, ~Е'! > 2, для любых двух различных ребер е' и в" которого е'() 20о 307 0 е" =- Ы. Голи такого подмножества не существует, то по определению дв(о) = 1. Теорема 70.3 (И. Томеску, 1968 г.). Пусть Яь Лг, ..., Н, — разбиение множества УН на независимые множества. Тогда 2(Н) ( гоах гп1п(~, йз + 1), где 1=1,Ь.
й; = гпахйн(о), чнв; Доказательства двух предыдущих теорем опускаем. Коли ~Я;~ = 1 (г = 1, Ь), то учитывая очевидное неравенство Л(Н) > й(Н), где й(Н) = птах Ып(о), получаем снуя Следствие 70.4. Для любого гиперграфа Н верно неравенство у(Н) й(Н)+1. Отсюда сразу имеем (ср. со следствием 54.2) Следствие 70.5. Для любого гиперграфа Н верно неравенство у(Н) ~ А(Н)+ 1. Па первый взгляд кажется, что наличие ребер высокой степени должно способствовать снижению хроматического числа гиперграфа.
Однако это не так, как показывает следующая Теорема 70,6. Для любых целых чисел Ь>1 и Ь > 2 существует такой гиперграф Н, что )((Н) > Ь и )е~ > Ь для любого ребра е = — ЖН. г' В качестве такого гиперграфа можно взять Ь-однородный гиперграф Н, построенный по следующему правилу: УН=(оп ог, ..., о„), где и > Ь(Ь вЂ” 1), 8Н вЂ” семейство всевозможных подмножеств множества УН мощности Ь.
Поскольку ссс(Н) - Ь вЂ” 1, то на основании теоремы 70.1 у(Н) > и/(Ь вЂ” 1), т. е. ~(Н) > Ь..ч Более сильный результат приведем без доказательства. Теорема 70.7 (П. Эрдеш, А. Хайнал, 1966 г.). Для любых целых чисел Ь, !с, 1 > 2 существует Ь-однородный Ь-хроматический гиперграф, который не содержит циклов длины меньше Е. Известно, какую роль в теории графов играют бихроматические графы, т.е. графы, хроматическое число которых не превосходит 2. Простои, но очень важный критерий би- 308 хроматичности графа дал Д.
Кениг: граф не должен содержать циклов нечетной длины. Гиперграф Н тоже будем называть оихроматичгским, если д(Н) ~ 2. Для гиперграфа пока не найдено критерия бихроматичности в терминах его структуры. У т в е р ж де н и е 70.8. Если гиперграф нг содержит циклов нечетной длины, то он является бихроматичгскиль, > Доказательство проводим по той же схеме, что и доказательство теоремы 9.1, предполагая, что гнперграф Рнс. 70.1 Рис.
70.2 связен. А именно, сначала окрасим произвольную вершину и гиперграфа Н в красный цвет, затем произвольную вершину и, отличную от щ окрасим в красный цвет, если расстояние й(и, и) — четное число, и в синий цвет, если это расстояние нечетко. Коли Н вЂ” пе бихроматический гиперграф, то найдутся две смежные вершины и и ш, окрашенные в один цвет, а тогда легко обнаруживается цикл нечетной длины. О Как показывает пример гиперграфа, изображенного на рнс. 70.1, условие утверждения 70.8 не являются необходимыми. Более широкий класс бихроматическнх графов нашли лйурнье и Лас Верньяс.
Этот результат приведем без доказате,зьства. Т е о р е м а 70.9 ()К. Фурнье, М. Лас Ворньяс, 1972). Если в каждом г1иклв нечетной длины гипгрграфа Н есть три ребра, имеющие общую инуидептную вершину, то гиперграф Н является бихроматическим. Пример гиперграфа на рис. 70.1 показывает, что это достаточное условие такгке не является необходимым. Непосредственно из теоремы Кенига следует Утверждение 70.10. Если гипгрграф является бихроматическим, то он не содержит ни одного цикла нечетной длины, состоящего лишь из ребер степени 2. Пример гиперграфа, изображенного па рпс.
70.2, покаеывает, что обратное утверждение неверно. Доказательства теорем, опугденпые в этом параграфе, можно найти в [20]. 309 з 71. Реализации гиперграфа Пусть задан гиперграф Н=1У, Ю). Реааизацией гилерграфа Н называется любой граф С, удовлетворяющий следующим условиям: 1) ГС= РН; 2) любое ребро графа С содержится в некотором ребре гиперграфа Н; 3) для любого ребра е ~яд' порожденный подграф 6(е) является связным. Реализацией ребра е ~иЮ гиперграфа Н является любой связный граф С„для которого и'6, = е. Поэтому и~ Ъ и Рис, 71.1 всякая реализация гиперграфа является объединением некоторых реализаций всех его ребер.
Па рис. 71.1 изображены гиперграф Н и две его реализации С н 6 Задачи построения реализации гиперграфов часто возникают в электронике при проектировании и изготовлении 31О интегральных схем. Элементы такой схемы, как правило, разбиты на группы. При изготовлении схемы элементы каждой группы должны быть соединены проводниками. Таким образом, можно считать, что спроектированная схема задается с помощью гиперграфа, а изготовленная— с помощью графа, являющегося реализацией заданного гиперграфа.
При этом соединять элементы можно произвольным способом, лишь бы получающийся в результате граф обладал заданными свойствами, например, был деревом, планарным или гамильтоновым графом и т. д. Следует отметить, что, как правило, задачи построения подобных реализаций являются очень сложными для алгоритмического решения.
Сначала рассмотрим реализацию гиперграфа деревом. Для этого введем определения. Реберным графом гиперграфа Е1 =((т, Ю) называется граф Е (Н)=(д', Е), множество вершин которого совпадает с множеством ребер д' гиперграфа Н, при этом две вершины графа Е (Н) смежны тогда и только тогда, когда смежны соответствующие им ребра гиперграфа Н. Таким образом, Е,(Н) — граф пересечений ребер гиперграфа Н.
Говорят, что множество (еь ег, ..., ев) попарно смежных ребер удовлетворяет условию Хелли, если П в~Ф 8', нли, другими словами, если существует по крайней мере одна общая вершина, инцидентная каягдому ребру еь Если любое множество попарно смененных ребер гипертрафа Н удовлетворяет условию Холли, то говорят, что гиперграф Н удовлетворяет условию Хелли, Т е о р е м а 71.1. Реализация связного гиперграфа Н деревом существует тогда и только говда, ковда Н удовлетворяет условию Хелли, а реберный граф 1(Н) триангулированный, > Необходимость. Пусть для гпперграфа Н существует его реализация деревом Т.
Сначала покажем, что Н удовлетворяет условию Хелли. Доказательство проведем индукцией по мощности множества попарно смежных ребер гиперграфа Н. Два смежных ребра, конечно, удовлетворяют условию Хелли. Преположим, что любое множество попарно смежных ребер в количестве к — 1 ~ 2 удовлетворяет условию Хелли, и рассмотрим множество (ен ен .... е,) попарно зы смежных ребер гиперграфа Н.
11о индуктивному предположению е — г 1,=П е;~Я, Рег = П ееч~ 1ег, 1е —— е, Д ее+ 1~ т. е. множество (еп ег, ..., ее) удовлетворяет условию Хеллп. Следовательно, гиперграф удовлетворнет условию Хеппи. Теперь методом от противного покажем, что реберный граф 1 (Н)=(д, Е) является триангулированным.
Пусть в Ь(Н) существует порожденный простой цикл С=(еи ее ег,, е„, е~), р ~ 4. Тогда этому циклу в Н соответствуют ребра еи ег, ..., е„, такие, что смежными среег дп них являются лишь пары ребер ° е~ и ег, ег и ез, ..., е„и е~ (рис. 71.2), а это значит, что при реализации ребер еп ег, ..., е„появится цикл. е, ° ° Однако это противоречит тому, что реализация Т гиперграфа Н является деревом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
