Оптимальная раскраска ребер в двудольных графах

Я столкнулся со следующей проблемой: найти оптимальную раскраску ребер в двудольном графе. Я знаю, что жадный алгоритм раскраски иногда не может вернуть оптимальное количество цветов. Под «жадным алгоритмом раскраски» я подразумеваю: выберите первую вершину с наивысшей степенью и раскрасьте ее края в цвета 1 ... степени, затем выберите вершину со степенью ‹= предыдущей степени и раскрасьте каждое ее инцидентное ребро на первом доступное число (наименьшее число, которое не используется его соседом), выбирает следующую вершину и т. д.

Но я ввел одну модификацию: ребра первой выбранной вершины I раскрашивают в порядке убывания (степень ... 1), а ребра следующих вершин, как и раньше, в 1 ... степени. Результатом этой модификации стали примеры, которые я придумал, у меня есть оптимальное количество цветов. Но я не совсем уверен, что это всегда правило. Кто-нибудь знает, оптимальна ли эта версия алгоритма раскраски краев, или, может быть, кто-нибудь сможет показать какой-нибудь контрпример?


graph algorithm graph-coloring
person adolzi    schedule 27.06.2016    source источник
comment
Вопрос, кажется, подразумевает, что ребра упорядочены. Это так? Как они заказываются?   -  person Daniel Wagner    schedule 27.06.2016
comment
Я использую матрицу смежности для представления графа, поэтому просматриваю индексы   -  person adolzi    schedule 27.06.2016

Ответы (1)


arrow_upward
1
arrow_downward

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

Поскольку все узлы, которые окрашиваются в порядке убывания, вставлены только что, все узлы в исходном контрпримере окрашиваются в порядке возрастания, следовательно, получают те же цвета, что и в исходном «наивном» жадном алгоритме. Поскольку оптимальная раскраска имеет по крайней мере столько же цветов, сколько степень исходного графа, а все только что вставленные узлы имеют меньшую степень, чем максимальная степень исходного графа, новому графу не нужно больше цветов, чем исходному. Следовательно, раскраска, производимая «сложным» алгоритмом, который все равно будет иметь больше цветов, чем необходимо для исходного графа, не оптимальна для нового графа.

Например, возьмите график, описанный в комментарии ниже, у которого есть узлы B, C, D слева и E, F, G, H справа. У него есть эти края:

B connects to E, F, and G
C connects to E, F, and G
D connects to G and H

На данный момент я предполагаю, что только первый узел, которого вы касаетесь, окрашивается в порядке убывания. (Для других узлов даже не ясно, что может означать «порядок убывания» - по убыванию от какого максимума? Степень узла может быть недостаточно высокой.)

Поэтому мы вставляем новый узел A слева и три узла I, J и K справа; подключение сейчас

A connects to I, J, and K
B connects to E, F, and G
C connects to E, F, and G
D connects to G and H

Поэтому сложный жадный алгоритм раскрасит AI-3, AJ-2, AK-1, а затем продолжит работу как наивный жадный алгоритм на оставшихся узлах.

person Daniel Wagner    schedule 27.06.2016
comment
Спасибо за ответ, но я не уверен, правильно ли понимаю эту конструкцию. Не могли бы вы добавить некоторую матрицу смежности до и после добавления узлов, чтобы изобразить это? - person adolzi; 28.06.2016
comment
@adolzi Я сделаю одно лучше: опубликуйте свой контрпример для наивного жадного алгоритма, и я покажу, как его изменить. Не могли бы вы также уточнить, какие узлы имеют убывающий порядок окраски? Только первый узел, на который вы смотрите, или каждый нечетный узел, на который вы смотрите? - person Daniel Wagner; 28.06.2016
comment
Возьмем граф G (X, Y), где X = {A, B, C} Y = {D, E, F, G}. Затем наивный жадный алгоритм раскраски раскрашивает его: AD-1, AE-2, AF-3, BD-2, BE-1, BF-4, CF-1, CG-2 и модифицированный алгоритм: AD-3, AE-2, AF-1, BD-1, BE-3, BF-2, CF-3, CG-1 - person adolzi; 28.06.2016
comment
@adolzi Вы также ответите на мой другой вопрос? Какие узлы имеют убывающий порядок окраски, только первый узел или все остальные узлы, которые вы посещаете? - person Daniel Wagner; 28.06.2016
comment
@adolzi Я обновил свой ответ примером, в котором предполагается, что только первый посещаемый вами узел окрашивается в убывающем порядке. - person Daniel Wagner; 28.06.2016