4430
правок
Радиораскраска в планарных графах: различия между версиями
Материал из WEGA
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 16:31, 11 апреля 2016
, 11 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
Дано: граф G(V, E). | Дано: граф G(V, E). | ||
Требуется: найти функцию <math>\phi : V \ | Требуется: найти функцию <math>\phi : V \to \{ 1, ..., \infty \} \;</math>, называемую ''k-раскраской графа'' G, такую, что <math>\forall u, v \in V, x \in \{0, 1, ..., k \} \;</math>: если <math>d(u, v) \ge k - x + 1 \;</math>, то <math>| \phi(u) - \phi(v)| = x \;</math>. | ||
Цель: Пусть <math>| \phi (V) | = \lambda_{ \phi } \;</math>. Тогда <math>\lambda_{ \phi } \;</math> - ''количество цветов'', фактически используемых <math>\phi \;</math> (обычно называемое ''порядком'' G относительно <math>\phi \;</math>). Количество <math>v_{ \phi } = max_{v \in V } \phi (v) - min_{ u \in V } \phi (u) + 1 \;</math> обычно называется ''диапазоном'' графа G относительно <math>\phi \;</math>. Функция <math>\phi \;</math> удовлетворяет одной из следующих целей: | Цель: Пусть <math>| \phi (V) | = \lambda_{ \phi } \;</math>. Тогда <math>\lambda_{ \phi } \;</math> - ''количество цветов'', фактически используемых <math>\phi \;</math> (обычно называемое ''порядком'' G относительно <math>\phi \;</math>). Количество <math>v_{ \phi } = max_{v \in V } \phi (v) - min_{ u \in V } \phi (u) + 1 \;</math> обычно называется ''диапазоном'' графа G относительно <math>\phi \;</math>. Функция <math>\phi \;</math> удовлетворяет одной из следующих целей: | ||
| Строка 29: | Строка 29: | ||
Дано: граф G(V, E). | Дано: граф G(V, E). | ||
Требуется: найти функцию | Требуется: найти функцию <math>\Phi : V \to N^* \;</math>, такую, что <math>| \Phi (u) - \Phi (v) | \ge 2 \;</math>, если d(u, v) = 1, и <math>| \Phi (u) - \Phi (v) | \ge 1 \;</math>, если d(u, v) = 2. | ||
Цель: наименьшее возможное число (порядок), необходимое для радиораскраски G, обозначим как Xorder(G). Наименьшее возможное число maxv2V Ф(у) — minu2V Ф(и) + 1 (диапазон), необходимое для радиораскраски G, обозначим как Xspan(G). Функция Ф удовлетворяет одному из следующих условий: | Цель: наименьшее возможное число (порядок), необходимое для радиораскраски G, обозначим как Xorder(G). Наименьшее возможное число maxv2V Ф(у) — minu2V Ф(и) + 1 (диапазон), необходимое для радиораскраски G, обозначим как Xspan(G). Функция Ф удовлетворяет одному из следующих условий: | ||
