Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > A sink in a directed graph is a vertex i such...
Start Learning for Free
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.
i = 0
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3)
flag = 0;
if (flag)
printf("Sink exists");
else
printf("Sink does not exist");
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3)
flag = 0;
if (flag)
printf("Sink exists");
else
printf("Sink does not exist");
Q. Choose the correct expressions for E3
- a)(A[i][j] && !A[j][i])
- b)(!A[i][j] && A[j][i])
- c)(!A[i][j] | | A[j][i])
- d)(A[i][j] | | !A[j][i])
Correct answer is option 'D'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
A sink in a directed graph is a vertex i such that there is an edge fr...
Below explanation is for Previous Part of this question: For vertex i to be a sink, there should be no edge from i to any other vertex.
According the input given in question,
A[i][j] = 1 means there is an edge from vertex i to j.
A[i][j] = 0 means there is no edge from i to j
A[i][j] = 0 means there is no edge from i to j
For a node to i to be sink,
A[i][j] should be 0 for all j
A[j][i] should be 1 for all j.
A[j][i] should be 1 for all j.
The above pseudo code checks every vertex i for sink, starting from i = 0. It basically checks every vertex j after i for being a sink. The trick in pseudo code is, it doesn't check for j smaller than i. The i picked by this loop may not be sink. It basically makes sure that we don't ignore a potential sink. The check whether i is actually a sink or not is done later after do while loop. Vertex i is a potential sink while A[i][j] is zero Thus, E1 : !A[i][j] If the above condition is false, then i is not a sink. All j < i can also not be a sink because there is no edge from i to j. Now, the next potential sink can be j. So, E2 : i = jExplanation for this question The following pseudo code basically checks if the potential sink picked by the code above is actually a sink or not.
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3)
flag = 0;
for (j = 0; j < n; j++)
if ((j! = i) && E3)
flag = 0;
flag equals to 0 means i is not a sink. The code sets the flag 0 as soon as it finds out that i is not a sink.
A node i is not a sink if either of the following two conditions become true for any j not equal to i.
A[i][j] is 1 for any j
OR A[j][i] is 0 for any j
A[i][j] is 1 for any j
OR A[j][i] is 0 for any j
E3 : (A[i][j] | | !A[j][i]) Therefore option D is correct
Most Upvoted Answer
A sink in a directed graph is a vertex i such that there is an edge fr...
Explanation:
The given algorithm is used to determine whether there is a sink in a directed graph. Let's go through the algorithm step by step to understand its working.
Step 1:
Initialize i to 0. This represents the current vertex being checked as a potential sink.
Step 2:
Start a loop that continues until j is greater than or equal to n (the number of vertices in the graph).
Step 3:
Set j = i + 1. This is to check if there is an edge from vertex i to j.
Step 4:
Start another loop that continues until j is less than n.
Step 5:
Check if there is an edge from vertex i to j (A[i][j] = 1). If there is, update j to j + 1 and continue to the next iteration of the loop.
Step 6:
If there is no edge from vertex i to j, break out of the loop.
Step 7:
Check if j is equal to n. If it is, it means that there is an edge from every vertex j to i, but no edge from i to any other vertex. Therefore, i is a sink.
Step 8:
Update i to i + 1 and repeat the process from Step 2.
Step 9:
After the loop ends, check if flag is still 1. If it is, it means that all vertices have been checked and there is a sink in the graph. If flag is not 1, it means that there is no sink in the graph.
E3:
The expression (A[i][j] || !A[j][i]) checks if there is an edge from vertex i to j (!A[j][i]) and there is no edge from j to i (A[i][j]). If this expression is true for all vertices j (except i), it means that i is a sink.
Therefore, the correct expression for E3 is (A[i][j] || !A[j][i]), which is option D.
The given algorithm is used to determine whether there is a sink in a directed graph. Let's go through the algorithm step by step to understand its working.
Step 1:
Initialize i to 0. This represents the current vertex being checked as a potential sink.
Step 2:
Start a loop that continues until j is greater than or equal to n (the number of vertices in the graph).
Step 3:
Set j = i + 1. This is to check if there is an edge from vertex i to j.
Step 4:
Start another loop that continues until j is less than n.
Step 5:
Check if there is an edge from vertex i to j (A[i][j] = 1). If there is, update j to j + 1 and continue to the next iteration of the loop.
Step 6:
If there is no edge from vertex i to j, break out of the loop.
Step 7:
Check if j is equal to n. If it is, it means that there is an edge from every vertex j to i, but no edge from i to any other vertex. Therefore, i is a sink.
Step 8:
Update i to i + 1 and repeat the process from Step 2.
Step 9:
After the loop ends, check if flag is still 1. If it is, it means that all vertices have been checked and there is a sink in the graph. If flag is not 1, it means that there is no sink in the graph.
E3:
The expression (A[i][j] || !A[j][i]) checks if there is an edge from vertex i to j (!A[j][i]) and there is no edge from j to i (A[i][j]). If this expression is true for all vertices j (except i), it means that i is a sink.
Therefore, the correct expression for E3 is (A[i][j] || !A[j][i]), which is option D.
Attention Computer Science Engineering (CSE) Students!
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Top Courses for Computer Science Engineering (CSE)View all
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer?
Question Description
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer?.
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer?.
Solutions for A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer?, a detailed solution for A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer? has been provided alongside types of A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.i = 0do { j = i + 1; while ((j < n) && E1) j++;if (j < n) E2;} while (j < n);flag = 1;for (j = 0; j < n; j++) if ((j! = i) && E3) flag = 0;if (flag) printf("Sink exists");else printf("Sink does not exist");Q.Choose the correct expressions forE3 a)(A[i][j] && !A[j][i])b)(!A[i][j] && A[j][i])c)(!A[i][j] | | A[j][i])d)(A[i][j] | | !A[j][i])Correct answer is option 'D'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup