南京信息工程大学-2011-2012-图论复习题(中文)(共7页).doc

精选优质文档-倾情为你奉上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) 不能确定答：15、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。答：, n-16、一棵无向树的顶点数n与边数m关系是()。答：m=n-17、一个图的欧拉回路是一条通过图中( )的回路。答：所有边一次且恰好一次8、有n个结点的树，其结点度数之和是()。答：2n-2（结点度数的定义）9、n个结点的有向完全图边数是(