1
$\begingroup$

I am interested in how a structure of the following representation would be called or if there even is an established definition of such a thing.

The structure is similar to a graph. The representation shown here has the following meaning:

  • There are nodes A, B and C.
  • There are edges x and y.
  • Node A has an edge x to node B.
  • Node C has an edge y to edge x.

The first three sentences are typical descriptions for a graph. The last one does not fit into the definition of a graph. Here is a representation:

(A)---x------>(B)
          ^
          |
          |
          y
          |
          |
         (C)

This example could too be modeled using multiple graphs, lists or other structures, but I hope to find something more 'native'.

$\endgroup$
4
$\begingroup$

I'm not aware of a name for such an object, but it can easily be modeled by a single vertex-colored directed graph $\Gamma$:

As vertex set of $\Gamma$, take the union of the vertices and edges of your original directed graph. Color the original vertices blue and the original edges red. Each original edge has a "source" and a "target", which in your case can be a vertex or an edge.

For the edge set of $\Gamma$, add two directed edges for each original edge: one from the source to the edge, and one from the edge to the target.

Now $\Gamma$ is a directed graph. (If your initial "thing" was an honest graph, then $\Gamma$ is bipartite.)

$\endgroup$
0
2
$\begingroup$

(sorry for posting as a comment before) A directed graph is a pair of sets $V$ and $E$ (I use "E", since "A" is already in use in the PO's question.). The first set, $V$, contains the vertices, the second set , $E$, contains ordered pairs of elements of the vertex set, the "arcs" or directed edges. Nothing prevents you from adding an ordered pair $(A,B)$ to the vertex set and then an ordered pair of two elements of the vertex set, say, $(C,(A, B))$ to the arcs set.

So one has for the example in the question: $V=\{A, B, (A,B)\}$ and $E=\{(A ,B), (C, (A, B)\}$. And I would call the OP's example a directed graph.

$\endgroup$
1
  • $\begingroup$ Notice that this description does not allow to recover the original object from the resulting directed graph alone: you have to "remember" the description of the elements of $V$. $\endgroup$ – Tom De Medts Nov 25 '19 at 10:40

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