2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Множества путей в графе
Сообщение16.04.2021, 04:36 


03/10/16
18
Есть ориентированный граф $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$.

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

 Профиль  
                  
 
 Re: Множества путей в графе
Сообщение27.04.2021, 05:09 
Модератор
Аватара пользователя


11/01/06
5660
Рассмотрим новую весовую функцию на ребрах:
$$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$-веса обязан принадлежать пересечению указанных множеств путей.

 Профиль  
                  
 
 Re: Множества путей в графе
Сообщение29.04.2021, 23:42 


03/10/16
18
Непонятно почему (в общем). Получается, что путь, который найден с использованием $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 при фиксированной стратегии второго. Повторяем процедуру.

 Профиль  
                  
 
 Re: Множества путей в графе
Сообщение01.05.2021, 18:03 
Модератор
Аватара пользователя


11/01/06
5660
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$-веса, уменьшить его вес не получится ни в первом, ни во втором случае.

 Профиль  
                  
 
 Re: Множества путей в графе
Сообщение09.05.2021, 01:24 


03/10/16
18
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)$).
Но это не тот же сам граф, т.к. граф зависит от изначальной фиксации ребер.

 Профиль  
                  
 
 Re: Множества путей в графе
Сообщение10.05.2021, 06:02 
Модератор
Аватара пользователя


11/01/06
5660
Dina98 в сообщении #1517637 писал(а):
Но это не тот же сам граф, т.к. граф зависит от изначальной фиксации ребер.

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

 Профиль  
                  
 
 Re: Множества путей в графе
Сообщение28.06.2021, 01:56 


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

 Профиль  
                  
 
 Re: Множества путей в графе
Сообщение02.07.2021, 22:17 
Модератор
Аватара пользователя


11/01/06
5660
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$-веса принадлежит как одному, так и другому множеству путей.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group