NOIP 普及组初赛 · NOIP 2014 普及组初赛试题 第 17 题

有向图中每个顶点的度等于该顶点的( )。

拿到题先别急着套公式，想清楚有向图和无向图的根本区别：边有方向，所以得从‘进’和‘出’两个方向数边，把两部分加起来才是顶点的度。

容易把无向图里‘度=相连边数’的习惯直接搬过来，只数了入度或只数了出度，或者误以为差值有意义。其实有向图里一条边对起点贡献出度、对终点贡献入度，两者缺一不可，漏掉任何一边都会少算一半。

这道题考什么

考察的是有向图里‘顶点的度’这个基本概念的准确定义。

概念：用大白话讲明白

无向图里，一个顶点的度就是跟它连了多少条边，数数就行。但有向图不一样，边有箭头，所以得拆开看：

• 入度：箭头指向这个顶点的边有几条；
• 出度：从这个顶点出发、箭头指出去的边有几条。

顶点的度，就是把这两部分合起来，即入度 + 出度。