Метод потенциалов - не могу понять определение

[Cube]

Вот эту часть не могу понять:

Цитата:

Решение методом потенциалов заключается в следующем:
1) для сети без ветвей-вентиляторов строится последовательность узлов

$$M_i$$

, которая обладает тем свойством, что в любой узел сети найдётся путь из первого узла последовательности только через узлы с меньшими порядковыми номерами, чем у данного узла;
2) ...

Есть пример сети:

$$ \xymatrix{ &&& \fbox{1} \ar@{-}[d]^1\\ &&& \fbox{2} \ar@/_1pc/@{-}[ddr]^5 \ar@/_1pc/@{-}[dll]_2 \ar@/^1pc/@{-}[drr]^6 &\\ & \fbox{4} \ar@/_1pc/@{-}[ddd]^3 \ar@/_1pc/@{-}[ddr]^4 &&&& \fbox{8} \ar@/^1pc/@{-}[dddr]^8 \ar@/_1pc/@{-}[dddr]^7\\ &&&& \fbox{3} \ar@/^1pc/@{-}[dll]_{10} \ar@/_1pc/@{-}[ddrr]^9\\ && \fbox{5} \ar@/^1pc/@{-}[dl]_{11}\\ & \fbox{6} \ar@{-}[d]^{12} &&&&& \fbox{9} \ar@{-}[d]^{13}\\ & \fbox{7} &&&&& \fbox{10} } $$

для которой

$$M_i=\left( 1, 2, 3, 4, 8, 5, 6, 7, 9, 10 \right)$$

Как строить эту самую M_i ? Не могу сообразить. Мне кажется, чего-то в определении не хватает. Если кому-нибудь знакомо, помогите пожалуйста.

[$]

Определение это определение. Только это не "определение" напоминает, а алгоритм решения какой то задачи. Ваш рисунок
вполне удовлетворяет требуемому условию

Цитата:

1) для сети без ветвей-вентиляторов строится последовательность узлов , которая обладает тем свойством, что в любой узел сети найдётся путь из первого узла последовательности только через узлы с меньшими порядковыми номерами, чем у данного узла;

Оно, определение, и не обязано чего то указывать, как строить. Я не в курсе о чем конкретно речь, так как и про этот метод не в курсе и откуда он, так и какого рода задачи решаются.

Сообщите публике контекст, а то так никто и не ответит, если не поймет в чем суть проблемы.

[Cube]

Цитата:

Только это не "определение" напоминает, а алгоритм решения какой то задачи.

Это определение последовательности

$$M_i$$

.

Цитата:

Я не в курсе о чем конкретно речь, так как и про этот метод не в курсе и откуда он

Если не в курсе, о чём речь, зачем отвечать ? Метод из динамического программирования:

Цитата:

Наиболее приемлимыми методами решения данной задачи являются методы динамического программирования. Остановимся на одном из них - методе потенциалов

Цитата:

контекст

Для каждой ветви есть три взаимосвязанных параметра:

$$h_i = r_{i}q_{i}^2$$

. Мне нужно на основе известных

$$q_i$$

определить

$$r_i$$

. Методика решения понятна во всём, кроме первого пункта - составления этой самой

$$M_i$$

.

[$]

Цитата:

Если не в курсе, о чём речь, зачем отвечать ? Метод из динамического программирования:

Я любопытствую. Что нельзя?

Я еще и про динамическое программирование полюбопытствую, а что это такое и с чем его едят.

[vbn]

Как я понимаю, последовательность $M_i$ строится произвольно,
лишь бы она "обладала тем свойством, что в любой узел сети найдётся путь из первого узла
последовательности только через узлы с меньшими порядковыми номерами, чем у данного узла".

И, похоже, в Вашем случае задача состоит не в построении последовательности $M_i$,
которую следует считать исходными данными.

[Cube]

vbn писал(а):

Как я понимаю, последовательность $M_i$ строится произвольно,
лишь бы она "обладала тем свойством, что в любой узел сети найдётся путь из первого узла
последовательности только через узлы с меньшими порядковыми номерами, чем у данного узла".

