路线端点:每条边贡献两个次数
用逐边计数解释无向图各点连接数总和为边数两倍的有限实例。
视频暂时无法加载。请检查网络后重试,或直接下载视频。
下载视频
展开视频文字稿
- 这个无向图只有四条边:AB、AC、BC和CD。每条边都有两个端点。
- 先数A,连接AB和AC,所以A的连接数是2。
- B连接AB和BC,也是2;C连接AC、BC、CD,所以是3。
- D只连接CD,连接数是1。逐点相加是2加2加3加1等于8。
- 换一种数法,四条边各贡献两个端点次数,也是4乘2等于8。
- 两种计数得到同一总和,能检查是否漏边;这里只验证这张有限图。
逻辑思维
逐边在两个端点各记一次。
看一个例子
四个点有边AB、AC、BC、CD,各点连接数之和是多少?
连接数为2、2、3、1,总和8。逐边在两个端点各记一次。
马上试一题
每条边贡献两个端点次数,三乘2等于6。