图和子图 图
图 G = (V, E)， 其中 V = {v1,v2,......,v?} V ---顶点集，
E = {e1,e2,......,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)?V(G),?(G)?E(G).。
习题
1.1.1 若G为简单图，则
a p q b c r d e f G = (V, E)
??????? 。
?2?1.1.2 n ( ? 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。
同构
在下图中， 图G恒等于图H , 记为 G = H ? V（G)=V(H), E(G)=E(H)。 图G同构于图F ? V(G)与V(F), E(G)与E(F)之间各存在一一对应关系，且这二对应关系保持关联关系。 记为 G ?F。
注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。
x adbwcxadbwca?x?d?b?w?c?eyz G=(V, E)
ez y H=(V?, E?)y?e?z?F=(V??, E??)
1
注 判定两个图是否同构是NP-hard问题。 完全图(complete 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 。
K1K2K3K4K5类似地可定义，完全三部图（例如 Km,n,p），完全 n-部 图等。
例。用标号法判定二部图。
二部图
K3,3K1,5K2,2,2
习题
1.2.1 G ? H ? ?(G) = ?(H) , ?(G) = ?(H) 。 并证明其逆命题不成立。
1..2.2 证明下面两个图不同构：
1.2.3 证明下面两个图是同构的：
1.2.4 证明两个简单图G 和H同构 ? 存在一一映射 f : V(G) ?V(H) ，使得 uv ? E(G)当且仅当
f(u)f(v) ? E(H) 。
1.2.5 证明：(a).?(Km,n ) = mn ;
(b). 对简单二部图有 ? ? ?2/4 .
1.2.6 记Tm,n为这样的一个完全m-部图：其顶点数为n，每个部分的顶点数为[n/m]或{n/m}个。证明：
?n?k??k?1? (a). ?(Tm,n) = ???(m?1)?? 其中 k =[n/m] .
?2??2? (b)*. 对任意的n顶点完全m-部图G，一定有 ?(G)? ?(Tm,n)，且仅当G? Tm,n时等式才成立。
1.2.7 所谓k-方体是这样的图：其顶点是由0与1组成的有序k-元组，其二顶点相邻当且仅当它们恰有一个坐标不同。证明k-方体有个顶点，k*2 k-1条边，且是一偶图。
1.2.8 简单图G的补图G c 是指和G有相同顶点集V的一个简单图，在G c中两个顶点相邻当且
2
仅当它们在G不相邻。
(a). 画出Kcn和 Kcm,n。
(b). 如果G ? G c则称简单图G为自补的。证明：若G是自补的，则 ? ? 0, 1 (mod 4)
关联矩阵M(G)与邻接矩阵A(G)
M(G)=[mi,j]???, A(G)=[ai,j]??? ,
其中 mi,j = 顶点vi与边ej 的关联次数= 0, 1, 2. ai,j = 连接顶点vi 与 vj 的边数 。 例。
e1?1?1M(G)???0??0
e21100e30110e40011e51001e60002e71?v10?v2?1?v3?0?v4v1e5e6v4e1e2e7e4G = (V, E)v2e3v3v1?0?2A(G)???1??1
v22010v31101v4101?v1?v ?2?v3?1?v4
子图
子图(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?中所有边的端点为顶点集的的子图。 例。
G[{f, c]}G[{c, d, e}]
3
u
ea yfv
dghb以上两种子图，其实，xcw对应于取子图的两种基本运算。下面是取子图的另两种G=(V, E)G[{u,w,x,y}]G[{u,w,x}]基本运算：
G - V’ ? 去掉V?及与V?相关联的一切边所得的剩
余子图。
? 即 G[V \\ V?]
G - E’ ? 从中去掉E? 后所得的生成子图
例。G - {b, d, g}, ( = G[E \\ {b, d, g}] ) G - {b, c, d, g}, ( ? G[E \\ {b, c, d, g}] ) G - {a, e, f, g}. ( ? G[E \\ {a, e, f, g}] )
注意 G[E \\ E?] 与G - E? 虽有相同的边集，但两者不一定相等 ： 后者一定是生成子图，而前者则不然。
上述四种运算是最基本取子图运算，今后老要遇到，一定要认真掌握好。关于子图的一些定义还有： G + E? ? 往G上加新边集E? 所得的（G的母）图。 为简单计，今后将 G ? {e} 简计为 G ? e ； G - {v} 简计为 G - v 。 设 G1, G2 ? G ，称G1与G2为 不相交的（disjiont） ? V(G1) ? V(G2) = ? ( ? E(G1) ? E(G2) = ? )
边不相交 （edge-distjiont）? E(G1) ? E(G2 ) = ? 。 ( 但这时G1与G2仍可能为相交的）。 并图 G1?G2 , 当不相交时可简记为 G1+G2. 交图 G1?G2 .
习题
1.4.1 证明：完全图的每个导出子图是完全图；偶图的每个导出子图是偶图。
1.4.2 设G为一 完全图，1? n ? ?-1。证明：若 ? ? 4，且G中每个n顶点的导出子图均有相同的边数，则 G ? K?或 Kc? 。
顶点的度
顶点 v的 度 dG(v) = G中与顶点v 相关联边数。 （每一环记为2） 最大、最小度 ?，? 。 （?(G) , ?(G) ) 定理1.1 (hand shaking lemma) 任一图中，
?d(v)?2? .
v?V系1.1 任一 图中，度为奇数顶点的个数为偶数。
例。任一多面体中，边数为奇数的外表面的数目为偶数。 证明。作一图，使其顶点对应于多面体的面，并使其中二顶点相邻当且仅当对应的两个面相邻。...... ?
4
k-正则图 （k-regular g.) ? d(v) = k, ?v ? V . 习题
0-正则图1-正则图2-正则图
1.5.1 证明：? ? 2?/? ? ? 。
1.5.2 若 k-正则偶图(k > 0)的2-划分为 (X, Y),则
?X? = ?Y?。
1.5.3 在人数 >1的人群中，总有二人在该人群中有相同的朋友数。
1.5.4 设V(G) = {v1,v2,......,v?}，则称 ( d(v1), d(v2), ...... , d(v?) ) 为G的度序列。证明：非负整数序列 ( d1 ,d 2, ......, d n) 为某一图的度序列 ?
3-正则图?di?1ni是偶数。
1.5.5 证明：任一 无环图G都包含一 偶生成子图H，使得 dH(v) ? dG(v)/2 对所有v ? V 成立。
*
1.5.6 设平面上有n个点，其中任二点间的距离 ? 1，证明：最多有 3n对点的 距离 = 1 。
路和连通性
途径 （walk) 例如 （u，x）-途径
W = ueyfvgyhwbvgydxdydx (有限非空序列） = uyvywvyxyx (简写法---当不引起混淆时） 起点（origin ） u 。 u终点（terminus） x。 ea内部顶点（internal vertex） y, v, w, x。
fy （注意，中间出现的x也叫内部顶点。）
g长 ? 边数（重复计算）。
dh节（段，section）。 例如W的(y, w)-节=yvw 。
-1
W（逆途径）, WW’（两条途径W与W?相衔接）。 迹( trail) ? 边各不相同的途径。 例如，yvwyx 。 xc路 (path) ? 顶点各不相同的途径。（可当作一个图或子图)。例如， yvwx 。
d(u, v) = u与v之间最短路的长。 例。（命题）G中存在(u, v)-途径 ? G中存在(u, v)-路。
G中顶点u与v为连通的(connected) ? G中存在(u, v)-路
( ? G中存在(u, v)-途径。)
V上的连通性是V上的等价关系，它将V划分为（等图 G价类）：
V1,......,V?
使每个Vi中的任二顶点u及v都连通（即存在(u, v)-路）。 称每个 G[Vi] i=1,2,......?
为G的一个分支（component）; 称?(G）为G的分支数。 G为连通图 ? ?(G) = 1
? G中任两点间都有一 条路相连。 G为非连通图 ? ?(G) ? 1。
vbw
5