Question

8, (10 pts) Show that given a directed graph G = (V,E) already stored in adjacency matrix form, determining if there is a ver
0 0
Add a comment Improve this question Transcribed image text
Answer #1

Given A is adjacent matrix of directed graph of V vertices.
(A)Algorithm to check if graph has a sink or not


We need to eliminate n – 1 non-sink vertices in O(V) time and check the remaining vertex for the sink property.

step-1 To eliminate vertices, we check whether a particular index (A[i][j]) in the adjacency matrix is a 1 or a 0.
(i)If it is a 0, it means that the vertex corresponding to index j cannot be a sink.
(ii)If the index is a 1, it means the vertex corresponding to i cannot be a sink. We keep increasing i and j in this fashion until either i or j exceeds the number of vertices.

step-2 keep doing step-1 until one vertex left.
At last we are left with only vertex i.
We now check for whether row i has only 0s and whether row j as only 1s except for A[i][i], which will be 0.

Add a comment
Know the answer?
Add Answer to:
8, (10 pts) Show that given a directed graph G = (V,E) already stored in adjacency matrix form, determining if there is a vertex with in-degree n - 1 and out-degree 0 can be done in O(n) time whe...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
  • For a directed graph the in-degree of a vertex is the number of edges it has...

    For a directed graph the in-degree of a vertex is the number of edges it has coming in to it, and the out- degree is the number of edges it has coming out. (a) Let G[i,j] be the adjacency matrix representation of a directed graph, write pseudocode (in the same detail as the text book) to compute the in-degree and out-degree of every vertex in the Page 1 of 2 CSC 375 Homework 3 Spring 2020 directed graph. Store results...

  • 114points Let G- (V,E) be a directed graph. The in-degree of a vertex v is the...

    114points Let G- (V,E) be a directed graph. The in-degree of a vertex v is the number of edges (a) Design an algorithm (give pseudocode) that, given a vertex v EV, computes the in-degree of v under (b) Design an algorithm (give pseudocode) that, given a vertex v E V, computes the in-degree of v incident into v. the assumption that G is represented by an adjacency list. Give an analysis of your algorithm. under the assumption that G is...

  • Assume that the adjacency list representing a directed graph G has already been constructed. Show how...

    Assume that the adjacency list representing a directed graph G has already been constructed. Show how to determine whether G contains a universal sink, that is a vertex with in-degree |V | − 1 and out-degree 0, in time O(|V |). **Please explain in detail

  • Reachability. You are given a connected undirected graph G = (V, E ) as an adjacency...

    Reachability. You are given a connected undirected graph G = (V, E ) as an adjacency list. The graph G might not be connected. You want to fill-in a two-dimensional array R[,] so that R[u,v] is 1 if there is a path from vertex u to vertex v. If no such path exists, then R[u,v] is 0. From this two-dimensional array, you can determine whether vertex u is reachable from vertex v in O(1) time for any pair of vertices...

  • Problem 1: Dynamic Programming in DAG Let G(V,E), |V| = n, be a directed acyclic graph...

    Problem 1: Dynamic Programming in DAG Let G(V,E), |V| = n, be a directed acyclic graph presented in adjacency list representation, where the vertices are labelled with numbers in the set {1, . . . , n}, and where (i, j) is and edge inplies i < j. Suppose also that each vertex has a positive value vi, 1 ≤ i ≤ n. Define the value of a path as the sum of the values of the vertices belonging to...

  • 10. You are given a directed graph G(V, E) where every vertex vi E V is...

    10. You are given a directed graph G(V, E) where every vertex vi E V is associated with a weight wi> 0. The length of a path is the sum of weights of all vertices along this path. Given s,t e V, suggest an O((n+ m) log n) time algorithm for finding the shortest path m s toO As usual, n = IVI and m = IEI.

  • Consider the following directed graph, which is given in adjacency list form and where vertexes have...

    Consider the following directed graph, which is given in adjacency list form and where vertexes have numerical labels: 1: 2, 4, 6 2: 4, 5 3: 1, 2, 6, 9 4: 5 5: 4, 7 6: 1, 5, 7 7: 3, 5 8: 2, 6, 7 9: 1, 7 The first line indicates that the graph contains a directed edge from vertex 1 to vertex 2, from 1 to vertex 4, and 1 to 6, and likewise for subsequent lines....

  • Let G (V, E) be a directed graph with n vertices and m edges. It is known that in dfsTrace of G t...

    Let G (V, E) be a directed graph with n vertices and m edges. It is known that in dfsTrace of G the function dfs is called n times, once for each vertex It is also seen that dfs contains a loop whose body gets executed while visiting v once for each vertex w adjacent to v; that is the body gets executed once for each edge (v, w). In the worst case there are n adjacent vertices. What do...

  • (a) Given a graph G = (V, E) and a number k (1 ≤ k ≤...

    (a) Given a graph G = (V, E) and a number k (1 ≤ k ≤ n), the CLIQUE problem asks us whether there is a set of k vertices in G that are all connected to one another. That is, each vertex in the ”clique” is connected to the other k − 1 vertices in the clique; this set of vertices is referred to as a ”k-clique.” Show that this problem is in class NP (verifiable in polynomial time)...

  • Translate psuedo code for computing chromatic number of a grapgh to java code 1 //graph G,...

    Translate psuedo code for computing chromatic number of a grapgh to java code 1 //graph G, vertices n, vertices are numbered o,1-- //G i //colors are stored in arrayq //qlil has color of vertex i, initially all0 s stored in adjacency list or adjacency matrix p , returns chromatic number //colors G using mininum number of colors int color () for (i 1 to n) //if G can be colored using i colors starting at vertex 0 if (color (0,...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT