(Solved): Help (b) Fig. 6.3. (a) A depth-first search tree of a connected graph, and (b) another drawing ...

Help

(b) Fig. 6.3. (a) A depth-first search tree of a connected graph, and (b) another drawing of this tree \[ \begin{aligned} \emptyset & \rightarrow 1 \rightarrow 12 \rightarrow 123 \rightarrow 1234 \rightarrow 12345 \rightarrow 123456 \rightarrow 1234567 \\ & \rightarrow 12345678 \rightarrow 1234567 \rightarrow 123456710 \rightarrow 12345671011 \\ & \rightarrow 123456710 \rightarrow 1234567 \rightarrow 123456 \rightarrow 12345 \rightarrow 1234 \rightarrow 123417 \\ & \rightarrow 12341718 \rightarrow 1234171819 \rightarrow 12341718 \rightarrow 123417 \rightarrow 1234 \rightarrow 123 \\ & \rightarrow 12 \rightarrow 1 \rightarrow \emptyset \end{aligned} \] The following proposition provides a link between the input graph \( G \), its DFStree \( T \), and the two time functions \( f \) and \( l \) returned by DFS. 11: \( \quad \operatorname{set} p(y):=x, \ell(y):=\ell(x)+1 \) and \( t(y):=i \) 12: append \( y \) to \( Q \) 13: else 14: remove \( x \) from \( Q \) 15: end if 16: end while 17: return \( (p, \ell, t) \) The spanning tree \( T \) returned by BFS is called a breadth-first search tree, or BFS-tree, of \( G \). An example of a BFS-tree in a connected graph is shown in Figure 6.2. The labels of the vertices in Figure \( 6.2 \mathrm{a} \) indicate the times at which they were added to the tree. The distance function \( \ell \) is shown in Figure 6.2b. The evolution of the queue \( Q \) is as follows, the vertices being indicated by their times. \[ \begin{aligned} \emptyset & \rightarrow 1 \rightarrow 12 \rightarrow 123 \rightarrow 1234 \rightarrow 12345 \rightarrow 2345 \rightarrow 23456 \\ & \rightarrow 234567 \rightarrow 34567 \rightarrow 345678 \rightarrow 3456789 \rightarrow 456789 \\ & \rightarrow 45678910 \rightarrow 5678910 \rightarrow 567891011 \rightarrow 67891011 \\ & \rightarrow 6789101112 \rightarrow 789101112 \rightarrow 89101112 \rightarrow 9101112 \\ & \rightarrow 910111213 \rightarrow 10111213 \rightarrow 111213 \rightarrow 1213 \rightarrow 13 \rightarrow \emptyset \end{aligned} \] (a) (0) Fig. 6.2. A breadth-first search tree in a connected graph: (a) the time function \( t \), and (b) the level function \( \ell \) The degree of a vertex \( v \) in a graph \( G \), denoted by \( d_{G}(v) \), is the number of edges of \( G \) incident with \( v \), each loop counting as two edges. In particular, if \( G \) is a simple graph, \( d_{G}(v) \) is the number of neighbours of \( v \) in \( G \). A vertex of degree zero is called an isolated vertex. We denote by \( \delta(G) \) and \( \Delta(G) \) the minimum and maximum degrees of the vertices of \( G \), and by \( d(G) \) their average degree, \( \frac{1}{n} \sum_{v \in V} d(v) \). The following theorem establishes a fundamental identity relating the degrees of the vertices of a graph and the number of its edges. Theorem \( 1.1 \) For any graph \( G \), \[ \sum_{v \in V} d(v)=2 m \]