图论与组合数学试卷a-2014年

《图论与组合数学试卷a-2014年》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、湘潭大学2014年上学期2013级《图论与组合数学》课程考试试卷（A卷）适用年级专业2013级计算机科学与技术考试方式闭卷考试时间120分钟题号—•二二四五/、七八总分阅卷教师得分学号姓名得分一、单项选择题（每小题2分，共20分,）学院信息工程学院专业计算机科学与技术班级1、2、3班澈联1、设（7（/?，为无向图，/?=6，^=16。于是，（7是（）。A.完全图；B.零图；C.简单图；D.伪图。2、四阶完全图'的所有非同构的生成子图中，有（）个由3条边组成的生成子图。A.1;B.2;C.3;D.4.o3、设为简单连通无向图，要确定G的

2、一棵生成树，则必须刪去。中（）条边。A.p—c[—\B.cj—pC.q-p—D.p—q+I。4、设简单无向图G是一个有6个顶点的3—正则图，则。有（）条边。A.3;B.6;C.9;D.12o5、设简单无向图G=是二分图，则G中（）奇回路。A.一包含；B.一^不包含；C.不一包含。6、设简单无向图G（p,q）是一个奇回路（p^3）,则G的点色数x（G）与其最大度A（G）的关系为（）。A.z（G）=A（G）+l;B.Z（G）=A（G）;C.z（G）=A（G）-k7、设H是p阶完全图Kp的真子图，于是当H是G的任意的（）时

3、，H仍是完全图。A.生成子图；B.点导出子图；C.边导出子图。8、设G（p,q）是简单连通无向图（q〉p）,于是可以去掉0的（）条边，得到恰含一个回路的连通生成子图。A.q-p;B.q-p+1;C.q-p+2;D.q-p+3o9、设G（p,q）和H（p’，q’）是无向标定图，G与H同构，于是（）必成立。A.V（G）=V（H）;B.E（G）=E（H）;C.p=p’或者q=q’；D.p=plq=q’。10、一个简单无向图G（p,q）共有（）个不同的定向图。得分A.p;B.2";C.2q;D.qo二、填空题（每空格2分，共20分）1、设G是

4、二分图，于是，其边色数x’（G）=。2、若平面图G的对偶图G*有环，则G有。3、设无向图G有9个顶点。若顶点的度数分别为0，1，3,4,4,5,5,5,7，则G有条边。4、若简单无向图G有7个顶点，n条边，则G的补图G有个顶点，有条边。5、若连通平面图G有4个顶点，3个面，则G有条边。6、若平面图G有/）个顶点，g条边及r个面，则G的对偶图G*有_个顶点，_个面。7、若无向图r是一棵有p个顶点的树，则r有条边。得分8、一个有限平面图G的每个面的次数之和S与G的边数<7之间的关系为。三、判断题（每题2分，共20分。正确的请在括号内打“V

5、”，否则打“X”）1、设D是简单有向图，于是，D的基础图G必是简单无向图。（）2、p（〉l）个顶点的树必是二分图。（）3、设G是有个顶点，厂-1条边的简单无向图，则G是树。（）4、任何树r至少有两个度为1的顶点。（）5、若简单图G的每条边都是割边，则（7必为树。（）6、设G（p,q）和G’（p’，q’）是无向标定图。若G与G’同构，则必有V（G）=V（G’）。（）7、若无向连通图G存在割边，则G必存在割点。（）8、设v是无向图G的顶点。若点色数x（G-v）^（G>l，则v是临界点。（）9、树r中任何两个顶点之间恰有一条通路。（）10、

6、任何一个简单无向图中，度数为偶数的顶点数目必为偶数。（）得分四、计算题（每小题5分，共20分）1、试求出下图关于顶点着色的色多项式/G，z）。2、试用Dijkstra算法计算出下面赋权图中顶点1到其它各顶点i的最短通路长度3、由数字1，2,3,4,5构成一个3位数请计算满足下列条件的数各有多少?(1)6/是一个偶数；(2)6/可以被5整除；(3)a>300.4、试计算：在由7个数字位组成的三进制序列中,0、1和2都出现的数字共有多少?五、证明题（每小题10分，共20分）1、设G（p，（y）是简单二分图。求证：q

7、简单无向图。证明：若图G不连通，则其补图G必连通。