Where I can find more information about graphs like those in my picture?

71 Views Asked by At

Picture of two graphs with same information In picture above I have two graphs that contain same information. In graph at bottom of picture I have changed upper graphs edges with same number to one node and nodes to edges.

Is there name for this kind of graphs? Where can I find more information about them?

Thank you.

3

There are 3 best solutions below

2
On

These are directed graphs, with weights on the edges and the vertices.

Weighted directed graphs (also known as directed networks) are (simple) directed graphs with weights assigned to their arrows, similarly to weighted graphs (which are also known as undirected networks or weighted networks).

https://en.wikipedia.org/wiki/Directed_graph

1
On

If the upper graph had an edge $5\to 14$ and an edge $7\to 15$, then it would be the line digraph of the lower one.

0
On

The top graph is a directed weighted graph, however the bottom one is a weighted directed multigraph, as you can see there are two edges between vertices 2 and 3.

Since this was not really the question, I would just roughly sketch the way I would think to go from the top to the bottom graph in your picture.

The best way to try to formally relate the two graphs is by first define a graph as $\mathcal{G} = (V,E,\mathrm{src},\mathrm{tgt})$ where $\mathrm{src}, \mathrm{tgt}: E \to V$.

Now, because you have many edges with the same labels you need to differentiate them by labeling them differently, e.g., the edges ''3'' can be labelled as $(3,1)$, $(3,2)$, etc. numbering is up to you as long as you are consistent.

So we would have $\mathrm{src}(3,1) = 15$ and $\mathrm{tgt}(3,1) = 10$, etc.

Now, to go from the top graph to the bottom graph, let us call this $\mathcal{G}'= (V',E',\mathrm{src}', \mathrm{tgt}')$ you are looking for a set of maps from $E \to E'$ and $V \to V'$ so that the $\mathrm{src}',\mathrm{tgt}'$ satisfy certain defined rules.

I hope this can help to clarify. Now, if you are looking to enforce some ''equivalence'' between the two graphs, the maps need to be designed so that such an ''equivalence'' provably holds.