Discrete Math Quiz: Translating Word Problems
19 questions · exam conditions
0:00
Translating Word ProblemsQuestion 1 of 19

A university course scheduling system must ensure that no student has conflicting exam times. Each course has exactly one exam, and students can be enrolled in multiple courses. Two courses conflict if they share at least one student. The system needs to assign exam time slots such that conflicting courses have different time slots. What type of discrete structure best models this problem, and what is the optimization goal?

Create a bipartite graph with courses on one side and students on the other; minimize the number of edges between time slot assignments
Create an undirected graph where vertices are courses and edges connect courses with shared students; find a proper vertex coloring with minimum colors
Create a directed graph where vertices are courses and edges point from prerequisite to dependent courses; find a topological ordering with minimum levels
Create an undirected graph where vertices are students and edges connect students in the same course; find a maximum independent set for each time slot
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Translating Word Problems

Practice Translating Word Problems in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Translating Word Problems, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

A university course scheduling system must ensure that no student has conflicting exam times. Each course has exactly one exam, and students can be enrolled in multiple courses. Two courses conflict if they share at least one student. The system needs to assign exam time slots such that conflicting courses have different time slots. What type of discrete structure best models this problem, and what is the optimization goal?

  1. Create a bipartite graph with courses on one side and students on the other; minimize the number of edges between time slot assignments
  2. Create an undirected graph where vertices are courses and edges connect courses with shared students; find a proper vertex coloring with minimum colors (correct answer)
  3. Create a directed graph where vertices are courses and edges point from prerequisite to dependent courses; find a topological ordering with minimum levels
  4. Create an undirected graph where vertices are students and edges connect students in the same course; find a maximum independent set for each time slot
Explanation: This is a classic graph coloring problem. Courses are vertices, edges represent conflicts (shared students), and colors represent time slots. We need a proper coloring (adjacent vertices have different colors) with minimum colors to minimize time slots. Choice A models enrollment but doesn't capture the conflict structure. Choice C incorrectly models prerequisites rather than enrollment conflicts. Choice D focuses on students rather than course conflicts.

Question 2

A task scheduling system manages project workflows where some tasks must be completed before others can begin, tasks have estimated durations, and some tasks can be performed in parallel. The system needs to determine the minimum project completion time and identify which tasks are critical (any delay in these tasks delays the entire project). Which modeling approach addresses both requirements?

  1. A directed acyclic graph with tasks as vertices and dependencies as edges, using topological sorting to find the optimal task ordering sequence
  2. A directed graph with tasks as vertices, dependencies as edges, and using depth-first search to identify strongly connected components of critical tasks
  3. An undirected graph where tasks are vertices, edges represent potential parallelism, and vertex weights are durations, finding the maximum weight independent set
  4. A directed acyclic graph with tasks as vertices, dependencies as edges, and vertex weights as durations, computing the longest path to identify critical tasks (correct answer)
Explanation: When you encounter project scheduling problems involving task dependencies, durations, and critical path analysis, you're dealing with a classic application of directed acyclic graphs (DAGs) and the Critical Path Method (CPM). The correct approach uses a DAG where tasks are vertices, dependencies are directed edges, and vertex weights represent task durations. To find the minimum project completion time, you compute the longest path from start to finish—this might seem counterintuitive, but since weights represent durations, the longest path determines when the project completes. Tasks on this longest path are critical because any delay in them delays the entire project. Option A uses topological sorting, which finds a valid ordering of tasks but doesn't identify critical tasks or compute minimum completion time—it just ensures dependencies are respected. Option B mentions strongly connected components, but DAGs by definition have no cycles, so this approach is fundamentally misapplied. A task scheduling problem requires directed edges to represent dependencies, making this inappropriate. Option C uses an undirected graph and seeks a maximum weight independent set, which would find the most time-consuming tasks that don't conflict with each other—completely missing the dependency relationships that define the scheduling problem. The key insight is that critical path analysis requires computing longest paths in a weighted DAG, where path length represents total duration. Remember: in scheduling problems, "critical path" always means the longest path through the dependency network, identifying bottleneck tasks that control project timing.

Question 3

