Back
0

Directed Graphs

Description: This quiz covers fundamental concepts and properties of directed graphs, including their representation, connectivity, and applications.
Number of Questions: 15
Created by:
Tags: graph theory directed graphs connectivity applications
Start the Quiz
Attempted 0/15 Correct 0 Score 0
‹
›

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

Show answer
Correct Option: A
Explanation:

The in-degree of a vertex in a directed graph is the number of edges that point to it.

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

Show answer
Correct Option: B
Explanation:

The out-degree of a vertex in a directed graph is the number of edges that originate from it.

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

Show answer
Correct Option: B
Explanation:

A directed graph is strongly connected if every vertex has a path to every other vertex.

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

Show answer
Correct Option: B
Explanation:

A directed acyclic graph (DAG) is a directed graph that contains no directed cycles.

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

Show answer
Correct Option: D
Explanation:

Directed graphs have various applications, including modeling computer networks, representing state machines, and scheduling tasks in a project.

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

Show answer
Correct Option: A
Explanation:

The topological sorting of a directed acyclic graph is a linear ordering of the vertices such that for every directed edge (u, v), u comes before v in the ordering.

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

Show answer
Correct Option:
Explanation:

In a strongly connected directed graph with n vertices, there must be at least n(n - 1) edges to ensure that every vertex can reach every other vertex.

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

Show answer
Correct Option:
Explanation:

The maximum number of edges that can be added to a directed graph with n vertices without creating a cycle is n(n - 1).

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

Show answer
Correct Option: A
Explanation:

Depth-First Search (DFS) can be used to find a topological sorting of a directed acyclic graph.

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

Show answer
Correct Option: A
Explanation:

Depth-First Search (DFS) can be used to find the strongly connected components of a directed graph.

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)

Show answer
Correct Option: A
Explanation:

The time complexity of finding the topological sorting of a directed acyclic graph using Depth-First Search (DFS) is O(V + E), where V is the number of vertices and E is the number of edges.

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)

Show answer
Correct Option: A
Explanation:

The time complexity of finding the strongly connected components of a directed graph using Depth-First Search (DFS) is O(V + E), where V is the number of vertices and E is the number of edges.

Which of the following is a directed graph data structure?

  1. Adjacency list

  2. Adjacency matrix

  3. Incidence matrix

  4. All of the above

Show answer
Correct Option: D
Explanation:

Adjacency list, adjacency matrix, and incidence matrix are all directed graph data structures.

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

Show answer
Correct Option: D
Explanation:

Directed graphs have various applications in computer science, including modeling computer networks, representing state machines, and scheduling tasks in a project.

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

Show answer
Correct Option: A
Explanation:

The main difference between a directed graph and an undirected graph is that in a directed graph, edges have a direction, while in an undirected graph, edges do not have a direction.

- Hide questions
ADVERTISEMENT

Find more quizzes from top tags

general knowledge
3615 Quizzes
119858 Questions
 technology
307 Quizzes
36705 Questions
 sports
963 Quizzes
19148 Questions
 history
1187 Quizzes
13475 Questions
 physics
598 Quizzes
13441 Questions
 biology
1160 Quizzes
12174 Questions
 science & technology
551 Quizzes
11015 Questions
 chemistry
490 Quizzes
9892 Questions
 maths
518 Quizzes
9324 Questions
 softskills
0 Quizzes
7131 Questions