Skip to main content

Graphs as Models of Constraint and Interaction

What This Concept Is​

A graph $G = (V, E)$ is a mathematical model built from:

  • a set of vertices $V$, representing objects, states, agents, tasks, or locations.
  • a set of edges $E$, representing some relation such as adjacency, dependency, conflict, communication, similarity, or reachability.

Graphs come in flavors: undirected (edges are unordered pairs) vs directed (edges are ordered pairs, called arcs); simple (no loops, no multi-edges) vs multigraphs (either allowed); weighted (edges or vertices carry numeric weights); labeled (vertices or edges carry symbolic labels). The right flavor is chosen to match the question, not the diagram.

The power of graph theory is not the picture. It is the disciplined choice of what counts as a vertex and what counts as an edge. A good model makes a previously vague question become a structural question with a well-defined answer; a bad model blurs distinctions that the original problem relied on.

Common graph families worth naming now:

  • $K_n$ (complete graph): every pair of $n$ vertices is connected.
  • $K_{m,n}$ (complete bipartite): two groups of sizes $m$ and $n$, every cross-pair connected.
  • $C_n$ (cycle): $n$ vertices in a ring.
  • $P_n$ (path): $n$ vertices in a line.
  • $T$ (tree): connected acyclic graph (covered in cluster 5).

Each is an idealized shape against which real problem graphs are compared.

Order and size. The number of vertices $|V|$ is called the order of the graph and is usually denoted $n$; the number of edges $|E|$ is the size and is usually denoted $m$. Every asymptotic claim about graph algorithms is stated in $n$ and $m$, so getting used to these names early matters for Semester 2.

Sparse vs dense. A graph is sparse when $m = O(n)$ or $m = O(n \log n)$ and dense when $m = \Theta(n^2)$. The representation you choose (adjacency list vs matrix, concept 12) is driven by this distinction more than by anything else.

Why It Matters Here​

Many computer science problems become tractable only after they are modeled as graphs:

  • scheduling via dependency graphs (topological order)
  • social networks via adjacency graphs (friendship, follower, citation)
  • conflict constraints via coloring graphs (exam timetabling, register allocation)
  • assignment problems via bipartite graphs (workers↔jobs, students↔projects)
  • routing / connectivity via path structure (shortest paths, minimum cuts)
  • build systems via DAGs of source files and artifacts
  • control flow via graphs of basic blocks in a compiler

Good graph reasoning starts with modeling decisions, not theorem memorization. The theorems you will meet in clusters 4-6 are tools that apply to the model you build; if the model is wrong, the theorem conclusions are meaningless for the real problem.

Concrete Examples​

Example 1: exam scheduling. Five exams must be scheduled in two time slots; pairs of exams that share students cannot be in the same slot.

Model:

  • one vertex per exam.
  • one edge between two exams if they share at least one student.

The question "can the exams be scheduled in two slots without conflict?" becomes the graph-theoretic question "is this graph $2$-colorable?" Equivalently, by a theorem from cluster 6, "does this graph contain an odd cycle?"

The graph is not decoration. It transforms a scheduling problem into a structural problem whose answer is forced by a property of the graph.

Example 2: directed graph for build systems. A large software project has source files where each file depends on others (C headers, imports, etc.).

Model:

  • one vertex per file.
  • a directed edge $u \to v$ if file $u$ depends on file $v$ (i.e., $v$ must be compiled first).

The question "can the project be built?" becomes "is this directed graph acyclic (a DAG)?" If yes, a topological sort gives a valid build order. If no, there is a circular dependency -- a cycle in the graph -- which must be broken before any build can succeed.

Example 3: multi-flavor modeling choice. Consider "rooms in a building with doors between some pairs." Two different graphs can be built:

  • vertices = rooms, edges = doors. Good for "can I walk from room A to room F?" (connectivity).
  • vertices = doors, edges = two doors that share a room. Good for "is there an inspection route through all doors without repeating?" (Eulerian tour, cluster 6).

Same building, two models, different theorems apply. The modeling choice is the insight. The graph built this way is the line graph $L(G)$ of the original, and many graph constructions in later semesters (interference graphs for register allocation, scheduling conflict graphs) are line graphs or close cousins.

