Graph8/图论 72图的术语/ Graph terminology 定义相邻和关联: 在无向图G中,若e=(a,b)∈E,则称a 与b相邻 adjacent,或边e关联a、 b/incident或联结 a、b/ connecto a、b称为边e的端点或结束顶点 /endpoint. 在有向图G中,若e=(a,b)∈E,即箭头由 的起点 nitial vertex,b称为e的终点 termina/b a到b,称a相邻到b,或a关联或联结b。a称为c end vertex o 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 6 7.2 图的术语/Graph Terminology [定义]相邻和关联： 在无向图G中，若e=（ａ，ｂ）∈Ｅ，则称ａ 与b相邻/adjacent，或边e关联a、ｂ/incident或联结 a、b/connect。a、b称为边e的端点或结束顶点 /endpoint. 在有向图G中，若e=（ａ，ｂ）∈Ｅ，即箭头由 ａ到ｂ，称ａ相邻到ｂ，或a关联或联结b。a称为e 的起点/initial vertex，b称为e的终点/terminal or end vertex
Graph8/图论 定义]孤立顶点: 若a∈V,a不与其他顶点相邻,称 a为孤立顶点/ solated 定义自回路: 若(a,a)∈E,({a,a}∈E), 称边(a,a)({a,a})是自回路/oop。 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 7 [定义]自回路： 若（ａ，ａ）∈Ｅ，（{ａ，ａ}∈Ｅ）， 称边（ａ，ａ）（{ａ，ａ}）是自回路/loop。 [定义]孤立顶点： 若ａ∈Ｖ，ａ不与其他顶点相邻，称 ａ为孤立顶点/isolated
Graph8/图论 定义顶点的次: 在无向图G中,与a相邻的顶点的数目称 为a的次或度 /degree记为deg(a)或da) 在有向图G中,以a为终点的边的条数称 为a的入次或入度 /in-degree记为deg(a或d (a)。以a为起点的边的条数称为a的出次或出 度/ out-degree。记为deg(a或d+(a)。 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 8 [定义]顶点的次： 在无向图G中，与a相邻的顶点的数目称 为a的次或度/degree。记为deg(a)或d(a)。 在有向图G中，以a为终点的边的条数称 为a的入次或入度/in-degree。记为deg– (a)或d – (a)。以a为起点的边的条数称为a的出次或出 度/out-degree。记为deg+ (a)或d + (a)
Graph8/图论 定理1( Handshaking)l设无向图G= (V,E)有e条边,则G中所有顶点的次 之和等于e的两倍 证明思路:利用数学归纳法。 定理2]无向图中次为奇数的顶点个数 恰有偶数个。 证明思路:将图中顶点的次分类,再利用 定理1。 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 9 [定理1 (Handshaking)] 设无向图G= （V，E）有e条边，则G中所有顶点的次 之和等于e的两倍。 证明思路：利用数学归纳法。 [定理2] 无向图中次为奇数的顶点个数 恰有偶数个。 证明思路：将图中顶点的次分类，再利用 定理1
Graph8/图论 定理3]设有向图G=(V,E)有e条边, 则G中所有顶点的入次之和等于所有顶点 的出次之和,也等于e 证明思路:利用数学归纳法。 2/24/202111:16PM Deren Chen Zhejiang univ
G r a p h s / 图 论 2/24/2021 11:16 PM Deren Chen, Zhejiang Univ. 10 [定理3] 设有向图G=（V，E）有e条边， 则G中所有顶点的入次之和等于所有顶点 的出次之和，也等于e。 证明思路：利用数学归纳法