v1 (a) v2
v4
v1
v2
(b)
结点的次数
2020/7/10
在图G中的任意一条边e E，都对其联结的结点贡献度数2 定理：在无向图G=<V, E>中， d(v) = 2|E| 通常，将度数为奇数的结点称为奇度结点
将度数为偶数的结点称为偶度结点 定理：在无向图G=<V, E>中，奇度结点的个数为偶数个
给每条边（弧）都赋予权的图，叫做加权图(weighted graph)
记作G=<V, E, W>，W是各边权之和
v3
v3
1
1
2
v1 (a) v2
1
1
2
v1
v2
(b)
v3
1
1
1
v1 1 v2
(c)
图的基本概念
2020/7/10
在无向图G=<V, E>中，V中的每个结点都与其余的所有结点邻
接，即 (va)(vb)(va, vb V [va, vb] E)，如图(a) 则称该图为无向完全图(complete graph)，记作K|V| 若|V|=n，则|E|= C 2 = n(n-1)/2
（va, vb V）则称e是有向边（或弧）
va是e的起始结点， vb是e的终结点
v3
v3
v3
v1 (a) v2
v1
v2
(b)
v1
v2
(c)
图的基本概念
2020/7/10
若va和vb与边（弧）e相联结，则称va和vb是e的端结点 va和vb是邻接结点，记作：va adj vb (adjoin) 也称e关联va和vb，或称va和vb关联e 若va和vb不与任何边（弧）相联结，则称va和vb是非邻接结点， 记作：va nadj vb 关联同一个结点的两条边（弧），称为邻接边（弧）
三、子图
定义：给定无向图G1=<V1, E1>， G2=<V2, E2> 若V2 V1，E2 E1，则称G2是G1的子图(subgraph)， 记作G2 G1 若V2 V1，E2 E1，且E2 ≠ E1，则称G2是G1的真子图， 记作G2 G1 若V2 = V1，E2 E1，则称G2是G1的生成子图(spanning subgraph)，记作G2 G1
V2 = V1
子图
例如：
2020/7/10
v2
v5
v1
v2
v5
v3
v4
(a)
v3 (a)的真子图 v4 v1
v2
v5
v3
v4
(a)的生成子图
子图
2020/7/10
定义：对于图G=<V, E>，G1=<V, E>=G，G2=<V, > G1和 G2都是G的生成子图，称为平凡生成子图 定义：设G2=<V2, E2>是G1=<V1, E1>的子图
第七章 图论基础
Graphs
第一节 图的基本概念
2020/7/10
一个图G定义为一个三元组：G=<V, E, Φ>
V —— 非空有限集合，V中的元素称为结点 (node)或 顶点(vertex)
E —— 有限集合（可以为空），E中的元素称为边(edge)
Φ —— 从E到V的有序对或无序对的关联映射 (associative mapping)
v3
v3
v3
v1 (a) v2
v1
v2
(b)
v1
v2
(c)
图的基本概念
2020/7/10
图G=<V, E, Φ>中的每条边都与图中的无序对或有序对联系
若边e E 与无序对结点[va, vb]相联系，即Φ(e)= [va, vb] （va, vb V）则称e是无向边（或边、棱）
若边e E与有序对结点<va, vb>相联系，即Φ(e)=<va, vb>
（或<u, v> E1 <f(u), f(v)> E2）
则称G1与G2同构(isomorphic)，记作 G1 G2
图的同构
2020/7/10
例7.1.1 证明下面两个图G1=<V1, E1>， G2=<V2, E2>同构
证明：V1={v1, v2, v3, v4}, V2={a, b, c, d}
对任意结点u, v V2，若有[u, v] E1，则有[u, v]E2， 则G2由V2唯一地确定，则称G2是V2的诱导子图 记作G[V2]，或G2=<V2> 若G2中无孤立结点，且由E2唯一地确定，则称 G2是E2的诱导子图，记作G[E2]，或G2=<E2>
子图
例如：
2020/7/10
v1
v2
关联同一个结点及其自身的边，称为环(cycle)，环的方向没有
意义 v3
v3
v3
v1 (a) v2
v1
v2
(b)
v1
v2
(c)
图的基本概念
2020/7/10
若将图G中的每条边（弧）都看作联结两个结点 则G简记为：<V, E>
每条边都是弧的图，称为有向图(directed graph)（如图b）
每条边都是无向边的图，称为无向图(undirected graph)
v1
构造双射函数f : V1 V2 ，f(v1)=a ，f(v2)=b
f(v3)=c ，f(v4)=d
v2
v4
可知，边[v1, v2], [v2, v3], [v3, v4], [v4, v1]被分别映射成[a, b], [b, c], [c, d], [d, a]，故G1 G2
a
b v3
G1
c
v5
v2
v5
v3
v4
G=<V, E>
v3
v4
G’=<V’, E’>
V’或E’的诱导子图
补图
2020/7/10
定义： 设G1=<V1, E1>和G2=<V2, E2>是G=<V, E>的子图，
若 E2 = E - E1，且G2是E2的诱导子图，即G2=<E2>
则称G2是相对于G的G1的补图
补图
图G1和G2互为
v1
相对于G补图
v2
v5
v1 v2
v3
v4
G
v5
v2
2020/7/10
v5
v3
v4
G1
v3
v4
G2
补图
2020/7/10
定义： 给定图G1=<V, E1> ，若存在图G2=<V, E2>
且 E1 E2 = ，及图<V, E1 E2 >是完全图
则称G2是相对于完全图的G1的补图，记作G2 = G1
补图
v1
v2
v5
2020/7/10
v3
v4
G2 = G1
v1
K5
v1
v2
v5
v2
v5
v3
v4
G1
v3
v4
G2
图的同构
2020/7/10
四、图的同构
定义：
给定图G1=<V1, E1>， G2=<V2, E2>
若存在双射函数f : V1 V2 ，使得对于任意u, v V1
有
[u, v] E1 [f(u), f(v)] E2
要注意的是，这不是充分条件
2020/7/10
图的同构
2020/7/10
例7.1.3 证明下面两个无向图是不同构的
n
v3
v3
v1 (a) v2
v1
v2
(b)
图的基本概念
2020/7/10
在有向图G=<V, E>中，V中的任意两个结点间都有方向相反的
两条弧，即
(va)(vb)(va,vbV <va,vb>E∧<vb,va>E)，如图(a)
则称该图为有向完全图，记作K|V|
若|V|=n，则|E|=
P
2 n
=
n(n-1)
平行边（弧）的条数，称为重数
v3
v3
v3
v1 (a) v2
v1
v2
(b)
v1
v2
(c)
图的基本概念
2020/7/10
在多重图的表示中，可在边（弧）上标注正整数，以表示平行边 （弧）的重数
把重数作为分配给边（弧）上的数，称为权(weight) 将权的概念一般化，使其不一定是正整数，则得到加权图的概念：
2020/7/10
类似问题： 1. 晚会上大家握手言欢，握过奇数次手的人数一定是偶数 2. 碳氢化合物中，氢原子个数是偶数 3. 是否有这样的多面体，它有奇数个面，每个面有奇数条
棱？
结点的次数
2020/7/10
问题2：是否存在这种情况：两个人或以上的人群中，至少
有两个人在此人群中的朋友数一样多？
以人为结点，仅当二人为朋友时，在此二人之间连一边， 得一“友谊图”G(V,E)， 设V={v1, v2, …, vn}，不妨 设各结点的次数为d(v1)≤d(v2)≤… ≤d(vn)≤n-1。 假设命题不成立，则所有人的朋友数都不一样多，则
d
G2
图的同构
2020/7/10
例7.1.2 证明下面两个有向图是同构的。
d
c
证明：如图所示，G1=<V1, E1>，
G2=<V2, E2>，结点编号如图所示。