Directed vs undirected graphs in Data Structures Theory - Practice Questions

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding edge direction in graphs

Which statement correctly describes the difference between a directed graph and an undirected graph?

A Both directed and undirected graphs have edges with directions, but directed graphs allow multiple edges between the same vertices.

B In a directed graph, edges connect vertices mutually without direction; in an undirected graph, edges have a direction from one vertex to another.

C In a directed graph, edges have a direction from one vertex to another; in an undirected graph, edges do not have direction and connect vertices mutually.

D Undirected graphs have edges with weights, while directed graphs do not have weights on edges.

💡 Hint

Think about whether the connection between two points has a one-way or two-way relationship.

Directed graphs have edges that point from one vertex to another, showing a one-way relationship. Undirected graphs have edges that connect vertices without direction, meaning the connection is mutual.

📋 Factual

intermediate

Counting edges in undirected graphs

In an undirected graph with 5 vertices where every vertex is connected to every other vertex exactly once, how many edges are there?

A 5

B 10

C 15

D 20

💡 Hint

Use the formula for edges in a complete undirected graph: n(n-1)/2.

For 5 vertices, the number of edges is 5 × 4 / 2 = 10.

🔍 Analysis

advanced

Edge count comparison between directed and undirected graphs

Consider a graph with 4 vertices where every possible edge exists. How many edges does the directed graph have compared to the undirected graph?

A Directed graph has 12 edges; undirected graph has 6 edges.

B Directed graph has 6 edges; undirected graph has 12 edges.

C Both directed and undirected graphs have 12 edges.

D Directed graph has 8 edges; undirected graph has 4 edges.

💡 Hint

Remember that directed graphs count edges in both directions separately, while undirected graphs count each connection once.

Directed graph edges = n × (n - 1) = 4 × 3 = 12. Undirected graph edges = n × (n - 1) / 2 = 4 × 3 / 2 = 6.

❓ Reasoning

advanced

Identifying graph type from edge list

Given the edge list: (A → B), (B → A), (B → C), (C → B), (A → C), (C → A), which type of graph does this represent?

A Directed graph with edges only in one direction between vertices.

B Undirected graph represented as directed edges in one direction only.

C Undirected graph with missing edges.

D Directed graph with edges in both directions between vertices.

💡 Hint

Check if edges exist in both directions between pairs of vertices.

Edges exist in both directions between vertices, indicating a directed graph where connections go both ways explicitly.

🚀 Application

expert

Determining connectivity in directed vs undirected graphs

Which statement correctly explains connectivity differences between directed and undirected graphs?

A In an undirected graph, if there is a path between two vertices, the path works both ways; in a directed graph, a path from vertex A to B does not guarantee a path from B to A.

B In a directed graph, connectivity is always mutual between vertices; in an undirected graph, connectivity is one-way only.

C Connectivity in undirected graphs depends on edge weights, while in directed graphs it depends on edge directions only.

D Both directed and undirected graphs always have mutual connectivity between any two connected vertices.

💡 Hint

Think about whether you can travel back and forth between two points in each graph type.

Undirected graphs have edges without direction, so paths are two-way. Directed graphs have edges with direction, so a path from A to B may not imply a path from B to A.