Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Scott104
Witam na forum
Posty: 1
Rejestracja: 02 paź 2021, 08:31
Płeć:

Hi,

I am currently struggeling with the following problem:

I have a DAG in which I want to weight the edges. I have multiple possibilities to weight the edges. For simplicity lets assume that they can be weighted with 1 or 2.

I have a constraint for the weights: Maximun two parallel nodes (below 2,3,4 run in parallel) can have in-edges-weight 1. The others need to have weight 2. At the end the weights of all paths are summed and the maximun is taken (should be as low as possible).

For example: 1 / |
2 3 4 | | | | 5 | \ | / 6

Node 1 has three successors: 2, 3 and 4 running in parallel. I need sonething that weights the graph such that the constrint is true. In this case a possible solution is: edges 1-4 should have weight 2. All other edges with weight 1.

It would be great if someone could help. Thanks.

Jerry
Fachowiec
Posty: 1550
Rejestracja: 18 maja 2009, 09:23
Podziękowania: 22 razy
Otrzymane podziękowania: 716 razy

Teksty matematyczne pisz w kodzie $$\color{blue}{\LaTeX}$$: https://zadania.info/fil/latex.pdf