Question about edge weighting

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

Question about edge weighting

Post autor: Scott104 » 02 paź 2021, 08:34

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.

Awatar użytkownika
Jerry
Fachowiec
Fachowiec
Posty: 1428
Rejestracja: 18 maja 2009, 09:23
Podziękowania: 19 razy
Otrzymane podziękowania: 661 razy

Re: Question about edge weighting

Post autor: Jerry » 02 paź 2021, 10:47

Scott104 pisze:
02 paź 2021, 08:34
I have a DAG ...

...For example: 1 / |
2 3 4 | | | | 5 | \ | / 6
I did not understand...

I greet you
Teksty matematyczne pisz w kodzie \(\color{blue}{\LaTeX}\): https://zadania.info/fil/latex.pdf
Ktoś poświęcił Ci swój czas i pomógł? Podziękuj Mu klikając 👍 .