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

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

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

!~6 л !. Задача составления расписаний. Предположим, что нужно прочесть несколько лекций за крат- 5 в чайшее время. Чтение каждой лекции в отдельности занимает один час, но покоторые лекции пе могут читаться одновременно (например, нх читает один п тот же лектор). Построим граф С, вершины которого бпоктивпо соответствуют лекциям, и две вершины сменены тогда и только тогда, когда соответствующие лекции нельзя читать одновременно. Очевидно, что любая правильная раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам графа, составлшощим цветной класс, читаются одновременно.

И, обратно, любое допустимое расписание определяет правильную раскраску графа С. Оптимальные расписания соответствуют минимальным раскраскам, а число часов, необходимое для прочтения всех лекций, равно у(С). 2. Задача распределения оборудоваяия. Заданы множества Р=(иь ом ..., о„) и Я=(вь вм ..., в ) работ и механизмов соответственно, Для выполнения каткдой из работ требуется некоторое время, одипаковоо длн всех работ, и некоторые механизмы.

Прн этом никакой пз механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы общее время выполнения всех работ было минимальным. Построим граф С, поло!кив т'С = И и объявив вершины гп и о; (1Ф!') смежными тогда и только тогда, когда для выполнения работ о; и о, требуется хотя бы один общий механизм.

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

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