A genetic research lab studies inheritance patterns in a population. They track family relationships, genetic markers, and disease occurrence. The research focuses on identifying genetic markers that appear in individuals who have the disease and also appear in their ancestors, but are absent in healthy family members. Each person has exactly two biological parents (if known), and genetic markers are inherited from parents. What discrete structure best models this for the research goal?

  1. A directed acyclic graph representing family lineage with vertex attributes for genetic markers and disease status, analyzing paths from ancestors to descendants (correct answer)
  2. An undirected graph where edges connect family members and vertex weights represent the number of shared genetic markers with diseased individuals
  3. A forest of binary trees where each tree represents a family, internal nodes are parents, leaves are current generation, and edge labels show inherited markers
  4. A bipartite graph with people on one side and genetic markers on the other, with edge attributes indicating inheritance source and disease correlation
Explanation: Family inheritance requires a directed acyclic graph (family tree) where edges show parent-child relationships and direction indicates inheritance flow. The research goal requires tracing marker inheritance paths from ancestors to diseased descendants. Choice B loses the inheritance direction and generational structure. Choice C restricts to binary trees, which can't represent cases where both parents are known and may themselves be related. Choice D loses the family relationship structure essential for inheritance analysis.

Question 4

A logistics company needs to model package delivery routes where drivers start at a central depot, visit multiple delivery locations exactly once each, and return to the depot. The company wants to minimize total travel time while ensuring each route takes no more than 8 hours. Drivers can carry at most 20 packages, and some locations require special handling equipment available on only certain vehicles. How should this be modeled?

  1. As a minimum spanning tree problem with weight constraints on edges and capacity constraints on vehicle subtrees
  2. As a vehicle routing problem using a complete weighted graph with additional constraint sets for time limits, capacity limits, and equipment requirements (correct answer)
  3. As a bipartite matching problem between drivers and delivery locations with edge weights representing travel time and equipment compatibility
  4. As a shortest path problem on a directed graph where nodes represent (location, time, capacity) states and edges represent valid transitions
Explanation: This is a constrained vehicle routing problem (VRP), which extends the traveling salesman problem to multiple vehicles with various constraints. It requires a complete weighted graph for distances plus separate constraint structures for capacity, time, and equipment. Choice A (MST) doesn't require returning to depot or visiting locations exactly once. Choice C (bipartite matching) doesn't model the routing aspect or return trips. Choice D (shortest path) doesn't capture the multiple-vehicle or cycle requirements.

Question 5

An online marketplace needs to detect fraudulent seller networks where multiple seller accounts are controlled by the same entity to manipulate reviews and rankings. The system has data on sellers, products, customer reviews, and shared characteristics like IP addresses, bank accounts, and shipping addresses. Fraudulent networks typically share multiple characteristics and have unusual review patterns between network members. How should this be modeled for fraud detection?

  1. Create a bipartite graph between sellers and shared characteristics, then identify dense subgraphs where sellers share many characteristics
  2. Create an undirected graph where sellers are vertices and edges represent shared characteristics, then use clustering algorithms to identify tightly connected components
  3. Create a multi-layer network with separate layers for different relationship types (shared IPs, accounts, addresses), then find overlapping communities across layers (correct answer)
  4. Create a directed graph where vertices are transactions and edges connect transactions sharing sellers or characteristics, then identify strongly connected components
Explanation: When you encounter network-based fraud detection problems, think about the complexity of relationships involved. Fraudulent networks typically exhibit multiple types of connections simultaneously, and single-layer approaches often miss the full picture of coordinated behavior. The correct approach is C because fraudulent seller networks are characterized by multiple, overlapping relationship types. A multi-layer network captures shared IP addresses in one layer, shared bank accounts in another, and shared shipping addresses in a third layer. Finding overlapping communities across these layers reveals sellers who share multiple characteristics simultaneously—the hallmark of coordinated fraud. This approach also detects sophisticated fraudsters who might vary some characteristics while maintaining others. A is flawed because a bipartite graph only shows seller-to-characteristic relationships, not seller-to-seller connections. Dense subgraphs here would show popular characteristics (like common IP ranges) rather than coordinated networks. B oversimplifies by collapsing all relationship types into single edges. This loses crucial information about which specific characteristics are shared and makes it impossible to distinguish between coincidental single connections and systematic multi-characteristic sharing. D focuses on individual transactions rather than seller relationships. Strongly connected components in transaction graphs reveal transaction flows, not seller network structures. This approach misses the account-level coordination that defines fraudulent seller networks. Study tip: For network fraud detection problems, look for approaches that preserve multiple relationship types and can identify overlapping patterns—fraudsters typically leave coordinated fingerprints across several dimensions simultaneously.

