【笔记】线图 / Line graph

Posted on

在图论中,一张无向图的线图是能体现其连边状态的一种生成图。有关线图的中文资料很少,但有关它的外文资料非常丰富。在这篇文章中,我将简单介绍线图的定义,以及提出计算线图最小生成树大小的一种方法。

Featured

【杂谈】Boy Erased: Some Thoughts

Posted on

在电影的这个故事里,Jared 经历了自我接受,完成了矛盾化解,但帮助过 Jared 的 Cameron 在最终结束了自己的生命。而电影之外,世界更多社会里,LGBTQ 社群的成员们则在更阴暗的角落里饱受折磨,他们离 Love, Simon 很远,离 Brokeback Mountain 更近,他们的生活是黑暗一片。

【笔记】从傅里叶变换到数论变换

Posted on

我们可以使用傅里叶变换来快速计算卷积。然而快速傅立叶变换具有一些实现上的缺点,我们必须做复数而且是浮点数的运算,因此计算量会比较大,而且浮点数运算产生的误差会比较大。
这个问题可以用数论变换解决。在模意义下,一些整数可以发挥单位复根的作用,使我们更精确地计算只有整数参加的卷积运算结果。