4551
правка
Редукция данных для доминирования в графах: различия между версиями
Перейти к навигации
Перейти к поиску
Редукция данных для доминирования в графах (посмотреть исходный код)
Версия от 01:30, 25 марта 2013
, 25 марта 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
В левой части рисунка показано подобное разбиение. Понятная и полезная интерпретация данного разбиения заключается в том, что вершины из <math>N_1(v) \; </math> рассматриваются как «выходы», поскольку они имеют прямые связи с «внешним миром» за пределами ближайшей окрестности v; вершины из <math>N_2(v) \; </math> – как «стражи», поскольку они имеют прямую связь с выходами, а вершины из <math>N_3(v) \; </math> – как «заключенные», поскольку они не видят «мира» за пределами <math> \{ v \} \cup N_1(v) \; </math>. | В левой части рисунка показано подобное разбиение. Понятная и полезная интерпретация данного разбиения заключается в том, что вершины из <math>N_1(v) \; </math> рассматриваются как «выходы», поскольку они имеют прямые связи с «внешним миром» за пределами ближайшей окрестности v; вершины из <math>N_2(v) \; </math> – как «стражи», поскольку они имеют прямую связь с выходами, а вершины из <math>N_3(v) \; </math> – как «заключенные», поскольку они не видят «мира» за пределами <math> \{ v \} \cup N_1(v) \; </math>. | ||
Рассмотрим вершину <math>w \in N_3(v) \; </math>. Такая вершина имеет соседей только из <math> \{ v \} \cup N_1(v) \cup N_3(v) \; </math>. Следовательно, для того, чтобы доминировать вершину w, по меньшей мере одна вершина из | Рассмотрим вершину <math>w \in N_3(v) \; </math>. Такая вершина имеет соседей только из <math> \{ v \} \cup N_1(v) \cup N_3(v) \; </math>. Следовательно, для того, чтобы доминировать вершину w, по меньшей мере одна вершина из <math> \{ v \} \cup N_1(v) \cup N_3(v) \; </math> должна входить в доминирующее множество входного графа. Поскольку v может доминировать все вершины, которые были бы доминированы в результате выбора из <math>N_1(v) \cup N_3(v) \; </math> в доминирующее множество, это дает следующее правило редукции данных: | ||
Если N3 (v) /0 для некоторой вершины v, удалить N2 (v) и N3(v) из G и добавить в G новую вершину v0 с дугой fv; v0g. | Если N3 (v) /0 для некоторой вершины v, удалить N2 (v) и N3(v) из G и добавить в G новую вершину v0 с дугой fv; v0g. | ||