2
$\begingroup$

So given a directed multigraph $G=(V,E)$ I am notating the nodes of any edge like so $(e_s,e_t) = e \in E$ where $e_s$ is the source and $e_t$ is the target.

However I am unsure how to notate the edges of a node that finish or start there. So far I have written $v_\text{in} = \{e_1,...,e_k\} \subseteq E$ where $v_\text{in}$ is all edges finishing at node $v$. However it's not explicit that the edges in $v_\text{in}$ actually finish at node $v$.

Is there a standard convention or more accepted way of expressing this?

Also I'm in the computer sciences so it would be great to know if I have made any mistakes in expressing the maths involved in this question.

Edit: Might have answered my own question, can I just write $v_\text{in} = \{e \mid e_t = v \}$?

$\endgroup$
3
$\begingroup$

Defining $v_{\text{in}} = \{e \mid e_t = v\}$ seems reasonable. (Even explaining in words "$v_{\text{in}}$ is the set of edges that end at $v$" would be fine.) It's not notation that I've seen people define before, but that's not a problem if you give a definition. My only doubt about it is that it's unusual for lowercase letters to denote sets.

There is not really notation that's so common that you can use it without defining it.

It's fairly common to define $E(S,T) = \{e \mid e_s \in S \text{ and } e_t \in T\}$: the set of edges from $S$ to $T$. If you do so, you could talk about $E(V, \{v\})$ for the set of edges that can start anywhere and end in $v$. This is a bit more cumbersome, but it's more flexible and will be familiar to some people.

Relatedly, $N^+(v)$ and $N^-(v)$ denote the set of "out-neighbors" and "in-neighbors" of $v$, respectively: $N^+(v)$ is the set of vertices that can be reached from $v$ by an edge, and $N^-(v)$ is the set of vertices which can reach $v$ by an edge. This isn't quite what you want. But if you, analogously, define $I^+(v)$ and $I^-(v)$ for the edges out of and into $v$, nobody will be too surprised. (I'm not convinced $I$ (for "incident") is the best letter to use here, but it's not the worst.)

$\endgroup$
  • $\begingroup$ The out-neighbors and in-neighbors thing actually massively simplified the thing I'm trying to express! It's amazing I could not find that anywhere. But also the rest of your answer was very helpful. $\endgroup$ – Jonathan Apr 1 '18 at 4:02
1
$\begingroup$

I would suggest using the notation $e_{ijk}$ to denote the $k^{th}$ edge that starts from vertex $v_i$ and ends at $v_j$. I come from a physics background and this notation is very popularly used in the network modeling of complex systems.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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