求证一关于图论结论
  • 板块学术版
  • 楼主__vector__
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/8/1 10:48
  • 上次更新2024/8/1 11:42:23
查看原帖
求证一关于图论结论
507348
__vector__楼主2024/8/1 10:48

本结论在无向图下,边有边权,可以有重边自环。

设所有环的异或和构成空间 VV,d′(u,v)d'(u,v) 表示 uu 到 vv 的任意路径的异或和。

d(u,v)d(u,v) 表示 uu 到 vv 的最大路径异或和。

则 d(u,v)=max⁡{d′(u,v)⊕x∣x∈V}d(u,v) = \max \{d'(u,v) \oplus x | x \in V \}

本蒟蒻太菜了不会证明,求大佬们帮忙,谢谢。

2024/8/1 10:48
加载中...