Graphs and networks
| English | Chinese | Pinyin |
|---|---|---|
| graph | 图 | tú |
| vertices | 顶点 | dǐng diǎn |
| edges | 边 | biān |
| degree | 度 | dù |
| path | 路径 | lù jìng |
| cycle | 环 | huán |
| connected | 连通 | lián tōng |
| tree | 树 | shù |
| shortest path | 最短路径 | zuì duǎn lù jìng |
| weighted graph | 带权图 | dài quán tú |
Dots and lines describe almost anything
- Roads between cities. Friends on a network. Which task must finish before which. All the same object.
- A graph 图 is a set of vertices 顶点 joined by edges 边.
- Nothing else about the picture matters — not where you draw the dots, not whether the lines are straight.
Reading a graph
- The degree 度 of a vertex is how many edges meet it.
- A path 路径 is a route along edges; a cycle 环 is a path returning to where it started.
- A graph is connected 连通 when every vertex can be reached from every other.
A vertex has four edges meeting it. What is its degree?
Degree counts the edges at a vertex, nothing else.
Trees
- A tree 树 is a connected graph with no cycles.
- A tree with $n$ vertices has exactly $n-1$ edges, always.
- Trees are everywhere in computing: a file system, an organisation chart, an HTML document, a decision process.
A tree has 4 vertices. How many edges does it have?
n − 1, always. That single fact answers the four-town road question with no arithmetic.
Why does the cheapest connecting network never contain a cycle?
Any redundant edge can be deleted for a saving, so the optimum is a tree.
Four towns, and the cheapest set of roads connecting them.
Any connecting set with a cycle contains a road you could delete and still get everywhere — so the cheapest solution never has one.
A connected graph with no cycles is a tree, and a tree on four vertices has exactly three edges. So the answer is three roads, chosen as the cheapest three that keep everything connected.
The problem was solved by knowing what a tree is, before any arithmetic.
Shortest paths, and why this matters
- A weighted graph 带权图 puts a number on each edge: distance, time, cost.
- A shortest path 最短路径 problem asks for the cheapest route between two vertices, and it is what a navigation app solves every time you use it.
- Work systematically: keep the best known distance to each vertex and improve it as you go. Guessing a route and checking it is not a method.
Match each situation to what its vertices and edges should be.
Deciding what the vertices represent is the modelling step, and it is where the marks are.
Model first, then compute. Most graph questions are won by deciding what the vertices and edges represent. Once tasks are vertices and "must finish before" is an edge, a scheduling problem becomes a graph problem you already know how to solve.
Two drawings that look different must be different graphs.
Only the connections matter. Position and line shape carry no information.
The drawing is not the graph. Two pictures that look completely different can be the same graph, and a question asking whether they are is testing whether you compare connections rather than positions.