2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Задача на максимум
Сообщение23.06.2023, 11:55 
Заслуженный участник
Аватара пользователя


16/07/14
9208
Цюрих
fesoh82663, а чем Вас решение tolstopuz не устраивает? (исток и сток в нём просто отдельные вершины, специально для этого созданные)

 Профиль  
                  
 
 Re: Задача на максимум
Сообщение23.06.2023, 12:33 


22/06/23
9
mihaild в сообщении #1598798 писал(а):
fesoh82663, а чем Вас решение tolstopuz не устраивает? (исток и сток в нём просто отдельные вершины, специально для этого созданные)


Я с макс потоком не очень знаком, поэтому не очень понимаю как мы строим граф. Если я правильно понял, то должно получиться что-то такое.
Изображение

Поиск максимального потока не предполагает, что у нас один исток и один сток? (тут у нас их несколько)
После того как мы найдем максимальный поток, то искомые переменные будут в ребрах данного графа?

 Профиль  
                  
 
 Re: Задача на максимум
Сообщение23.06.2023, 12:39 
Заслуженный участник
Аватара пользователя


16/07/14
9208
Цюрих
fesoh82663, в графе есть четыре группы вершин:
1. Исток.
2. Неравенства первой группы.
3. Неравенства второй группы.
4. Сток.
Переменным соответствуют не вершины, а ребра. Точнее, для каждой переменной соединяем ребром включающие её неравенства из первой и второй группы.

 Профиль  
                  
 
 Re: Задача на максимум
Сообщение23.06.2023, 12:40 
Заслуженный участник


31/12/05
1525
Нарисуйте новый исток, из которого будут ребра в вершины $4, 7, 2$, с пропускными способностями соответственно $4, 7, 2$. И новый сток, в который пойдут ребра из вершин $4', 3, 5, 1$, с пропускными способностями $4, 3, 5, 1$. Да, переменные - это шесть нарисованных вами ребер. Их пропускные способности бесконечны, но можно взять, например, максимум из меток вершин, которые это ребро соединяет.

 Профиль  
                  
 
 Re: Задача на максимум
Сообщение23.06.2023, 13:07 


22/06/23
9
tolstopuz в сообщении #1598812 писал(а):
Нарисуйте новый исток, из которого будут ребра в вершины $4, 7, 2$, с пропускными способностями соответственно $4, 7, 2$. И новый сток, в который пойдут ребра из вершин $4', 3, 5, 1$, с пропускными способностями $4, 3, 5, 1$. Да, переменные - это шесть нарисованных вами ребер. Их пропускные способности бесконечны, но можно взять, например, максимум из меток вершин, которые это ребро соединяет.

Вроде получается такой граф. Т.е. я должен найти поток из вершины s в вершину t и те значения которые получатся на ребрах и будут решением?
Изображение

p.s. Еще, наверно, ребра у s и t должны быть неориентированы т.к. иначе потока из s в t не существует

 Профиль  
                  
 
 Re: Задача на максимум
Сообщение23.06.2023, 13:27 
Заслуженный участник
Аватара пользователя


16/07/14
9208
Цюрих
Вроде такой, только ребра которые идут из $t$ должны вести в $t$.

 Профиль  
                  
 
 Re: Задача на максимум
Сообщение23.06.2023, 14:11 


22/06/23
9
Буду разбираться. Спасибо!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2

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



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

Сейчас этот форум просматривают: epros


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

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