| English | 意味 |
|---|---|
| graph/ɡræf/ | グラフ |
| vertices/ˈvɜːtɪsiːz/ | 頂点 |
| edges/ˈedʒɪz/ | 辺 |
| degree/dɪˈɡriː/ | 次数 |
| path/pæθ/ | 経路 |
| cycle/ˈsaɪkl/ | 環 |
| connected/kəˈnektɪd/ | 連結 |
| tree/triː/ | 木 |
| weighted graph/ˈweɪtɪd ɡræf/ | 重み付きグラフ |
| shortest path/ˈʃɔːtɪst pæθ/ | 最短路 |
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.
ループのない単純な無向グラフにおいて、ある頂点に4本の辺が接続されている。その次数（degree）はいくつか？
難易度 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 コイン + 今日初回完了時に小ボーナス付与
頂点が4つある有限木は n − 1 = 3 本の辺を持つ。この数は、グラフが実際に連結かつ非循環的であることを前提としている。
重みがすべて正である接続無向グラフにおいて、すべての頂点を覆う最小コストの接続部分グラフにサイクルが存在しないのはなぜか。
難易度 1/5 · 100 コイン + 今日初回完了時に小ボーナス付与
どの辺を_cycle_としても接続性は維持され、その重みが正であるため総コストは低下する。したがって、これらの仮定のもとでサイクルを含む部分グラフが最小となることはあり得ない。
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.
見た目が異なる2つの図は、必ず異なるグラフである。
難易度 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.