I've found several sources describing a relation notated $\sim$ signifying adjacency in an undirected graph, but nothing explicitly describing an equivalent for a directed graph. I've been using $\overset{\mathit{member}}{\longrightarrow}$, mainly because I have different types of edges so I need a long symbol to overset with the type of the edge linking the nodes. Is this appropriate? Is there a more usual notation?
What's the equivalent of the adjacency relation for a directed graph?
2 Answers
An arrow is absolutely appropriate to use in this case. For example, see Shimon Even's Graph Algorithms. In fact, I think it would be questionable to use anything but an arrow for a directed edge.
Note that Even places the name of the edge over the arrow; your notation of putting the edge type over the arrow is fine too. Or you might put the type underneath, to save room above for the name in case you might need it later.
-
0Thanks Mark. Now I'm glad I defined a macro for the arrow notation so I don't have to change it all over the place. – 2012-07-25
-
0I did find another notation for directed edges: Bollobás uses $\overrightarrow{xy}$ for a directed edge from vertex $x$ to vertex $y$. – 2012-07-25
If by relation is meant the pairwise relation $R$ on the graph's vertices $V \times V$ such that $vRw$ iff there is an edge (resp arc) between $v$ and $w$ in a graph (resp. digraph), then this relation is neither reflexive nor transitive (hence the importance of transitive closure and transitive reduction). $R$ is symmetric for graphs, and asymmetric for digraphs.
-
0Yup, that's exactly the relation I mean. What I'm looking for is the appropriate notation for the relation. As you observe, the relation for a directed graph doesn't have the right properties to be an equivalence relation, a partial order or anything convenient like that, so I'm not sure what to use... – 2012-07-25
-
0As Mark Dominus says below, arrow is the standard notation for arcs in digraphs if that's all you were asking about. The edge relation in graphs with self-loops is a *tolerance* (formalized by the topologist Zeeman in the 1960s) but arc relation in digraphs means it is not even that, being asymmetric... When arcs (or edges) are labeled, the corresponding relation is no longer binary-valued but valued in a more general set or structure. – 2012-07-25
-
0Thanks Alan, I'd thought loosely about the properties of these relations but hadn't seen anything explicit. These pointers are very helpful. – 2012-07-25