《图论》练习题201410VIP免费

《图论》练习题(2014)1、利用Dijkstra算法求下图中顶点到其它各顶点的距离，并写出到顶点的最短路。2、1、列出色数为的三个图：。2、阶完全图的色数为：。3、阶树的邻接多项式为：。4、阶完全图的邻接多项式为：。5、如下图所示的图的邻接矩阵为，关联矩阵为。6、度序列为的简单图是。7、是否存在度序列为，的简单图？若存在，给出一个图；若不存在，请说明理由。8、画出如下图的所有生成子图。1e1e5e6e3e7e4e2v2v4v5v3v6v1v1v2v3v49、设图如下图所示，求该图的生成树个数。10、已知图G（V、E），画出G－V5，G－v3v4，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、证明非平凡树的边连通度为。2e1e5e6e3e7e4e2v2v4v5v3v6v118、阶完全图的连通度为。19、设G是一个p阶图，且，则G连通图。20、若图G是不连通的，则其补图GC是连通的。21、证明：设是由和两个连通分支组成的图，则。22、证明：设是由和两个连通分支组成的图，则。23、证明：如果是连通图的一个割点，则不是的割点。24、证明：如果是不连通的，则是连通的。反之不成立，试举例说明。25、设图G为简单图且δ≥k，k∈/N，则G包含一条长为R的路。26、若G的最小度δ（G）≥2，则G中存在一条长度至少为δ（G）+1的圈。27、设图G（V、E）且|V|＝p，|E|＝q，则G为树当且仅当G为连通的且p＝q＋1。28、证明：图G为树当且仅当G的任意两个不同顶点之间存在唯一的一条路。29、画出全部非同构的6阶树。30、利用Cayley公式计算图G的生成树数目（写出演算过程）。G：31、下列图是否为Enler图？G1：G2：332、证明：为条边的阶树当且仅当不包含圈且。33、证明：设为条边的阶连通简单图且，则包含圈。34、证明：为树当且仅当的任意两个不同顶点之间存在唯一的一条路。35、证明：非平凡树的最长路的起点和终点均为悬挂点。36、证明：恰好有两个悬挂点的树是一条路。37、证明图G为非平面图。G：38、给出下图G的一个最大匹配（最大对集）。G：39、设图G有完美匹配，则G为偶数阶图。40、证明：路至多有一个完美匹配。41、证明：树至多有一个完美匹配。42、写出p（≥1）阶树T的色多项式，并确定T的色数。43、写出5个阶轮图W5的色多项式，并求χ（w5）W5：444、设G为任一偶图，则χ（G）≤2。45、证明：一个8×8方格棋盘移去其中两个对角上的1×1方格之后，不可能用1×2长方形恰好填满剩余棋盘。46、证明：非平凡连通偶图的色数为。47、证明圈的色数为或。48、证明：设为具有条边的阶极大平面图，则。49、证明：设为阶平面图，则其最小度。50、证明：Ramsey数。51、证明：Ramsey数。52.平面上有n个点，其中任意两个的距离至少为1。证明，这n个点中至多有3n对点，每对点的距离恰好是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即可得证。54.证明：在空间中，不可能有这样的多面体存在，它们有奇数个面，而它们的每个面又都有奇数条边。（北京，1956）证明：假设存在这样的多面体，将这多面体的面用顶点表示，当且仅当两个面有公共棱时，在相应的顶点间连一边，得图G。按题意，G有奇数个奇顶点。显然，这样的图不5存在，故这样的多面体是不存在的。55．平面上有n条线段，n≥3，其中任意3条都有公共点，则这n条线段有一个公共点。证:将这n条线段的端点看作一个图G的顶点，线段看...