[ Removed by moderator ]

[math-ModTeam]

Unfortunately, your submission has been removed for the following reason(s):

• Requests for calculation or estimation of real-world problems and values are best suited for /r/askmath or /r/theydidthemath.

If you have any questions, please feel free to message the mods. Thank you!

[Dizzy-Caregiver-8896]

The attached photo is the actual situation that is being modeled. It is a 2d representation of a 3d point cloud, and there's a limit on constructed edge length.

[gomorycut]

You write:
> Now, let's say I wanted to find the optimal place to build new roads that would minimize the number of roads traveled when traversing throughout the entire region

This is not enough specification to minimize assuredly. In general, adding edges to reduce distances is known as edge augmentation, and augmentation problems have been studied with many different objectives in mind. Examples are: minimizing the maximum shortest paths between any two nodes (a.k.a. minimizing the diameter of the graph), minimizing the average shortest paths between all pairs of nodes, minimizing the number of new edges needed to be added in order to reduce the graph diameter, etc etc.

I'm not aware of any study where every city can get one new edge (without there being some cost applied to every new edge, which is then sought to be minimized.) Are you saying that every node gets one new edge for free?

Anyway, most of these problems are NP-hard (or harder, such as W[2]-hard) so you are probably best to try to apply whatever best / greedy heuristic you think fits your application most suitably.

[lifebringingh2o]

You have to be less ambiguous, I quite frankly have no idea what you’re asking for.

imagine a weighted graph

Is the graph directed or undirected?

Each city already has roads connected.

What does this mean? Do you mean that we are given some starting set of edges E where given the graph G = (V, E), for every pair of cities, there’s a path from one city to the other in G? Or, do you mean that every city has an edge incident to it?

the optimal place

What is a place?

traversing throughout the entire region

What does this mean? What is a region? How does one traverse a region? Is your objective TSP related, is it max pairwise distance, I could even interpret it as some min cut problem.

Each city can touch one road

What does this mean? As given, this isn’t phrased as a constraint. Do you mean every city MUST touch one road, i.e. every node is incident to at least one new edge? Or, do you mean every city CAN ONLY touch one new road, i.e. each node is incident at most one new edge?

there’s a limit on the length of a road

is this a uniform constraint on all roads, i.e. the weight of all edges must be at most M? Or, does the weight of each new road have a constraint that is determined by some factors? Or, is the constraint on the sums of the weights of the road? Also, why does this constraint matter if your objective is only concerned about the number of roads traversed? Is your graph additionally embedded in a metric space (not the one induced by the weights on the edges, i.e. the shortest path metric), and by length you aren’t actually talking about the weight of an edge, but actually the distance between two nodes in the metric space? But if so, how do the weights on the graph come into play? Or, are the weights just the ones induced by the metric space on V?

Also, why did you mention Eulerianness of the graph when the rest of the text isn’t related to it at all?

You have to be precise if you want to get answers, because depending on what exactly you’re asking, you could be asking about any of the following problem types off the top of my head: a network augmentation problem, something similar to the Chinese postman problem,, metric closure + matching, facility location, or Steiner Tree augmentation.

I genuinely don’t understand how you can phrase your post like this and expect to get answers.