How can we realize a negative weighted edge in real-world situations? The applications of negative weighted edges.
the weight can measure an elevation difference, positive when climbing from u to v, negative when descending from u to v. Otherwise, negative weights can measure some financial subvention (a driver is paid to go from u to v, while he has to pay to go, say, from a to b). However, most of the time, negative cost result from using reduced costs. For instance in column generation, the subproblem consists in finding an improving column wrt. its reduced cost. This cost takes into account the original cost as well as the dual values from the master problem. As a consequence, it can be positive or negative.
Mr. Duhamel Christophe :
So should we conclude that edges cost negative with respect to other edges(Positive). So their identity is limited only till the context of positive edges.
Can't we think of negative edges without the positive ones ?
what about their own identity?
Precisely we can have an all Negative edged graph .
It would be nice of you if you further promote this thread.
Thanks for you contribution.
I suggest we go one step further, namely edges with 'Complex weight'. Edges with complex weigh (Real value + Imaginary value) may be used to represent an electrical circuit comprising resistors, capacitors and coils. This can easily be represented in the Adjacency matrix. However, most of the commonly used graph metrics assume non-directional edges with unit-weight. Especially graph analysis tools such as Graph Spectra, Effective Graph Resistance, Assortativity etc. will become more complex.
This is an area of ongoing (and interesting) research.
- Badges
- Science topic