---
# System prepended metadata

title: CSCI6212_HW7
tags: [' Algorithm', CSCI6212]

---

---
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:
   ![](https://i.imgur.com/msiYDsu.jpg)

   a) (5 points) Show the resulting depth-first-search tree of $G$.
   ![](https://i.imgur.com/kbizKn9.png)
   
   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.
   ![](https://i.imgur.com/i82cAOu.png)
   
   (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.**
   ![](https://i.imgur.com/0MXVCHd.jpg)

   ![](https://i.imgur.com/dxHfQrh.jpg)

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$.

   ![](https://i.imgur.com/ujd99op.jpg)
   
   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$.
   ![](https://i.imgur.com/y3Q0Aws.jpg)
   
   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.
   ![](https://i.imgur.com/T6seYYM.jpg)
   
   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$.
   ![](https://i.imgur.com/YJs3btr.jpg)
  
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.**
   ```python=
   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|)$.