Дефектные раскраски и расписания / forpes.ru

Главная
Дефектные раскраски и расписания

Дефектные раскраски и расписания +2

29.07.2025 07:47

DARYIEN 1 625 Источник

В рамках Большой Математической Мастерской (БММ) на площадке Новосибирского государственного университета мы изучали тему дефектных раскрасок, их связь с расписанием. В этой статье представлены результаты нашей двухнедельной работы на БММ.

Исследования раскрасок графов ведутся с 1850-х годов. Большинство задач в этой области относится к классу NP-трудных. Основной интерес вызывают правильные раскраски, однако существуют и другие типы — например, совершенные и дефектные. В нашем проекте акцент сделан на исследовании дефектных раскрасок графов.

Теория раскрасок графов находит широкое практическое применение. Как отмечается в Википедии:

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

Мы заинтересовались задачей дефектных раскрасок графов благодаря их прикладному применению в составлении расписаний. Основная идея связи между раскраской графа и расписанием: объекты в графе, окрашенные в одинаковые цвета, будут распределены в один временной слот расписания; а объекты разных цветов — в разные слоты. Это позволяет переформулировать задачу построения оптимального расписания в терминах раскраски графа с определенными ограничениями.

Приложение: задача о расписании

Прикладная задача, в таком случае, может звучать следующим образом:

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

Вот два типа расписаний, которые мы изучали:

Расписание 1 (Время на работу):
- Каждому пользователю выделяется один интервал времени на пользование серверами с учетом порога конфликта
- Каждый пользователь может использовать любые нужные ему серверы во время отведенного ему интервала
Расписание 2 (Время на пользование сервером):
- Каждой паре пользователь-сервер выделяется свой временной интервал с учетом порога конфликта сервера
- Каждый пользователь может пользоваться только одним сервером в определенный интервал времени

Подход через вершинные раскраски

Чтобы решать задачу о расписании через раскраски графа, необходимо для начала построить граф, который будем красить. Действуем так:

По заданному множеству пользователей, серверов и запросов пользователей к серверам построим граф пользователь-сервер, в котором есть вершины-серверы, вершины-пользователи и ребро между такими двумя вершинами существует, если этот пользователь требует доступ к этому серверу.

Имея граф связей пользователь-сервер, строим граф конфликтов.

Вершины в графе конфликтов — пользователи. Вершины соединены ребром, если эти пользователи претендуют на работу с одним сервером.
Представим, что мы окрасили вершины графа. Пользователи одного цвета будут работать в одно время.
Если у любой вершины графа нет соседей того же цвета, мы получим правильную раскраску графа. Это означает, что один сервер используется одним пользователем.

Правильная раскраска — раскраска вершин графа так, что у любой вершины нет ни одного соседа ее же цвета.

Дефектная раскраска — раскраска вершин графа так, что любая вершина смежна не более, чем с соседями своего цвета. То есть правильная раскраска эквивалентна дефектной раскраске при .

На гифке показано, как получается граф связей пользователь-сервер, как из этого графа получается граф конфликта между пользователями и как получается в итоге расписание (первого типа) по уже раскрашенному графу.

Связь между расписанием и графом конфликтов

По раскраске на гифке получается такое расписание:

Вершинные раскраски

Существует множество различных алгоритмов правильной раскраски. Большинство из них приближенные, но есть и точные алгоритмы.

Точный алгоритм — алгоритм, который находит оптимальное (лучшее) решение.
Приближенный алгоритм — алгоритм, который необязательно находит оптимальное решение. Как правило такие алгоритмы выполняются быстрее, чем точные для тех же задач.
Мы адаптировали некоторые приближенные алгоритмы правильных раскрасок для дефектных раскрасок. А также попытались перевести и точный алгоритм, но потерпели поражение.

Сначала сделаем небольшое замечание о дефектной раскраске полного графа.

Обозначим $\chi_d(G)$ : дефектное хроматическое число — минимальное количество цветов, необходимое для вершинной раскраски графа с дефектном .

Для полного графа (): $\chi_d (K_n) = \left\lceil\frac{n}{d+1}\right\rceil$ цветов

