— 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.
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 \(\).
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.