Вот здесь я и не могу разобраться. К методе у меня только один пример, который я и указал в первом сообщении, а последовательность добавления узлов в

$$M_i$$

там не изложена. Почему и спрашиваю, может, кто-нибудь сможет мне это пошагово "разжевать".

Цитата:

И, похоже, в Вашем случае задача состоит не в построении последовательности $M_i$,
которую следует считать исходными данными.

Конечно, задача состоит в определении

$$r_i$$

. Но вычисления зависят от порядка узлов в

$$M_i$$

.

[vbn]

Ваша задача состоит не в задании порядка узлов.
Порядок узлов уже однозначно задан.

[Cube]

vbn писал(а):

Ваша задача состоит не в задании порядка узлов.

Ну хорошо, а в чём тогда ? Подскажите.

Цитата:

Порядок узлов уже однозначно задан.

Задан чем ? Последовательностью из примера ? Так у меня другая сеть. Условием ? Ну вот с условием я и не могу разобраться. Как мне для произвольной сети последовательность построить ?

[vbn]

Раз у Вас другая сеть, значит Вам придется строить последовательность $M_i$.
Правило построения последовательности Вы указали сами:
лишь бы она "обладала тем свойством, что в любой узел сети найдётся путь из первого узла
последовательности только через узлы с меньшими порядковыми номерами, чем у данного узла".
Очевидно, таких последовательностей может быть несколько.

[RIP]

Вот набросок алгоритма. Берем любой узел. Это узел 1. Занумеруем оставшиеся узлы как-нибудь: $v_1,v_2,...,v_n$. Для k=1,2,...,n идем из вершины 1 в вершину $v_k$, нумеруя последовательно все узлы, встречающиеся на пути, но только если им еще не присвоен номер. В итоге, очевидно, получим то, что надо.

[Cube]

vbn писал(а):

Правило построения последовательности Вы указали сами:
лишь бы она "обладала тем свойством, что в любой узел сети найдётся путь из первого узла
последовательности только через узлы с меньшими порядковыми номерами, чем у данного узла".
Очевидно, таких последовательностей может быть несколько.

Указал, да - просто переписал. Но не могу разобраться. Если Вы понимаете, объясните пожалуйста, пошагово процесс добавления узлов в

$$M_i$$

для тестовой сети. Почему на первом месте - узел "1", на втором - "2", почему после узла "4" идёт узел "8", а не "5".

RIP писал(а):

Вот набросок алгоритма...

Взял 1, занумеровал остальные узлы:

$$v_1=2, v_2=3, v_3=4, ..., v_9=10 (v_n=n+1)$$

.
Получил (номер итерации : путь : номер для очередного узла):

$$k=1: 1 \to v_1: 2$ $$k=2: 1 \to v_2: 3$$ $$k=3: 1 \to v_3: 4$$ $$k=4: 1 \to v_4: 5$$ $$k=5: 1 \to v_5: 6$$ $$k=6: 1 \to v_6: 7$$ $$k=7: 1 \to v_7: 8$$ $$k=8: 1 \to v_8: 9$$ $$k=9: 1 \to v_9: 10$$

т.е., пронумеровал сеть как было, а что считать за

$$M_i$$

?

[RIP]

Cube писал(а):

а что считать за

$$M_i$$

?

$M_i$ - вершина с номером i

Добавлено спустя 8 минут 25 секунд:

Cube писал(а):

пронумеровал сеть как было

Просто сеть была так пронумерована изначально, что в качестве $M_i$ можно взять просто $M_i=i$. И зачем так извращаться с ними, как в примере, я тоже не понимаю. Может, я просто не понял определения.

[Cube]

RIP писал(а):

$M_i$ - вершина с номером i

Но тогда получается просто список узлов по порядку, а в примере

$$M_i=(1, 2, 3, 4, \textbf{8}, \textbf{5}, 6, 7, 9, 10)$$

.