Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was wondering what the proper notation would be when concatenating paths, written as a sequence of nodes, rather than a set of edges.

That is:

Given:

$$ P = ( x, y, z ) $$

Is it valid to write the following path concatenations?

$$ \begin{eqnarray} P' & = & ( s, x, y, z, t ) \\ & = & ( s, P, t ) \\ & = & ( s ) \cup P \cup ( t ) \\ & = & ( s ) + P + ( t ) \end{eqnarray} $$

I'm assuming not all of them are regarded as valid. So which one is preferable? Or am I overlooking a better notation?

I would prefer not having to fallback to the more verbose:

$$ \begin{eqnarray} P &=& \{(x,y), (y,z)\} \\ P'&=& \{( s, x ), (x, y), (y,z), (z,t)\} \\ &=& \{(s,x),(z,t)\} \cup P \end{eqnarray} $$

However, I would still like to be able to reason about the edges along the path $P$ and $P'$, e.g.:

$$ (x,y) \in P $$

or write itterations over edges in P: $$ \{ \text{do something with $v$ and/or $w$...} \; | \; ( v, w ) \in P \} $$

share|improve this question

3 Answers 3

I suggest that you pick something reasonable and unambiguous, state it clearly, and then stick with it. Do not use $\cup$, since that means set union.

For example, you might use a semicolon: $P_1;P_2$ means that $P_1$ ends at the same vertex at which $P_2$ starts, and we want the path that traces $P_1$ and then $P_2$. This expands nicely to include extra vertices: $P_1;v;P_2$ means the path that goes along $P_1$, then from the end vertex of $P_1$ to $v$, then to the start vertex of $P_2$, and so on. This notation requires that we understand the $v$ by itself as a trivial path with no edges, which is quite reasonable. Similarly $s;P;t$ is a straightforward extension of the notation.

Usually paths are sequences of edges, not sets of edges; the order of the edges in the path is important. I would avoid writing $P = \{(a,b), (b,c)\}$ for this reason, preferring something like $P = \langle a,b,c\rangle$ if there is at most one edge between any pair of vertices, or $P=a\stackrel{E_1}{\to}b\stackrel{E_2}{\to}c$ otherwise or if the names of the edges are important.

You could say that you will abuse notation by writing $E_1\in P$ when you mean that $E_1$ is one of the edges in the path $P$, and this probably won't bother anyone. If it worries you, you might say that you will use $\lvert P\rvert$ to mean the set of edges in $P$, and then $E_1\in\lvert P\rvert$ and $\{\text{do something with $v$ and/or $w\ldots$} \mid (v,w)\in\lvert P\rvert\}$ are completely reasonable and also easy to understand.

You might also take a look at some elementary graph algorithm books to see what they do in similar cases.

share|improve this answer
    
I agree with your statement that writing a sequence of nodes is preferable and unambiguous. But that still leaves the question on how to write concatenations unambiguously. –  A.J.Rouvoet Feb 26 '13 at 17:20
    
I have added a new second paragraph that you might like better. –  MJD Feb 26 '13 at 17:26
    
Thank you, your suggestions have been helpful. I think I will use it. I do however would like to know if the kind of notation you proposed is common or if it is usually solved differently; it seems to me that some kind of standard has been set long ago for something this elementary. –  A.J.Rouvoet Feb 26 '13 at 17:29
    
I think you should wait before accepting my answer; you might get one later that you like better. –  MJD Feb 26 '13 at 17:34

In topology, a path is a function from an interval to a specified topological space, and the composition of two paths $f$ and $g$ is often just denoted $fg$.

In formal languages, a string is a sequence of characters from a specified alphabet, and the concatenation of two strings $\sigma_1$ and $\sigma_2$ is denoted $\sigma_1\sigma_2$.

Paths in a graph are closely analogous both to topological paths and to sequences of nodes/edges, which suggests denoting path concatenation simply as juxtaposition. In particular, I would write the path in your question simply as $sPt$, or as $e_1Pe_2$ where $e_1$ and $e_2$ join $s$ to $x$ and $z$ to $t$ respectively.

share|improve this answer

It depends. If your paths are simple (i.e. no vertex can appear twice), then the usual set operations should be enough.

If you can have arbitrarily complex paths, then consider the following solutions:

  • Define a new operator for path concatenation, for example $\circ$ or $\oplus$, and then use it like $\langle s \rangle \circ P \circ \langle t \rangle$, remember to differentiate between sets of nodes and paths, e.g. by using $\{$ braces $\}$ and $\langle$ brackets $\rangle$.
  • Use notation from rewriting systems, where usually a single edge is denoted by $\alpha \to \beta$ or $\alpha \leadsto \beta$, while multiple edges get a star (or a plus $+$ if there is at least one edge), $\alpha \to^* \beta$ or $\alpha \leadsto^* \beta$. Of course, if you need you can label edges $\alpha \xrightarrow{e_{\alpha\beta}} \beta$ or entire paths $\alpha \xrightarrow{P}{\!\!}^* \beta$. If you were to use this one, I recommend \xrightarrow{text} instead of \stackrel{text}{\to}.

Have fun ;-)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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