浅议图论复习题

《浅议图论复习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅议图论复习题浅议图论复习题导读：任意一条边则不连通的图。3、5阶无向完全图的边数为（）。A．5B．10C．15D．204、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（）A．n/2B．n(n+1)C．nk-2mD．n(k+1)-2m5、设G=<V，E>为有向图，则有（）。A．E?VxVB．E?Vx图论复习题1、设G是由5个顶点构成的完全图，则从G中删去（）边可以得到树。A．6B．5C．8D．42、下面哪几种图不一定是树（）。A．无回路的连通图B．有n个结点，n-1条边的连通图C．对

2、每对结点间都有通路的图D．连通但删去任意一条边则不连通的图。3、5阶无向完全图的边数为（）。A．5B．10C．15D．204、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（）A．n/2B．n(n+1)C．nk-2mD．n(k+1)-2m5、设G=<V，E>为有向图，则有（）。A．E?VxVB．E?VxVC．VxV?ED．VxV=E6、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（）。A．充分条件B．必要条件C．充分必要条件D．既不充分也不必要条件7、设G=<V，

3、E>为有向图，V={a,b,c,d,e,f}，E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是（）。A．强连通图B．单向连通图C．弱连通图D．不连通图8、无向图G中的边e是G的割边（桥）的充分必要条件是（）。A．e是重边B．e不是重边C．e不包含在G的任一简单回路中D．e不包含在G的某一简单回路中9、在有n个结点的连通图中，其边数（）A．最多有n-1条B．至少有n-1条B．C．最多有n条D．至少有n条10．设无向简单图的顶点个数为n，则该图最多有（）条边。

4、A．n-1B．n(n-1)/2C．n(n+1)/2D．n211．n个结点的完全有向图含有边的数目（）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）12．一个有n个结点的图，最少有（）个连通分量。A．0B．1C．n-1D．n13．一个有n个结点的图，最多有（）个连通分量。A．0B．1C．n-1D．n14．在一个无向图中，所有顶点的度数之和等于所有边数（）倍。A．1/2B．2C．1D．415．在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A．1/2B．2C．1D．416、连通图G是一棵树，当且仅当G中（）A．有些边不

5、是割边B．所有边都是割边C．无割边集D．每条边都不是割边17．4个顶点的完全图G，其不同构的生成树个数是（）。A．4B．3C．5D．618、下面四组数能构成无向图的度数列的有()。A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。19、图的邻接矩阵为()。?1??0?1??A、?1000??1??101??1?1101????000?；B、??1111??0??111??0?1111????111?；C、??1100??0??011??0?1101????000?；D、??1100??101

6、?101??000??。20、一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（）片树叶。A、3；B、4；C、5；D、621、设V＝{a,b,c,d},与V能构成强连通图的边集E＝()(A){<a,b>,<a,c>,<d,a>,<b,d>,<c,d>}(B){<a,d>,<b,a>,<b,c>,<b,d>,<d,c>}(C){<a,c>,<b,a>,<b,c&

7、gt;,<d,a>,<d,c>}(D){<a,d>,<b,a>,<b,d>,<c,d>,<d,c>}题1：已知图的结点集V={a,b,c,d}以及图G和图D的边集合分别为：E(G)={(a,a),(a,b),(b,c),(a,c)}E(D)={<a,b>,<a,c>,<c,d>,<c,a>,<c,b>}试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图？题2：设简单连通无向图G有12

8、条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．题3：设简单连通无向图G有9条边，G中有4个3度结点，