Math Problems Vault

Problem 148

For a given set of vertices $v_{1}, \ldots , v_{n}$ , find

?

(a)

the total number of graphs;

(b)

the number of graphs without loops;

(c)

the number of graphs in which there is at most one edge between any two vertices;

(d)

the number of graphs without loops in which there is at most one edge between any two vertices;

(e)

the number of tournaments. A tournament is a graph without loops in which there is exactly one edge between any two distinct vertices.

Problem 149

Prove that a directed graph without cycles has at least one source and at least one sink.

?

Problem 150

Let $\mathfrak {G}=(V, E)$ be an acyclic graph. Prove that its vertices can be numbered $V=\left\{ v_{1}, \ldots , v_{n}\right\}$ so that if $\left(v_{i}, v_{j}\right) \in E$ , then $i<j$ .

?

Problem 151

Let $\mathfrak {G}=(V, E)$ be a graph, $V=\left\{ v_{1}, \ldots , v_{n}\right\}$ , $A$ the adjacency matrix, $W \subseteq V$ , and let the column vector $w$ contain zeros and ones, where $w_{i}=1$ means $v_{i} \in W$ . Determine the meaning of the Boolean products $A w$ and $w^{T} A$ .

?

Problem 152

Prove that in a tournament, from the vertex $v$ with the largest out-degree there is a path of length at most two to any other vertex.

?

Problem 153

By induction on the number of vertices, prove the following statement: a tournament has a simple path passing through all vertices.

?

Problem 154

A championship is organized as a round-robin tournament (each team plays one match against every other team, and the winner is determined by the number of matches won). Prove that if the champion lost to team $A$ , then $A$ lost to some team $B$ , which in turn lost to the champion.

?

Problem 155

(a)(b)

Determine what the reachability graph is for

?

(a)

a graph with $n$ vertices and an empty set of edges;

(b)

a graph with $n$ vertices: $V=\left\{ v_{1}, \ldots , v_{n}\right\}$ , whose edges form a cycle: $E=\left\{ \left(v_{1}, v_{2}\right),\left(v_{2}, v_{3}\right), \ldots ,\left(v_{n-1}, v_{n}\right),\left(v_{n}, v_{1}\right)\right\}$ .

Problem 156

Compute the reachability matrix $A_{\mathfrak {G}}$ * for the following graph

\mathfrak {G}=(\left\{ a, b, c, d, e, f, g\right\} ,\left\{ (a, b),(b, a),(a, c),(b, d),(e, d),(d, f),(f, c),(c, f),(g, e)\right\} )

and construct its corresponding reachability graph. Find all bases of the graph $\mathfrak {G}$ .

?

Problem 157

Construct the adjacency matrices and adjacency lists for the directed graphs $\mathfrak {G}_{1}$ and $\mathfrak {G}_{2}$ shown in Fig. 27. Compute the reachability matrices and construct the corresponding reachability graphs.

$Fig. 27. Graphs \mathfrak {G}_{1} and \mathfrak {G}_{2}.$ Fig. 27. Graphs \mathfrak {G}{1} and \mathfrak {G}{2}.

?

Problem 158

Prove Lemma 60 on page 193.

Lemma 60: The relation of strict reachability on the strongly connected components is a relation of strict partial order, i.e., it is antireflexive, antisymmetric, and transitive.

?

Problem 159

Let the graph $\mathfrak {G}=(V, E)$ be given by its adjacency matrix:

A_{\mathfrak {G}}=\left[\begin{smallmatrix} 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \end{smallmatrix}\right].

Construct the reachability graph $\mathfrak {G}^{*}=\left(V, E^{*}\right)$ for $\mathfrak {G}$ and determine how many new edges it has, i.e., what the difference $\left|E^{*}\right|-\left|E\right|$ equals.

?

Problem 160

Prove that a loopless graph is acyclic if and only if every strongly connected component contains exactly one element.

?

Problem 161

Show that for every positive $n$ there exists an acyclic graph with $n$ vertices and $\frac{n(n-1)}{2}$ edges. Prove that in any graph with more edges than that, there is necessarily a cycle.

?

Problem 162

Prove that in a directed graph without cycles there exists a unique basis, consisting of all sources.

?

Problem 163

For the graphs $\mathfrak {G}_{1}$ and $\mathfrak {G}_{2}$ in Fig. 28, determine the strongly connected components and the strict reachability relation on them.

$Fig. 28. Graphs \mathfrak {G}_{1} and \mathfrak {G}_{2}.$ Fig. 28. Graphs \mathfrak {G}{1} and \mathfrak {G}{2}.

?