Множества путей в графе

[Dina98]

Есть ориентированный граф $G = (V,E)$.
Выделен один источник и один сток: $s, t \in V$.
Предполагаем, что имеется простой (без самопересечений) ориентированный путь из $s$ в $t$.
Более того, такой путь проходит через любое ориентированное ребро $e \in E$.
Ребер, выходящих из $t$, нет.

На каждом ребре $e \in E$ заданы два строго положительных числа $c(1,e)$ и $c(2,e)$.
Предполагаем (для простоты), что все ориентированные пути из $s$ в $t$ имеют разные суммы как первых чисел, так и вторых.

Все вершины, исключая $t$, разбиты на два непересекающихся множества: $V - t = V_1 \cup V_2$.
Фиксируем выходящее ребро в каждой вершине $v$ из $V_1$
(соответственно, $v$ из $V_2$) и все остальные ребра,
выходящие из $v$, удаляем из графа.
В полученном редуцированном графе выбираем
путь из $s$ в $t$ с минимальной суммой чисел $c(1,e)$
(соответственно, $c(2,e)$).
Если пути из $s$ в $t$ вообще нет, то ничего не выбираем.

Делаем так для всех возможных выборок выходящих ребер из $V_1$ и $ V_2$.

Пытаюсь доказать (или опровергнуть), что полученные два множества путей пересекаются.
Моделирование не находят контрпримеров.

[maxal]

Рассмотрим новую весовую функцию на ребрах:

$$w((u,v)) := \begin{cases} c(2,(u,v))&\text{if}\ u\in V_1;\\ c(1,(u,v))&\text{if}\ u\in V_2. \end{cases} $$

Тогда путь из $s$ в $t$ минимального $w$-веса обязан принадлежать пересечению указанных множеств путей.

[Dina98]

Непонятно почему (в общем). Получается, что путь, который найден с использованием $w$, использует только одно значение изначальных весов.

Этот как для двух игроков. Вершины $V_1$ относятся к игроку №1, вершины $V_2$ относятся к игроку №2.

Мы фиксируем стратегию первого игрока (Фиксируем выходящее ребро в каждой вершине $v$ из $V_1$ и все остальные ребра, выходящие из $v$, удаляем из графа). В полученном редуцированном графе выбираем путь из $s$ в $t$ с минимальной суммой чисел $c(1,e)$, который может быть интерпретирован как оптимальная стратегия игрока №2 при фиксированной стратегии первого. Повторяем процедуру, выбирая другую стратегию первого игрока и т.д. Из таких путей (стратегий) формируем множество.

Точно также поступаем с игроком №2: Фиксируем выходящее ребро в каждой вершине $v$ из $V_2$ и все остальные ребра, выходящие из $v$, удаляем из графа). В полученном редуцированном графе выбираем путь из $s$ в $t$ с минимальной суммой чисел $c(2,e)$, который может быть интерпретирован как оптимальная стратегия игрока №1 при фиксированной стратегии второго. Повторяем процедуру.

[maxal]

Dina98, когда фиксируются ребра выходящие из $V_1$ и минимизируется сумма $c(1,e)$ выбором ребер выходящих из $V_2$, то минимизируется и сумма $w(e)$ (т.к. если $e$ выходит из $V_2$, то $w(e)=c(1,e)$). Аналогично, если фиксируются ребра выходящие из $V_2$ и минимизируется сумма $c(2,e)$ выбором ребер выходящих из $V_1$, то снова минимизируется сумма $w(e)$ (т.к. если $e$ выходит из $V_1$, то $w(e)=c(2,e)$).
Таким образом, в обоих случаях происходит попытка уменьшить сумму $w(e)$ на некоторых ограниченных множествах. Но для пути минимального $w$-веса, уменьшить его вес не получится ни в первом, ни во втором случае.

[Dina98]

maxal в сообщении #1516317 писал(а):

когда фиксируются ребра выходящие из $V_1$ и минимизируется сумма $c(1,e)$ выбором ребер выходящих из $V_2$, то минимизируется и сумма $w(e)$ (т.к. если $e$ выходит из $V_2$, то $w(e)=c(1,e)$).

Согласна.

maxal в сообщении #1516317 писал(а):

Аналогично, если фиксируются ребра выходящие из $V_2$ и минимизируется сумма $c(2,e)$ выбором ребер выходящих из $V_1$, то снова минимизируется сумма $w(e)$ (т.к. если $e$ выходит из $V_1$, то $w(e)=c(2,e)$).

Но это не тот же сам граф, т.к. граф зависит от изначальной фиксации ребер.

[maxal]

Dina98 в сообщении #1517637 писал(а):

Но это не тот же сам граф, т.к. граф зависит от изначальной фиксации ребер.

Это неважно. В зафиксированном графе есть данный путь, а мы пытаемся найти путь с меньшим $w$-весом.

[Dina98]

Не могли бы Вы привести более четкое доказательство, что полученные два множества путей пересекаются. Я вижу, что компьютернон моделирование не находит контрпримеров, но мне непонятно почему (ведь изначальная фиксация ребер может быть разная).

[maxal]

Dina98, я не только утверждаю, что два множества путей пересекаются, а указываю конкретный путь, который принадлежит их пересечению:

maxal в сообщении #1515780 писал(а):

Рассмотрим новую весовую функцию на ребрах:

$$w((u,v)) := \begin{cases} c(2,(u,v))&\text{if}\ u\in V_1;\\ c(1,(u,v))&\text{if}\ u\in V_2. \end{cases} $$

Тогда путь из $s$ в $t$ минимального $w$-веса обязан принадлежать пересечению указанных множеств путей.

Попробуйте посмотреть как это работает на примерах, а потом и доказать, что путь из $s$ в $t$ минимального $w$-веса принадлежит как одному, так и другому множеству путей.