В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

е. такое решение может оказаться плохим. Рассмотрим граф С = С, для которого множества Уь )Гг, Уз, (и), Ы образуют разбиение УС, ! Г;! = т б (з= 1, 3), ЕС = () Е;, Е~ = (ох: х~и Ц, Ез=(ху: х~ Кь уее О, Ез=(ху: х~н $а, у~ И, Е4=(их: хану, 11 Ц, Еь = (ху: х ~ г'и у ~ 'г'и х Ф у) (см. рис. 25.4, где изображен граф 64). Летно видеть, что при любом т ~ 2 верно равенство аэ(6 ) = 2ти. В то же время мощность мпоткества М в графе 6 равна трем. Пусть снова 6 — произвольный граф, Л = Л(6) — максимум степеней его вершин. Тогда из теоремы 25.1 очевидно следует неравенство аэ(6) ~ п((Ь + 1), п = 16(, (3) 105 которое, впрочем, нетрудно получить непосредственно. Теорема Брукса (см.

з 54) дает более точную оценку: если С вЂ” связяьш граф, Л =. Л (6) - 3 н С Ф К„, то схз(С)) п~Л. (4) Эта оценка продпочтптельпео оценки (!) в случае, когда граф 6 — рогулярньш нлн близкий к регулярному. Так, l ссг Рис. 25.4 еслп С вЂ” кубический граф, то из неравенства (4) получаем ссь(С)~ пс3, в то время как (1) дает только ас(6)~ ~ и!4ч. Легко, однако, прпвестн примеры, в которых более точна оценка (1). Дальнейшее уточнение ннжней оценки числа ас(6) связано с пспользовапвем, помимо степенной последовательности, дополнительной информации о графе и суженном класса рассматриваемых графов. Следующая теорема, приводимая без доказательства, усиливает оценки (1) и (3) для рассматриваемых в ней классов графов.

Т е о р е м а 25.3 (Д. Грсчггс, 1983 г.) . Пусть С вЂ” связссый граф порядка п ~ 3, ссе содсрасащий треугольников и ссе яв,чясощийся цепью либо ссиклом иечетссой длиньс. Тогда аз(6)) " + ~~ (1+ Йенс)-с, Л = Л(6). (5) й- во Приведенное неравенство превращается в равенство тогда и только тогда, когда граф С является ссиклом четной длины или совпадает с одним из графов, изобразсессньсх па рис 35 5 Независимое множество вершин графа имеет естественную матричную интерпретацию.

Пусть Х = (эь ом ... о,) — независимое множество вершин графа 6, А = А(6) — матрица смежности. Множеству Х в матрице А соответствует подматрица, элементы которой, располоя~енпые в строках и столбцах, соответетву1ощих элементам Рнс. 25.5 множества Х, равны нулю. Такое представление позволяет получить верхню1о оценку числа ас(6) с помощью характеристических чисел матрицы А. Обозначим через р+, р и р' число положительных, отрицательных и нулевых собственных значений матрицы смежности графа соответственно. Теорема 25.4 (Д. Цветкович, 1973 г.). Для всякого срау7а 6 справедливо пераеепсгво яэ(6) -.р +ппв(р, Р+). (6) > Пусть ас(6)= — т.

В графе С есть порол|донный пустой подграф порядка т. Прп подходящей нумерации вершин этому подграфу соответствует подматрнца А' матрицы А, занимающая строки и столбцы с номерами 2, ..., т, все элементы которой равны нулю. Пусть )л »« » йэ»»... » ») н р1»» дз»... »» дщ — собственные зпачения матриц А и А' соответственно.

Эти числа связаны известными неравенствами Коши )..л < 1и < Х;, 1 = 1, т (см. [23) ). Поскольку А' — нулевая матрица, то все рэ = О. Отсюда получаем неравенства 0<ее е — н<0 1=1, т. Из этих неравенств следует, что р++ рс » ~т и р + рс > пэ, т. е. пг<рс+тп1п(р, р"). Неравенство (6) доказано. 4 Независимые множества вершин графа имеют самые равнообразные применения. Оставляя в стороне головоломки и задачи развлекательного характера, рассмотрим одно из применений независимости в теории информа- 107 цип. Возникающую здесь ситуацию можно упрощенно описать следующим образом.

Источник информации посылает сообщения, являющиеся последовательностями сигналов нз множества Х = (хп хм ..., х ). При передаче возникают (например, вследствие помех) искажения сигналов. Позтому на прннимаюгцей станции некоторые сигналы могут быть поняты как другие, т. е. перепутаны. Рассмотрим граф 6, у которого т'С =Х и х;х,~КС, если и только если х, и х могут быть перепутаны. Тогда, чтобы получить безошибочный код, т. е. исключить перепутывания, следует пользоваться сигналами пз независимого подмножества вершин графа С. Стремление получить максямальпое количество таких сигналов приводит к задаче отыскания наибольшего независимого множества вершин в графе 6. Обычно одним скгналом не ограничиваются, а посылают тексты в виде слов.

Коли все передаваемые слова имеют длину Й, то очевидно, что рассматриваемый код содержит по меньшей мере (аг(6))' слов, различаемых при приеме. Но фактически их может быть больше. Рассмотрим пример, принадлежащий К. Шенпону. Пусть 6 =Се — простой цикл дчпны 5 с вершинами, пронумерованными числами 1, 2, ..., 5 в порядке следования по циклу. Тогда ио (6) = 2, (1, 3) — наибольшее независимое множество вершин графа С. Это множество дает 4 слова (1, 1), (1, 3), (3, 1), (3, 3) длины 2, которыо разли галсы, т.

о. прп приеме не могут быть приняты одно в качестве другого. Однако 5 слов (1, 1), (2, 3), (3, 5), (4, 2), (5, 4) также различимы. Максимальное число различимых слов удобно описывается с помощью вводимых ниже терминов. Пусть С вЂ” произвольный граф, й— натуральное число. Оледуюгцнм образом ряс 28.8 определим граф С" — сильную степень графа С. Множество вершин графа 6' совпадает с декартовой степенью (|тС)', несовпадающие вершины (ип иг,..., ит) и (ип ип..., и,) смежны в графе С' тогда н только тогда, когда для каждого индекса 1= = 1, й выполняотся условие и; = и; или и;и;~п ЕС. Иа рис.

25.3 изображен граф Сп где 6 = Рг. Очевидно, что если графу 6 придается тот же смысл, что и в описанной выше задаче из теории информации, то наибольшее число различимых слов длины й равно 108 числу независимости ас(С"). Очевидно также, что ис(6ь) > ~(ас(6) ) ° К. Шеннон ввел параметр 0(6) = зпр У ав(С~), ь>1 называемый теперь шенноновской емкостью вра4а 6.

Из предыдущего следует, что 9(6)>ив(6) и что в общем случае это неравенство не превращается в равенство. Вычисление шенноновской емкости является очень трудной задачей даже для графов с небольшим числом вершин. Шенноном доказано, что если число кликового покрытия с (6) (см. з 26) удовлетворяет равенству с(6)=аз(6), то 0(6)=аз(6).

Таковы, например, все совершенные графы (см. з 61). Однако последнее равенство неверно у1ке для простейшего графа, не являющегося совершенным, а именно для цикла Сы Л. Ловас доказал, что 0(Сз)= 75. Получение этого частного результата потребовало немалых ухищрений, развитая при этом техника позволяет находить шенноновские емкости ряда других графов. С понятием независимости в графе связано понятие доминирования. Подмнонгество У вершин графа 6 пазывается доминирующим (или внешне устойчивым), если каждая вершина из УС~У' смежна с некоторой вершиной из У. Иначе говоря, каждая вершина графа находится па расстоянии не более 1 от доминирующего множества. Доминирующее множество называется минимальным, если никакое его собственное подмножество пе является доминирующим.

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

25.7. Подмножество вершин графа, являющееся как независимым, так и доминирующим, называется ядром. 109 Очевидно, что независимое множество является максимальным (пе обязательно наибольшим) тогда и только тогда, когда оно доминирующее. Таким образом, ядра графа — зто максимальные незавпсимыо множества вершин. С другой стороны, доминирующее множество не обязательно независимо. Например, множества вершин 11, 2, 3, 7), 11, 2, 3, 8), 12, 3, 5, 7), 12, 3, 5, 8), (4, 7) являются ядрами графа, изображенного на рис. 25.2. Наименьшее доминирующее множество вершин цепи Р4 состоит из двух смежных 'Ь' вершин.

