Given an undirected(weighted) graph depicted in the attached diagram which is a representation of relationships between different kinds of drink, how best can I assign weight to the edges? Is there a technique that I can use?
Hi Jesujoba,
AFAIK, this should be accomplished based on previous knowledge (a.k.a background), or ranking the content using certain aspect such as personal preferences; otherwise, there is no meaning/logic behind such process.
HTH.
Samer Sarsam, PhD.
The attribute that the weights of the edges represent depends on the problemthe graph is used for modelling.
Consider the map of a state as a graph with the cities forming the vertices and the edges denoting the route of travel from one city to another. The weights can denote any one of the following.
- The cost associated for travelling from one city to another.
- The time taken for the trip from one city to another.
The following example is from Wikipedia
Consider the situation where a telecommunications company is trying to lay cable in a new neighborhood. If it is constrained to bury the cable only along certain paths (e.g. roads), then there would be a graph containing the points (e.g. houses) connected by those paths.
Some of the paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. Currency is an acceptable unit for edge weight – there is no requirement for edge lengths to obey normal rules of geometry such as the triangle inequality.
We are given a graph G=(V,E)G=(V,E) and we need to find an assignment of non-negative edge weights (You must give every edge a non-negative weight). We are also given a set R⊆VR⊆V and mapping ca,b:R×R→R+ca,b:R×R→R+ where R+R+ is all positive (>0>0) reals (ca,b=cb,aca,b=cb,a for all a,ba,b and ca,a=0ca,a=0 for all aa ). Our edge weight assignment is constrained by the requirement that for all vertex pairs (a,b)∈R×R(a,b)∈R×R, all paths from aa to bb need to have at least weight ca,bca,b where the weight of the path is the sum of all edge weights on that path.
Now assume that there exists an assignment such that for all vertex pairs (a,b)∈R×R(a,b)∈R×Rthere exists at least one path from aa to bb whose weight is exactly equal to ca,bca,b.
Now consider the assignment of edge weights (*) that satisfies the constraints and minimizes the total sum of edge weights. Is it true that for all vertex pairs (a,b)∈R×R(a,b)∈R×R there will exist at least one path from aa to bb whose weight is exactly equal to ca,bca,b ?
My thoughts: consider, out of all assignments which satisfy the constraints and have for all vertex pairs (a,b)∈R×R(a,b)∈R×R there exists at least one path from aa to bb whose weight is exactly equal to ca,bca,b, the one which minimizes the total sum of edge weights. Assume towards contradiction that for the assignment (*) that there exists a vertex pair in R×RR×R s.t. for all paths between these vertices all paths are strictly larger than the required constraint. and i'm hoping this yields a contradiction.
graph-theory shortest-path weight
The Graph in question needs to specify the relationship ,like the consumers or amount of consumption etc. more clarity is imp. If number , the proportions could be weights. Ther can be more than one. It is an example
You may assign weights from the semiring for flexibility of computations. E.g: Take time or cost of transportation as weight such that these weights set form a semiring under suitable binary operations. Apply shortest path algorithms in algebraic settings.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs