4430
правок
Параметризованные алгоритмы графического представления графов: различия между версиями
Материал из WEGA
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 18:58, 30 марта 2016
, 30 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 53: | Строка 53: | ||
Теорема 2 ([3]). '''cr(G, <_1, <_2) = 0 \;''' в том и только том случае, если G является ациклическим и для любого пути (x, a, y) в G, '''x, y \in V_1 \;''', выполняется следующее: для всех '''u \in V_1 \;''' при <math>x <_1 u <_1 y \;</math> единственным ребром, инцидентным u, если таковое существует, является (u, a). | '''Теорема 2 ([3]). '''cr(G, <_1, <_2) = 0 \;''' в том и только том случае, если G является ациклическим и для любого пути (x, a, y) в G, '''x, y \in V_1 \;''', выполняется следующее: для всех '''u \in V_1 \;''' при <math>x <_1 u <_1 y \;</math> единственным ребром, инцидентным u, если таковое существует, является (u, a).''' | ||
| Строка 59: | Строка 59: | ||
Лемма 3. | Лемма 3. <math>\sum_{u, v \in V_2, u <_2 c_{uv} } C_{uv} = cr(G, <_1, <_2) \;</math>. | ||