Доказательство:
- порог конфликта
- количество пользователей

Если окрасить вершину и ее соседей в цвет, так как граф полный, мы больше не сможем покрасить ни какую вершину в этот цвет. Разделим граф на группы по вершин, каждую группу вершин окрасим в один цвет.
Таким образом получим $\left\lceil\frac{n}{d+1}\right\rceil$ групп, соответственно $\chi_d(K_n) = \left\lceil\frac{n}{d+1}\right\rceil$ цветов. ЧТД.

При пользователям понадобится n промежутков времени, чтобы все смогли получить доступ ко всем серверам. В этом случае будут запрещены конфликты.

При пользователям понадобится один промежуток времени, чтобы все смогли получить доступ ко всем серверам.

Это замечание пригодится как для верхней оценки количества красок графа, так и для вычисления хроматического дефектного числа. Перейдем к рассмотрению алгоритмов.

Greedy Coloring (Welsh, Powell, 1967):

GC — это жадный алгоритм правильной вершинной раскраски, который обходит граф повершинно. Порядок обхода при этом не важен, алгоритм красит каждую вершину в минимальный доступный цвет.

Алгоритм GC:

1 for all v $\in$ V do:
2 Покрасить в минимальный допустимый цвет, отличный от цветов соседей

Теорема:

Пусть и $\Delta(G)$ – макс степень вершины в G. Алгоритм GC, примененный к G,

использует не более $\Delta (G) + 1$ цветов,
имеет оценку точности не более $\frac{\Delta (G) + 1}{2} \leq \frac{n}{2}$

Доказательство:

$GC(G) ≤ \Delta + 1$ : каждом шаге рассматриваемая вершина имеет не более ∆ соседей ⇒ не более ∆ цветов запрещены.
Оценка точности: $\chi (G) = 1$ , то алгоритм использует 1 цвет. Если $\chi (G) ≥ 2$ , то
$\frac{GC(G)}{\chi(G)} \leq \frac{\Delta(G) + 1}{2}$ . ЧТД.

Замечание:

Жадный алгоритм дает оценку на хроматическое число:
$\chi (G) \leq\Delta (G) + 1$ , где $\Delta (G)$ — макс. степень вершины в G.

Greedy Defective Coloring (GDC)

Greedy Defective Coloring представляет собой алгоритм Greedy Coloring, адаптированный для дефектной раскраски графов.
GDC — это жадный алгоритм дефектной вершинной раскраски. Красит каждую новую вершину графа в самый первый из доступных цветов. Для этого проверяет, что при покраске в этот цвет не нарушается порог конфликта.

Алгоритм GDC:

1    for all v $\in$ V do:
2    for all i $\in$ C do:
3        if все соседи (включая её саму) вершины v имеют дефект цвета i меньше d:
4            Покрасить вершину v в цвет i
5        иначе: продолжить

Оценка хроматического числа GDC

Действуя по аналогии GC, мы оценили сколько в худшем случае будет использовано цветов GDC. Это даёт как оценку на хроматическое дефектное число, так и оценку точности алгоритма.

Представим, что алгоритм использовал цвет. Тогда для того, чтобы получить вершину последнего цвета, у нее должно быть хотя бы по одному соседу каждого цвета. И при этом у каждого ее соседа есть еще d соседей своего цвета.

Тогда $\deg(v) \geq d + (k - 1) + 1$

Следовательно, $\Delta(G) \leq d + (k - 1) + 1$

Из этого получаем для GDC(G): $\mathrm{GDC}(G) = k + 1 \leq \Delta(G) - d + 1$

Отсюда следует неравенство для обобщённого хроматического числа: $\chi_d(G) \leq \Delta(G) - d + 1$

Если $\chi_d(G) = 1$ , то алгоритм использует 1 цвет. Если $\chi_d(G) ≥ 2$ , то точность GDC:

$\frac{GDC(G)}{\chi_d(G)} \leq \frac{\Delta(G) + 1 - d}{2}$

Greedy Independent Set Coloring:

