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

''Редукция данных для доминирования в графах''

''В левой части показано разбиение окрестности вершины v; в правой части показан результат применения приведенного ниже правила редукции данных к этому конкретному (под)графу.''

 

В левой части рисунка показано подобное разбиение. Понятная и полезная интерпретация данного разбиения заключается в том, что вершины из <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, по меньшей мере одна вершина из fvg [ N2(v) [ N3(v) должна входить в доминирующее множество входного графа. Поскольку v может доминировать все вершины, которые были бы доминированы в результате выбора из N2(v) [ N3(v) в доминирующее множество, это дает следующее правило редукции данных: