Skip to content

Quiz: Graph Theory and Graph Database Foundations

Test your understanding of graph theory concepts, graph database structures, and traversal algorithms with these review questions.

1. In graph database terminology, what is the key architectural difference that allows graph databases to outperform relational databases on multi-hop queries?

  1. Graph databases store all data in memory, eliminating disk I/O entirely during query execution
  2. Graph databases use index-free adjacency, storing direct pointers from each node to its connected neighbors rather than requiring index lookups
  3. Graph databases compress relationship data so that queries on connected data require less bandwidth than relational joins
  4. Graph databases automatically partition data across multiple servers, distributing join workloads in parallel
Show Answer

The correct answer is B. Index-free adjacency is the architectural foundation of graph database performance. Each node stores direct pointers to its neighboring nodes, so traversing from one node to the next is a constant-time O(1) operation following a pointer. Relational databases must perform index lookups or table scans at each join step, causing performance to degrade as hop count increases.

Concept Tested: Graph Database

2. What is a property graph, and what three components define it?

  1. A graph that uses property-based access control to restrict which users can view which nodes and edges
  2. A graph model consisting of nodes, edges, and key-value properties attached to both nodes and edges
  3. A graph where all nodes must have the same set of required properties, enforced by a strict schema
  4. A specialized graph for tracking intellectual property assets, using directed edges to represent ownership chains
Show Answer

The correct answer is B. A property graph consists of three components: nodes (representing entities), edges (representing relationships between entities), and properties (key-value pairs attached to both nodes and edges). This simple but expressive model allows nodes to carry attributes like hostname and OS version, while edges carry contextual metadata like criticality scores and dependency types—all without a rigid schema.

Concept Tested: Property Graph

3. What distinguishes a Directed Acyclic Graph (DAG) from a general directed graph, and why does this matter for IT dependency management?

  1. A DAG requires that all edges point in the same direction (left-to-right), while directed graphs allow edges in any direction
  2. A DAG allows at most one path between any two nodes, while a directed graph allows multiple paths between nodes
  3. A DAG contains no cycles, meaning you cannot follow directed edges from a node and return to that same node, preventing circular dependencies
  4. A DAG limits the maximum number of edges per node to avoid complex dependency chains that are difficult to analyze
Show Answer

The correct answer is C. A DAG is a directed graph with no cycles—you cannot start at any node and follow directed edges back to the same starting node. For IT dependency management, this is critical because cycles would create contradictions: which component deploys first if A depends on B and B depends on A? DAGs ensure clean dependency hierarchies that support topological sorting, deployment orchestration, and impact analysis.

Concept Tested: Directed Acyclic Graph

4. Which graph traversal algorithm guarantees finding the shortest path (fewest hops) between two nodes in an unweighted graph?

  1. Depth-First Search, because it follows each branch to its deepest point before backtracking
  2. Breadth-First Search, because it explores all nodes at the current distance before moving to nodes farther away
  3. Topological Sort, because it orders nodes by dependency depth and naturally produces shortest paths
  4. Dijkstra's algorithm, because it is the only algorithm designed specifically for path length minimization
Show Answer

The correct answer is B. Breadth-First Search explores all nodes at distance 1, then all nodes at distance 2, then distance 3, and so on. Because it processes nodes level by level, when it first reaches the target node, it has necessarily found the path with the fewest hops—any shorter path would have been found in an earlier level. Dijkstra's algorithm is needed for weighted graphs where edges have varying costs.

Concept Tested: Breadth-First Search

5. An IT management team needs to determine which business services will be impacted if a specific database server is taken offline for maintenance. Which graph operation best supports this analysis?

  1. Topological sort, starting from the database node and ordering all nodes by dependency depth
  2. Shortest path algorithm, finding the minimum-hop route from the database to each business service
  3. Traversal following incoming edges (reverse dependency direction) from the database node upward through applications to business services
  4. Cycle detection algorithm, identifying all circular dependencies involving the database node
Show Answer

The correct answer is C. Dependencies typically flow from services down toward infrastructure (Service DEPENDS_ON App DEPENDS_ON Database). To find what is impacted by a database failure, you must traverse in the reverse direction—following incoming edges from the database upward through applications to business services. This "blast radius" analysis is one of the most common and valuable operations in graph-based IT management.

Concept Tested: Graph Traversal

