1 图和子图 图和简单图 图 G = (V, E)， 其中 V = {vvv,......,,21} V ---顶点集， ---顶点数 E = { e ee12,,......, }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）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：()() ,()().GV GGE G。 习题 1.1.1 若 G 为简单图，则 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。 注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。 d e f G = (V, E) p q a b c r ayzxwbcde G=(V, E)xwbcdea yz H=(V’, E’)x’d’w’a’b’c’y’e’z’F=(V’’, E’’) 2 注 判定两个图是否同构是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 。 类似地可定义，完全三部图（例如 Km,n,p），完全 n-部 图等。 例。用标号法判定二部图。 习题 1.2.1 G H (G) = (H) , (G) = (H) 。 并证明其逆命题不成立。 1..2.2 证明下面两个图不同构： 1.2.3 证明下面两个图是同构的： 1.2.4 证明两...
