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 , where is the set of vertices and is the set of edges (bonds). b) Initialize each vertex 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 , 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?

參考答案與解析
答案 (E) None of the above choices。
依附圖,以化學鍵為邊(雙鍵也是一條邊,因為步驟 b 的 degree 是「相連的邊數」):12-11、13-11、11-10、10-9、10-5、9-8、8-7、7-6、6-5、5-4、4-3、3-1、3-2,共 13 條邊。
| 頂點 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 初始(degree) | 1 | 1 | 3 | 2 | 3 | 2 | 2 | 2 | 2 | 3 | 3 | 1 | 1 |
| 第 1 輪 | 3 | 3 | 4 | 6 | 7 | 5 | 4 | 4 | 5 | 8 | 5 | 3 | 3 |
| 第 2 輪 | 4 | 4 | 12 | 11 | 19 | 11 | 9 | 9 | 12 | 17 | 14 | 5 | 5 |
例如第 2 輪的頂點 5:鄰居是 10、6、4,第 1 輪的值 。
依值由大到小排序,同值時小的編號在前:
- 5(19)、10(17)、11(14)
- 3 與 9 都是 12,3 在前
- 4 與 6 都是 11,4 在前
- 7 與 8 都是 9
- 12 與 13 都是 5
- 1 與 2 都是 4
結果是 5, 10, 11, 3, 9, 4, 6, 7, 8, 12, 13, 1, 2,與 (A)~(D) 都不同。(B) 是同值時改讓大的編號在前的結果,與題目「tie breaking with smaller labels」不符。