# Directed graphs, chains, paths…

First of all - what's a directed graph? Is this just some normal graph but with no loops or edges? I don't really understand definitions found in the web...

What is a path? I mean, as far as I know, it is a directed chain, where the chain is a "path between two vertices, connected anyhow". Ok, I understand what the chain is, but what is the DIRECTED chain?

-
A directed graph is a graph where the edges have a direction: they point from one vertex to another, rather than just connecting two vertices. – Qiaochu Yuan May 25 '13 at 23:23
All edges, right? So if there's even one edge connecting two vertices, it's not a directed graph? – khernik May 25 '13 at 23:24
And if so, what is a directed path then? Because in normal path I still can't move twice on the same edge, so what's the difference? – khernik May 25 '13 at 23:26
That depends on your conventions. You can think of one edge connecting two vertices as a pair of directed edges. In a directed path you have to follow the direction of all of the edges you travel on. – Qiaochu Yuan May 25 '13 at 23:26
Thank you very much, I understood this, but I have one more simple question if u had some time - if a path cannot repeat edges, how does this differ from a "simple path" in which I also cannot repeat vertices?...Isn't this the same requirement? If I can't repeat edges, I can't have two vertices either. – khernik May 25 '13 at 23:35

## 2 Answers

Let's use the simplest possible definitions.

A graph is a set $(V,E)$ of vertices and edges between those vertices, where an edge is an unordered pair $e=(v_1,v_2)$ of vertices. Thus $(v_1,v_2)=(v_2,v_1)$.

A directed graph is a set $(V,E)$ of vertices and directed edges between those vertices, where a directed edge is an ordered pair $\tilde e=(v_1,v_2)_\mathrm d$ of vertices. I'm using a subscript $\mathrm d$ to indicate the pair is ordered. Thus $(v_1,v_2)_\mathrm d\neq(v_2,v_1)_\mathrm d$.

In these definitions, there is no such thing as a 'partially directed graph' with some edges of each type. If you want a directed graph with some pair of vertices linked in both directions, you just include both $(v_1,v_2)_\mathrm d \;\&\; (v_2,v_1)_\mathrm d$.

An (undirected) path is any sequence of edges $(e_1,e_2,\cdots,e_n)$ connecting vertices continuously, which is invariant under reversal, so $(e_1,e_2,\cdots,e_n) = (e_n,\cdots,e_2,e_1)$. A directed path is the same without the reversal property. Generally you think about directed paths if and only if you're thinking about directed graphs.

A simple path is a path with no repeated vertices.

-

A directed graph is a graph where the edges (i.e., the "connections" between vertexes) have a direction. In diagramms, such edges are usually drawn as arrows.

You use such graphs if you want to represent relationships between nodes (i.e., the vertexes) which aren't symmetric. Say, for example, your graph represents the debt between the members of a group of people. The vertices are the individuals, and edges represent debts. Now, debt isn't a symmetric relationship - there's a difference between you owing me 30 dollars, and me owing you 30 dollars. So just knowing that person $A$ and $B$ have some non-zero debt balance isn't sufficient - you need to know who owes whom. Thus, when drawing such a graph, you draw an arrow from the lending to the borrowing party to indicatie the direction of the debt.

Now, for directed graphs, when looking at chains (or paths, or whatever you call them), you aren't usually interested in just any connection between two nodes, but in connections with a certain direction as well. In the debt-graph situation from above, you might ask yourself "Does $A$, directly or indirectly, owe $B$ money?". This is the case if there's either an arrow from $B$ to $A$, or if there are intermediate parties $C_1,C_2,\ldots,C_n$ such that there are arrows $$B\to C_1 \to C_2 \to \ldots \to C_n \to A$$

Note that this is more specific than asking for just any connection between $A$ and $B$. For example, if both $A$ and $B$ lent money to $C$, then you will have $$A \to C \leftarrow B$$ Yet this doesn't imply that $A$ owes anything to $B$, nor that $B$ owes anything to $A$.

-