Радиораскраска в планарных графах: различия между версиями

Радиораскраска в планарных графах (посмотреть исходный код)

67 байт добавлено , 11 апреля 2016

4430

правок

@@ Строка 31: / Строка 31: @@
 Требуется: найти функцию <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, обозначим как <math>X_{order}(G) \;</math>. Наименьшее возможное число <math>v_{ \phi } = max_{v \in V } \phi (v) - min_{ u \in V } \phi (u) + 1 \;</math> (диапазон), необходимое для радиораскраски G, обозначим как Xspan(G). Функция Ф удовлетворяет одному из следующих условий:
 •	минимальный диапазон для радиораскраски:  Ф находит минимальный диапазон, т.е. Аф = Xspan(G);