Есть другой жадный подход в правильных раскрасках: знаем, что независимое множество в графе можно красить в один цвет. Будем искать независимые множества, красить их в какой-то цвет и убирать из графа.

Независимое множество — это множество попарно несмежных вершин графа.

Как найти независимое множество? Можно снова использовать жадный подход: на каждом шаге выбираем вершину и затем удаляем ее из графа вместе с соседями.

Хочется построить множество побольше, следовательно на каждом шаге стоит выбирать вершину минимальной степени.

Алгоритм GISC:

1    procedure FindIndSet (G = (V, E))
2       = $\emptyset$
3      repeat
4        Найти вершину мин. степени в G.
5         $S = S \cup \{v\}$
6        убрать из вместе с соседями
7      until G = $\emptyset$
8    Положить текущий цвет
9    repeat
10       = FindIndSet(G)
11      Красим вершины в цвет c, затем \
12      Inc(c)
13    until G = $\emptyset$

Заметим:

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

Greedy Defective Set Coloring (GDSC):

Greedy Defective Set Coloring представляет собой алгоритм Greedy Independent Set Coloring, адаптированный для дефектной раскраски графов.

Алгоритм GDSC ищет такие подграфы, что максимальная степень вершины в них не превышает порог конфликта. После этого окрашивает подграф в один цвет и повторяет это, пока все вершины не будут окрашены. Чтобы получать подграфы наибольшие по размеру, будем как и в GISC, выбирать сначала вершины наименьшей степени.

Алгоритм GDSC:

1    procedure FindDefSet (G = (V, E), d)
2      S = $\emptyset$
3      , , $\ldots$ , — вершины, отсортированные по возрастанию
4      for i = 1, $\ldots$ , n do:
5        S = S $\cup \{v_i\}$
6        if $\Delta(S)$ > d:
7          S = S $\setminus \{v_i\}$
8      return S
9    Begin
10      G = (V, E)
11      Положить текущий цвет
12      repeat
13        S = FindDefSet(G)
14        Красим вершины S в цвет c
15         \
16        Inc(c)
17      until G = $\emptyset$

Connection-Contraction (Зыков, 1949)

В отличие от двух предыдущих жадных алгоритмов, этот алгоритм точный.
Полезное наблюдение:
Если — правильная раскраска графа в $\chi(G)$ цветов и , — пара несмежных вершин графа , то:
Если $c(u) \neq c(v)$ , то — минимальная раскраска и для графа $G \cup (u,v)$ (это граф , которому добавили ребро ).
Если , то $c|_{u=v}$ — минимальная раскраска и для графа $G|_{u=v}$ .
Здесь $G|_{u=v}$ — граф, полученный склейкой вершин и : вершины и заменили на новую вершину , которая смежна со всеми соседями вершин и графа .
$c|_{u=v}$ — раскраска, которую перенесли с графа на граф $G|_{u=v}$ , окрасив вершину в тот же цвет, в который были окрашены вершины и .

Отсюда получаем рекуррентное соотношение

$\chi(G) = min\{\chi(G\ \cup\ (u,\ v)),\ \chi(G|_{u=v})\},\ \forall(u,v)\notin E(G)$

Пусть — неполный граф. Выбираем пару несмежных вершин и либо соединяем их, либо объединяем. Один из полученных графов имеет то же хром. число, что и исходный. Повторяем процесс, пока не получим набор полных графов. $\chi(G)$ = размеру минимального графа из набора.

Замечание:
Задача правильной вершинной раскраски графа является NP-трудной, а значит точный алгоритм не может работать быстро. В данном случае ветвление может быть экспоненциальным числом от количества вершин в изначальном графе. Даже в случае, если мы будем хранить текущий рекорд и обрезать ветки перебора, всё равно объем перебора может получиться экспоненциальным.

Попытка получения точного алгоритма для дефектной раскраски

Примечание: Если вершина имеет соседей цвета , скажем что вершина имеет — конфликт цвета .

Дефектное хроматическое число

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

$\chi(G) = min\{\chi(G\ | \ c(v) = c(u)),\ \chi(G \ | \ c(v) \neq c(u))\},\ \forall(u,v)\notin E(G)$

