求证明结论
  • 板块学术版
  • 楼主xsmfollower
  • 当前回复2
  • 已保存回复3
  • 发布时间2024/7/13 09:55
  • 上次更新2024/7/13 11:15:47
查看原帖
求证明结论
1308728
xsmfollower楼主2024/7/13 09:55

对于一个有 nn 个点 mm 条边的无向图(点的编号为 1∼n1 \sim n),称一个节点是可行的,表示删掉这个节点和这个点连出去的边后图变成了一棵树。保证图中至少存在一个可行的节点。

求证明:一个节点是可行的当且仅当他不是原图的割点且他的度数为 m−n+2m-n+2。

2024/7/13 09:55
加载中...