4430
правок
Радиораскраска в планарных графах: различия между версиями
Материал из WEGA
Радиораскраска в планарных графах (посмотреть исходный код)
Версия от 13:50, 11 апреля 2016
, 11 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Рассмотрим граф G(V, E). Обозначим для любой пары вершин u, v | Рассмотрим граф G(V, E). Обозначим для любой пары вершин <math>u, v \in V \;</math> за d(u, v) расстояние между u и v в графе G. В общем виде задачу раскраски графа G можно определить следующим образом: | ||
| Строка 10: | Строка 10: | ||
Дано: граф G(V, E). | Дано: граф G(V, E). | ||
Требуется: найти функцию | Требуется: найти функцию <math>\phi : V \mapsto \{ 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>. | ||
Цель: Пусть \<p(V)\ = A#. Тогда A^ - количество цветов, фактически используемых ' (обычно называемое порядком G относительно <p). Количество Уф = тах„еуф(у)—т1пиеуф(и)+ 1 обычно называется диапазоном графа G относительно '. Функция ' удовлетворяет одной из следующих целей: | Цель: Пусть \<p(V)\ = A#. Тогда A^ - количество цветов, фактически используемых ' (обычно называемое порядком G относительно <p). Количество Уф = тах„еуф(у)—т1пиеуф(и)+ 1 обычно называется диапазоном графа G относительно '. Функция ' удовлетворяет одной из следующих целей: | ||
| Строка 48: | Строка 48: | ||
Еще одна родственная задача заключается в раскраске квадрата графа G, G2, таким образом, чтобы никакие две соседние вершины в G2 не были раскрашены в один цвет. Целью является использование минимального числа цветов, которое обозначается /(G2) и называется хроматическим числом квадрата графа G. В [5, 6] было впервые замечено, что для любого графа G значение Xorder(G) совпадает с (вершинным) хроматическим числом G2, т.е. Xorder(G) = 2. | Еще одна родственная задача заключается в раскраске квадрата графа G, G2, таким образом, чтобы никакие две соседние вершины в G2 не были раскрашены в один цвет. Целью является использование минимального числа цветов, которое обозначается /(G2) и называется хроматическим числом квадрата графа G. В [5, 6] было впервые замечено, что для любого графа G значение Xorder(G) совпадает с (вершинным) хроматическим числом G2, т.е. Xorder(G) = 2. | ||
== Основные результаты == | == Основные результаты == | ||
