4551
правка
Редукция данных для доминирования в графах: различия между версиями
Перейти к навигации
Перейти к поиску
Редукция данных для доминирования в графах (посмотреть исходный код)
Версия от 01:08, 25 марта 2013
, 25 марта 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 18: | Строка 18: | ||
• N2(v) содержит все вершины из N(v) nN1(v), связанные дугами по крайней мере с одной вершиной из N1(v); | • N2(v) содержит все вершины из N(v) nN1(v), связанные дугами по крайней мере с одной вершиной из N1(v); | ||
• N3(v) содержит всех соседей вершины v, не принадлежащих к N1(v) или N2(v). | • N3(v) содержит всех соседей вершины v, не принадлежащих к N1(v) или N2(v). | ||
[[Файл:DRDG.jpg]] | |||
Рис. 1. Редукция данных для доминирования в графах | |||
В левой части показано разбиение окрестности вершины v; в правой части показан результат применения приведенного ниже правила редукции данных к этому конкретному (под)графу. | |||
В левой части рисунка показано подобное разбиение. Понятная и полезная интерпретация данного разбиения заключается в том, что вершины из N1 (v) рассматриваются как «выходы», поскольку они имеют прямые связи с «внешним миром» за пределами ближайшей окрестности v; вершины из N2(v) – как «стражи», поскольку они имеют прямую связь с выходами, а вершины из N3 (v) – как «заключенные», поскольку они не видят «мира» за пределами fvg [ N(v). | В левой части рисунка показано подобное разбиение. Понятная и полезная интерпретация данного разбиения заключается в том, что вершины из N1 (v) рассматриваются как «выходы», поскольку они имеют прямые связи с «внешним миром» за пределами ближайшей окрестности v; вершины из N2(v) – как «стражи», поскольку они имеют прямую связь с выходами, а вершины из N3 (v) – как «заключенные», поскольку они не видят «мира» за пределами fvg [ N(v). | ||