Понятия доминирую- У щего множества и ядра естественным образом переносятся и на случай ориентированных с7 графов. Получаемые при этом результаты более интересны, чем в случае неориентированных графов (см. з 67). Отыскание в графе наименьшего доминируРвс. 25.7 ющего множества явля- ется содержанием многих прикладных задач. Типпшая ситуация, в которой возникает подобная задача, такова. Имеется множество населенных пунктов, связанных дорожной сетью. В некоторых пз ш1х надо разместить предприятия обслуживания так, чтобы расстояние от каждого из населенных пунктов до какого-либо пз предприятий не превосходило заданной величины.

Размещение следует выполнить так, чтобы обойтись минимальным количеством предприятий. Коли поставить в соответствие населенным пунктам вершины графа, в котором две вершины смежны тогда и только тогда, когда расстояние между соответствующими пунктами не превышает заданной величины, то задача очевидно сводится к построению в графе наименьшего доминирующего множоства. Введем еще одно понятие, связанное с понятием независимости. Будем говорнттч что веритна и ребро графа покрывают друг друга, если они инцидентпы. Таким образом, ребро е аЬ покрывает вершины а п Ь, а каждая из этих вершин покрывает ребро е. Подмножество à — $'С ПО называется покрытием (вершинным покрытием, опорой) графа С, если каподое ребро из ЕС ннцндентно хотя бы одной вершине нз (т'.

Характеристики

Список файлов лекций