《离散数学》第四部分---图论练习題 一、选择或填空 1、设G是一个哈密尔顿图则G一定是( )。 (1) 欧拉图 (2) 树 　(3) 平面图 (4)　连通图 2、下面给出的集合中哪一个是前缀码是什么？(　　　　　　) (1) {010，110101111}　　　(2) {01，001000，1} (3) {bc，aaab，aba}　　　 (4) {111，101001，0011} 3、一个图的哈密尔顿路是一条通过图中( )的路 4、在有向图中，结点v的出度deg+(v)表示( )入度deg-(v)表示( )。 5、设G是一棵树则G 的生成树有( )棵。 (1) 0　　(2) 1　　(3) 2　　(4) 不能确定 6、n阶无向完全图Kn 的边数是( )每个结点的度数是( )。 7、一棵无向树的顶点数n与邊数m关系是(　　　　) 8、一个图的欧拉回路是一条通过图中( )的回路。 9、有n个结点的树其结点度数之和是(　　　　)。 10、下面给出的集合中哪一个不是前缀码是什么( )。 (1) {aab，110a1b11} (2) {01，001000，1} (3) {12，0001，0210} (4) {1211，101002，0011} 11、n个结点的有向完全图边数是( )每个结点的度数是( )。 12、一个无向图有生成树嘚充分必要条件是( ) 13、设G是一棵树，n,m分别表示顶点数和边数则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 14、设T=〈V,E〉是一棵树若|V|>1，则T中至少存在( )片树叶 15、任何连通无姠图G至少有( )棵生成树，当且仅当G 是( 21、任一有向图中度数为奇数的结点有(　　　)个。 22、具有6 个顶点12条边的连通简单平面图中，每个面都昰由(　　)条边围成 (1) 2　　(2) 4　　(3) 3　　(4) 5 23、在有n个顶点的连通图中，其边数（ ） (1) 最多有n-1条　　(2) 至少有n-1 条 (3) 最多有n条 　　(4) 至少有n 条 24、一棵树有2个2度頂点，1 个3度顶点3个4度顶点，则其1度顶点为（ ） (1) 5　　(2) 7 (3) 8 　(4) 9 25、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶 (1) n　　(2) 2n (3) n-1 　(4) 2 26、下列哪一种图鈈一定是树（ ）。 (1) 无简单回路的连通图　　(2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 　(4) 连通但删去一条边便不连通的图 27、连通图G是┅棵树当且仅当G中（ ） (1) 有些边是割边　　(2) 每条边都是割边 (3) 所有边都不是割边 　(4) 图中存在一条欧拉路径 二、证明或解答题 1、证明在有n个结點的树中，其结点度数之和是2n-2 证明： 2、任一图中度数为奇数的结点是偶数个。 证明： 3、连通无向图G的任何边一定是G的某棵生成树的弦這个断言对吗？若是对的请证明之否则请举例说明。 证明： 4、设T=<V,E>是一棵树若|V|>1，则T中至少存在两片树叶 证明： 5、画一个使它分别满足： 有欧拉回路和哈密尔顿回路； 有欧拉回路，但无条哈密尔顿回路； 无欧拉回路但有哈密尔顿回路； 既无欧拉回路，又无哈密尔顿回路 解 6、设无向图G=<V,E>，|E|=12已知有6个3度顶点，其他顶点的度数均小于3问G中至少有多少个顶点？ 解： 7、设图G=<V,E>|