Home › Quizzes › Directed Graphs

Directed Graphs

This quiz covers fundamental concepts and properties of directed graphs, including their representation, connectivity, and applications.

15 Questions Published
Play Quiz Practise this topic out loud

Questions

Question 1 Multiple Choice (Single Answer)

In a directed graph, what is the in-degree of a vertex?

  1. The number of edges entering the vertex
  2. The number of edges leaving the vertex
  3. The sum of the in-degrees and out-degrees of the vertex
  4. The number of vertices adjacent to the vertex
Question 2 Multiple Choice (Single Answer)

What is the out-degree of a vertex in a directed graph?

  1. The number of edges entering the vertex
  2. The number of edges leaving the vertex
  3. The sum of the in-degrees and out-degrees of the vertex
  4. The number of vertices adjacent to the vertex
Question 3 Multiple Choice (Single Answer)

Which of the following is a necessary condition for a directed graph to be strongly connected?

  1. Every vertex has an in-degree and out-degree of at least 1
  2. Every vertex has a path to every other vertex
  3. The graph is acyclic
  4. The graph has no cycles
Question 4 Multiple Choice (Single Answer)

What is a directed acyclic graph (DAG)?

  1. A graph with no cycles
  2. A graph with no directed cycles
  3. A graph with no edges
  4. A graph with no vertices
Question 5 Multiple Choice (Single Answer)

Which of the following is an application of directed graphs?

  1. Modeling computer networks
  2. Representing state machines
  3. Scheduling tasks in a project
  4. All of the above
Question 6 Multiple Choice (Single Answer)

What is the topological sorting of a directed acyclic graph?

  1. A linear ordering of the vertices such that for every directed edge (u, v), u comes before v in the ordering
  2. A linear ordering of the vertices such that for every directed edge (u, v), v comes before u in the ordering
  3. A linear ordering of the vertices such that every vertex has an in-degree of 0
  4. A linear ordering of the vertices such that every vertex has an out-degree of 0
Question 7 Multiple Choice (Single Answer)

What is the minimum number of edges required in a directed graph with n vertices to ensure that it is strongly connected?

  1. n - 1
  2. n
  3. n + 1
  4. 2n - 1
Question 8 Multiple Choice (Single Answer)

What is the maximum number of edges that can be added to a directed graph with n vertices without creating a cycle?

  1. n - 1
  2. n
  3. n + 1
  4. 2n - 1
Question 9 Multiple Choice (Single Answer)

Which of the following algorithms can be used to find a topological sorting of a directed acyclic graph?

  1. Depth-First Search (DFS)
  2. Breadth-First Search (BFS)
  3. Dijkstra's algorithm
  4. Floyd-Warshall algorithm
Question 10 Multiple Choice (Single Answer)

Which of the following algorithms can be used to find the strongly connected components of a directed graph?

  1. Depth-First Search (DFS)
  2. Breadth-First Search (BFS)
  3. Dijkstra's algorithm
  4. Floyd-Warshall algorithm
Question 11 Multiple Choice (Single Answer)

What is the time complexity of finding the topological sorting of a directed acyclic graph using Depth-First Search (DFS)?

  1. O(V + E)
  2. O(V^2)
  3. O(E log V)
  4. O(V^3)
Question 12 Multiple Choice (Single Answer)

What is the time complexity of finding the strongly connected components of a directed graph using Depth-First Search (DFS)?

  1. O(V + E)
  2. O(V^2)
  3. O(E log V)
  4. O(V^3)
Question 13 Multiple Choice (Single Answer)

Which of the following is a directed graph data structure?

  1. Adjacency list
  2. Adjacency matrix
  3. Incidence matrix
  4. All of the above
Question 14 Multiple Choice (Single Answer)

Which of the following is an application of directed graphs in computer science?

  1. Modeling computer networks
  2. Representing state machines
  3. Scheduling tasks in a project
  4. All of the above
Question 15 Multiple Choice (Single Answer)

What is the difference between a directed graph and an undirected graph?

  1. In a directed graph, edges have a direction, while in an undirected graph, edges do not have a direction
  2. In a directed graph, vertices can have multiple edges between them, while in an undirected graph, vertices can only have one edge between them
  3. In a directed graph, cycles are allowed, while in an undirected graph, cycles are not allowed
  4. In a directed graph, the number of edges is always greater than or equal to the number of vertices, while in an undirected graph, the number of edges is always less than or equal to the number of vertices
← Back to Quizzes