I was wondering what to call a graph that can have a group of vertices as one vertex while at the same time allowing individual vertices in the group to be linked to other vertices in the graph. Here is a figure to illustrate:
In the example figure, note the following:
- we cannot have 2 edges from a and b to c. The semantics here is: the (a,b) group has to be linked to C and not a and b individually.
- we can have the group act as one vertex ((d,e) -> f) and we can have a subset of the group to act as one vertex as well (c -> e)
- let's assume we are only dealing with a directed graph
- let's assume the group cannot have an inward edge (the destination of every edge is a single vertex)
This cannot be represented as a hypergraph because the vertices inside a group are never linked together.
What I have in mind: we can look at this graph as a directed graph that can have vertex groups (including those that with 1 vertex). So every vertex becomes a vertex group, and then the notation would be: G(V, S, E). V is the set of individual vertices, S is the set of vertex groups defined over V, and E is the set of edges connecting v -> w s.t. v and w are in S. Does this seem sound?
Any pointers would be appreciated.
Best Answer
This is called a directed hypergraph.
Each edge of a directed hypergraph is a pair of subsets of the vertex sets: a "tail subset" and a "head subset". We think of the hyperedge as going from the tail subset to the head subset.
In the example you drew, the three edges are