New answers tagged weighted-graphs
2
Not sure if this is a stretch for this question, but an NFA for the regex (xx)? is
ϵ
[Start] ─────→ [Accept]
│ ↑
└───── xx ─────┘
It's not technically a number, but semantically the ϵ edge is a "null"-weighted edge: you can take it without incurring any "cost" (which in this case might be consumption of ...
1
Three computers (nodes a, b, and c) networked together (edges) with the amount of traffic between the each node the weight, in MB.
(a) <-- 50MB --> (b) <--+
^ |
| 10MB
| |
\-- 0MB --> (c) <-----+
Here the edges are a<->b, b<->c, and a<->c with weights 50, 10, ...
1
Consider a road network that consists of segments of toll roads, with a fixed toll for each type of vehicle on each segment.
So we represent the road network as a graph and to work out the cost of a path add up the cost of the links in the path. However some links don't have tolls for bike, hence will have a zero cost.
If we removed these zero cost links ...
1
Airport terminals
(That's an interesting question and kind of a nice brain-teaser. I haven't seen the answers given in the other question, so I might be duplicating something)
Imagine a graph of world's international airport routes with:
each terminal being a vertex
each edge being a flight connection with scheduled flight time as its weight
Then quite ...
11
The classic strategy game Civilization by MicroProse represents the world map as a square grid where each node of the grid is a tile of the world map, representing some type of terrain. Players control civilian and military units over this map. Each unit has a specific allocation of movement points, and each terrain type costs a specific amount of movement ...
2
Neural networks
A neural network assigns weights to each connection between the simulated neurons. As you say, when calculating the output of the network, any edges with zero weight are equivalent to missing connections.
However, the training step considers both the weight of the edge and the partial derivative of the output value with regards to the weight. ...
7
In circuity, we often construct a graph of a circuit. Wires are typically modeled as 0 resistance because, frankly, measuring the resistance of wires is really tricky and rarely profitable. So if we have multiple devices connected to a single wire, we can treat that as separate vertices with 0 weight nodes between them.
We can transform them into one "...
4
Such a graph does not need to represent an actual road network. It can be anything representable by a network. For example, conversion options between various online banking and cryptocurrency services. Most of them have a little or more fee, but sometimes you can do it for free (most likely, internal conversions by the same service, like sending cash from ...
3
Distances and times (and other units of measurement)
Consider a graph where the edges are the driving distances between warehouses across the country. If two warehouses are on the same premises, they could potentially be given a distance of 0. Strictly speaking there might be some distance between them, but this may be considered negligible if the distance ...
0
An video game example.
Take a game where raw resources are processed into more complex items.
For example, Wire can be made from copper, but it can also be made from Iron.
The game does not differ between Regular Wire and Iron Wire (they are the same thing), hence edge weight of 0.
However, it is organizationally advantageous for player to consider them ...
23
Of course. The weight can mean things that are irrelevant to the existence of an edge.
Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one.
Consider a road network. If you want to find a path from A to B in a road network, you need to keep all the road segments that exist. There are two important measures:
...
4
Negative edge weights are important for abstract planning.
In a typical graph you might use for this, there are two specific properties that are important:
The nodes represent possible states of a complex system that is being modeled.
The graph is directed.
As a result, the graph is functionally a representation of a state machine.
In such a graph, each ...
3
Say you are traveling city to city and along the way, you can pick up cargo or a passenger or whatever and earn profit on some of the travel hops (there are a number of carpooling services online where people post their to/from/when needs and how much they are willing to pay). So building a graph of possible profits (and on legs without a carpool offer, ...
3
Consider someone speedrunning a complex videogame, which we abstract to moving through a graph. While the run is measured in absolute time, they might want to use relative time for judging strategies: how much time a route gains or loses them relative to some baseline "par". Then negative edges would correspond to time saved, and positive edges to ...
34
Distance between cities can't be negative, but if you are programming for an electric car, then a downhill road segment will regen, thus the energy used is negative. It is very important to take that into account when predicting range.
In a neural network, we can use negative weights to indicate that one neuron firing is inversely correlated with another ...
7
In a social network. Where the source node is a person the target node is another person and the connection represents the preference the source has for the target. The sign representing the direction of the sentiment.
In quantitative finance where the nodes are securities and the connections are the correlation coefficients.
A few years ago I made a ...
0
How about an electricity network where the positivity/negativity of the weight indicates the direction of current flow.
0
The shortest walk must have the form
u
\
t<->w
/
v
where the edges in each arrow are disjoint. To see this, suppose in the shortest walk, we go through nodes $u_1'=u,\ldots,u_{k'}',u_1,\ldots,u_k=w$ from $u$ to $w$, go through nodes $v_1=w,\ldots,v_l,v_1',\ldots,v_{l'}'=v$ from $w$ to $v$, where $v_1',\ldots,v_{l'}' \notin \{u_1',\ldots,u_{k'}',...
0
Add a new vertex $s_0$. Add edges of weight 0 from $s_0$ to each other vertex. Now you have a graph with a source vertex $s_0$. Run the previously mentioned algorithm on this new graph, using $s_0$ as the source vertex.
1
Add a new vertex $v$ to the graph. For every city node $u$ that contains a temple, add a $0$ weighted edge $(v,u)$ to the graph. Let the new graph be $G'$. Find the minimum spanning tree of $G'$. It would give the minimum cost of constructing roads such that every city has access to at least one temple.
Please try to prove correctness by yourself. Let me ...
3
If the MST does not contain at least one among the two minimum-cost edge then add it to the MST (you get a graph with a single loop and the loop has length 3 or larger) remove from the loop the edge having larger cost (it costs more than the one you just introduced) and you are left with a Tree and this tree is Spanning and it costs less than the original ...
4
Assuming that the graph has at least $3$ vertices, is connected, and edges have distinct weights you can see that the two edges with the lowest weights must belong to the (unique) MST of the graph by noticing that they cannot induce any cycle and hence they must be selected by Kruskal's algorithm.
Alternatively, you can notice that each cycle must contain at ...
23
For simple graphs*, it is true for the following reason:
Kruskal’s algorithm is correct
Kruskal’s algorithm works as follows:
sort the edges by increasing weight
repeat: pop the cheapest edge, if it does not create cycles, include it in the MST
Two edges cannot construct a cycle in a simple graph
By the correctness of Kruskal’s algorithm, the two ...
2
Your problem is NP-hard even for $k=2$, as it can be seen by a reduction from the partition problem.
The reduction is as follows:
Let $S = \{s_1, \dots, s_n\}$ be a set of $n$ positive integers.
Let $\varepsilon = \frac{1}{2n}$.
Create a graph that has $n+1$ vertices numbered from $1$ to $n+1$ and $2n$ edges. Specifically, for each $i \in \{1, \dots, n\}$ ...
Top 50 recent answers are included