6. How does Depth-First Search (DFS) differ from Breadth-First Search (BFS) in terms of memory usage and its suitability for different graph problems?

  1. DFS uses more memory than BFS because it must store all nodes at the current depth level simultaneously
  2. DFS uses less memory because it only tracks the current exploration path, while BFS must store all nodes at each depth level in a queue
  3. DFS and BFS use identical amounts of memory because they both visit every node in the graph exactly once
  4. BFS uses less memory because it terminates earlier by finding the target node on the first path it follows
Show Answer

The correct answer is B. DFS only needs to track the current path being explored (using a stack), so memory usage is proportional to the maximum path depth. BFS must store all nodes discovered at each level in a queue before processing the next level, which can require substantial memory for wide graphs with many nodes at the same depth. DFS is preferred when memory is constrained, while BFS is preferred when shortest paths matter.

Concept Tested: Depth-First Search

7. In a property graph, what is the advantage of storing properties directly on edges (relationships) rather than requiring a separate junction table?

  1. Edge properties enable the database to compress relationship data more efficiently than junction table rows
  2. Edge properties eliminate the need for relationship types, making queries simpler by treating all connections uniformly
  3. Edge properties capture contextual metadata about connections—such as criticality or last-verified date—without additional table joins during traversal
  4. Edge properties allow multiple nodes to share the same relationship instance, reducing storage duplication across the graph
Show Answer

The correct answer is C. In a relational model, a junction table row connecting two entities cannot directly carry metadata about the relationship without adding columns to that junction table, which then requires another join to retrieve. In a property graph, the edge itself carries key-value properties (like criticality: "HIGH" or last_tested: "2024-01-20") that are retrieved in the same operation as the traversal—no additional query or join step needed.

Concept Tested: Edge Property

8. A software deployment system must determine a safe order to deploy 12 microservices with complex dependencies. Which graph concept enables this analysis?

  1. Shortest path algorithm, finding the fastest route through the dependency graph from first to last service
  2. Topological sorting of a DAG, producing a linear ordering where each service appears before all services that depend on it
  3. Betweenness centrality, identifying the microservice that most frequently appears on paths between other services
  4. Undirected graph traversal, treating all dependencies as bidirectional to find the most connected service
Show Answer

The correct answer is B. Topological sorting works on Directed Acyclic Graphs to produce a linear ordering of nodes where every node appears before any node it points to (i.e., every dependency is deployed before the services that depend on it). This ensures that when a service is deployed, all its dependencies are already running. Topological sorting is one of the most practical applications of DAG theory in software and IT operations.

Concept Tested: Directed Acyclic Graph

9. Which of the following best illustrates an UNDIRECTED relationship in an IT management graph?

  1. An application DEPENDS_ON a database, because the dependency flows from the application to the database and not vice versa
  2. A server HOSTS an application, because hosting is a one-way relationship from infrastructure to software
  3. Two network switches are CONNECTED_TO each other, because packets can flow in either direction between them
  4. A team MANAGES an application, because management authority flows from the team to the asset it oversees
Show Answer

The correct answer is C. A network connection between two switches is symmetric—traffic flows in both directions, and neither switch is inherently the "source" or "target" of the connection. This makes it a natural undirected relationship. The other options (DEPENDS_ON, HOSTS, MANAGES) are all directional: the relationship has clear asymmetric semantics where reversing the direction would convey a completely different and incorrect meaning.

Concept Tested: Undirected Graph

10. A property graph node representing a Linux server and another node representing a Windows server are stored in the same graph database. The Linux server node has properties for kernel_version and package_manager, while the Windows server node has properties for service_pack and registry_path. What does this illustrate about property graphs?

  1. Property graphs require separate node types for each operating system because nodes of the same label cannot have different properties
  2. Property graphs support heterogeneous data naturally, allowing different node instances to have different sets of properties without schema conflicts
  3. Property graphs enforce that all nodes with the same label must have exactly the same set of properties to maintain data consistency
  4. Property graphs store OS-specific properties in a separate metadata table linked to the node by foreign key reference
Show Answer

The correct answer is B. One of the key advantages of property graphs is their ability to accommodate heterogeneous data. Two nodes with the same label (e.g., :Server) can have completely different sets of properties without any schema conflict or NULL padding. This flexibility is particularly valuable for IT infrastructure, where different device types, vendors, and configurations require tracking different attributes—something that requires sparse tables or complex EAV patterns in relational databases.

Concept Tested: Node Property