文档介绍：图和子图
图和简单图
图 G = (V, E), 其中
V = {} V ---顶点集, ---顶点数
E = {}E ---边集, ---边数
例。左图中,
V={a, b,......,f},
E={p,q, ae, af,......,ce, cf}
注意, 左图仅仅是图G的几何实现(代表), 它们有无穷多个。真正的图G 是上面所给出式子,它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。
称边 ad 与顶点 a (及d) 相关联。也称顶点 b(及 f) 与边 bf 相关联。
称顶点a与e 相邻。称有公共端点的一些边彼此相邻,例如p与af 。
环(loop,selfloop):如边 l。
棱(link):如边ae。
重边:如边p及边q。
简单图:(simple graph)无环,无重边
平凡图:仅有一个顶点的图(可有多条环)。
一条边的端点:它的两个顶点。
记号:。
习题
若G为简单图,则。
n ( ³ 4 )个人中,若每4人中一定有一人认识其他3人,则一定有一人认识其他n-1人。
同构
在下图中,
图G恒等于图H , 记为 G = H Û VG)=V(H), E(G)=E(H)。
图G同构于图F Û V(G)与V(F), E(G)与E(F)之间各存在一一对应关系,且这二对应关系保持关联关系。记为 G F。
注往往将同构慨念引伸到非标号图中,以表达两个图在结构上是否相同。
注判定两个图是否同构是NP-hard问题。
plete graph) Kn
空图(empty g.) Û E = Æ 。
V’( Í V) 为独立集Û V’中任二顶点都互不相邻。
二部图(偶图,bipartite g.) G = (X, Y ; E) Û存在 V(G) 的一个 2-划分(X, Y), 使X与Y 都是独立集。
完全二部图 Km,n Û 二部图G = (X, Y),其中X和Y之间的每对顶点都相邻,且|X| = m, |Y| = n 。
类似地可定义,完全三部图(例如 Km,n,p),完全 n-部图等。
例。用标号法判定二部图。
习题
G @ H Þ n(G) = n(H) , e(G) = e(H) 。并证明其逆命题不成立。
1.. 证明下面两个图不同构:
证明下面两个图是同构的:
证明两个简单图G 和H同构Û 存在一一映射 f : V(G) ®V(H) ,使得 uv Î E(G)当且仅当 f(u)f(v) Î E(H) 。
证明:(a).e(Km,n ) = mn ;
(b). 对简单二部图有 e £ n2/4 .
记Tm,n为这样的一个完全m-部图:其顶点数为n,每个部分的顶点数为[n/m]或{n/m}个。证明:
(a). e(Tm,n) = 其中 k =[n/m] .
(b)*. 对任意的n顶点完全m-部图G,一定有 e(G)£ e(Tm,n),且仅当G@ Tm,n时等式才成立。
所谓k-方体是这样的图:其顶点是由0与1组成的有序k-元组,其二顶点相邻当且仅当它们恰有一个坐标不同。证明k-方体有个顶点,k*2 k-1条边,且是一偶图。
简单图G的补图G c 是指和G有相同顶点集V的一个简单图,在G c中两个顶点相邻当且仅当它们在G不相邻。
(a). 和 Kcm,n。
(b). 如果G @ G c则称简单图G为自补的。证明:若G是自补的,则 n º 0, 1 (mod 4)
关联矩阵M(G)与邻接矩阵A(G)
M(G)=[mi,j]n*e,
A(G)=[ai,j]n*n ,
其中 mi,j = 顶点vi与边ej 的关联次数= 0, 1, 2.
ai,j = 连接顶点vi 与 vj 的边数。
例。
子图
子图(subgraph) H Í G Û V(H) Í V(G) , E(H) Í E(G) 。
真子图 H Ì G。
母图(super graph)。
生成子图(spanning subg.) Û H Í G 且V(H) = V(G) 。
生成母图。
基础简单图(underlying simple g.)。
导出子图(induced subg.)G[V’], (非空V’Í V )
Û 以V’为顶点集,以G中两端都在V’上的边全体为边集构成的G的子图。
边导出子图 G[E’] 非空E’Í E
Û 以E’为边集,以E’中所有边的端点为顶点集的的子图。
例。
以上两种子图,其实,对应于取子图的两种基本运算。下面是取子图的另两