Category Archives: Translations

图论科学家教你如何安排婚礼座次

0

本文由我及其他两位译者翻译并转载至微信公众号“大数据文摘”

该文章最先发表于Quanta Magazine,该杂志为Simons Foundation独立出版,致力于通过报道数学、物理、与生命科学的前沿研究

选文:纪思亮

翻译&校对:闫蒲 Lily 赵娟

摘要:完美图,指的是用尽可能有限的一组颜色着色的网络图。在给图表着色时,每一个处于相互之间密集联系的“团”内的节点都必须被指定一个独一无二的颜色。而至今为止,关于如何处理方形结构的着色,仍然没有得到解决。

四年前,数学家Maria Chudnovsky 遭遇到一个常见困境:如何给120名参加婚礼的客人安排好座位,在所有客人中有可能存在矛盾,问题的关键在于如何避免将有矛盾的客人安排在同一张桌子前就座。很幸运,这个问题恰巧在她的研究领域内。Maria把客人视作网络中的节点,用线将“不相容”的节点间连接在一起。问题于是转化为:用一系列不同颜色来代表不同餐桌,再将节点分别着色。只要毗邻节点保证不同色,婚宴中便不会出现尴尬事件。

Continue reading