где — цвет вершины , которая эквивалентна

$\chi(G) = min\{\chi(G\ \cup\ (u,\ v)),\ \chi(G|_{u=v})\},\ \forall(u,v)\notin E(G)$

В правильной раскраске у нас всего 2 действия, которые алгоритм выполняет рекуррентно:

соединение несмежных вершины разного цвета,
слияние двух несмежных вершин одинакового цвета .

Первая формула, очевидно, верна и для дефектных раскрасок. Но в их случае такие действия слияния и соединения ребром несмежных вершин не будут гарантировать полный перебор, т.к. соединение ребром двух несмежных вершин не эквивалентно тому, что они разных цветов из-за порога конфликта. То же самое и со слиянием вершин.

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

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

соединение ребром несмежных вершины разного цвета,
слияние двух несмежных вершин одинакового цвета .
соединение ребром несмежных вершины одинакового цвета,
слияние двух несмежных вершин разного цвета .

В ситуации, где мы соединяем ребром разноцветные вершины, мы не изменяем “конфликт цвета c” ни одной из вершин и спокойно можем рекуррентно продолжить выполнять алгоритм

НО, в трех других случаях мы сталкиваемся с проблемой:
важно понимать, что “конфликт цвета c” может измениться и превысить порог конфликта либо у полученной в результате слияния вершины и у ее соседей, либо у вершин, соединенных ребром.

Из-за этого нюанса не удалось построить точный алгоритм вершинной дефектной раскраски и составить рекуррентную формулу вычисления количества допустимых раскрасок, существующую для правильных:

$P(G,q) = P(G\ \cup\ (u,\ v), q) \ + \ P(G|_{u=v}, q)$

Реберная раскраска

Расписание, составленное на основе реберной раскраски графа похоже на расписание на основе вершинной тем, что один цвет означает один временной слот. Но в реберной раскраске:

красится граф пользователь-сервер;
во временном слоте пользователь может работать только с конкретными серверами.

На этом все наши наработки в вершинных раскрасках закончились и пришло время начать тему реберных раскрасок.

Дефектной реберной раскраской графа назовем присвоение цветов ребрам графа таким образом, что у каждой вершины не более d одноцветных инцидентных ей ребер (при получим правильную реберную раскраску).

Теорема Визинга

Ключевой теоремой в теме реберных раскрасок является теорема Визинга:

Хроматический индекс любого графа равен либо максимальной степени вершин графа, либо больше ее на единицу
то есть $\chi ^{,}(G) = \Delta(G)+1$ или $\chi ^{,} = \Delta(G)$ ,
где $\Delta(G)$ – максимальная степень вершин графа.

Хроматический индекс $\chi ^{,} (G)$ — минимальное количество цветов, необходимых для раскраски ребер графа так, чтобы инцидентные ребра имели разные цвета.

Алгоритм Кёнига для правильной раскраски

Теорема Визинга применима для любых графов, а мы будем работать только с двудольными графами, так как граф пользователь-сервер является двудольным.
Поэтому будем опираться на алгоритм Кёнига.

Для того, чтобы бы получить алгоритм Кёнига, нужен алгоритм раскраски регулярных двудольных графов:

Для того, чтобы раскрасить $\Delta$ -регулярный двудольный граф правильной раскраской:

Находим совершенное паросочетание (для $\Delta$ -регулярного двудольного графа гарантируется наличие совершенного паросочетания).
Паросочетание — это набор не инцидентных ребер.
Совершенное паросочетание — это паросочетание, которое покрывает все вершины графа.
Красим рёбра из найденного паросочетания в один цвет. И удалим это паросочетание из графа, при этом граф станет $(\Delta-1)$ -регулярным, так как у каждой вершины степень уменьшится на 1.
Выделим следующее совершенное паросочетание, раскрасим его в следующий цвет.
Повторим процедуру до тех пор, пока не раскрасим все ребра исходного графа.
Очевидно, что окрасим ребра графа в итоге в $\Delta(G)$ цветов.

На самом деле любой двудольный граф можно раскрасить в $\Delta$ цветов, и для этого нужно:

