《图论》练习题201410

《《图论》练习题201410》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《图论》练习题(2014)1、利用Dijkstra算法求下图中顶点到其它各顶点的距离，并写出到顶点的最短路。2、1、列出色数为的三个图：。2、阶完全图的色数为：。3、阶树的邻接多项式为：。4、阶完全图的邻接多项式为：。5、如下图所示的图的邻接矩阵为　　　　　　　　　　，关联矩阵为　　　　　　　　。6、度序列为的简单图是　　　　　　　　　　　　。7、是否存在度序列为，的简单图？若存在，给出一个图；若不存在，请说明理由。8、画出如下图的所有生成子图。9、设图如下图所示，求该图的生成树个数。610、已知图G（V、E），画出G－V5，G－v3

2、v4，G[{v2，v3，v5}]，G[{v3v4，v4，v6，v7v8}]G：11、已知图G的邻接矩阵，画出G，并求出度序列。12、证明：偶图G的任意子图H仍为偶图。13、证明：设图G（V、E）的度序列为（），边数为q，则14、证明：在任何图中，奇顶点个数为偶数。15、证明：整数序列（6，6，5，4，3，3，1）不可能为一个简单图的图序列。16、证明顶点度数均为的简单连通图是圈。17、证明非平凡树的边连通度为。18、阶完全图的连通度为。19、设G是一个p阶图，且，则G连通图。20、若图G是不连通的，则其补图GC是连通的。621、证明：

3、设是由和两个连通分支组成的图，则。22、证明：设是由和两个连通分支组成的图，则。23、证明：如果是连通图的一个割点，则不是的割点。24、证明：如果是不连通的，则是连通的。反之不成立，试举例说明。25、设图G为简单图且δ≥k，k∈/N，则G包含一条长为R的路。26、若G的最小度δ（G）≥2，则G中存在一条长度至少为δ（G）+1的圈。27、设图G（V、E）且

4、V

5、＝p，

6、E

7、＝q，则G为树当且仅当G为连通的且p＝q＋1。28、证明：图G为树当且仅当G的任意两个不同顶点之间存在唯一的一条路。29、画出全部非同构的6阶树。30、利用Cayle

8、y公式计算图G的生成树数目（写出演算过程）。G：31、下列图是否为Enler图？G1：G2：32、证明：为条边的阶树当且仅当不包含圈且。33、证明：设为条边的阶连通简单图且，则包含圈。34、证明：为树当且仅当的任意两个不同顶点之间存在唯一的一条路。635、证明：非平凡树的最长路的起点和终点均为悬挂点。36、证明：恰好有两个悬挂点的树是一条路。37、证明图G为非平面图。G：38、给出下图G的一个最大匹配（最大对集）。G：39、设图G有完美匹配，则G为偶数阶图。40、证明：路至多有一个完美匹配。41、证明：树至多有一个完美匹配。42、写出

9、p（≥1）阶树T的色多项式，并确定T的色数。43、写出5个阶轮图W5的色多项式，并求χ（w5）W5：44、设G为任一偶图，则χ（G）≤2。45、证明：一个8×8方格棋盘移去其中两个对角上的1×1方格之后，不可能用1×2长方形恰好填满剩余棋盘。646、证明：非平凡连通偶图的色数为。47、证明圈的色数为或。48、证明：设为具有条边的阶极大平面图，则。49、证明：设为阶平面图，则其最小度。50、证明：Ramsey数。51、证明：Ramsey数。52.平面上有n个点，其中任意两个的距离至少为1。证明，这n个点中至多有3n对点，每对点的距离恰好

10、是1。证:将n个点看成是图G的n个顶点，若两点的距离为1，则该两个顶点相邻（有连边）。平面上和点v距离为1的点就是图G中和顶点v相邻的顶点。由于平面上和点v距离为1的点的个数至多为6，所以图G中顶点v的度数满足d(v)≦6.从而图G中的边数q(G)≦3n(As2q(G)=∑d(v)≤6n)。即平面上这n个点中至多有3n对点，每对点的距离恰好是1。53.试证明：在任何一群人中，认识这群人中奇数个人的人有偶数个。（匈牙利，1942）证明：把每个人用顶点表示，若两人认识，则它们之间有边相连，故认识这群人中奇数个人的顶点度数为奇数，由推论1即

11、可得证。54.证明：在空间中，不可能有这样的多面体存在，它们有奇数个面，而它们的每个面又都有奇数条边。（北京，1956）证明：假设存在这样的多面体，将这多面体的面用顶点表示，当且仅当两个面有公共棱时，在相应的顶点间连一边，得图G。按题意，G有奇数个奇顶点。显然，这样的图不存在，故这样的多面体是不存在的。55．平面上有n条线段，n≥3，其中任意3条都有公共点，则这n条线段有一个公共点。证:将这n条线段的端点看作一个图G的顶点，线段看作G的边，依题意，G是无圈的连通图，且最长的路的长度是2，所以G是星图（如图5所示），即这n条线段有一个公

12、共点。56.某工厂有六种颜色的纱，用来生产双色布，每种双色布用两种颜色搭配织成。在生产过程中，每种颜色的纱至少各其他三种颜色的纱搭配。证明，可以选出三种不同的双色布，它们包含所有六种颜色的纱。（匈牙利数学竞赛题）6证:先