Minimize the sum of the length of the edges in a graph with movable vertices

Objective: Minimize the sum of the length of the edges in a graph with movable vertices

In a unidirected graph with fixed edges and with 2 types of vertices, one with a fixed position, the other with a variable position

Formula to calculate the x or y of each node (N_0) belonging to N

Let’s understand the formula:

• N = set of vertices with x and y variables reachable from N_0 passing only through vertices belonging to N
• O = set of vertices with fixed x and y
• i = node belonging to N
• O_j = set of nodes belonging to O adjacent to N_0
• P_((N_0) -> i) = set of all possible paths between node N with 0 to node “i”,
  passing only through nodes belonging to N. A path is a multiplication of the number / quantity of arcs for all the nodes it crosses, N with 0 included, “i” included, (e.g. if it starts from a node that has 7 adjacent edges, then goes through one that has 2, and ends up with one that has 3, the calculation will be 7*2*3 = 42

P.s. Im not a mathematical, and not even an expert, so the formula can be absolutely wrong.

In this port I will not cover the proof, but the formula is derived from the classical “Mean”

Example in python

Google Colaboratory

Attention

I’m not an expert, and there may be errors in this project. For this reason, considerations, improvements or criticisms are welcome in the comments