路线端点:每条边贡献两个次数

逻辑思维 · 建议年级 5

用逐边计数解释无向图各点连接数总和为边数两倍的有限实例。

下载视频
展开视频文字稿
  1. 这个无向图只有四条边:AB、AC、BC和CD。每条边都有两个端点。
  2. 先数A,连接AB和AC,所以A的连接数是2。
  3. B连接AB和BC,也是2;C连接AC、BC、CD,所以是3。
  4. D只连接CD,连接数是1。逐点相加是2加2加3加1等于8。
  5. 换一种数法,四条边各贡献两个端点次数,也是4乘2等于8。
  6. 两种计数得到同一总和,能检查是否漏边;这里只验证这张有限图。
讲解依据

逻辑思维

逐边在两个端点各记一次。

看一个例子

四个点有边AB、AC、BC、CD,各点连接数之和是多少?

连接数为2、2、3、1,总和8。逐边在两个端点各记一次。

马上试一题

三角形有3条边,各点连接数总和是多少?