4551
правка
Редукция данных для доминирования в графах: различия между версиями
Перейти к навигации
Перейти к поиску
Редукция данных для доминирования в графах (посмотреть исходный код)
Версия от 01:23, 25 марта 2013
, 25 марта 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 13: | Строка 13: | ||
Основная идея редукции данных заключается в предварительной обработке на основе локально применяемых правил упрощения. В качестве примера может служить правило, согласно которому рассматривается локальная окрестность каждой вершины графа. Для этого потребуются следующие определения. | Основная идея редукции данных заключается в предварительной обработке на основе локально применяемых правил упрощения. В качестве примера может служить правило, согласно которому рассматривается локальная окрестность каждой вершины графа. Для этого потребуются следующие определения. | ||
Окрестность N(v) произвольной вершины v | Окрестность N(v) произвольной вершины <math>v \in V \; </math> входного графа разбивается на три непересекающихся множества <math>N_1(v) \; </math>, <math>N_2(v) \; </math> и <math>N_3(v) \; </math>, зависящих от структуры локальной окрестности. Эти множества таковы: | ||
<math>N_1(v) \; </math> содержит всех соседей вершины v, от которых идут дуги к вершинам, не являющимся соседями v; | |||
<math>N_2(v) \; </math> содержит все вершины из <math>N(v) \setminus N_1(v) \; </math>, связанные дугами по крайней мере с одной вершиной из <math>N_1(v) \; </math>; | |||
<math>N_3(v) \; </math> содержит всех соседей вершины v, не принадлежащих к <math>N_1(v) \; </math> или <math>N_2(v) \; </math>. | |||
[[Файл:DRDG.jpg]] | [[Файл:DRDG.jpg]] | ||
Редукция данных для доминирования в графах | ''Редукция данных для доминирования в графах | ||
В левой части показано разбиение окрестности вершины v; в правой части показан результат применения приведенного ниже правила редукции данных к этому конкретному (под)графу. | В левой части показано разбиение окрестности вершины v; в правой части показан результат применения приведенного ниже правила редукции данных к этому конкретному (под)графу. | ||
'' | |||
В левой части рисунка показано подобное разбиение. Понятная и полезная интерпретация данного разбиения заключается в том, что вершины из N1 (v) рассматриваются как «выходы», поскольку они имеют прямые связи с «внешним миром» за пределами ближайшей окрестности v; вершины из N2(v) – как «стражи», поскольку они имеют прямую связь с выходами, а вершины из N3 (v) – как «заключенные», поскольку они не видят «мира» за пределами fvg [ N(v). | В левой части рисунка показано подобное разбиение. Понятная и полезная интерпретация данного разбиения заключается в том, что вершины из N1 (v) рассматриваются как «выходы», поскольку они имеют прямые связи с «внешним миром» за пределами ближайшей окрестности v; вершины из N2(v) – как «стражи», поскольку они имеют прямую связь с выходами, а вершины из N3 (v) – как «заключенные», поскольку они не видят «мира» за пределами fvg [ N(v). | ||