资源描述：
《图论复习题 新 优质文档.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、优质文档最新《图论》复习题一、选择题1．设图G＝，vÎV，则下列结论成立的是(C)．A．deg(v)=2½E½B．deg(v)=½E½C．[PPT23]D．定理1图G=（V，E）中，所有点的次之和为边数的两倍2．设无向图G的邻接矩阵为则G的边数为(B)．A．6B．5C．4D．33、设完全图K有n个结点(n³2)，m条边，当（C）时，K中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数解释：K每个结点的度都为n－1，所以若存在欧拉回路则n－1必为偶数。n必为奇数。4．欧拉回路是（B）A.路径B.
2、简单回路[PPT40]C.既是基本回路也是简单回路D.既非基本回路也非简单回路5．哈密尔顿回路是（C）A.路径B.简单回路C.既是基本回路也是简单回路D.既非基本回路也非简单回路11优质文档[PPT40]：哈密尔顿回路要求走遍所有的点，即是基本回路的点不重复，也可以是简单回路的边不重复。6．设G是简单有向图，可达矩阵描述两点之间是否有路相连P(G)刻划下列关系中的是（C）A、点与边B、边与点C、点与点D、边与边7．下列哪一种图不一定是树（C）。A.无简单回路的连通图 B.有n个顶点n-1条边的连通图C.每对顶点间都
3、有通路的图 D.连通但删去一条边便不连通的图8．在有n个结点的连通图中，其边数（B）A.最多有n-1条B.至少有n-1条C.最多有n条D.至少有n条9．下列图为树的是（C）。A、B、C、D、10、下面的图7-22是（C）。A.完全图；B.平面图；C.哈密顿图；D.欧拉图。二、填空题1．无向完全图K6有15条边。[6×（6-1）]/2=152．设连通无向图G有k个奇顶点，要使G变成欧拉图，在G中至少要加k/2条边。解：∵任何图中的奇点的个数为偶数11优质文档∴在每对奇点处多加一条边形成了多重边，G图就成了欧拉图。∵连通
4、无向图G有k个奇顶点∴有k/2对奇顶点∴有多少对奇点就加多少条边3、n阶无向完全图Kn的边数是()，每个结点的度数是(n-1)。证明：∵1个顶点的图有0条边2个顶点的图有1条边∴满足当3个顶点以上时假如n=k-1k>=3时∵k-1个顶点的图有条边k个顶点的图有条边∴k-1个顶点的图与k个顶点的图产生的边数为而又∵k-1个顶点的图的边数加上这条边k-1恰好为∴当n=k时满足条件∴一个具有N个顶点的无向完全图的边数为4、n个结点的有向完全图边数是(n(n-1))，每个结点的度数是(2n-2)。解：仿用握手定理假设把每个顶
5、点看成一个人A点到B点相当于A主动向B伸手。每个点要与n-1个点握手。因为是有向的，所以A向B伸手和B向A伸手有区别。总共握手次数是n(n-1)所以总共边数是n(n-1)5、设有向图G=，的邻接矩阵11优质文档，则的入度=3，的出度=1，6、一棵无向树的顶点数为n，则其边数为n-1，其结点度数之和是2(n-1)。所有的次之和为边数的两倍7、一个无向图有生成树的充分必要条件是(此图为连通图)。8、设T=〈V,E〉是一棵树，若
6、V
7、>1，则T中至少存在(2)片树叶。9、任何连通无向图G至少有(1)棵生成树，当且
8、仅当G是(树)，G的生成树只有一棵。10、设T是一棵树，则T是一个连通且(无圈)的图。11、设无向图G有18条边且每个顶点的度数都是3，则图G有(12)个顶点。解：∵18条边的次之和为，且每个顶点的度数都是3∴顶点数为36/3=12。如图：12、任一有向图中，度数为奇数的结点有(偶数)个。[PPT23]13、一棵树有2个2度顶点，1个3度顶点，3个4度顶点，则其1度顶点为（9）。如图：11优质文档14、设G是由5个顶点组成的完全图，则从G中删去（6）条边可以得到树。解：∵5个顶点组成的完全图边数为又∵树有5个顶点∴树
9、的边数应为4∴完全图应删除10-4=6条边可以得到树。úúúúúúûùêêêêêêëé010101001000001110000010015、已知图G是相邻矩阵为则G的边数为（B）。A.5；B.4；C.6三、计算题1．设G=，V={v1，v2，v3，v4，v5}，E={(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5)}，试(1)给出G的图形表示；(2)写出其邻接矩阵；11优质文档(3)求出每个结点的度数；解：(1)(2)(3)、每个结点的度数分别为V1→1、V2
10、→2、V3→4、V4→3、V5→22．图G=，其中V={a,b,c,d,e}，E={(a,b),(a,c),(a,e),(b,d),(b,e),(c,e),(c,d),(d,e)}，对应边的权值依次为2、1、2、3、6、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．解：(1)(2)(3)