Построить копию графа и соединить вершины с их копиями нужным числом рёбер так, чтобы получить $\Delta$ -регулярный двудольный граф. На самом деле получится мультиграф, потому что между вершиной и его копией может быть больше одного ребра
Найти совершенное паросочетание в $\Delta$ -регулярном графе и раскрасить его.
Взять следующее совершенное паросочетание и повторять до тех пор, пока не будут закрашены все рёбра в исходном графе.
В итоге граф окрасится в $\Delta(G)$ цветов.
Удаляем копию изначального графа.

Алгоритм Кёнига:

1    По данному графу G построить граф H — $\Delta(G)$ -регулярный надграф, $H \subseteq G$ .
2    for to $\Delta$ do
3        Найти совершенное паросочетание $M \subseteq H$
4        Покрасить в цвет
5        Обновить $H = H \setminus M$

Алгоритм Кёнига для дефектной раскраски

Перейдем к тому, что мы адаптировали под дефектные раскраски в разделе реберных.

По аналогии с правильными раскрасками, получим сначала алгоритм покраски $\Delta(G)$ -регулярных двудольных графов с учетом порога конфликта .

Утверждение. Любой $\Delta$ -регулярный двудольный граф c порогом конфликта
$(\left\lceil \frac{\Delta}{d} \right\rceil, d)$ -раскрашиваемый (это означает, что его можно покрасить в $\left\lceil \frac{\Delta}{d} \right\rceil$ цветов)

Доказательство:
Совершенное паросочетание покрывает все вершины графа. Берем совершенных паросочетаний.
Это означает, что из каждой вершины исходят “пучки” по ребер
Раскрасим их в один цвет.

Степень каждой вершины в графе равна $\Delta$ , следовательно кол-во таких “пучков” равно $\left\lceil \frac{\Delta}{d} \right\rceil$ . Это означает, что можно найти покрытие регулярного двудольного графа совершенными паросочетаниями (их будет $\Delta$ штук). Затем разбить их на группы по d паросочетаний и каждую группу окрасить в свой цвет. Значит и дефектный хроматический индекс равен $\left\lceil \frac{\Delta}{d} \right\rceil$ . ЧТД.

Далее по аналогии с алгоритмом Кёнига получаем алгоритм дефектной раскраски любого двудольного графа:

Утверждение. Любой двудольный граф ( $\left\lceil \frac{\Delta}{d} \right\rceil$ , )-раскрашиваемый:

Доказательство. Если граф нерегулярный, дополним его до регулярного:

построим его копию , и соединим каждую вершину из () c из () с помощью $(\Delta(G)-deg(v))$ ребер. Полученный $\Delta(G)$ -регулярный двудольный мультиграф назовём . В находим $\Delta$ совершенных паросочетаний, объединяем их в группы по штук, красим отдельно каждую группу паросочетаний. В итоге сужаем раскраску до раскраски графа . ЧТД.

Из всех размышлений получаем точный и полиномиальный (т.к. поиск совершенного паросочетания — полиномиально разрешимая задача) алгоритм.

Дефектный алгоритм Кёнига:

1    По данному графу G построить $\Delta(G)$ -регулярный надграф H — $H \subseteq G$ .
2    for to $\left\lceil \frac{\Delta}{d} \right\rceil$ do
3        Найти совершенных паросочетаний $M \subseteq H$
4        Покрасить в цвет
5        Обновить $H = H \setminus M$

Алгоритм “Размножения серверов”

Вернемся к задаче расписания доступа к серверам. Будем ставить в расписание не пользователя, а пару пользователь-сервер. Таким образом каждый пользователь будет иметь отдельный временной слот для работы с каждым отдельным сервером, который ему нужен. При этом одним сервером может пользоваться несколько пользователей одновременно.

Представим граф пользователь-сервер. В изначальной формулировке задачи говорилось, что “на каждом сервере может работать одновременно не более человек”. То есть порог конфликта есть, но он актуален только для серверов. Будем считать, что пользователь при этом не может разорваться и работать более, чем на одном сервере одновременно. Для графа описанное расписание означает реберную раскраску, которую мы будем называть полудефектной.