Question 6

A social media platform wants to model friendship relationships among users to detect potential spam accounts. Each user can be friends with any other user, friendships are mutual, and a user cannot be friends with themselves. Spam accounts typically have very few mutual friends with legitimate users. Which discrete structure would be most appropriate for modeling this scenario, and what property would be most useful for spam detection?

  1. An undirected graph where vertices represent users and edges represent friendships; analyze the clustering coefficient of each vertex (correct answer)
  2. A directed graph where vertices represent users and edges represent friendship requests; analyze the in-degree minus out-degree for each vertex
  3. A bipartite graph where one set contains users and another contains friendship groups; analyze the degree of vertices in the user set
  4. An undirected graph where vertices represent users and edges represent friendships; analyze the total degree of each vertex
Explanation: Since friendships are mutual, an undirected graph is appropriate. The clustering coefficient measures how many of a user's friends are also friends with each other, which directly relates to mutual friends. Choice B is wrong because friendships are mutual (undirected), not requests. Choice C incorrectly suggests a bipartite structure when the relationship is among users themselves. Choice D focuses on total connections rather than the mutual friend pattern that identifies spam.

Question 7

A recommendation engine needs to suggest products to customers based on purchase history. The system has three types of entities: customers, products, and categories. Each product belongs to exactly one category, customers purchase multiple products, and the goal is to recommend products from categories that similar customers have purchased. Which modeling approach best captures these relationships?

  1. A single undirected graph with customers and products as vertices, where edges represent purchases and categories are vertex labels
  2. Three separate sets (customers, products, categories) with two relation functions: purchases(customer, product) and belongs_to(product, category) (correct answer)
  3. A directed acyclic graph where categories are root nodes, products are intermediate nodes, and customers are leaf nodes
  4. A bipartite graph with customers on one side and categories on the other, where edge weights represent the number of products purchased in each category
Explanation: This scenario involves multiple entity types with different relationship structures that are best modeled using sets and relations. The purchase relationship is many-to-many between customers and products, while belongs_to is many-to-one from products to categories. Choice A loses the category structure. Choice C incorrectly suggests a hierarchical relationship where customers depend on products. Choice D loses the individual product information needed for detailed recommendations.

Question 8

A cybersecurity system monitors network traffic to detect potential intrusions. The system tracks which computers communicate with which others, the frequency of communication, and whether communications are initiated internally or externally. An intrusion is suspected when an external computer communicates with many internal computers that don't normally communicate with each other. What modeling approach best supports this analysis?

  1. A directed weighted graph where vertices represent computers, edge direction shows communication initiation, and weights represent frequency
  2. An undirected graph where vertices are computers and edges represent any communication, with separate tracking of external vs. internal vertex sets
  3. A bipartite graph with internal computers on one side and external computers on the other, where edge weights represent communication frequency
  4. A directed graph with vertex attributes for internal/external status, edge weights for frequency, and analysis of star subgraphs centered on external vertices (correct answer)
Explanation: The intrusion pattern described is an external computer (hub) communicating with many internal computers (star pattern). Direction matters (who initiates), frequency is important (weights), and internal/external status is crucial (vertex attributes). The analysis specifically looks for star subgraphs. Choice A lacks the internal/external distinction. Choice B loses direction information needed to identify initiation. Choice C forces a bipartite structure that doesn't capture internal-to-internal communications that establish normal patterns.

Question 9

A smart city traffic management system optimizes traffic light timing at intersections. Each intersection has sensors that detect approaching vehicles, traffic lights can be in one of several states (red, yellow, green for different directions), and state changes must follow safety rules (e.g., cannot go directly from green in one direction to green in the perpendicular direction). The system needs to minimize average vehicle wait time while ensuring safety. What discrete structure best models this problem?

  1. A finite state automaton where states represent traffic light configurations and transitions represent safe state changes, with optimization on transition timing (correct answer)
  2. A directed graph where vertices are intersections and edges are roads, with edge weights representing current traffic density and shortest path algorithms for routing
  3. A bipartite graph with intersections on one side and time slots on the other, where edges represent valid light configurations for each time period
  4. An undirected graph where vertices represent vehicle positions and edges represent possible movements, with vertex coloring to prevent conflicts
