《第八章图论剖析》由会员分享，可在线阅读，更多相关《第八章图论剖析（53页珍藏版）》请在金锄头文库上搜索。
1、第八章图论L名词解释1 .邻接点:2 .邻接边:3 .平行边:2.名词解释1 .零图2 .平凡图3 .简单图：.4 .多重图:3,填空：G是个无向图,、VV(G),结点v所关联边数，称之为().记作()。4,填空：G=是无向图，A(G)表示()，6(G)表示()。A(G)=(),5(G)=()(5 .简答题：无向图G=,所有结点度总和等于什么？为什么？6 .无向图中，奇数度的结点有多少个？为什么？7 .选择题：在一次集会中，与奇数个人握手的人数共有()个。供选择的答案：A：奇数：B：不能确定：C：偶数；D：不知道。8 .下面哪些数的序列不是一个图的结点度数序列？为什么？如果可能是一个图的结点度
2、数序列，请试画出它的图。哪些可能不是简单图的结点度序列?为什么？a)(123,4,5)b)(2,2,2,22)c)(12,3,2,4)d)(l,l,l,4)e)(l,2,2,4,5)9,.已知无向简单图G中，有10条边，4个3度结点，其余结点的度均小于或等于2。问G中至少有多少个结点?为什么？10 .无向图G中有16条边,每个结点都是2度结点。问G中有几个结点？为什么？11 .无向图G中有21条边，3个4度结点，其余都是3度结点.问G中有几个结点？为什么？12 .无向简单图G中有10条边，各个结点的度数相同。问G中有几个结点？为什么？答案唯一吗？如果唯一，说明理由.如果不唯一，请列出所有可能的
3、答案。13 .在具有n个结点的无向简单图G中，6(G)=n-l,问A(G)应为多少？为什么？14 .构造简单图G使之分别满足:1. k(G)=入(G)=6(G)2. k(G)=X(G)5(G)3. k(G)X(G)=5(G)15 .名词解释G=是有向图，vEV,1 .有向图结点v的出度：2 .有向图结点v的入度：3 .有向图结点v的度：16 .G=是一个有向图，则G的所有结点的出度之和与所有结点的入度之和有什么关系？为什么？17 .填空题：设G是有向简单图.其结点度数序列为(2,2,3,3),入度序列为(0.023)。求它的出度序列()。18 .什么叫无向完全图？有n个结点的无向完全图记作什么
4、？它有多少条边？19 .有n个结点的无向完全图Kn有多少条边？为什么？20什么叫有向简单完全图？有n个结点的有向简单完全图它有多少条边？为什么？21.什么叫有向完全图？有n个结点的有向完全图它有多少条边？为什么？22.证明任何有向简单完全图中，所有结点的入度平方之和等于所有结点出度平方之和。23 .设G是个具有n个结点的有向简单图。G是G的子图，且G中边，m，=n(nl)o问G中边数m为多少？要求有解题过程。24 .什么叫生成子图(支撑子图)？25 .什么叫图G的补图？26 .给定G如下图所示,求G的补图.27 .画出下面图G的补图28 .设G是个有n个结点的简单图，n是个大于2的奇数，如果G
5、中有k个奇数度的结点，那么G的补图G中有奇数度的结点也是k个。此说法正确吗?为什么?29 .什么叫做图的同构？30 .填空：图之间的同构关系三满足（）性质，是（）关系。31 .指出下面各个图中哪些是彼此同构的.口殳0了abcdefghij32 .给定图的集合G=A.B,C.D.EEH.K.M.N.RST,V.W.X,Y,其中各个图如下，三是G中图的同构关系，求商集G/三。ABDEFHKMNRSTWVXY33 .具有1、2、3个结点的简单图各有多少种不同构的形式？试画出这些图形。34 .具有4个结点的简单图各有多少种不同构的形式？试画出这些图形。35 .画出K的所有不同构的生成子图。36 .什么
6、叫做自补图？37 .多于两个而少于或等于6个结点的简单图中，哪些图可能是自补图？对不是自补图的要说明原因。对有自补图的，要画出所有可能的自补图。38 .下面哪些图同构？（只标出结点之间的对应关系即可.）39 .下面哪些图同构？（只标出结点之间的对应关系即可.）(a)(b)(d)40 .给定图G=,G中vu到Vn的路是任何定义的？什么是路的长度？41 .名词解释：回路:42 .名词解释：1 .迹2 .闭迹43名词解释:1 .通路2 .圈44.请回答“什么是无向图的连通分支？什么叫做连通分支数？G的连通分支数用什么表示？”45.什么叫做无向连通图？47 .证明如果图G是不连通的，则它的补图3是连通
7、的.48 .说明：什么叫做点割集？什么叫做割点?49 .什么叫做点连通度？用什么符号表示点连通度？它表示什么含义？50 .说明：什么叫做边割集？什么叫做割边？割边也称之为什么？51 .说明：什么叫做边连通度？用什么符号表示？它表示什么含义?52 .填空：在有向图中，从u到v可达定义为()。53 .在有向图中，从u到v的距离是任何定义的？用什么符号表示?54 .填空：下而是讲述有向图结点的可达性时的几个结论，请在括号内填入适当的符号。可达性的性质：(u,v,w是有向图中的结点。)1) d()2) d=()o3) d+d()d4)如果从u到v不可达，则d=()o5)如从u可达v,从v也可达u,d(
8、)do55 .给定有向图如下：在这个图中找出分别满足下面结论的结点。1) d+ddo2)从u到v不可达,则d=o3)如从u可达v,从v也可达u,d不一定等于do56 .有向图G的直径是如何定义的？下而的有向图的直径是多少？为什么？57 .名词解释：1 .强连通2 .单侧连通3 .弱连通58 .下面给出三个有向图，分别说出它们是哪种连通图，并说明原因.59 .求下面有向图G的强分图,单侧分图和弱分图。60 .求下面有向图G的强分图,单侧分图和弱分图。61 .给出有向图如图所示，分别指出它的强分图、单侧分图和弱分图。62 .证明有向图中,每个结点必位于一个且只位于一个强分图中。63从无向图的邻接矩
9、阵能看出该图哪些特征?64.从有向图的邻接矩阵能看出该图哪些特征?65.给定无向图G如下图所示：1 .写出G的邻接矩阵A。2 .求A的平方AZ3 .在矩阵中的第3行，第4列元素为多少？对于这个数字在G的图上你能做何解释？对你的解释在图上明确表示出来。G66 .设GXV,E是简单图，令V=vl,v2,v3,vn,G的邻接矩阵的k次方(A(G)”中的第i行第j列元素叫对此你在G的图上做何解释。67 .求下面图的邻接矩阵，可达矩阵和距离矩阵。V4OV468 .设G=GE是无环的无向图,且V=vi,V2,v，,Vm,E=ei,e3,en,无向图G的完全关联矩阵是如何写出的？69 .求下而无向图的完全关
10、联矩阵。70 .从无向图关联矩阵能够看到图的哪些特征？如何看出这些特征？71 .设G=vV,E是个简单有向图,且V=w,V2,V3,Mn,E=ehe2,e3,.,en),G的完全关联矩阵是如何写出的？72 .求下面有向图的完全关联矩阵。73 .从有向图关联矩阵能够看到图的哪些特征？如何看出这些特征？74 .名词解释1 .欧拉路:2 .欧拉回路：3 .欧拉图:乃,有欧拉路的判定：76 .无向图G具有欧拉回路,的判定77 .构造一个欧拉图，使得结点数v和边数e满足:a）v,e奇偶性一样.b）v,e奇偶性相反.78 .n取何值时,完全图Kn是个欧拉图?79 .名词解释1 .汉密尔顿路：2 .汉密尔顿
11、回路（H回路）:3 .汉密尔顿图（H图）：80 .a）画一个有一条欧拉回路和一条汉密尔顿回路的图。b）画一个有一条欧拉回路但没有一条汉密尔顿回路的图。c）画一个没有一条欧拉回路但有一条汉密尔顿回路的图。81 .首先判断下面命题的正误，然后说明原因，“不是所有完全图Kn都是欧拉图，但是所以完全图Kn都是汉密尔顿图J82 .填空：这是判定一个图有汉密尔顿路和汉密尔顿回路的定理。“设G是有n个结点的简单无向图，若G中每对结点度数之和大于或等于()，则G有一条汉密尔顿路。若G中每对结点度数之和大于或等于()，则G有一条汉密尔顿回路。”83 .填空：这是判定一个图有汉密尔顿回路的必要条件定理，“若图G=
12、有H回路，则对V的任何非空子有限集S.均有W(G-S)W(),其中W(G-S)是从G中删去S中所有结点及与这些结点关联的边所得到的子图的连通分支数。84 .“若图G=有H回路,则对V的任何非空子有限集S.均有W(GS)WISI,其中W(G-S)是从G中删去S中所有结点及与这些结点关联的边所得到的子图的连通分支数J用此定理判断下面图G不是H佟I。85 .今有a,b,c,d,e,f,g七个人，已知下列事实：a:会讲英语。b:会讲英语和汉语。c:会讲英语、意大利语和俄语。d:会讲日语和汉语。e:会讲德语和意大利语。f:会讲法语、日语和俄语。g:会讲法语和德语。试问能否将这七个人适当安排座位，使得每个
13、人都能与他两边的人直接交谈？如果能,请给予安排；如果不能，说明原因.(用图论的理论求解,)86 .给定图G如图所示，G是欧拉图还是汉米尔顿图，若是请写出一条相应的回路。如果不是，请说明理由。87 .什么叫做平面图？什么叫做一个图是可以平面化的？88 .说明:必和K3.3不是平而图。89 .名词解释1 .平面图的面2 .而的边界3 .而的次数90 .平面图的而分有限而与无限面，请问无限而的边界是由无数条边围成的吗？为什么？答91 .给定平面图如下，求各个面的边界，以及各个而的次数。92 .请说明欧拉公式。93 .说明叫做-在2度结点内同构（同胚）。94 .请画出两个图，使得它们不同构，但在2度结
14、点内同构。95 .请说出判定一个平面图的充分且必要条件，即Kuratowski（库拉托斯基）定理。96,用Kuratowski（库拉托斯基）定理说明下而彼得森（Petersen）图不是平而图。97 .证明：在6个结点12条边的连通平面简单图中，每个而由3条边围成.98 .证明：若G是每一个而至少由k(k23)条边围成的连通平而图，则c&P这里v;e分别是G的结点数和边数“99,给定定理：若G是每一个而至少由k(k23)条边围成的连通平而图，则，这里v.e分别是G的结点数和边数。用此定理说明Ks和K3.3不是平而100 .如果可能，把下而画成平而图，否则说明它包含一个与Ks或K3.3在2度结点内同构子图。101 .证明a)对于Ks中任何边e.K5-e是平面图。b)对于K3.3中任何边e,K3,3-e是平面图。102 .证明小于30条边的平面简单图G有一个结点度数小于等于4。103 .设G是个有n(n22)个连通分支的平面图，则G的结点数v,边数e,以及而数r之间是什么关系？并给予证明之。104 .填空：共5个空白，括号内分别标有1,2,3,4,5o下面是对偶图(偶图)的定义：给定平面图