Итак, полудефектная реберная раскраска двудольного графа — это раскраска ребер двудольного графа такая, что:

вершинам одной доли (вершинам-пользователям) инцидентны рёбра разных цветов;
вершинам второй доли (вершинам-серверам) могут быть инцидентны не более, чем (порог конфликта) одноцветных рёбер.

То есть для одной доли графа раскраска будет правильной, а для другой доли раскраска будет дефектной с порогом конфликта .

Используем такой подход:
Если на каждом сервере может единовременно работать не более человек, то можно представить, что это различных серверов, на каждом из которых работает отдельный пользователь.

Мы можем размножить каждый сервер на “подсерверов”. Случайно распределим пользователей этого сервера поровну между его подсерверами. В полученном графе сохранилась максимальная степень вершины-пользователя, а максимальная степень вершины-серверы стала равна $\left\lceil \frac{\Delta s }{d} \right\rceil$ , где $\Delta s$ — максимальная степень вершины-сервера изначального графа. Полученный граф можно раскрасить правильно, используя алгоритм Кёнига для двудольных графов.
Тогда мы можем правильно раскрасить его в $max(\Delta u, \left\lceil \frac{\Delta s }{d} \right\rceil)$ цветов, а потом обратно слить копии сервера в единый.

Заметим, что в каждом сервере не более подсерверов, у каждого из которых не более одного ребра каждого цвета (т.к. раскраска правильная). А значит в итоге из вершины-сервера будет выходить не более ребер каждого цвета.

Алгоритм «Размножения серверов»:

