Creating two graphs from one weighted graph in such a way that the weight difference between the two graphs created is minimal

Arman 0
Viewed 27

As in the picture below, we have a weighted chart and we intend to convert this chart into two charts in such a way that the difference in the total weight of the two charts created is the minimum value. The edges of the graph are displayed as a two-dimensional array. The solution I have in mind is to remove one of the edges each time to create two graphs and then calculate the weight of the two graphs created and thus be able to calculate the difference as well. Finally, when we have removed all the edges once and checked all the states, we return the state with the smallest weight difference between the two graphs. I am having trouble implementing this solution. If you can share a sample code with javascript language with me. Grateful

Edges = [ [1,9] , [1,4] , [4,8] , [4,3] , [3,2] , [3,5] , [5,6] , [6,7] ]

enter image description here

graph-theory arrays algorithm javascript
1 Answers

remove one of the edges each time to create two graphs

What do you mean by "two graphs"

My best guess: you mean two components. A component is a subset of the nodes in a graph which have no connections to nodes that are not part of the same component.

Here is a graph with two components.

enter image description here

In general removing one edge is not sufficient to split a graph into two components.

For example:

enter image description here

So the bottom line is that there is no algorithm to meet the requirements as you have posted. You will need to think through what exactly you want and edit your question.

ravenspoint0
Related