Represent a concrete question as a graph without confusing a drawing with the system.
By the end: state the objects, relation, direction, and omissions before choosing an algorithm.
This course assumes arithmetic and familiarity with ordinary maps and task lists. It introduces graph notation and algorithm reasoning without requiring programming or calculus. All networks are constructed teaching examples with at most six vertices, not measured infrastructure or advice about an actual organization.
A graph consists of vertices and edges. A vertex stands for an object chosen by the modeler. An edge records a specified relation between two objects. In a transport model, vertices might be stations and edges might be direct train services. If vertices instead mean individual trains, the same lines would need a different interpretation.
The definition of an edge determines which questions the graph can answer. A direct-service edge can establish whether a journey is possible through transfers. It does not supply a timetable, transfer time, ticket restriction, or available seat. Those facts need additional data and sometimes a larger model.
Suppose six stations are named A, B, C, D, E, and F. We record seven undirected connections: AB, AC, BC, BD, CE, DE, and EF. Here AB means that a passenger can travel directly between A and B in either direction. The vertex set is the collection of station names, with each name included once. The edge set is the collection of these seven connections. Calling them sets matters because writing AB a second time does not create another station connection in this simple model. The drawing must agree with these records, however the stations are arranged.
The word directly excludes intermediate stations. There is no AF edge in this record, but a passenger can still travel from A through C and E to F. Each successive move uses a recorded connection. Thus a missing edge answers a narrower question than a missing journey. It says that one direct move is unavailable, not that every sequence of moves is unavailable. Conversely, drawing AF because the journey is possible would change the meaning of every edge. It would mix direct services with journeys assembled from several services and make a count of connections misleading.
The choice of objects can change even before any edge changes. If A represents a whole station, the model treats its platforms as one place. That is reasonable when transfers inside the station are always possible for the question being asked. It fails if two platforms have no permitted connection for the passenger concerned. A more detailed model might make those platforms separate vertices and record permitted transfers between them. Neither description is universally better. The simpler description is adequate only when the differences it removes cannot change the answer to the particular question.
A vertex does not need an edge to exist. Consider a separate paper example with vertices A, B, C, and D and only edges AB and BC. D could be a listed station whose services are suspended. Keeping D records that the station belongs to the system but currently has no recorded connection. Omitting D would instead describe a system containing only three stations. Those alternatives give the same journeys among A, B, and C, but different answers to how many stations have no service. Define the object list independently of the edge list when absence itself matters.
An edge can also depend on a rule rather than a physical link. Among three tasks A, B, and C, suppose AB means that both tasks require the same machine, and the only edges are AB and BC. The graph records conflicts between pairs. It does not mean A must precede B, or that doing A makes C possible. In particular, sharing a machine with B does not make A and C share a machine. A graph can record many kinds of relation, but the permitted reasoning follows the chosen relation rather than the shape of its lines.
Before using the station graph, ask how someone established the seven records. A route diagram, a service timetable, and an observation of one train each support different claims about direct service. An absent record may mean that no service exists, or merely that nobody checked it. A calculation can establish a consequence of the supplied edge set without resolving that uncertainty. For a journey recommendation, checking a disputed connection may matter more than refining the calculation. This separates a definition of the relation, the evidence for each record, and the consequences derived from those records.
An undirected edge allows travel in either direction. A directed edge, drawn with an arrow, allows only its stated direction. An edge from A to B does not grant travel from B to A. In a dependency graph, it can instead mean that A must finish before B starts. Fix that convention before reading arrows.
A weight is a number attached to an edge. Its units and meaning are part of the model. Travel minutes add along a route. Capacity limits the rate that may pass through a link. Probabilities generally cannot be added as travel minutes. The same topology can support incompatible optimization questions.
For a directed connection, order is part of the record. The ordered pair A, B means a move from A to B. The ordered pair B, A means a different move. On the six-station example, orient the seven records as A to B, A to C, B to C, B to D, C to E, D to E, and E to F. A passenger starting at B can move directly to C or D, but not directly to A. B appears in the A-to-B record as a destination, and that fact grants no permission to depart toward A.
An undirected connection is different from an arrow whose direction has not yet been investigated. It positively permits both directions. If the evidence establishes A to B but leaves B to A unknown, replacing the arrow by an undirected edge assumes something extra. Likewise, forgetting directions to make a simpler drawing loses information that can determine whether a return journey exists. Two opposite arrows between A and B are separate directed records. If we intentionally forget their directions, they become one undirected connection, not two duplicate undirected edges in our simple graph.
Numbers need equally explicit meanings. In a separate directed example, let the vertices be A, B, C, and let the complete edge record be A to B taking 2 minutes, B to C taking 3 minutes, and A to C taking 7 minutes. Assume each service is immediately available and these durations do not change during the trip. The direct A-to-C trip takes 7 minutes. The trip through B takes 2 plus 3, or 5 minutes. The intermediate station adds a move yet reduces total time. Counting moves and adding minutes answer different questions.
The same numbers would behave differently if they described the number of parcels each connection can carry per hour. Two successive connections limited to 2 and 3 parcels per hour cannot carry 5 parcels per hour along that chain. Every parcel must pass the first connection, so that connection limits the chain to at most 2. This conclusion needs only the meaning of a rate limit. It does not require a new algorithm. Adding weights is justified by additive quantities such as fixed travel durations, not by the fact that all the labels happen to be numbers.
An edge weight can be zero without the edge disappearing. A transfer between two modeled places might have zero added fare, even though the transfer is permitted and still counts as a move. If a fare model records A to B with fare 0 and no A-to-C service, those are different facts. One is a present edge with a numerical property; the other is an absent edge. Keeping existence separate from value prevents a later calculation from treating a free transfer as impossible. The representation lesson develops an explicit way to preserve this distinction.
| Interpretation | AB, BC, AC values | Chain through B | Direct AC |
|---|---|---|---|
| Fixed travel time | 2, 3, 7 minutes | 2 + 3 = 5 minutes | 7 minutes |
| Capacity limits | 2, 3, 7 parcels/hour | At most 2 parcels/hour | At most 7 parcels/hour |
A single weight also fixes what differences the model ignores. If travel time varies with departure time, writing one integer on each edge amounts to an assumption about which trip conditions are represented. It might be a stated planning example rather than a measured forecast. If tickets forbid a particular transfer, the presence of each individual service does not establish that they can be combined. The five-minute result above follows because the example explicitly permits immediate combination. Changing those premises changes the journey question, even when the same three arrows remain visible on the page.
Reachable from F: A, B, C, D, E, F.
Reachable from F: F.
| Edge | Permission |
|---|---|
| A → B | One-way |
| A → C | One-way |
| B → C | One-way |
| B → D | One-way |
| C → E | One-way |
| D → E | One-way |
| E → F | One-way |
| Question | Required edge meaning |
|---|---|
| Can a parcel reach a depot? | Permitted directed transfer |
| What is the fastest route? | Additive travel time under stated conditions |
| How much can pass per hour? | Capacity, not travel time |
In the model above, start with the selected relation set to follow arrows only. Its directed records are exactly A to B, A to C, B to C, B to D, C to E, D to E, and E to F. To find which places are reachable from F, begin by including F itself. Reaching the starting place requires no move. Then inspect the records for arrows leaving F. There are none. No first move is possible, so no longer journey from F is possible either. The complete reachable set is therefore the single vertex F.
The E-to-F arrow does not alter this result. It tells us how a passenger elsewhere might arrive at F, not how that passenger could leave after arriving. A useful check is to put a finger on F and follow only arrowheads away from the current place. Searching backward along an incoming arrow answers a different question, namely which origins can lead to F. In this particular graph, all six stations can lead to F. For example, B can use B, D, E, F, while A can use A, C, E, F. Arrival and departure questions have different answers.
Now select Allow both directions. The model keeps all six station identities and all seven endpoint pairs, but each pair permits movement either way. From F the first move can now reach E. From E one can reach C and D, then reach A through C and B through either C or D. There is no need to infer a direct F-to-A edge. Reachability accumulates through successive permitted moves. The final set contains every station because each has such a sequence from F. The reference drawing remains visible so that the changed permission can be compared without remembering an earlier display.
You can check the undirected result with one complete journey through all the stations: F, E, D, B, C, A. Its successive endpoint pairs are EF, DE, BD, BC, and AC, all present in the fixed record. This is evidence that each of those places is reachable from F. It is not a claim that this journey uses the fewest moves to each place, or that its drawn lines have the shortest geographic length. Different questions need different evidence. A valid journey establishes possibility, while a minimum claim must also rule out better alternatives.
Consider a paper variation rather than another setting of this model. Keep the directed records but replace E to F by F to E. From F one can then reach E, yet cannot leave E because its former outgoing edge has been reversed. The reachable set becomes E and F, not all six stations. Reversing one incoming arrow removes the obstacle to the first move but does not reverse the other permissions. By contrast, reversing every directed edge would let F follow former arrival routes backward to all the vertices. These are two different edits with different consequences.
The model comparison establishes a conditional statement about recorded permissions. It does not show that real services are one-way, that a station is closed, or that a passenger has the right ticket. Nor does highlighting only F mean that F has no incident line. One line still touches it, with its arrow pointing inward. Reading that visible distinction explains the result without treating the displayed status as an unexplained verdict. When a model output surprises you, tracing a first permitted move often reveals which assumption caused the difference before any more elaborate reasoning is needed.
Moving a vertex on the page does not change the graph when its edge endpoints remain the same. Line length here is not travel distance. Two lines crossing do not create a vertex unless a labeled vertex explicitly joins them. Graph diagrams are representations of connectivity, not automatically geographic maps.
We use finite simple graphs: no self-loops and no parallel edges of the same direction. Real networks may need both. Two independent cables between the same sites must not disappear into a single edge when studying cable failure. Missing or uncertain observations can also make a calculated answer inapplicable to the real system.
A redraw can preserve every connection while changing the appearance of the network. Take the undirected six-station record AB, AC, BC, BD, CE, DE, EF. Arrange the vertices around a circle, then arrange them in two rows. If both drawings contain exactly those seven endpoint pairs and the same six labels, they represent the same named graph. An edge that looks long in one drawing may look short in the other. Without distance units attached to the geometry, neither drawing supports a claim that one train service covers more kilometers than another.
Crossings require particular care when reading a map-like diagram. In a separate graph with vertices A, B, C, D and only edges AB and CD, draw the two lines so that they cross. There is still no connection between the pair A, B and the pair C, D. The crossing has no vertex label and grants no transfer. To model an actual junction there, introduce a fifth vertex E and replace the two edges by AE, EB, CE, and ED. That revised graph permits a journey from A through E to C. The change is in the records, not just the ink.
Combining objects can hide constraints even when every line is drawn carefully. Suppose a paper model has vertices A, B, C and only undirected edges AB and BC. If B stands for two buildings with no passage between them, and the A service reaches one building while the C service leaves the other, then the model's apparent A-to-C journey is false. Splitting B into separate objects can remove that false connection. In the other direction, splitting a station into platforms without recording real internal transfers can wrongly remove journeys. The vertex definition and the edge definition must agree.
Even an accurate record of individually available services may omit their order in time. Consider vertices A, B, C with directed services A to B departing at 09:00 and arriving at 09:10, and B to C departing at 09:05 and arriving at 09:15. There are no other services, and we ask about travel starting at A at 09:00 that day. The static edge record allows the sequence A, B, C. The timetable does not, because the B departure has already left when the passenger arrives. Pairwise service existence does not establish that this sequence is usable.
One remedy for that timetable question is to distinguish a place at one time from the same place at another time, then record only movements and waits that time permits. That is a different model with more detailed vertices, not an extra meaning secretly supplied by the old arrows. We do not add that model to this bounded visualizer. The example instead identifies a specific missing premise behind static journey reasoning. If all required connections are available whenever reached, combining them is justified. If availability depends on time, the model needs evidence or structure that represents that dependence.
| Service | Departs | Arrives | Can this passenger board? |
|---|---|---|---|
| A to B | 09:00 | 09:10 | Yes, starts at A at 09:00 |
| B to C | 09:05 | 09:15 | No, reaches B at 09:10 |
For a final audit, separate three kinds of change. Moving a labeled vertex while preserving every endpoint record changes presentation. Reversing an arrow changes a permission within the same object list. Replacing a station by several platforms changes the objects themselves and may require a new edge list. Only the first is guaranteed to preserve all graph answers. This distinction helps when comparing two diagrams offered as evidence. Read the identities and records before comparing their visual density. A cleaner-looking drawing can depict a different relation, while a tangled drawing can still record the intended relation exactly.
A directed edge A to B means A must finish before B starts. Someone reverses every arrow but keeps that definition. Is this merely another drawing?
Ask which task must now finish first.
| Graph | Required order |
|---|---|
| A to B | A before B |
| B to A | B before A |
No. The original requires A before B; the reversed graph requires B before A. Moving positions would preserve the relation, but reversing its ordered endpoints changes it.
Two sites have two separate cables. Why can a simple graph with one connecting edge mislead a single-cable failure analysis?
Distinguish a relation being present from how many physical links support it.
| Physical failure | Remaining cables |
|---|---|
| Neither fails | 2 |
| One fails independently | 1 |
| Shared conduit fails | Possibly 0 |
The one edge says only that a connection exists. Removing it disconnects the simple graph, although losing one of two independent physical cables leaves the other. Use a multigraph or explicitly record cable multiplicity and common failure modes.
Selected reference passages support the definitions and algorithms below. The networks, explanations, and implementations are original. Terminology and assumptions are stated within each lesson; source review is not an independent audit of this course. Optional links are not runtime dependencies.
Graph representations, degree, trees, BFS and DFS. This course explicitly reserves path for a walk without repeated vertices; the reference uses a different path convention.
Directed reachability, strong components, DAGs, and topological orders. The lesson uses zero-indegree removal rather than the reference implementation's reverse-postorder method.