— Chinese Systematic Naming of Saturated Chain Hydrocarbon by Graph Algorithms

Doing systematic naming is an important job in Chemistry when doing organic research, which helps the academic communication. As learnt in high school, systematic naming is tedious, which always gave deductions in exams to the Monkey. Furthermore, manually naming is low-efficient. Using his knowledge gained from algorithm contests, the Monkey abstracts the problem to graph problem, where organic compounds become graphs and  saturated chain hydrocarbon (SCH) becomes Tree Network.


An example of SCH (饱和链烃的例子)

According to the rules used in Chinese systematic naming, we must solve three main problems, i.e. finding the main chain, choosing the end to start, and sorting the side-chains. The SCH shown above is named as "2,2,4,4-四甲基-3,3-二(1,1-二甲基乙基)戊烷" ["2,2,4,4-Si Jia Ji-3,3-Er(1,1-Er Jia Ji Yi Ji)Wu Wan" in Chinese phonetic symbol].


In the proposed model, for SCH, the main chain corresponds to the diameter of a tree network, and grouping the side-chains corresponds to the isomorphic problem of trees. The Monkey shows that this problem is a P problem, which means that it has "meaningful solutions". Then, the Monkey proposes an algorithm  for systematic naming with a time complexity of \(O(n^2 \log n)\).

在我们提出的模型中,饱和链烃的主链对应着树网的直径,合并官能团对应着树的同构问题。猴哥指出该问题是P类问题,即存在“有意义的解”。之后,猴哥提出了一个时间复杂度为\(O(n^2 \log n)\)的命名算法。

This research project won the 2nd Prize of Applied Mathematics Contest in Beijing. With the research, the Monkey was awarded as the 3rd Prize of Annual Awards Program for Future Scientists of Tomorrow by Chinese Ministry of Education and the Award of Innovations for High Students of Beijing High School Four in 2009. The corresponding paper was published in Bulletin des Sciences Mathematics (in Chinese) in 2011.


Presentation of Systematic Naming Research (系统命名研究的演示文稿)