Check if graph is semiconnected

22.5-7
A directed graph G=(V,E) is semiconnected if, for all pairs of vertices (u,v)
we have u to v or v to u. Give an efficient algorithm to determine whether
or not G is semiconnected. Prove that your algorithm is correct, and analyze its
running time.


Call STRONGLY-CONNECTED-COMPONENTS.

Form the component graph.

Topologically sort the component graph. It is possible to topologically sort the component graph, because component graph is always a DAG (Directed Acyclic Graph)


 Verify that the sequence of vertices (v1,v2,...vk) given by topological sort forms a linear chain in the component graph. That is, verify that the edges (v1,v2),(v2,v3) ,(v (k-1),vk)  exist in the component graph. If the vertices form a linear chain, then the original graph is semiconnected; otherwise it is not.

Because we know that all vertices in each SCC are mutually reachable from each other, it suffices to show that the component graph is semiconnected if and only if it contains a linear chain.

Total running time is O(V+E).

Check if graph is singly connected

A directed graph G = (V,E) is singly connected if there is at most one
directed path from u to v for all vertices u, v  in V . Give an efficient algorithm to determine whether or not a directed graph is singly connected.

Solution. For each vertex u in V , perform a DFS on the given graph G. Check if there are any foward edges or cross edges (in the same component) in any one of the searches. If no such edges exist, then the graph is singly connected, else not.
Time complexity: O(|V |(|V | + |E|)).
The graph is singly connected even with back edges existed. Since back edges implies there is a path u to  v and v to u, which is consistent with the definition of single connectedness.

DFS using stack not recursion.

s[x] = start time of x;
f[x]= finish time of x
color[x] - stores the state of the vertex
WHITE: undiscovered
GRAY: still processing
BLACK: finished
time - global variable to update start and finish times

 DFS(G)
         for each u in V do
                  color[u]=WHITE;
                  p[u]=NIL;
         end for
         for each u in V do
                  if color[u]=WHITE do
                         DFS-VISIT(G,u)
                  end if
         end for

DFS-VISIT(G,u)
         stack S=nil
         push(S,u)
         while S is not empty do
                   x=pop(S)
                  if color[x]=WHITE do
                            time=time+1
                            s[x]=time
                            color[x]=GRAY
                            push(S,x)
                            for each v in Adj[x] do
                                     if color[v]=WHITE do
                                              p[v]=x;
                                              push(S,v);                                             
                                    end if
                           end for
                  else if colox[x]=GRAY do
                           time=time+1
                            f[x]=time
                            color[x]=BLACK
                   end if
          end while

Check if a graph is bipartite/ determines whether it is possible to designate some of the wrestlers as good guys and the remainder as bad guys such that each rivalry is between a good guy and a bad guy.

Algorithm:
Perform as many BFS's as needed to cover all vertices. Assign all wrestlers whose distance is even as good guys and all wrestlers whose distance is odd to be bad guys.Then check each edge to verify that it goes from a good guy to a bad guy. 

O(V+E) : BFS using adjacency lists
O(V): designate a wrestler as good or bad
0(E): check edges.



Simpler implementation : Uses adjacency matrix.


// C++ program to find out whether a given graph is Bipartite or not

#include <iostream>

#include <queue>

#define V 4

using namespace std;

// This function returns true if graph G[V][V] is Bipartite, else false

bool isBipartite(int G[][V], int src)

{

    // Create a color array to store colors assigned to all veritces. Vertex

    // number is used as index in this array. The value '-1' of  colorArr[i]

    // is used to indicate that no color is assigned to vertex 'i'.  The value

    // 1 is used to indicate first color is assigned and value 0 indicates

    // second color is assigned.

    int colorArr[V];

    for (int i = 0; i < V; ++i)

        colorArr[i] = -1;

    // Assign first color to source

    colorArr[src] = 1;

    // Create a queue (FIFO) of vertex numbers and enqueue source vertex

    // for BFS traversal

    queue <int> q;

    q.push(src);

    // Run while there are vertices in queue (Similar to BFS)

    while (!q.empty())

    {

        // Dequeue a vertex from queue ( Refer http://goo.gl/35oz8 )

        int u = q.front();

        q.pop();

         // Find all non-colored adjacent vertices

        for (int v = 0; v < V; ++v)

        {

            // An edge from u to v exists and destination v is not colored

            if (G[u][v] && colorArr[v] == -1)

            {

                // Assign alternate color to this adjacent v of u

                colorArr[v] = 1 - colorArr[u];

                q.push(v);

            }

            //  An edge from u to v exists and destination v is colored with

            // same color as u

            else if (G[u][v] && colorArr[v] == colorArr[u])

                return false;

        }

    }

    // If we reach here, then all adjacent vertices can be colored with

    // alternate color

    return true;

}

// Driver program to test above function

int main()

{

    int G[][V] = {{0, 1, 0, 1},

        {1, 0, 1, 0},

        {0, 1, 0, 1},

        {1, 0, 1, 0}

    };

    isBipartite(G, 0) ? cout << "Yes" : cout << "No";

    return 0;

}

Time complexity: O(V^2) (BFS with adjacency matrix)

Better : O(V+E): BFS with adjacency list

Show that determining whether a directed graph G contains a universal sink – a vertex of indegree |V| - 1 and outdegree 0 – can be determined in time O(V ).

How many sinks could a graph have?

• 0 or 1

How can we determine whether a given vertex u is a universal sink?

• The u row must contain 0’s only

• The u column must contain 1’s only

• A[u][u]=0

How long would it take to determine whether a given vertex u is a universal sink?

• O(V) time 

UNIVERSAL-SINK(A)

let A be |V|x|V|

i=j=1

while i<=|V| and j<=|V| 

      if a<sub>ij =1
          then i=i+1;
          else j=j+1;
if i>|V|
   return "no universal sink";
if ISSINK(A,i) =false
   return "no universal sink";
else 
  return i;

ISSINK(A,k)</sub>

let A be |V|x|V|
for j=1 to |V|
   if a_kj=1 or (a_jk=0 and j!=k)
       return false
return true