[Math] a simple path in a directed graph

definitiongraph theory

In graph theory, a simple path is a path that contains no repeated vertices. But, in a directed graph, the directions of the arrows must be respected, right? That is A -> B <- C is not a path? However, I have a source which states that would also be a simple path, but, according to the same source, that would not be a directed path. Why would A -> B <- C be considered a simple path, or is the source wrong? So, what is a simple path in a directed graph?

Best Answer

There is not a quite universal consensus about the terminology here.

However, generally, most people would probably assume that when you have a directed graphs, the paths you're talking about will be directed path unless you're being quite explicit about ignoring the directionality.

I don't think just saying "simple" will be explicit enough to convey that. By that I would understand that the path cannot repeat vertices, but there's no reason such a path cannot be expected to respect the direction of edges -- so it makes plenty of sense to speak about either directed or undirected simple paths, and to implicitly assume the former when your edges happen to have direction.

If you want to speak about an undirected path in a directed graph, for the sake of communication please say "undirected path". If you need to decode something someone else says, you're at the mercy of their terminology. Ask for clarification if it is not clear what they mean.