資料結構›Ch6 圖形
第 2 題/共 26 題
◀ DS 2/26
2. 圖形表示、圖演算法模擬
#DS-06-002中圖形表示圖演算法模擬

Many graph theory can be used to find the number of a chemical structure; a possible one can be used according to the following steps: a) Represent the molecule as an undirected graph G=(V,E)G=(V,E), where VV is the set of vertices and EE is the set of edges (bonds). b) Initialize each vertex v∈Vv \in V with a value equal to its degree (number of incident edges). c) For a fixed number of iterations or until convergence: a. For each vertex vv, compute a new value as the sum of the current values of its neighbors (not including itself). b. Update all vertex values simultaneously. d) After the iterations, sort the vertices based on their final values in non-increasing order, tie breaking with smaller labels.

Consider the following 2-Carboxyoxybenzoic acid structure represented as a graph (Numbers in parentheses are temporary labels for reference, not the final numbering.):

Apply the above algorithm for two iterations to this graph. What is the correct ordering of the vertices after these iterations?

題目附圖
📄 台大114
跳轉到第題
▤完整推導請見《WH 資工筆記 · 資料結構》Ch6 圖形
本章題號 · 1–20 / 26