— 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].
根据中文系统命名的规则，我们必须解决三个主要的问题，即：寻找主链、选择开始命名的一端、对侧链（官能团）进行排序。上图中所示的饱和链烃命名为“2,2,4,4-四甲基-3,3-二(1,1-二甲基乙基)戊烷”。
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 \(\).
在我们提出的模型中，饱和链烃的主链对应着树网的直径，合并官能团对应着树的同构问题。猴哥指出该问题是P类问题，即存在“有意义的解”。之后，猴哥提出了一个时间复杂度为\(\)的命名算法。
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.
该研究项目获北京市应用数学竞赛二等奖、中国教育部组织的“明天小小科学家”奖励活动三等奖、北京市第四中学中学生创新奖。对应的论文于2011年在数学通报上发表。
Leave a Reply
You must be logged in to post a comment.