# Yong Liu - DSA - HW 4

## 1.
## 2.
## 3.
## 4.
>Given an O(V + E)-time algorithm to compute a path in a connected
undirected graph G = (V, E) that traverses each edge in E exactly once in each
direction.
:::info
I misunderstand the question.
:::
## 5. CLRS - Excersice 22.3-12

> Show that we can use a depth-first search of an undirected graph G to identify the
connected components of G, and that the depth-first forest contains as many trees
as G has connected components. More precisely, show how to modify depth-first
search so that it assigns to each vertex `v` an integer label v.cc between 1 and k,
where k is the number of connected components of G, such that u.cc = v.cc if
and only if u and v are in the same connected component.

The modifications work as follows:
each time the if-condition of line 8 is satisfied in `DFS-CC`, we have a new root of a tree in the forest, so we update its `cc` label to be a new value of `k`. In the recursive calls to `DFS-VISIT-CC`, we always update a descendant's connected component to agree with its ancestor's.

DFS-CC(G)
    for each vertex u ∈ G.V
        u.color = WHITE
        u.π = NIL
    time = 0
    k = 1
    for each vertex u ∈ G.V
        if u.color == WHITE
            u.cc = k
            k = k + 1
            DFS-VISIT-CC(G, u)

DFS-VISIT-CC(G, u)
    time = time + 1
    u.d = time
    u.color = GRAY
    for each vertex v ∈ G.Adj[u]
        v.cc = u.cc
        if v.color == WHITE
            v.π = u
            DFS-VISIT-CC(G, v)
    u.color = BLACK
    time = time + 1
    u.f = time

### Reference
https://walkccc.github.io/CLRS/Chap22/22.3/
## 6. CLRS - Excercise 22.4-1
> Show the ordering of vertices produced by TOPOLOGICAL-SORT when it is run on
the dag of Figure 22.8, under the assumption of Exercise 22.3-2.

| label | m | q | t | r | u | y | v | w | z | x | n | o | s | p |
| ----- | --- | -- | --- | --- | --- | --- | --- | --- | --- | --- | --- | -- | --- | --- |
| d | 1 | 2 | 3 | 6 | 7 | 9 | 10 | 11 | 12 | 15 | 21 | 22 | 23 | 27 |
| f | 20 | 5 | 4 | 19 | 8 | 18 | 17 | 14 | 13 | 16 | 26 | 25 | 24 | 28 |

## 7.
## 8. CLRS - Problem 22.1
> A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first tree can also be used to classify the edges reachable from the source of the search into the same four categories.
> **a.** Prove that in a breadth-first search of an undirected graph, the following properties hold:
>
> 1. There are no back edges and no forward edges.
> 2. For each tree edge (u,v), we have v.d=u.d+1
> 3. For each cross edge (u,v), we have v.d=u.d or v.d=u.d +1

> **b.** Prove that in a breadth-first search of a directed graph, the following properties hold:
>
> 1. There are no forward edges.
> 2. For each tree edge (u,v), we have v.d=u.d+1
> 3. For each cross edge (u,v), we have v.d≤u.d+1
> 4. For each back edge (u,v), we have 0≤v.d≤u.d0

### a.

1. Since we are in an undirected graph, if a node $x$ can go to its non-direct-parent ancestor $y$, $x$ should be the direct child of y when y is searching its childs.

2. If there is an edge (u,v) in the BFS tree, u must be discovered just 1 unit distance earlier than v, since this is an unweighted undirected graph.
- Contrapositive speaking:
- If u.d=v.d, it means they are siblings or from different branches, so there is no edge (u,v).
- If v.d-u.d>1, it means they cannot be parent and child, nor exists edge (u,v).

3.
- For v.d - u.d >= 2 (v is deeper), v is too deep to be discovered when we are standing at u.
- For u.d - v.d >= 1 (u is deeper), i.e., we are going from u to v and v is at least 1 level higher than u, this condition is impossible. Since this is an undirected graph, v shall be u's parent, leading to a tree edge.
- u.d = v.d is possible when are siblings or form branches with the same depth.
- v.d = u.d + 1 is possible when v is just discovered one shell earlier than u.

### b.

1. To have a forward edge, we would need to have already processed a vertex using more than one edge, even though there is a path to it using a single edge. Since the breadth-first search always considers shorter paths first, this is not possible.

2. Since we discover v when we stand on u, this is the shortest path from the root to v. The v.d is u.d+1.

3. There is some path from the root to v of length u.d+1 obtained by appending (u,v) to v. Since there is a path of that length, it serves as an upper bound on the minimum length of all such paths from the root to v.

4.
- It is trivial that 0≤v.d, since it is impossible to have a path from the root to v of negative length.
- From the definition of the back edge, there is a tree path from v to u. Let's say there are v,v_1,v_2,…,v_k,u in this path (it is unique because it is the tree edges). Then, we have that u.d=v_k.d+1=v_k−1.d+2=⋯=v_1.d+k=v.d+k+1. So, we have that u.d>v.d.

## 9. 22.3
> An **_Euler tour_** of a strongly connected, directed graph G=(V,E) is a cycle that traverses each edge of G exactly once, although it may visit a vertex more than once.

> **a.** Show that G has an Euler tour if and only if in-degree(v)=out-degree(v) for each vertex v∈V.

> **b.** Describe an O(E)-time algorithm to find an Euler tour of G if one exists. Hint: Merge edge-disjoint cycles.)

This is called a Eulerian path of a graph, which can be found by Hierholzer's algorithm in O(E+V) time.

### Terminology

- circuit
A circuit is a path which ends at the vertex it begins (so a loop is an circuit of length one).
### Existence
- An Eulerian cycle exists if and only if the degrees of all vertices are even.
- An Eulerian path exists if and only if the number of vertices with odd degrees is two (or zero, in the case of the existence of a Eulerian cycle)

### Key Concepts

If the graph is such that the Eulerian path is not a cycle, then add the missing edge, find the Eulerian cycle, then remove the extra edge. (This is done by finding out the two vertices with odd degrees and connecting them to each other.)

1. Try to find the 1st circuit.
2. If we have traversed all the vertices then we are done.
3. If not yet done, then we try to find a vertex in the 1st circuit, which is connecting to an undiscovered edge.
4. Starting from the vertex above, we try to find a new circuit and merge the new circuit to our 1st circuit to form the 2nd circuit.
5. If we have traversed all the vertices then we are done.
6. If not, go to 3.

### Rerefence
https://cp-algorithms.com/graph/euler_path.html
https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer%27s_algorithm
https://www.geeksforgeeks.org/hierholzers-algorithm-directed-graph/
https://primes.utm.edu/graph/glossary.html