高数-图论基础.doc

《高数-图论基础.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第六章习题图论基础6.1下列各组数中，那些能构成无向图的度数列？那些能构成无向简单图的度数列？（1）1，1，1，2.3(2)2,2,2,2,2(3)1,2,3,4,5(4)1,3,3,36.2设有向简单图D的度数为2，2，3，3，入度列0，0，2，3，试求D的除度列。6.3设是4阶有向简单图，度数列为3，3，3，3.它的入度列9或出度列）能为1，1，1，1吗？6.4设()为一正整数序列，互不相同，问此序列能构成n阶无向图的度数列吗？为什么？6.5下面无向图中有几个顶点？（1）16条边，每个顶点都是2度顶点.（2

2、）21条边，3个4度顶点，其余的都是3度顶点.（3）24条边，各顶点的度数是相同的.6.635条边，每个顶点的度数至少为3的图最多有几个顶点?6.7设n阶无向简单图中，（G）=n-1，问（G）应为多少？6.8一个n（n　　２）阶无向简单图Ｇ中，ｎ为奇数，已知Ｇ中有ｒ各奇度顶点，问Ｇ的补图　中有几个奇度顶点？6.9设Ｄ是ｎ阶有向简单图，　是Ｄ的子图，已知的边数　　＝ｎ（ｎ－１），问Ｄ的边数ｍ为多少？6.10画出　－－－的所有非同构的子图，其中有几个是子图？生成子图中有几个是连通图？6.11设Ｇ为ｎ阶简单图（无向图

3、或有向图），－－为Ｇ的补图，若Ｇ－－－－，则称Ｇ为自补图，――的生成子图中有几个非同构的自补图？6.12．设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G中至少有几个顶点？在最少顶点的情况下，写出G的度数列、Δ(G)、δ(G).6.13．设n阶图G中有m条边，证明：δ(G)≤2m/n≤Δ(G).6.14．设无向图中有6条边，3度与5度顶点各一个，其余的都是2度顶点，问该图有几个顶点？6.15．证明空间中不可能存在有奇数个面且每个面都有奇数条棱的多面体。6.16．阶2-正则图有几种非同构的

4、情况？6.17．设n阶无向图为3-正则图，且边数m与n满足2n-3=m，问这样的无向图有几种非同构的情况？6.18画出３阶有完全图所有非同构的子图，问其中有几个是生成子图？生成子图中有几个是自补图？6.19设－－－－均为４阶无向简单图，他们均由两条边，他们能彼此均非同构吗？为什莫？6.20已知ｎ阶无向图Ｇ中有ｍ条边，各顶点的度数均为３，又已知２ｎ－３＝ｍ，问在同构的意义下，Ｇ是唯一的吗？又若Ｇ为简单时，是否唯一？6.22在－－的边上涂上红色或蓝色，证明对于任意一种随意的涂法，总存在红色――或蓝色　――？6.23

5、试寻找３个４阶有向简单图－－－，使得－－强连通图；－－为单向连通图，但不是强连通图；而－－是弱连通图，但不是单向连通图，当然，更不是强连通图．6.24设---和----分别为无向连通图G的点割集.G—----的连通图分支个数k一定为几？G-----l连通分支数也是定数吗？6.25有向图D如图7.19所示.求D中长度为4的通路总数，并指出其中有多少条是回路？又有几条是----到---的通路？6.26．现有3个4阶4条边的无向简单图G1,G2,G3,证明它们中至少有两个是同构的。6.27．设G是n阶自补图，证明n=

6、4k或n=4k+1，其中k为正整数。6.28．设G是n阶无向简单图，n≥3且为奇数，证明G与中奇度顶点的个数相等。6.29．已知在完全二部图Kr,s中，r≤s.(1)Kr,s中含有多少种非同构的圈？(2)Kr,s中至多有多少个顶点彼此不相邻？(3)Kr,s中至多有多少条边彼此不相邻？(4)Kr,s的点连通度κ为几？边连通度λ为几？