文章目录
5.1 无向图及有向图
5.1.1 无向图
多重集合：元素可以重复出现的集合
定义 无向图G=<V,E>, 其中
(1) 顶点集V是非空有穷集合, 其元素称为顶点
(2) 边集E为V&V的多重子集，其元素称为无向边，简称边
5.1.2 有向图
定义 有向图G=<V,E>D=<V,E>, 其中
(1)顶点集V是非空有穷集合, 其元素称为顶点
(2) 边集E为 V× V的多重子集，其元素称为有向边，简称边
D的基图:用无向边代替有向边
5.1.3 无向图与有向图
-
通常用G表示无向图, D表示有向图, 也常用G泛指无向图和有向图。
V(G), E(G), V(D), E(D): G和D的顶点集, 边集n阶图: n个顶点的图
零图: E= ∅
平凡图: 1 阶零图
空图: V= ∅
5.1.4 顶点和边的关联与相邻
定义 设e=(u,v)是无向图G=<V,E>的一条边, 称u,v为e的端点,e与u(v)关联。
若u≠v, 则称e与u(v)的关联次数为1;
若u=v, 则称e为环, 此时称e与u 的关联次数为2;
若w不是e端点, 则称e与w 的关联次数为0。
无边关联的顶点称作孤立点。
定义 设无向图G=<V,E>, u,v∈V, e,e’∈E, 若(u,v)∈E, 则称u,v相邻;
若e,e’至少有一个公共端点, 则称e,e’相邻。
对有向图有类似定义。设e=<u,v>是有向图的一条边,又称u是e的始点,v是e的终点, u邻接到v, v邻接于u。
5.1.5 顶点的度数
设G=<V,E>为无向图, v ∈ V,
v的度数(度) d(v): v作为边的端点次数之和
悬挂顶点: 度数为1的顶点
悬挂边: 与悬挂顶点关联的边
G的最大度 △ (G)=max{d(v)|v∈V}
G的最小度 δ (G)=min{d(v)| v∈V}
右图中d(v5)=3, d(v2)=4, d(v1)=4,△(G)=4, δ(G)=1,v4是悬挂顶点, e7是悬挂边, e1是环
设D=<V,E>为有向图, v∈V,
v的出度d+(v) : v作为边的始点次数之和
v的入度d-(v): v作为边的终点次数之和
v的度数(度)d(v) : v作为边的端点次数之和
d(v)= d+(v)+ d-(v)
D的最大出度△+(D) =max{d+(v)|v∈V}
最小出度δ+(D) =min{d+(v)|v∈V}
最大入度△-(D) =max{d-(v)|v∈V}
最小入度δ-(D) =min{d-(v)|v∈V}
最大度 △ (D)=max{d(v)|v∈V}
最小度 δ (D)=min{d(v)|v∈V}
实例：
5.1.6 握手定理
-
定理
任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点入度之和等于出度之和等于边数。
-
证明
G中每条边（包括环）均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，m条边共提供2m度。
有向图的每条边提供一个入度和一个出度, 故所有顶点入度之和等于出度之和等于边数。
-
推论
任意无向图和有向图的奇度顶点个数必为偶数。
5.1.7 图的度数列
设无向图G的顶点集V={v1, v2, …, vn}
G的度数列: d(v1), d(v2), …, d(vn)
如右图度数列:4,4,2,1,3
设有向图D的顶点集V={v1, v2, …, vn}
D的度数列: d(v1), d(v2), …, d(vn)
D的出度列: d+(v1), d+(v2), …, d+(vn)
D的入度列: d-(v1), d-(v2), …, d-(vn)
如右图度数列:5,3,3,3
出度列:4,0,2,1
入度列:1,3,1,2
例题：
-
一个部门有25个人，由于意见不同，是否可能每个人恰好与其他5个人意见一致？
A 可能 B 不可能
-
唐氏夫妇邀请另外三对夫妇来家里吃饭，已知每个人都不和自己握手，不和自己的配偶握手，同时最多和一人握手一次。在大家吃完饭后，唐先生问大家握了几次手，每个人的回答都不相同。请问：唐太太握手几次？
A 0 B 1 C 2 D 3 E 4 F 5 G 6
答案：1. B 2. D
5.1.8 多重图与简单图
(1)在无向图中,如果有2条或2条以上的边关联同一对顶点, 则称这些边为平行边, 平行边的条数称为重数。
(2)在有向图中,如果有2条或2条以上的边具有相同的始点和终点, 则称这些边为有向平行边, 简称平行边, 平行边的条数称为重数。
(3) 含平行边的图称为多重图。
(4) 既无平行边也无环的图称为简单图。
注意:简单图是极其重要的概念。
实例：
5.1.9 完全图
n阶无向完全图Kn：每个顶点都与其余顶点相邻的n阶无向简单图。
简单性质：边数m=n(n-1)/2，Δ=δ=n-1
K5：
n阶有向完全图：每对顶点之间均有两条方向相反的有向边的n阶有向简单图。
简单选择：边数m=n(n-1)，Δ=δ=2(n-1)
Δ+=δ+=Δ-=δ-=n-1
3阶有向完全图：
5.1.10 子图
设G=<V,E>，G’=<V’,E’>是两个图。
(1)若V’⊆V且E’⊆E，则称G’是G的子图，G是G’的母图，记作G’⊆G。
(2) 若G’⊆G 且V’=V，则称G’为G的生成子图。
(3) 若V’⊂V 或E’⊂E，称G’为G的真子图。
(4) 设V’⊆V 且V’≠∅, 以V’为顶点集, 以两端点都在V’中的所有边为边集的G的子图称作V’的导出子图，记作 G[V’]。
(5) 设E’⊆E且E’≠∅, 以E’为边集, 以E’中边关联的所有顶点为顶点集的G的子图称作E’的导出子图, 记作 G[E’]。
注意：每个图都是本身的子图。
生成子图的实例：
K4的所有非同构的生成子图
导出子图的实例：
5.1.11 补图
定义：设G=<V,E>是n阶无向简单图，以V为顶点集,所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图。记作G’。若G≌G’，则G是自补图。
5.1.12 图的同构
定义:G1=<V1,E1>, G2=<V2,E2>为两个无向图(有向图), 若存在双射函数 f: V1→V2, 使得对于任意的vi,vj∈V1, (vi,vj)∈E1（<vi,vj>∈E1）当且仅当 (f(vi),f(vj))∈E2（<f(vi),f(vj)>∈E2），并且, (vi,vj)（<vi,vj>）与 (f(vi),f(vj))（<f(vi),f(vj)>）的重数相同，则称G1与G2是同构的，记作G1≌G2。
同构实例：
左边上下两图是同构的，右边上下两图也是同构的。
说明：
-
图之间的同构关系具有自反性、对称性和传递性。
-
能找到多条同构的必要条件，但它们都不是充分条件：
①边数相同，顶点数相同
②度列数相同（不计度数的顺序）
③对应定点的关联集及领域的元素个数相同，等等
-
若破坏必要条件，则两图不同构
-
至今没有找到判断两个图同构的多项式时间算法
例题：
（1）
A 同构 B 不同构
（2）
A 同构 B 不同构
（3）
A 同构 B 不同构
答案：（1）A （2）A （3） B