关于图的分块
  • 板块学术版
  • 楼主AE酱
  • 当前回复9
  • 已保存回复9
  • 发布时间2020/9/6 13:41
  • 上次更新2023/11/5 13:37:52
查看原帖
关于图的分块
28172
AE酱楼主2020/9/6 13:41

看到网上有博客说,
一个 nn 个点 mm 条边的无向图,把度数小于 m\sqrt m 的点记为轻点,把度数大于等于 m\sqrt m 的点记为重点,那么一个轻点只与不超过 m\sqrt m 个点相邻,一个重点只与不超过 m\sqrt m 个重点相邻。

这个怎么证明?我试了下,假设 uu 这个重点与 m\sqrt m 个重点相邻,与它相邻的重点度数都大于等于 m\sqrt m,那么总度数至少为 m×m+m=m+m\sqrt m\times \sqrt m+\sqrt m=m+\sqrt m,仍然小于 2m2m

2020/9/6 13:41
加载中...