Graphs and trees
Introduit| English | Sens |
|---|---|
| graph/ɡræf/ | A mathematical structure consisting of vertices connected by edges. |
| edge/edʒ/ | Connections between vertices in a graph, or boundary segments of a geometric shape. |
| degree/dɪˈɡriː/ | An angular unit equal to one three-hundred-and-sixtieth of a full turn. |
| directed | directed |
| vertex/ˈvɜːteks/ | A corner or meeting point of edges, a turning point of a parabola, or a node in a graph, depending on the context. |
| adjacency matrix | adjacency matrix |
| adjacency list/əˈdʒeɪsənsi lɪst/ | adjacency list |
| sparse | sparse |
| handshake lemma | handshake lemma |
| tree/triː/ | tree |
| acyclic | acyclic |
| leaf | leaf |
| breadth-first search/bredθ fɜːst sɜːtʃ/ | breadth-first search |
| depth-first search/depθ fɜːst sɜːtʃ/ | depth-first search |
Friends, flights and build steps
- A social network, an airline map and the order in which code modules must compile look nothing alike. Each one is a set of things joined by links.
- That shared shape is a graph. Learn it once and the same tools count, search and check all three.
Vertices, edges and degree
- A graph 图 $G = (V, E)$ has vertices 顶点 $V$ and edges 边 $E$ joining pairs of them. Edges can be directed 有向 (one-way, like build order) or undirected (like friendship).
- The degree 度 of a vertex is the number of edges touching it. An isolated vertex has degree 0 and still counts as a vertex.
Match each system to the kind of graph that models it.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Friendship runs both ways; build order runs one way and cannot loop; distances are weights; links can point back.
Two ways to store a graph
- An adjacency matrix 邻接矩阵 is an $n \times n$ grid of 0s and 1s. It takes $n^2$ space but answers "is there an edge from $u$ to $v$?" in $O(1)$.
- An adjacency list 邻接表 stores each vertex's neighbours. It takes $O(|V| + |E|)$ space, so it suits sparse 稀疏 graphs with few edges per vertex.
A road map has a million junctions, each joined to about four others. The best storage is —
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
A matrix needs 10¹² cells, almost all 0; a list stores only the 4 million or so edges that exist.
The handshake lemma
- Each edge adds 1 to the degree of each of its two ends, so $\sum_v \deg(v) = 2|E|$. This is the handshake lemma 握手引理. In the figure, $3 + 2 + 2 + 2 + 3 = 12 = 2 \times 6$.
- Corollary: the number of odd-degree vertices is always even. Seven people cannot each shake hands with exactly three others, because $7 \times 3 = 21$ is odd.
A graph has 9 edges. What is the sum of all its vertex degrees?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Each edge adds 2, so $2 \times 9 = 18$.
A graph can have exactly three vertices of odd degree.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
The degree sum is even, so the odd degrees must come in an even number.
Trees: connected, no cycles
- A tree 树 is connected (one piece) and acyclic 无环 (no cycles). Every tree with $|V|$ vertices has exactly $|E| = |V| - 1$ edges.
- A leaf 叶子 has degree 1. Combine the two facts with the handshake lemma to answer most tree questions.
A tree has 12 vertices, 5 of them leaves. Edges: $12 - 1 = 11$, so the degree sum is $2 \times 11 = 22$. The leaves give 5, so the other 7 vertices carry $22 - 5 = 17$.
A tree has 30 vertices. How many edges does it have?
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
Every tree has $|E| = |V| - 1 = 29$.
Two ways to search
- Breadth-first search 广度优先搜索 (BFS) uses a queue and visits level by level. In an unweighted graph it finds shortest paths, counted in edges.
- Depth-first search 深度优先搜索 (DFS) uses a stack or recursion and goes as deep as it can before backing up. It finds connected pieces and detects cycles.
Which statements about BFS are true? Select all that apply.
Difficulté 2/5 · 140 pièces + un petit bonus lors de la première réussite aujourd'hui
BFS counts edges, so it gives shortest paths only when every edge costs the same.
Marks that slip away
- Connected is not complete. Connected means one piece; complete means every pair is joined.
- BFS on weighted graphs. BFS counts edges, not weights; a weighted shortest path needs another method.
- Ignoring degree-0 vertices. They still count in $|V|$.
You've got it
- $G = (V, E)$; a matrix costs $n^2$ with $O(1)$ edge tests; a list costs $O(|V| + |E|)$, best for sparse graphs.
- $\sum \deg = 2|E|$, so the number of odd-degree vertices is even.
- Tree: connected and acyclic, $|E| = |V| - 1$. BFS: queue, level order; DFS: stack, depth first.