关于一个数学中图论的证明
  • 板块灌水区
  • 楼主yyz1005
  • 当前回复39
  • 已保存回复39
  • 发布时间2021/11/2 18:44
  • 上次更新2023/11/4 01:34:04
查看原帖
关于一个数学中图论的证明
220824
yyz1005楼主2021/11/2 18:44

已知有一个有向图 GG,它包含了 VV 个点和 SS 条边,记 f(i,j)f(i,j) 表示第 ii 个点和第 jj 个点之间有一条有向边,由 ii 指向 jj

若存在两个点:aa,bb 满足 f(a,b)f(a,b)f(b,a)f(b,a) 则删除 a,ba,b,由 aa 指向 bb 的边和由 bb 指向 aa 的边,但是不删除由除 a,ba,b 之外的点指向 a,ba,b 的边。

求证:最后剩下的途中必然存在一个环或一个链。

环:ab...aa \rightarrow b \rightarrow ... \rightarrow a

链:abc...?a \rightarrow b \rightarrow c \rightarrow... \rightarrow ? \rightarrow

2021/11/2 18:44
加载中...