1        Размножаем каждую вершину сервера на вершин.
2        Распределить ребра, инцидентные этой вершине поровну между её копиями.
3        Получили граф .
4        По данному графу построить $\Delta(G')$ -регулярный надграф $H \subseteq G'$ .
5        for to $\max(\Delta_u, \left\lceil \frac{\Delta_s}{d} \right\rceil)$ do
6            Найти совершенное паросочетание $M \subseteq H$
7            Покрасить в цвет
8            Положить $H = H \setminus M$ .
9        Слить все размноженные вершины серверов.

Замечание по полудефектным раскраскам:

Т.к. у вершины-пользователя порог конфликта равен нулю, для раскраски понадобится как минимум $\Delta u$ цветов.
При этом т.к. у каждой вершины-сервера порог конфликта равен , для раскраски понадобится как минимум $\left\lceil \frac{\Delta s }{d} \right\rceil$ цветов.

А алгоритм размножения серверов красит граф ровно в $max(\Delta u, \left\lceil\frac{\Delta s}{d} \right\rceil)$ цветов.
Это означает, что $\chi^{’’}_d(G)=max(\Delta u, \left\lceil \frac{\Delta s }{d} \right\rceil)$ , где $\chi^{’’}_d(G)$ — минимальное число цветов, необходимое для полудефектной реберной раскраски двудольного графа.

Greedy Defective Edge Coloring

Полиномиальный перебор паросочетаний в предыдущих алгоритмах приводит к точному решению. Но, как мы понимаем, полиномы бывают разных степеней. Можно было бы получить новый приближенный алгоритм, который будет работать ещё быстрее, чем предыдущий точный.
Используем жадный подход: будем перебирать рёбра, красить их в подходящий цвет. Вопрос тогда только в том, как именно перебирать рёбра. Появилась идея ввести вес ребра, а перебор реализовывать по порядку весов. Разумно полагать, что вес ребра должен зависеть от степени пользователя и сервера, которых оно связывает.
Итак, получили алгоритм GDEC:

Обозначения:
— количество цветов
— множество одноцветных рёбер. Изначально $H = \emptyset$
$\Delta_u(H)$ — максимальная степень вершины из доли подграфа , индуцированного рёбрами из
$\Delta_s(H)$ — максимальная степень вершины из доли подграфа , индуцированного рёбрами из
— множество весов рёбер
$w(e) = \frac{\deg(V_s)}{\deg(V_u)}$ — вес ребра

Алгоритм GDEC:

1    Сортируем по возрастанию весов.
2    procedure MonochromeSetEdges:
3         $H = \emptyset$
4        for in do
5             $H = H \cup \{e\}$
6            if $\Delta_u(H)>1$ $\text{or}$ $\Delta_s(H)>d$ then
7                 $H = H \setminus \{e\}$
8         return
9     Пусть
10    repeat
11         = MonochromeSetEdges
12        Красим подмножество рёбер из в цвет
13         $E(G') = E(G') \setminus H$
14        Inc
15    until $E(G') = \emptyset$

Вывод:

Идея с присваиванием каждому ребру вес оказалась бессмысленной, так как алгоритм GDEC и жадный алгоритм, выбирающий любые рёбра, могут ошибаться в одинаковое количество раз (около 2-х раз). Помимо того, в GDEC повышается временная сложность, т.к. добавляется действие (присвоение веса).

Заключение

Большая математическая мастерская (БММ) — это мероприятие, помогающее молодым любителям математики, студентам и действующим исследователям работать над открытыми проблемами. Здесь можно развивать свои способности в написании проектов, в выступлениях на заинтересованную публику. Можно общаться с людьми, которые уже добились многого в науке, чтобы узнавать новое. Здесь можно найти своих единомышленников, общаться, объединяться с ними и работать над поставленными задачами в области математики. Это является одним из главнейших принципов БММ — продуктивная коммуникация.

Во время работы над проектом мы получили много нового опыта и впечатлений. Мы познакомились с интересными экспертами, которые помогли нам проверить наши теории.

Особую благодарность хотим выразить и.о. заведующего кафедры Теоретической кибернетики НГУ Тахонову Ивану Ивановичу, который не только помог углубиться в задачу, но и оказал неоценимую помощь в её решении. Также мы благодарим организаторов, которые обеспечили комфортные условия для работы и стали настоящими друзьями для всех участников Мастерской. Конечно же, без одного человека наша проектная работа на БММ абсолютно не состоялось бы. Это наш куратор — Сирина Татьяна. Спасибо большое Татьяне за абсолютную включенность в работу, и за умение быть настоящим куратором: где-то уйти в сторону и дать команде самой разобраться с проблемой, а где-то помочь или объяснить.

Благодаря БММ мы смогли реализовать наш проект и внести вклад в популяризацию науки, в частности математики. Мы выражаем благодарность всем участникам и организаторам, которые сделали это возможным. Наша команда уверена, что полученные результаты будут полезны дальнейшим исследователям в этой области математики.

Команда проекта:
Сморогов Александр https://t.me/smorogov07
Жаворонков Никита https://t.me/NikitaZhav
Татауров Савелий https://t.me/Pylmo4ka
Горелова Анна https://t.me/Nyusya2121
Валентинова Авелиция https://t.me/mmmkett

Комментарии (1)

wataru
29.07.2025 11:26
#28633186
Вопрос вызывает самый первый шаг, где идет переход от расписания к раскраскам в графе конфликтов.

Да, в правильной раскраске (с дефектом не более d) ни один сервер не будет нагружен более чем на d, если разные цвета пускать ко всем серверам отдельно.

Но нет, правильное расписание может соответствовать и не правильной раскраске (более d соседей у какой-то вершины того же цвета). Потому что эти >d конфликтов могут быть размазаны по разным серверам.

Вот контрпример: d=2, 4 пользователя {1,2,3,4} и 3 сервера {a,b,c}. Пользователь 1 хочет все сервера 1->a 1->b 1->c, остальные пользователи 2-4 хотят только один свой сервер 2->a 3->b 4->c. В итоге каждый сервер требуется только двумя ползователями, поэтому можно их всех четырех пустить сразу. Но граф конфликтов будет "звездой": пользователь 1 конфликтует со всеми остальными пользователями: ребра 1-2, 1-3, 1-4. В раскраске одним цветом вы получите более чем 2-дефектную раскраску. Т.е. решая задачу раскраски вы меньше чем в 2 слота расписание не составите, а оно есть.

Таким образом, задачу раскрасок можно свести к расписанию, но расписания к раскраскам - нет.