Explanation: Traffic light control is fundamentally a state machine problem where each intersection cycles through valid light configurations (states) according to safety rules (transition constraints). The optimization involves timing these transitions based on traffic sensors. Choice B models the road network but not the light control logic. Choice C doesn't capture the sequential nature of light state changes or safety transition rules. Choice D focuses on individual vehicles rather than intersection control systems.

Question 10

A database system stores information about employees, departments, and projects. Each employee works in exactly one department, each department has multiple employees, employees can work on multiple projects, and projects can have employees from different departments. The system needs to efficiently query: 'Find all employees working on projects that have at least one employee from the Marketing department.' What discrete structure best supports this query?

  1. A directed graph where employees point to their departments and projects, with a breadth-first search algorithm for query processing
  2. A hypergraph where employees are vertices and hyperedges represent projects, with department membership as vertex attributes
  3. Three separate sets with binary relations worksin(employee,department)works_in(employee, department) and assignedto(employee,project)assigned_to(employee, project), using relational algebra operations (correct answer)
  4. A bipartite graph between employees and projects, with department information stored as edge weights representing interdepartmental collaboration
Explanation: This is fundamentally a relational data problem requiring set operations and joins. The query needs to: (1) find Marketing employees, (2) find their projects, (3) find all employees on those projects. Relational algebra with separate entity sets and relation functions naturally supports these operations. Choice A doesn't efficiently support the complex join operations needed. Choice B (hypergraph) unnecessarily complicates the employee-project relationship. Choice D stores department information incorrectly as edge weights rather than employee attributes.

Question 11

A database administrator needs to ensure that sensitive employee records are only accessible to authorized personnel. There are 5 departments (A, B, C, D, E) and the access rules are: A can access B and C's records, B can access C and D's records, C can access D's records, D can access E's records, and E cannot access any other department's records. What is the minimum number of security clearance levels needed, and how should they be assigned?

  1. 3 levels: A(1), B(2), C(2), D(3), E(3) where higher numbers represent higher clearance
  2. 4 levels: A(4), B(3), C(2), D(2), E(1) where higher numbers represent higher clearance
  3. 4 levels: A(4), B(3), C(2), D(1), E(1) where higher numbers represent higher clearance (correct answer)
  4. 5 levels: A(5), B(4), C(3), D(2), E(1) where higher numbers represent higher clearance
Explanation: This is a topological ordering problem on a DAG where edges represent 'can access'. We need the minimum number of levels such that if X can access Y, then X has higher clearance than Y. The longest path determines minimum levels needed: A→B→C→D gives 4 levels. E has no incoming edges, so it can share level 1 with D. Choice A uses only 3 levels but violates A>B and B>C constraints. Choice B incorrectly places C and D at same level when B can access both. Choice D uses unnecessary 5 levels.

Question 12

A logistics company needs to determine the minimum number of delivery trucks required to service all neighborhoods in a city. Each truck can only service neighborhoods that are directly connected by roads, and the company wants to ensure every neighborhood is covered by exactly one truck. The city's road network forms a connected planar graph with 20 neighborhoods and 35 roads. What type of discrete optimization problem is this?

  1. Minimum dominating set problem where each truck must be positioned to cover all neighborhoods within distance 1 (correct answer)
  2. Graph partitioning problem where neighborhoods must be divided into connected subgraphs of roughly equal size
  3. Minimum vertex cover problem where trucks are placed at vertices to cover all road segments
  4. Connected components problem where trucks are assigned to maintain connectivity within each component
Explanation: This is a dominating set problem. Each truck (dominating vertex) must service (dominate) its neighborhood and all adjacent neighborhoods. We want minimum trucks to cover all neighborhoods exactly once. Choice B focuses on equal-sized partitions, not minimum coverage. Choice C covers edges (roads) rather than vertices (neighborhoods). Choice D assumes pre-existing components rather than finding minimum coverage.

Question 13

