- 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?
Answer: A graph where vertices are courses and edges connect courses with common students; finding a proper vertex coloring with minimum colors
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.
- 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?
Answer: Create an undirected graph where vertices are courses and edges connect courses with shared students; find a proper vertex coloring with minimum colors
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.
- 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?
Answer: As a vehicle routing problem using a complete weighted graph with additional constraint sets for time limits, capacity limits, and equipment requirements
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.
- 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?
Answer: Create a multi-layer network with separate layers for different relationship types (shared IPs, accounts, addresses), then find overlapping communities across layers
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.
- 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?
Answer: Three separate sets with binary relations works_in(employee,department) and assigned_to(employee,project), using relational algebra operations
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. - 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?
Answer: Minimum dominating set problem where each truck must be positioned to cover all neighborhoods within distance 1
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.
- 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?
Answer: An undirected graph where vertices represent users and edges represent friendships; analyze the clustering coefficient of each vertex
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.
- 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?
Answer: A directed acyclic graph for precedence constraints and a separate conflict graph for resource sharing; solve as a constrained graph coloring problem
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.
- 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?
Answer: Minimum vertex cut between the attacker's entry points and critical servers in the network topology graph
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.
- 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?
Answer: A directed graph with vertex attributes for internal/external status, edge weights for frequency, and analysis of star subgraphs centered on external vertices
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.
- 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?
Answer: Find a perfect matching in the complement of the conflict graph where vertices are students and edges represent avoidance requests
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.
- 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?
Answer: A finite state automaton where states represent traffic light configurations and transitions represent safe state changes, with optimization on transition timing
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.
- 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?
Answer: 4 levels: A(4), B(3), C(2), D(1), E(1) where higher numbers represent higher clearance
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.
- 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?
Answer: Two projection graphs derived from the user-movie bipartite graph: project onto users and onto movies, then find communities in each projection
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.
- 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?
Answer: A directed acyclic graph with tasks as vertices, dependencies as edges, and vertex weights as durations, computing the longest path to identify critical tasks
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.
- 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?
Answer: A directed acyclic graph representing family lineage with vertex attributes for genetic markers and disease status, analyzing paths from ancestors to descendants
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.
- 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?
Answer: Finding maximal cliques in an undirected graph where vertices are users and edges represent mutual follow relationships
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.
- 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?
Answer: Geometric set cover where each potential tower location defines a circular coverage area and we seek minimum towers to cover all residential points
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.
- 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?
Answer: Three separate sets (customers, products, categories) with two relation functions: purchases(customer, product) and belongs_to(product, category)
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.
