| English | 释义 | 拼音 |
|---|---|---|
| graph/ɡræf/ | 图 | tú |
| vertices/ˈvɜːtɪsiːz/ | 顶点 | dǐng diǎn |
| edges/ˈedʒɪz/ | 边 | biān |
| degree/dɪˈɡriː/ | 度 | dù |
| path/pæθ/ | 路径 | lù jìng |
| cycle/ˈsaɪkl/ | 环 | huán |
| connected/kəˈnektɪd/ | 连通 | lián tōng |
| tree/triː/ | 树 | shù |
| weighted graph/ˈweɪtɪd ɡræf/ | 带权图 | dài quán tú |
| shortest path/ˈʃɔːtɪst pæθ/ | 最短路径 | zuì duǎn lù jìng |
A connection model needs its assumptions
- A graph 图 has vertices 顶点 and edges 边. Decide what they represent and whether the connections are directed, weighted or undirected.
- The worksheet uses finite simple undirected graphs without loops or repeated edges. Drawing position does not change their connections, but an arrow or edge weight can change the mathematical model.

Count connections consistently
- Degree 度 counts incident edges in a simple undirected graph. The total degree is twice the number of edges, so it must be even.
- A path 路径 follows connections; a cycle 环 returns to its start without repeating other vertices. A graph is connected 连通 when each vertex can be reached from every other.
在一个无环的简单无向图中,四个边与一个顶点相连。该顶点的度是多少?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
其度为 4,即在该图约定下与该顶点关联的边数。
A tree needs two properties
- A tree 树 is connected and has no cycles. A finite tree with n vertices has n minus 1 edges.
- Having n minus 1 edges alone does not prove a tree: a triangle plus a separate two-vertex component has five vertices and four edges but is disconnected and cyclic.
一棵树有 4 个顶点,它有几条边?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
具有四个顶点的有限树拥有 n − 1 = 3 条边。此计数依赖于该图确实是连通且无环的。
在一个边权严格为正值的连通无向网络中,为什么包含所有顶点的最小成本连通子图不含环?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
移除任意一条环上的边均可保持连通性并降低总成本,因为其权重严格为正。因此,在这些假设下,含环的子图不可能是最小成本的。
Positive-cost connecting roads. For a connected network with strictly positive road costs, removing a cycle edge leaves connectivity and lowers cost. A minimum-cost connecting subgraph is therefore a tree. To find a minimum spanning tree, choose edges that connect all vertices without a cycle; blindly choosing the cheapest n minus 1 edges can leave separate components.
A shortest route is not a spanning tree
- A weighted graph 带权图 attaches a specified value to each edge. A shortest path 最短路径 minimises route weight between the given endpoints.
- A minimum spanning tree instead connects every vertex at minimum total included weight. A shortest route can have more edges than a direct expensive route; sum the weights rather than count the edges.
把每种情形与其顶点和边的含义配对。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
确定顶点代表什么,就是建模这一步,而分数也在这里。
A closed edge changes feasibility. Sheet 4.5 finds a route of weight 7, then closes an edge and checks a replacement of weight 9. Do not reuse the old total for a path that no longer exists.
两张看起来不同的图画,一定是不同的图。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
不同的布局可能具有相同的标记邻接关系。当这些要素属于指定图的一部分时,还需比较方向和权重。
Compare all structure relevant to the question: vertex correspondence, adjacency, directions and weights where specified. Equal-looking pictures need not represent the same graph; different layouts can represent the same labelled connections.