性质1.1.4K,的边数是号(m-) 明：K中每各结点的度都是(n一1)，由性质1,1.1即得、 性质1.1.5简单图(；中一定存在肢相同的结点， 证明：设G中不存在弧立结点，则对个结点的简 单图，每个结点度d()的取值范倒是1~(-…1)，由抽屉 原理，定存在两个度相同的结点。若存在孤立结点，亦 类似可证， 定义1.1.4如果图G=(V,E)的每条边e=(, ,)都赋以一个实数心：作为该边的权，则称G是赋权图。 特别地，如果这些权都是正实数，就称G是E权图。 图1.5就是一个正权图。权可以表示该边的长度.时 1.5 间，费用或容量等。 定义1.1.5给定G=(V,E),如果存在另-个图(G”=(,E),满足V'三V,三E, 则称G是（的-个子图。特别地，如果V=V,就称G是C的支撑子图或生成子图；如泉 '二V,且E包含了G在结点子集V之间的所有边，则称G是G的导出子图。 例如，图1.6中的G和G:分别是的支撑子图和导出子图，（是G的子图。按照 子图的定义，显然G也是它自身的子图，而且既是支撑子图，也是导出子图。空图也是G 的了图.而月是支撑子图.它们都称为平凡子图。 G 图1.6 定义1.1.6给定两个图G1=(V,E,),G一(V2,Ez)。令GUG=(V,E),其中V =VUV2,E=EUE,CG∩G2=(V,E),其中V=V:∩V2,E=E∩E2,G,①G2=(V. E),其中V=V1UV:,E=E,⊕E2,分别称为G和G2的并、交和对称差。 例如图1.？中G和G2的并、交，对称差分别是(a)、(b)和(c)。 在G中删去一个子图H,指删掉H中的各条边，记作G一H,特别地，对于简单图G, 称K.一G为G的补图，记作G。例如图1.7中G1的补图是(d)。从G中去某个结点v 及其关联的边所得到的图记作G一v。从G中删去某条特定的边e=(u,u),记作G-e,例 如图1.6中G一=(G2,G2一(，s)=G。显见G一是(G的导出子图，而G一e是G的支 撑子图。如果在G中增加某条边e,可记作G十e,例如G3十(v,u)=G2。 ▣3·