A telecommunications company needs to place cell towers to provide coverage to all residential areas in a region. Each tower has a fixed coverage radius, and the goal is to minimize the number of towers while ensuring every residential area is within range of at least one tower. If residential areas and potential tower locations are modeled as points on a coordinate plane, what discrete optimization problem does this represent?

  1. Geometric set cover where each potential tower location defines a circular coverage area and we seek minimum towers to cover all residential points (correct answer)
  2. Facility location problem where we minimize the sum of tower installation costs plus distances from residential areas to nearest towers
  3. Steiner tree problem where we find minimum-cost network connecting all residential areas through tower locations
  4. Voronoi diagram construction where each tower defines a region of closest residential areas to minimize overlap
Explanation: This is a geometric set cover problem. Each potential tower location defines a circular coverage set containing all residential areas within its radius. We want the minimum number of towers (sets) such that every residential area (element) is covered by at least one tower. Choice B considers distances and costs beyond just coverage. Choice C connects areas through networks rather than covering them. Choice D partitions space but doesn't minimize tower count.

Question 14

A project manager needs to schedule tasks for a software project where some tasks cannot begin until others are completed, and some tasks require the same specialized equipment and cannot run simultaneously. Given the precedence constraints and resource conflicts, what combination of discrete structures best models this scheduling problem?

  1. A directed acyclic graph for precedence constraints and an undirected graph for resource conflicts; solve using topological ordering with conflict resolution
  2. A bipartite graph connecting tasks to resources with precedence constraints as edge weights; solve using maximum flow algorithms
  3. A single directed graph where edges represent both precedence and resource constraints; solve using critical path method
  4. A directed acyclic graph for precedence constraints and a separate conflict graph for resource sharing; solve as a constrained graph coloring problem (correct answer)
Explanation: When you encounter scheduling problems with multiple types of constraints, the key insight is recognizing that different constraint types require different graph structures to model effectively. This problem has two distinct constraint types: precedence (Task A must finish before Task B can start) and resource conflicts (Tasks X and Y cannot run simultaneously because they need the same equipment). These fundamentally different relationships need separate mathematical representations. Answer D correctly identifies this multi-model approach. A directed acyclic graph (DAG) naturally models precedence constraints where edges point from prerequisite to dependent tasks. The separate conflict graph represents resource sharing as an undirected graph where edges connect tasks that cannot run simultaneously. Solving this as a constrained graph coloring problem means assigning "colors" (time slots) to tasks such that connected tasks in the conflict graph get different colors, while respecting the precedence ordering from the DAG. Answer A incorrectly suggests using topological ordering with ad-hoc "conflict resolution" - there's no standard algorithmic framework for this hybrid approach. Answer B misrepresents the problem as a bipartite matching between tasks and resources, ignoring that precedence constraints aren't naturally expressed as edge weights in this structure. Answer C tries to force both constraint types into a single directed graph, but resource conflicts aren't directional relationships and don't belong in the same graph as precedence constraints. Remember: when facing multi-constraint optimization problems, identify whether different constraint types need separate mathematical models rather than forcing everything into one structure.

Question 15

A university registrar needs to assign students to dormitory rooms such that no student shares a room with someone they have requested to avoid. The registrar has a list of 200 students and 850 mutual avoidance requests. If each room holds exactly 2 students, what graph theory problem must be solved to determine if a valid room assignment exists?

  1. Find a maximum matching in a bipartite graph where one vertex set is students and the other is rooms
  2. Find a perfect matching in the complement of the conflict graph where vertices are students and edges represent avoidance requests (correct answer)
  3. Determine if the conflict graph has a proper 2-coloring where vertices are students and edges represent avoidance requests
  4. Find a Hamiltonian path in the student preference graph where edges connect students willing to room together
Explanation: We need to pair students into rooms such that no pair has an avoidance request between them. The conflict graph has edges for avoidance requests. Its complement has edges between students who CAN room together. A perfect matching in this complement graph gives a valid room assignment where every student is paired with a compatible roommate. Choice A doesn't model student-student compatibility. Choice C would assign students to two groups, not specific roommate pairs. Choice D requires visiting all students in sequence, not pairing them.

Question 16

A streaming service wants to recommend movies to users by identifying groups of users with highly similar viewing preferences and groups of movies that are frequently watched together. The service has viewing data showing which users watched which movies. What discrete structures should be used to model both types of groupings simultaneously?

  1. Two separate graphs: a user similarity graph and a movie co-viewing graph, then find cliques in both graphs independently
  2. A single bipartite graph with users and movies as vertex sets, then find dense subgraphs that include both users and movies
  3. A hypergraph where hyperedges connect users to the sets of movies they watched, then find overlapping hyperedges
  4. Two projection graphs derived from the user-movie bipartite graph: project onto users and onto movies, then find communities in each projection (correct answer)
