0
$\begingroup$

Given are some vertexes, arranged in a list (so there every vertex is connected with two others and there are no circles in the graph). Every Vertex contains one number. Now you can lower the Number in one vertex and higher the one in one of the Vertexes connected to it by 1 in one so called "step". How would an Algorythm works that calculates the minimal number of steps after that every the difference between the number in two neighbor-vertexes is over a certain value?

Here an example since you might not understand what I'm trying to explain:

first a given List of vertexes with numbers in them:

2 5 1 3 4

now a step would look like that:

2 5+1 1-1 3 4 = 2 6 0 3 4

or like that:

2 5 1 3-1 4+1 = 2 5 1 2 5

now just reaching the goal with a min difference of 5 (hope I make no mistakes here):

2 5 1 3 4

1 6 1 3 4

1 6 1 4 3

1 6 1 5 2

1 6 1 6 1

(the list of vertexes at the beginning is random, as well as the result is so symetric in this case) (since a list is a graph there are these tags)

$\endgroup$
  • $\begingroup$ Why is this related to graphs? $\endgroup$ – xskxzr Mar 27 '18 at 6:24
  • $\begingroup$ A list is - in its deffinition - just a special graph and I thought some algorytms in weighted graphs could work here. $\endgroup$ – hasxfgh Mar 27 '18 at 11:15
  • $\begingroup$ This is an interesting question. To attract answers, you can take some time to edit it to improve the formatting and show your effort. In addition, I don't think it is related to graphs. $\endgroup$ – xskxzr Mar 28 '18 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.