---
title: CSCI6212_HW7
tags: CSCI6212, Algorithm
---

<style>
.text-center{
text-align: center; //文字置中
}
.text-left{
text-align: left; //文字靠左
}
.text-right{
text-align: right; //文字靠右
}
</style>

<h1 class="text-center">CSCI 6212 - Homework 7</h1>
<h3 class="text-center">Chien-Huan Kao (G37556856)</h3>
<br>

1. (30 points) Consider the graph $G$ in Figure $1$ where the number next to each vertex shows a depth-first-number obtained by applying the depth-first-search. A sequence of low points assigned and revised to each vertex is given as:

a) (5 points) Show the resulting depth-first-search tree of $G$.

b) (10 points) List a sequence of 18 edges in the order that they have been examined. Note that such a sequence may not be unique.

(c,a) (a,h) (h,j) (j,k) (k,i) (i,j) (i,h) (k,l) (l,j) (a,b) (b,c) (c,f) (f,d) (d,e) (e,f) (e,c) (d,c) (c,g)

c) (5 points) Show all articulation points of $G$.

**Sol.**
The $c, a$,and $h$ points are articulation points of $G$.

d) (10 points) Apply the $O(|E|)$ time algorithm to compute all biconnected components of $G$. Show all your work including stack operations.

**Sol.**


2. (20 pts each) Given a graph $G$, an independent set of $G$ with size $k$ is defined as a subgraph $g \subseteq G$ with $k$ vertices such that there is no edge in $G$ between any pair of vertices in $g$. Let $T_1$ be a breadth-first-search tree of an unknown graph $G_1$ starting at $a$ and $T_2$ be a depth-first-search of tree of an unknown graph $G_2$ starting at $a$.


a) Is it possible for $G_1$ to have an independent set of size $6$? Justify your answer.

**Sol.**
No, there is no possible for $G_1$ to have an independent set of size $6$. If there is an edge between two vertices in $T_1$, these two vertices cannot be in the same independent set. Therefore, the layer $i$ of the vertices in possible independent sets cannot contain the vertices in layer $i+1$ and $i-1$. The maximum independent set size is 5.

b) What is the maximum possible number of edges $G_1$ can have?

**Sol.**
The maximum possible number of edges $G_1$ is $23$.

c) Is it possible for $G_2$ to have an independent set of size $6$? Justify your answer.

**Sol.**
Yes, it is possible for $G_2$ to have an independent set of size $6$. If two nodes are not connected, there must have different paths in DFS like follwoing picture.

d) What is the maximum possible number of edges $G_2$ can have?

**Sol.**
The maximum possible number of edges $G_2$ can have is $15$.

3. (10 points) Let $v$ be a vertex in a connected graph $G$. Let $T_D$ be a depth-first-search tree of $G$ starting at $v$. Let $T_B$ be a breadth-first-search tree of $G$ starting at $v$. Is it always true that $depth(T_D) \geq depth(T_B)$ ? Give a clear argument if your answer is yes. Otherwise, give a counterexample.

**Sol.**
Yes. BFS always do that we insert a first node (root) in a queue then we keep removing nodes from the rear and keep inserting their adjacent nodes in the same queue if they are not already visited. This restricts visiting a non-adjacent node before all adjacent ones. By doing this, we can find the unique shortest path from the root to any other node. Since BFS of $G$ finds the shortest path, the layer of the BFS tree must be minimum. As a result, the possible depth of $T_D$ in $G$ must greater or equal to the $T_B$.

4. (15 points) Consider an undirected tree $T$ with $w(e) = 1$ for each $e \in E(T)$. A longest path in $T$ must start at a leaf node and also end at a leaf node. Give an $O(|E|)$ time algorithm to find a longest path in $T$.

**Sol.**
First, we choose any leaf node $u$ as a starting node.
Second, we perform a DFS search from $u$ to find the farthest node $v$. We can compute the distance of each node from $u$. We store these distances in an array $d$. The maximum in $d$ represents the node $v$.
Third, we perform another DFS search from $v$ to find the farthest leaf node $w$.
The longest path in the $T$ is from $v$ to $w$.
This algorithm takes $O(|E|)$ time as it performs two DFS searches, each of which visits every node and edge in the tree once.

5. (10 points) The input is a connected undirected graph $G$, a spanning tree $T$ of $G$, and a vertex $v \in V(G)$. Design an $O(|E|)$ time algorithm to determine whether $T$ is a valid breadth-first-search tree of $G$ rooted at $v$, i.e., determine whether $T$ can be an output of BFS on $G$ starting with $v$.

**Sol.**

   def Check(G, T, v):
        Q = [v]
        visited = set([v])
        while Q:
            u = Q.pop(0)
            for w in T.neighbors(u):
                if w not in visited:
                    visited.add(w)
                    Q.append(w)
                if not T.has_edge(u, w):
                    return False
        return True

6. (15 points) Given an undirected graph $G$ with $w(e) = 1$ for each $e \in E(G)$, the length of the smallest cycle is called the girth of the graph. Design an $O(n|E|)$ time algorithm to compute the girth of a given graph $G$.
Note that we can use the Floyd's all-to-all shortest algorithm to find the girth in $O(n^3)$ time. But if the given graph is sparse such as planar graphs. (For any planar graph $G, |E(G)| = O(n)$ ). An $O(n|E|)$ time algorithm can be significantly better than an $O(n^3)$ time algorithm for such graphs.

**Sol.**
Procedure **bfs_cycle_length**(root):
$\text{ } \text{ } \text{ } \text{ }$ visited = []
$\text{ } \text{ } \text{ } \text{ }$ queue = []
$\text{ } \text{ } \text{ } \text{ }$ dist = []
$\text{ } \text{ } \text{ } \text{ }$ queue.append(root)
$\text{ } \text{ } \text{ } \text{ }$ visited.append(root)
$\text{ } \text{ } \text{ } \text{ }$ while queue is not empty:
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ u = queue.pop(0)
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ for v in all u adjacnt nodes:
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ if v not in visited:
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ visited.append(v)
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ queue.append(v)
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ dist[v]=dist[u]+1
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ else if v not queal to the parent node of u:
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ cycle_len=dist[u]+dist[v]+1
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ return cycle_len
$\text{ } \text{ } \text{ } \text{ }$ return $\infty$

Procedure **girth**:
$\text{ } \text{ } \text{ } \text{ }$ $girth = \infty$
$\text{ } \text{ } \text{ } \text{ }$ For each vertex $v \in V(G)$:
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ cycle_len = bfs_cycle_length(v)
$\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }$ girth = min(girth, cycle_len)
$\text{ } \text{ } \text{ } \text{ }$ return girth

The time complexity of BFS is $O(|E|)$ and I run each node as root. So, the total time complexity is n * |E| = $O(n|E|)$.