д.), то соответствующие вершины графа соединим ребром. Вершины, имеющие один цвет при правильной раскраске этого графа, определяют шестерни, которые могут находиться на одном валу, а хроматическое число у(6) равно минимальному количеству валов, нужных для проектируемой коробки. Для некоторых графов хроматические числа найти песлоягно. Например, у(К,) = и, )((ʄ— е) = и — 1, )((К„, )= =2, у(Сг„)= 2, у(Сг„ч.~)= 3. Очевидно, что граф является 1-хроматическим тогда и только тогда, когда он пустой, а 2-хроматическим— когда оп двудольный и непустой. Обычно 2-хроматический граф называют бихроматическии.

Поэтому теорему Кепига о двудольных графах можно сформулировать в следующем виде: Теорема 53.1. Непустой граф является бихроматическин тогда и только тогда, когда он не содержит ииклов нечетной длины. Задачи определения хроматического числа и построения минимальной раскраски произвольного графа являются очень сложными, эффективные алгоритмы их решения неизвестпы. Рассмотрим простой алгоритм построения правильной раскраски, в ряде случаев приводящий к раскраскам, близким к минимальным.

Алгоритм последовательной раскраски. 1. Произвольной вершине о~ графа 6 припишем цвет 1. 2. Если вершины он ог, ..., и; раскрашены 1 цветами 2, ..., 1, 1 ( г, то новой произвольно взнтой вершине о,„~ припишем минимальный цвет, ве использованный ири раскраске вершин из ее окружения. Раскраска, н которой приводит описанный алгоритм, называется последовательной. Очевидно, что это — правильная раскраска. Для некоторых классов графов (например, полных к-дельных) последовательная раскраска является минимальной.

В общем случае это не так. Следующая теорема сводит задачу построения правильной раскраски графов к аналогичной задаче для двухсвязных графов. Теорема 53.2. Если каждый блок графа й-раскрашиваеаб то и саж граф также й-раскрашиваем. > Воспользуемся ппдукцпей по числу блоков рассматрпваомого графа. Для графа, являющегося блоком, утверждение тривиально. Предполоягим, что теорема верна для графов, состоящих из пт ~ 1 блоков.

Пусть теперь С вЂ” граф, имеющий ровно т+1 блоков,  — один из его концевых блоков,  — обьедипеиие всех остальных блоков. По индуктивному предиоложеипю оба графа В и Н являются Й-раскрашиваемыми. Зафиксируем для каждого из пнх правильную й-раскраску. Графы В и И имеют ровно одну общую вершину о. Если ее цвета в ооепх фиксированных к-раскрасках совпадают, то получена правильная й-раскраска графа 6. В противном случае нужно очевидным образом переставить цвета в одной из фиксированных раснрасок.

<~ 3 54. Оценки хроматического числа Поскольку задачу правильной раскраски точно решить трудно, то актуальны оценки хроматического числа, выражаемые в терминах более или менее просто вычислимых параметров графа. Рассмотрим несколько оценок хроматического числа, связанных со степепямп вершин графа. Обозначим через У множество всех порожденных подграфов графа 6, а через 6(6), нан обычно,— минимальную из степеней вершин графа С.

Тоо рема 54.1. Для любого графа С верно неравенство 1((6)(1+ шах 6(н). его У ь Утверятдеиие теоремы очевидно для пустых графов. Пусть 6 — произвольный )1-хроматический граф, т, ~ 2, 238 а Н вЂ” его минимальный поронсденный подграф, удовлетворягощнй условию у(Н)=т. В этом случае Х(Н вЂ” о) = ~ у — 1 для любой вершины о графа Н.

Предположим, что дедя о ( т — 1. Граф Н вЂ” о правильно раскрасим у — 1 цветами. Окрасив затем вершину о в один из этих цветов, не использованный при окраске смежных с пей вершин, получим правильную (у — 1)-раскраску графа Н. Следовательно, йейв о ) т, — 1 и 2-1< б(Н) ( б(Н). а им У Как и ранее, через Л(6) обозначим наибольшую из степеней вершин графа 6. Следствие 54.2. Для любого графа С верно неравенство Х(6) «1+ ст(6). Нокоторое улучшение последней оценки дает следующая Теорема Брукса (1941 г). Если С вЂ” связный граф не являющийся полным, и сг (6) ~ 3, то у (6) < Л (6) .

~> Пусть й(6) = и ~ 3. Очевидно, что максимальная степень воршин как<доге блока графа С не превосходит пг. Поэтому, с учетом теоремы 53.2, достаточно, не теряя общности, провести доказательство для двусвязпых графов.

Пусть С вЂ” двусвязпый граф. Сначала покажем существование в графе С таких вершин и и о, что расстояние а(и, о) равно 2 и граф 6 — и — о связен. Это очевидно, если х(6) ~ 3. Допустим, что х(6)=2. Пусть Р— мнонсество всех доминирующих вершин графа С. Поскольку С не является полным графом, то ~ т'СЮ~ ~ 2. Если Р Ф 8, то в качестве вершин и и о можно взять любые две несмеиспые вершины из Р'С'Р. Пусть Р = И. Выберем в графе С вершипу г степени пе менее трех. Если граф С вЂ” г 2-связный, то'в качестве верпшпы и возьмем г, а в качестве о — любую вершину, находящуюся от г па расстоянии 2.

Пусть х(6 — г)=1, А и  — два концевых блока графа С вЂ” г. Существуют две вершины и ш А и о ш В, не являющиеся точками сочленения графа 6 — г и смежные с вершиной г, иначе оказалось бы, что х(6)=1. Легко видеть, что граф С вЂ” и — о связен. Действительно, удаление вершин и и о не нарушает связности бло. 239 ков А и В, поэтому граф 6 — и — о — г связеп. Из того, что Йейг ~ 3, следует теперь сзнзпость графа 6 — и — о. Итак, показано существование пухзных вершин и и о, сможпых с некоторой вершиной г'.

Поскольку граф 6 — и — о связен, то его вершины можно так занумеровать числами 1, 2, ..., и — 2, что каждая вершина, кроме г~ =г, будет смехгна по крайней мере с одной вершиной, имеющей меньший номер. Теперь окрасим несмежные вершины и н о в цвет 1. Затеи будем последовательно приписывать вершинам г„г, г„з, ..., г~ один из цветов 1, 2, ..., т по следующему правилу.

Пусть й> 1 и вершины и, о, г„-г, г„-з,, гы~ уже окрашены. Так как г„смежна хотя бы с одной из вершин с меньшим номером, то степень верши/ пы г„в порожденном подграфе С(и, о, г„г,..., г,+и г,) меньше ш. Вершине г, присвоим любой цвет, не использованный при раскраске смехгных с ней вершин. Так же поступим н с вершиной Гнс. 543 гь Так как йедг~ ~ тп и хотя бы две вершины из окружения вершины г~ (и и о) окрашены в один цвет, то в множестве цветов (1, 2, ..., т) существует цвет, не использованный при раскраске вершин из этого окружения. Этот цвет и припишем вершине гь Очевидно, что получена правильная и-раскраска графа 6. <з Оценка, устанавливаемая теоремой Брукса, достих<има.

Так, для кубического графа 6, изображенного на рис. 54.1, существует правильная З-раскраска, а правильная 2-раскраска невозможна, ибо это не двудольпый граф. Следовательно, т(6)= 3 =Л(6). Однако теорема может дать и завышенную оценку хроматического числа. Например, из этой теоремы следует, что у (К~ „) ( и, в то время как д(К~ „) = 2. Две вершины графа называются соуветными относительно некоторой правильной раскраски, если прн этой раскраске они имеют один цвет. Следствие 54.3, При любой минимальной раскраске связного неполного графа существуют две соуветпые относительно этой раскраски вершины, расстояние между которыми равно 2. 1> Пусть С вЂ” связный неполный граф. При )(= )( (6) = 240 = 2 утверждение тривиально, так как в этом случае 6 является связным двудольным графом, имеющим пе менее трех вершин.

Если т ~ 3, то из предыдущей теоремы следует, что граф содержит хотя бы одну вершину и, для которой дед и ~ т, Поэтому среди смоячпых с и вершин найдутся по крайней море две верзпины, имеющие один цвет. з Следующая теорема связывает хроматическое число графа с числами его вершин и ребер. Теор е м а 54.4 (А. П. Ершов, Г. И. Кожухин, 1962 г.) . Для любого связного (и, т)-графа 6 верны неравенства -~-.П"."1(1-1" "И01+ 1"."ИЛ- ~ 3 + ~/9 + 8 (и — в) ~ (Напомним, что пара [ ) квадратных скобок означает целузо часть числа, а пара ( ) фигурных скобок — дробну|о часть.) ~> Докажем только правое неравенство (доказательство левого громоздко).

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

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