0
$\begingroup$

What are the rules of converting a weighted digraph to a weighted, undirected graph?

I understand that the edges should go in both directions from vertex to vertex. However, do the weights of each edge to/from other edges need to be the same? If not, how does one decide which weight to attach to the undirected vertices?

For example, can this adjacency matrix representation of a weighted digraph be converted into an undirected weighted graph?

$\endgroup$
  • $\begingroup$ Can you give more context to your situation? What is the purpose of the conversion? What is the problem you're trying to solve? For some problems the conversion may be trivial, for others it may be more difficult. Can we change the shape of the graph, add more vertices and edges or can we only merge existing bidirectional edges in some way? $\endgroup$ – ryan Jul 7 '17 at 2:42
2
$\begingroup$

There aren't any rules. Do whatever is most appropriate to your specific situation. What do the weights mean? That should probably tell you what weights to use in the new graph.

If there is no meaning, translation doesn't make sense: translation is, by definition, an operation that preserves meaning. For example, suppose I give you the following exercise:

Translate the program function int int (hello_) repeat end begin int into Java.

The program doesn't mean anything so it can't be translated. You can't possibly give me a Java program and say "This is the right one" because there's no definition of "right". Similarly, without saying what the edges and weights of some digraph mean, there's no way to justify the claim "This undirected graph is the correct translation."

There's no intrinsic equivalence between directed and undirected graphs. Usually, one associates an undirected graph with the directed graph in which every edge is replaced by a directed edge in each direction. In many contexts, these behave the same way (e.g., if I can get from A to B in the graph, I can follow the same route in the digraph). In other circumstances, though, they might be different. For example, an undirected edge might represent the existence of a two-way road between two cities, whereas a pair of directed edges might represent separate one-way roads in each direction.

$\endgroup$
  • $\begingroup$ I've updated my post with an image of the adjacency matrix of the graph. The weights are without meaning - this is simply an exercise in understanding the difference between directed and undirected weighted graphs. $\endgroup$ – Indie Inc Jul 7 '17 at 0:10
  • $\begingroup$ If the weights are without meaning, then it doesn't matter how to you transform directed to undirected. There should be some meaning and as David said, it would be specific to your situation. If you can give more context on the situation it might be easier to find a suitable transformation. $\endgroup$ – ryan Jul 7 '17 at 2:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.