## Problem

### A directed graph G is semi-connected if, for every pair of vertices u and v, either u is reachable from v or v is reachable from u (or both).

### **a) Give an example of a directed acyclic graph with a unique source that is not semi-connected**


S here is the source dor the graph and it is unique.

why it works:

Consider the directed graph with vertices {s,a,b} and edges {(s,a),(s,b)}.
It is acyclic because all edges go out of s and there is no way to return to a vertex along directed edges. Its only vertex with in-degree 0 is s, so it has a unique source. Finally, for the pair of vertices 𝑎 and b, there is no path from a to b and no path from 𝑏 to a; hence the graph is not semi-connected. Thus this is an example of a directed acyclic graph with a unique source that is not semi-connected.

### b) **Describe and analyze an algorithm to determine whether a given directed acyclic graph is semi-connected**

### Algorithm:

Because the graph is acyclic, we can obtain a topological ordering of all vertices. Let: x1, x2, x3, ..., xn be any valid topological order.

To check semi-connectedness, it is enough to verify reachability between adjacent vertices in this order.

Steps:
1. Compute a topological ordering of G.

2. For each consecutive pair (xi, xi+1):

Run a DFS/BFS starting from xi.

If xi+1 is not reachable from xi, return False (not semi-connected).

3. If all pairs pass the reachability test, return True.

IsSemiConnected(Graph H):
    order = TopoOrder(H)

    for i from 1 to order.length - 1:
        a = order[i]
        b = order[i+1]

        if not Reachable(a, b, H):
            return False

    return True

### Correctness

We prove that the algorithm correctly determines whether the DAG is semi-connected.

If at any step xi cannot reach xi+1, then xi+1 also cannot reach xi (because in a topological ordering, edges never point backward). This means neither vertex can reach the other, which violates the definition of semi-connectedness. Returning False is therefore correct.

We now prove that if every consecutive pair satisfies reachability, then every pair of vertices in the topological order is comparable by reachability.
This is the statement we prove by induction on the distance (j − i).

## Base Cases:
(j − i = 1):
When the distance between indices in the topological order is 1, we are looking at a consecutive pair (xi, xi+1). The algorithm directly checks every such pair by running a DFS/BFS from xi and confirming that xi+1 is reachable. Therefore, the statement “xi reaches xj” is true for all pairs where j − i = 1, and the base case holds.

### Inductive Hypothesis ###
Assume that for all pairs of vertices where j - i = k,
xi reaches xj.

Inductive Step (prove for j - i = k + 1)

Consider xi and x(i + k + 1).

From the inductive hypothesis: xi reaches x(i + k)

x(i + k) reaches x(i + k + 1)

Combining these two paths, we get:

xi reaches x(i + k + 1)

Thus the claim holds for distance k+1.

## Time complexity:

Topological sort: O(V + E)

DFS/BFS for each of the (n-1) consecutive pairs: O(V + E) each

then total time: O(V + E) + (V - 1) * O(V + E) = O(V * (V + E))