1
$\begingroup$

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?

2 Answers 2

1

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.

  • 0
    I 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
1

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.

  • 0
    Thanks 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