图和子图 图和简单图图 G = (V, E)， 其中 V = {νv v v ,......,,21} V ---顶点集， ν---顶点数E = {e e e 12,,......,ε}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 为简单图，则εν≤⎛⎝ ⎫⎭⎪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 。
注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。
de f G = (V, E)y z w cG =(V , E )w cyz H =(V ’, E ’)’a ’c ’y ’e ’z ’F =(V ’’, E ’’)注 判定两个图是否同构是NP-hard 问题。
完全图(complete graph) Kn空图（empty g.） ⇔ E = ∅ 。
