图论复习试题及答案

　　图论是数学的一个分支，它以图为研究对象。以下是由阳光网小编整理关于图论复习试题的内容，希望大家喜欢!

　　图论复习试题及答案

　　1、设G是一个哈密尔顿图，则G一定是( )。

　　(1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图

上海油压工作室 　　答：(4)(考察图的定义)

　　2、一个图的哈密尔顿路是一条通过图中( )的路。

　　答：所有结点一次且恰好一次

上海油压工作室 　　3、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。 答：以v为起点的边的条数， 以v为终点的边的条数

上海油压工作室 　　4、设G是一棵树，则G 的生成树有( )棵。

　　(1) 0 (2) 1 (3) 2 (4) 不能确定

　　答：1

　　5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 n(n?1)答：, n-1 2

上海油压工作室 　　6、一棵无向树的顶点数n与边数m关系是( )。

　　答：m=n-1

上海油压工作室 　　7、一个图的欧拉回路是一条通过图中( )的回路。

　　答：所有边一次且恰好一次

　　8、有n个结点的树，其结点度数之和是( )。

上海油压工作室 　　答：2n-2(结点度数的定义)

上海油压工作室 　　9、n个结点的有向完全图边数是( )，每个结点的度数是( )。 答：n(n-1),2n-2

　　10、一个无向图有生成树的充分必要条件是( )。

　　答：它是连通图

　　11、设G是一棵树，n,m分别表示顶点数和边数，则

　　(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

　　答：(3)

　　12、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 答：2

　　13、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。

上海油压工作室 　　答：1， 树

　　14、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:

上海油压工作室 　　(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。

　　答：(1)

上海油压工作室 　　15、设T是一棵树，则T是一个连通且( )图。

　　答：无简单回路

　　16、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。

　　(1) 10 (2) 4 (3) 8 (4) 16

　　答：(4)

上海油压工作室 　　17、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。

　　(1) 10 (2) 4 (3) 8 (4) 12

　　答：(4)

　　18、设图G=<V，E>，V={a，b，c，d，e}，E={<a,b>,<a,c>,<b,c>,<c,d>,<d,e>},则G是有向图还是无向图?

　　答：有向图

上海油压工作室 　　19、任一有向图中，度数为奇数的结点有( )个。

　　答：偶数

　　20、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成?

上海油压工作室 　　(1) 2 (2) 4 (3) 3 (4) 5

　　答：(3)

上海油压工作室 　　21、在有n个顶点的连通图中，其边数( )。

上海油压工作室 　　(1) 最多有n-1条 (2) 至少有n-1 条

　　(3) 最多有n条 (4) 至少有n 条

　　答：(2)

上海油压工作室 　　22、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为( )。

上海油压工作室 　　(1) 5 (2) 7 (3) 8 (4) 9

　　答：(4)

　　23、若一棵完全二元(叉)树有2n-1个顶点，则它( )片树叶。

　　(1) n (2) 2n (3) n-1 (4) 2

　　答：(1)

　　24、下列哪一种图不一定是树( )。

　　(1) 无简单回路的.连通图 (2) 有n个顶点n-1条边的连通图

　　(3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图 答：(3)

　　25、连通图G是一棵树当且仅当G中( )。

　　(1) 有些边是割边 (2) 每条边都是割边

上海油压工作室 　　(3) 所有边都不是割边 (4) 图中存在一条欧拉路径

　　答：(2)

下一页更多有关“图论复习试题及答案”的内容