《第8章图的基本概念.docVIP

习题8 1. 给定下面两个图的集合表示，画出他们的图形表示。 , 其中， , 其中， 注：改为 解： 2. 先将下图中各图的顶点标定次序，然后写出各图的集合表示。 解：顶点标定如下： (1) 其中， (2) 其中， (3) 其中， 3. 写处下图中各图的度数列，对有向图还要写出出度列和入度列。 解：（1）4,2,2,2 （2）度数列：1,4,1,5,1；出度列：1，2，0，3，0；入度列：0，2，1，2，1 4. 设无向图中有6条边，3度与5度顶点各1各，其余的都是2度顶点，问该图有几个顶点？ 注：“各1各”改为“各1个”。 解：设该图有x个顶点，3×1+5×1+2×(x-1-1)=6×2，x=4 5. 画以（1，2，2，3）为度数列的简单图和非简单图各一个。 解： 6．证明在任何有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之和。 证明：设有向完全图有n个结点v1, v2,…, vn， 结点vi的入度为d-(vi)=n-1，出度为d+(vi)=n-1， 所有结点入度的平方之和为， 所有结点出度的平方之和为， 故所有结点入度的平方之和等于所有结点的出度平方之和。 7．写出下图相对于完全图的补图。 解： 8．证明下图中的两个图不同构。 证明：将图的顶点标定如下： 如果这两个图同构，那么对应结点的度数应相同。度数为3的两个结点v1与v1相对应。但与v1邻接的三个结点中一个结点v2度数为2，两个结点v3 ,v4度数为1，而与v1邻接的三个结点中有两个结点v2v3度数为2，一个结点v4度数为1，故他们不同构。 9．一个图如果同构于它的补图，则该图称为自补图。 1）试给出一个五个结点的自补图。 2）是否有三个结点或六个结点的自补图。 3）一个图是自补图，其对应的完全图的变数必为偶数。 注：3）中“变数”应为“边数”。 解： 1) 2)没有。由3），n(n-1)/2应为偶数，而n=3,6时，n(n-1)/2为奇数。 3）若n阶图G与其补图同构，G与的边数应相同，因此G与的总边数为偶数。而G与的总边数为对应的完全图的边数，即n(n-1)/2，故对应的完全图的边数为偶数。 10．证明简单图的最大度小于结点数。 证明：设简单图G有n个结点。对任一结点u，由于G没有环和平行边，u至多与其余n-1个结点中每一个有一条边相连接，即deg(u)≤n-1，因此，⊿(G)＝max deg(u)≤n-1。 11．在无向图G中，从结点u到结点v有一条长度为偶数的通路，从结点u到结点v有一条长度为奇数的通路，则在G中必有一条长度为奇数的回路。 证明：设从结点u到结点v长度为偶数的通路是ue1u1e2u2…e2kv，长度为奇数的通路是ue11u11e12u12…e12h-1v，那么路ue1u1e2u2…e2kve12h-1…u12e12u11e11u就是一条回路，它的边数＝2k+(2h-1)＝2(h+k)-1，是奇数，故这条回路的长度是奇数。 12．若无向图G中恰有两个奇数度的结点，则这两结点间必有一条路。 证明反证法G中的两个奇数度结点分别为u和v。假设u和v不连通，即它们之间无任何通路，则G至少有两个连通分支G1，G2，使得u和v分别属于G1和G2 (否则,它们之间必有)，于是G1和G2各含有一个奇数度结点。这与握手定理的推论矛盾（教材P136定理8.1.2）。因而u和v一定是连通的。 13．若图G是不连通的，则G的补图是连通的。 注：图G是无向图。 证明：若图G＝V，E是不连通的，可设图G的连通分支是G(V1)，G(V2)，…，G(Vm)(m≥2)。由于任意两个连通分支G(Vi)与G(Vj)(i≠j)之间不连通，因此两个结点子集Vi与Vj之间的所有连线都在图G的补图中。任取两个结点u和v，有两种情形： (1)u和v分别属于两个不同结点子集Vi与Vj。由上可知包含边(u,v)，故u和v在中是连通的。 (2)u和v属于同一个结点子集Vi。可在另一个结点子集Vj中取一个结点w，由上可知边(u,w)及边(v,w)均在中，故邻接边(u,w)和(v,w)组成的路连接结点u和v，即u和v在中也是连通的。 由此可知，当图G不是连通图时，必是连通图。 14. 设G是n阶自补图，证明n=4k或n=4k+1，其中k为正整数。 证明：由第9题3)，n(n-1)/2须是偶数。 (1)当n=4k时，n(n-1)/2=4k(4k-1)/2=2k(4k-1)为偶数； (2)当n=4k+1时，n(n-1)/2=(4k+1)4k/2=2k(4k+1)为偶数； (3)当n=4k+2时，n(n-1)/2=(4k+2)(4k+1)/2=(2k+1)(4k+1)为奇数；