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.

Practice

1. Which of the following best describes a directed graph?

easy

A. Edges have a direction from one vertex to another

B. Edges connect vertices without any direction

C. Edges are weighted but have no direction

D. Edges connect only vertices of the same type

Solution

1. Step 1: Understand edge direction in graphs

   Directed graphs have edges that point from one vertex to another, showing direction.

2. Step 2: Compare with undirected graphs

   Undirected graphs have edges without direction, connecting vertices both ways equally.

3. Final Answer:

   Edges have a direction from one vertex to another -> Option A

4. Quick Check:

   Directed graph = edges with direction [OK]

Hint: Directed means edges point one way only [OK]

Common Mistakes:

• Confusing directed with weighted edges
• Thinking undirected edges have direction
• Assuming all graphs have directions

2. Which of the following is the correct way to represent an undirected edge between vertices A and B?

easy

A. (A → B) only

B. (A, B) only

C. (B, A) only

D. (A, B) and (B, A) both included

Solution

1. Step 1: Understand undirected edge representation

   Undirected edges connect two vertices both ways, so both (A, B) and (B, A) are included.

2. Step 2: Compare with directed edge representation

   Directed edges include only one direction, like (A → B), not both.

3. Final Answer:

   (A, B) and (B, A) both included -> Option D

4. Quick Check:

   Undirected edge = both directions stored [OK]

Hint: Undirected edges need both directions listed [OK]

Common Mistakes:

• Listing only one direction for undirected edges
• Confusing directed arrow notation with undirected
• Assuming undirected edges are stored once only

3. Given the directed graph edges: [(1, 2), (2, 3), (3, 1)], what is the result of checking if there is a path from vertex 3 to vertex 2?

medium

A. Only if the graph is undirected

B. Yes, there is a path

C. No, there is no path

D. Cannot determine without weights

Solution

1. Step 1: Analyze edges for path from 3 to 2

   Edges are (1 → 2), (2 → 3), (3 → 1). From 3, you can go to 1 only.

2. Step 2: Check if path leads to 2

   From 3 to 1, then from 1 to 2 is possible, so path exists: 3 → 1 → 2.

3. Final Answer:

   Yes, there is a path -> Option B

4. Quick Check:

   Path 3->1->2 exists [OK]

Hint: Follow edges direction step-by-step [OK]

Common Mistakes:

• Ignoring indirect paths
• Assuming no path if direct edge missing
• Confusing directed with undirected paths

4. Identify the error in this undirected graph edge list representation: edges = [(1, 2), (2, 3), (3, 1)] used as is for an undirected graph.

medium

A. Edges should be duplicated in reverse order

B. Edges must be tuples of length 3

C. Edges cannot connect vertex 3 to 1

D. No error, this is correct

Solution

1. Step 1: Understand undirected edge storage

   Undirected edges require both (u, v) and (v, u) to represent two-way connection.

2. Step 2: Check given edge list

   Edges are only listed one way, missing reverse edges like (2, 1), (3, 2), (1, 3).

3. Final Answer:

   Edges should be duplicated in reverse order -> Option A

4. Quick Check:

   Undirected edges need both directions [OK]

Hint: Undirected edges must appear both ways [OK]

Common Mistakes:

• Assuming one direction is enough
• Thinking tuples need 3 elements
• Believing given list is complete

5. You want to model a social network where friendships are mutual. Which graph type should you use and why?

hard

A. Directed graph, to track who follows whom

B. Directed graph, because friendships have direction

C. Undirected graph, because friendships go both ways

D. Weighted graph, to show friendship strength

Solution

1. Step 1: Understand the nature of friendships

   Mutual friendships mean if A is friend with B, then B is friend with A.

2. Step 2: Choose graph type matching mutual connections

   Undirected graphs represent mutual connections naturally, with edges having no direction.

3. Final Answer:

   Undirected graph, because friendships go both ways -> Option C

4. Quick Check:

   Mutual relations = undirected graph [OK]

Hint: Mutual means undirected edges [OK]

Common Mistakes:

• Choosing directed graph for mutual relations
• Confusing following with friendship
• Ignoring edge direction meaning