当前位置: article > 正文

从农夫过河问题理解顶点覆盖、团和独立集_团覆盖问题

作者：Gausst松鼠会 | 2024-04-07 12:31:11

踩

团覆盖问题

经典的农夫过河问题，相冲突的生物之间有连线，每次携带走某几个生物后，要保证剩下的没有连线存在。问船的容量最小是多少呢？

视频：【Numberphile】农夫过桥问题和阿尔昆数
过河问题
直观的思路就是，找最少需要几只手盖住顶点后能消除所有连线（即最小覆盖）：
在这里插入图片描述
但有时只有最小顶点覆盖个位置是不够的。

如下面的例子，最小顶点覆盖显然是1，把狼盖住就行了：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/378616