Explanation: Start with a bipartite graph (users-movies with viewing edges). Project onto users (edges between users who watched common movies) and onto movies (edges between movies watched by common users). Find communities/cliques in both projections to get user groups with similar preferences and movie groups frequently watched together. Choice A doesn't specify how to construct the similarity graphs. Choice B seeks mixed user-movie groups rather than separate homogeneous groups. Choice C uses hypergraphs but doesn't clearly address finding both types of groupings.

Question 17

A cybersecurity analyst needs to model potential attack paths in a network where an attacker can move from one compromised system to another if they share certain vulnerabilities or trust relationships. The goal is to identify which systems, if properly secured, would prevent the attacker from reaching critical servers. What graph-theoretic concept best describes these critical systems?

  1. Articulation points in the attack graph where vertices are systems and edges represent potential compromise paths
  2. Maximum independent set in the vulnerability graph where edges connect systems sharing common vulnerabilities
  3. Minimum vertex cut between the attacker's entry points and critical servers in the network topology graph (correct answer)
  4. Dominating set in the network graph where each secured system can monitor and protect its neighbors
Explanation: When analyzing network security problems involving attack prevention, you need to identify which graph concept best models the relationship between systems and the goal of blocking attackers. The key insight is recognizing this as a flow control problem where you want to disconnect sources (entry points) from targets (critical servers). A minimum vertex cut represents the smallest set of vertices that, when removed, disconnects two parts of a graph. In this context, it's the minimum number of systems that must be secured to completely block all paths from attacker entry points to critical servers. This directly answers the question of which systems are most critical for prevention. Option A describes articulation points, which are vertices whose removal increases the number of connected components. While these identify important systems, they don't specifically focus on protecting critical servers from entry points—they just identify systems whose failure fragments the entire network. Option B focuses on independent sets in vulnerability graphs, which would identify systems that don't share vulnerabilities. However, this doesn't address blocking attack paths or protecting specific targets. Option D describes dominating sets, which ensure every vertex is either in the set or adjacent to it. This is more about monitoring coverage than blocking specific attack paths between entry points and targets. Remember: when you see cybersecurity questions about blocking attackers from reaching targets, think about graph cuts and flow problems. The minimum vertex cut gives you the most efficient way to sever connections between two specific parts of a network.

Question 18

A university course scheduling system needs to assign time slots to courses such that no student has a conflict. Each course has a list of students enrolled. What discrete structure best models this problem, and what does finding a solution correspond to?

  1. A graph where vertices are courses and edges connect courses with common students; finding a proper vertex coloring with minimum colors (correct answer)
  2. A bipartite graph where one set contains courses and the other contains students; finding a maximum matching
  3. A directed graph where vertices are courses and edges show prerequisite relationships; finding a topological ordering
  4. A set partition where each subset contains courses that can be scheduled simultaneously; finding the partition with maximum subset size
Explanation: This is a graph coloring problem. Courses are vertices, edges connect courses that share students (creating conflicts), and colors represent time slots. A proper coloring ensures no adjacent vertices (conflicting courses) have the same color (time slot). Choice B models course-student assignment but not scheduling conflicts. Choice C models prerequisites, not enrollment conflicts. Choice D doesn't capture the conflict relationships between courses.

Question 19

A social media platform wants to identify groups of users who all follow each other mutually to suggest "close friend circles." Given that the platform has millions of users and follows relationships, what specific discrete structure and computational problem does this represent?

  1. Finding strongly connected components in a directed graph where vertices are users and directed edges are follow relationships
  2. Finding maximal cliques in an undirected graph where vertices are users and edges represent mutual follow relationships (correct answer)
  3. Finding minimum vertex cuts in a flow network where users are vertices and follow relationships are edges with unit capacity
  4. Finding articulation points in an undirected graph where vertices are users and edges represent any follow relationship
Explanation: A group where everyone follows everyone else is a clique in the mutual follow graph. We want maximal cliques (cannot be extended). Choice A finds strongly connected components in directed graphs, but we need complete subgraphs. Choice C relates to network flow and connectivity, not complete subgroups. Choice D finds critical vertices for connectivity, not complete subgroups.