第8章图的基本概念 【例81.3】求解下列各题 (1)无向完全图Kn有28条边,则它的顶点数n为 多少? (2)图G的度数列为2,2,3,5,6,则边数m为 多少? (3)图G有12条边,度数为3的顶点有6个,余者 度数均小于3,问G至少由几个顶点?
第8章 图的基本概念 【例8.1.3】 求解下列各题: （1）无向完全图Kn有28条边，则它的顶点数n为 多少？ （2）图G的度数列为2，2，3，5，6，则边数m为 多少? （3）图G有12条边，度数为3的顶点有6个，余者 度数均小于3，问G至少由几个顶点？
第8章图的基本概念 解(1)因为无向完全图K的边数m=112mn(m-1)=28, 所以n=8。 (2)由握手定理2m∑以(v)=2+2+3+5+6-18,知 (3)由握手定理∑d(v)=2m=24,度数为3的顶点有 6个占去18度,还有6度由其余顶点占有,而由题意, 其余顶点的度数可为0,1,2,当均为2时所用顶点数 最少,所以应有3个顶点占有此6度,即G中至少有9个 顶点
第8章 图的基本概念 解 （1）因为无向完全图Kn的边数m=1/2 n(n-1)=28， 所以n=8。 （2）由握手定理2m=∑d(v)=2+2+3+5+6=18，知 m=9。 （3）由握手定理∑d(v)=2m=24，度数为3的顶点有 6个占去18度，还有6度由其余顶点占有，而由题意， 其余顶点的度数可为0，1，2，当均为2时所用顶点数 最少，所以应有3个顶点占有此6度，即G中至少有9个 顶点
第8章图的基本概念 【例814】证明在n(n2)个人的团体中,总有 两个人在此团体中恰好有相同个数的朋友。 解以顶点代表人,二人如果是朋友,则在代表他 们的顶点间连上一条边,这样可得无向简单图G,每个 人的朋友数即图中代表它的顶点的度数,于是问题转 化为:n阶无向简单图G中必有两个顶点的度数相同。 用反证法,设G中各顶点的度数均不相同,则度数 列为0,1,2,…,n-1,说明图中有孤立顶点,这与有 n-1度顶点相矛盾(因为是简单图),所以必有两个顶 点的度数相同
第8章 图的基本概念 【例8.1.4】 证明在n（n≥2）个人的团体中，总有 两个人在此团体中恰好有相同个数的朋友。 解 以顶点代表人，二人如果是朋友，则在代表他 们的顶点间连上一条边，这样可得无向简单图G，每个 人的朋友数即图中代表它的顶点的度数，于是问题转 化为：n阶无向简单图G中必有两个顶点的度数相同。 用反证法，设G中各顶点的度数均不相同，则度数 列为0，1，2，…，n-1，说明图中有孤立顶点，这与有 n-1度顶点相矛盾（因为是简单图），所以必有两个顶 点的度数相同
第8章图的基本概念 2子图 在深入研究图的性质及图的局部性质时,子图的 概念是非常重要的。所谓子图,就是适当的去掉一些 顶点或一些边后所形成的图,子图的顶点集和边集是 原图的顶点集和边集的子集。 定义8.1.2设G=〈VE),G′=〈,E'〉均是图(同 为有向或无向)
第8章 图的基本概念 2.子图 在深入研究图的性质及图的局部性质时，子图的 概念是非常重要的。所谓子图，就是适当的去掉一些 顶点或一些边后所形成的图，子图的顶点集和边集是 原图的顶点集和边集的子集。 定义8.1.2 设G=〈V,E〉，G′=〈V′ ,E′〉均是图（同 为有向或无向）
第8章图的基本概念 (1)若VEE∈则称G是G的子图,记作GG。 ≤(2)若IV或E′E,则称G"是G的真子图,记作 (3)若W=,E"E,则称G是G的生成子图。 设G1=(V1,E1)是G的子图,若且W≠,E1由 端点均在V中的所有边组成,则称G1是由V导出的导 出子图,记作G[1]。若E1E且E1≠,V1由E1中 边所关联的所有顶点组成,则称G是由E1导的导出 子图,记作G[E1]
第8章 图的基本概念 （1）若V′V，E′E，则称G′是G的子图，记作G′G。 （2）若V′ V或E′ E，则称G′是G的真子图，记作 G′ G。 （3）若V′=V，E′E，则称G′是G的生成子图。 设G1 =〈V1 ,E1〉是G的子图，若V′V且V′≠ ，E1由 端点均在V1中的所有边组成，则称G1是由V1导出的导 出子图，记作G［V1］。若E1 E且E1≠ ，V1由E1中 边所关联的所有顶点组成，则称G1是由E1导出的导出 子图，记作G［E1］。