高数-图论基础

第六章习题图论基础
6.1下列各组数中，那些能构成无向图的度数列？那些能构成无向简单图的度数列？
（1）1，1，1，2.3
(2)2, 2, 2, 2 , 2
(3)1,2,3,4,5
(4)1,3,3,3
6.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）21条边，3个4度顶点，其余的都是3度顶点.
（3）24条边，各顶点的度数是相同的.
6.6 35条边，每个顶点的度数至少为3的图最多有几个顶点?
6.7设n阶无向简单图中，（G）=n-1，问（G）应为多少？
6.8一个n（n２）阶无向简单图Ｇ中，ｎ为奇数，已知Ｇ中有ｒ各奇度顶点，问Ｇ的补图中有几个奇度顶点？
6.9设Ｄ是ｎ阶有向简单图，是Ｄ的子图，已知的边数＝ｎ（ｎ－１），问Ｄ的边数ｍ为多少？
6.10画出－－－的所有非同构的子图，其中有几个是子图？生成子图中有几个是连通图？
6.11设Ｇ为ｎ阶简单图（无向图或有向图），－－为Ｇ的补图，若Ｇ－－－－，则称Ｇ为自补图，――的生成子图中有几个非同构的自补图？
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-正则图有几种非同构的情况？
6.17．设n阶无向图为3-正则图，且边数m与n满足2n-3=m，问这样的无向图有几种非同构的情况？
6.18画出３阶有完全图所有非同构的子图，问其中有几个是生成子图？生成子图中有几个是自补图？
6.19设－－－－均为４阶无向简单图，他们均由两条边，他们能彼此均非同构吗？为什莫？
6.20已知ｎ阶无向图Ｇ中有ｍ条边，各顶点的度数均为３，又已知２ｎ－３＝ｍ，问在同构的意义下，Ｇ是唯一的吗？又若Ｇ为简单时，是否唯一？
6.22在－－的边上涂上红色或蓝色，证明对于任意一种随意的涂法，总存在红色――或蓝色――？
6.23试寻找３个４阶有向简单图－－－，使得－－强连通图；－－为单向连通图，但不是强连通图；而－－是弱连通图，但不是单向连通图，当然，更不是强连通图．
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=4k或n=4k+1，其中k为正整数。

6.28．设G是n阶无向简单图，n≥3且为奇数，证明G与中奇度顶点的个数相等。

6.29．已知在完全二部图K r,s中，r≤s.
(1)K r,s中含有多少种非同构的圈？
(2)K r,s中至多有多少个顶点彼此不相邻？
(3)K r,s中至多有多少条边彼此不相邻？
(4)K r,s的点连通度κ为几？边连通度λ为几？。