Common Confusion / Misconceptions​

  • Overloading edges with multiple meanings. If an edge sometimes means "can communicate" and sometimes means "cannot be simultaneous", the model is broken. Each relation deserves its own graph (or a labeled multigraph).
  • Wrong granularity for vertices. Sometimes people/tasks/states should be vertices; sometimes whole sets or configurations should be. "What is a vertex?" is the first design question.
  • Drawing is not the graph. Two diagrams with very different appearances can represent the same graph; the graph is defined by its vertex set and edge set, not by positions on paper.
  • Directed vs undirected conflation. "Follows" on Twitter is directed; "is friends with" on Facebook is undirected. Picking the wrong one silently changes every downstream theorem's applicability.
  • Treating "edges = pixels". Thinking of an edge as a line segment on paper encourages reasoning about intersections and positions that are not part of the graph's definition. Two edges crossing in a drawing does not mean anything graph-theoretic -- unless the graph is being studied for planarity (concept 18).

How To Use It​

When building a graph model, ask in order:

  1. What are the basic entities the problem manipulates? (Candidates for vertices.)
  2. What relation do I need to represent? Is there exactly one, or several?
  3. Is the relation symmetric (undirected) or directional?
  4. Do multiple edges between the same pair matter, or are they equivalent to one?
  5. Do weights or labels on edges encode relevant information (cost, time, capacity)?
  6. What specific graph property answers the original question? (Connectivity, coloring, matching, cycle existence, shortest path?)
  7. Could an alternative model (e.g., swap vertices and edges as in Example 3) make the question cleaner?

The graph model is good only if a graph-theoretic property corresponds cleanly to the real question, with no leaks or ambiguities.

A useful sanity check: after drafting a model, write the original question in one sentence using only graph-theoretic vocabulary ("is the graph connected?", "does it contain a cycle of length $k$?", "is there a matching of size $n$?"). If you cannot, the model is leaky.

Transfer / Where This Shows Up Later​

  • Semester 2 algorithms: nearly every core algorithm is a graph algorithm (BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, network flow, strongly connected components). The modeling discipline from this concept is what lets you recognize when a real problem admits these algorithms.
  • Semester 3 data structures: graph representations (adjacency list, adjacency matrix, edge list) determine algorithmic constants. Trade-offs appear throughout later coursework.
  • Semester 4 databases: query plans are DAGs of operators; foreign-key schemas are directed graphs; graph databases (Neo4j, SPARQL) treat the graph as the primary data model.
  • Semester 5 OS: deadlock detection is cycle-finding in a resource-allocation graph. Thread-dependency analysis uses DAGs.
  • Semester 6 distributed systems: service topology (who talks to whom), data dependency between replicas, gossip protocols, and consensus quorums are all graph problems. Topological ordering of migrations is a DAG sort.
  • Semester 7 architecture: dependency graphs of microservices drive reliability analysis; call graphs drive fitness-function checks for forbidden cross-module dependencies.

Check Yourself​

  1. In a course prerequisite system, what should vertices and edges represent? Directed or undirected?
  2. In a roommate-assignment conflict problem, what kind of graph is natural? What question are you asking about it?
  3. Why can the same real-world situation admit several different graph models? Give a concrete example.
  4. What is lost if you model Twitter as an undirected graph? What question becomes unanswerable?
  5. Name three problems from computer science (not in this page) that naturally reduce to graph questions.
  6. Given a graph $G$, what is the smallest $n, m$ for which the graph is trivially a tree? For which it is forced to contain a cycle (consult the handshaking discussion in concept 11)?
  7. Explain the difference between the "line graph" and the "original graph" in Example 3. Which structural property changes most dramatically under this transformation?

Mini Drill or Application​

Model each problem as a graph and say what graph property matters:

  1. Can a set of tasks be completed without circular dependency?
  2. Can you assign two meeting rooms to a set of conflicting meetings?
  3. Can every applicant be assigned to an acceptable job (each applicant eligible for a subset of jobs)?
  4. Can a graph of web pages be crawled fully from a single starting URL?
  5. In a network of $n$ servers where certain pairs have direct links, can a message go from any server to any other? What is the minimum number of links that would disconnect the network?
  6. Flight network between cities with one-way fares. Is the resulting graph directed or undirected? Weighted? Which real question becomes "shortest path"?
  7. Garbage collection in a managed-memory runtime: every object is a vertex, every reference is a directed edge; live objects are those reachable from a fixed root set. Which graph property determines "garbage"?

Read This Only If Stuck​