Graph terminology

A graph is a set $V$ together with a map $m : V \times V \rightarrow {\mathbb{N}}$ (where ${\mathbb{N}}$ denotes the set of nonnegative integers). A vertex of the graph is an element of $V$. An edge of the graph is an ordered pair $(x,y)$ with $m(x,y) > 0$. We say that the graph has no loops, when $m(x,x) = 0$ for all $x \in V$. We say that the graph has no multiple edges, when $m(x,y) \le 1$ for all $x,y \in V$. We say that the graph is undirected when $m(x,y) = m(y,x)$ for all $x,y \in V$.

In case of a graph without multiple edges, one can also specify the graph by giving the set of vertices $V$ and the set of edges $E$.

A graph is strongly connected if for any two vertices $x,y$ there is a directed path from $x$ to $y$, i.e., there are vertices $x_0=x, x_1, ..., x_m = y$ such that $(x_{i-1},x_i) \in E$ for $1 \le i \le m$.

A tournament is a directed graph without loops such that $m(x,y)+m(y,x) = 1$ for all $x,y \in V$, $x \ne y$.

Our graphs will usually be finite, and for finite graphs one can view the map $m$ as a square matrix, the adjacency matrix of the graph.