图论第二次作业 电子科技大学
图论第二次作业
一、第四章
4.3（1）画一个有Euler 闭迹和Hamilton 圈的图； （2）画一个有Euler 闭迹但没有Hamilton 圈的图； （3）画一个有Hamilton 圈但没有Euler 闭迹的图； （4）画一个既没有Euler 闭迹也没有Hamilton 圈的图； 解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下：
（2）一个有Euler 闭迹但没有Hamilton 圈的图形如下：
（3）一个有Hamilton 圈但没有Euler 闭迹的图形如下：
（4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下：
4.7证明：若G 没有奇点，则存在边不重的圈C 1,C 1,....,C m ,使得E(G)=E(C 1) E(C 2) ..... E(C m )。
证明：将G 中孤立点除去后的图记为G 1,则G 1也没有奇点，且δ(G 1)≥2，则G 1含圈C 1，在去掉G 1-E(C 1)的孤立点后，得图G 2，显然G 2仍无奇度点，且(G 2)≥2，从而G 2含圈C 2，
如此重复下去，直到圈C m ，且G m -E(C m )全为孤立点为止，于是得到E(G) E(C 1) E(C 2) ... E(C m )。
4.10证明：若
（1）G 不是二连通图，或者
（2）G 是具有二分类(X,Y)的偶图，这里|X|≠|Y|， 则G 是非Hamilton 图。
证明：（1）因为G 不是二连通图，则G 不连通或者存在割点V ，有w(GV)2，由相关定理得：若G 是Hamilton 图，则对于V(G)的任意非空顶点集S ，有：w(GS)S ，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。
（2）因为G 是具有二分类(X,Y)的偶图，又因为|X|≠|Y|，在这里假设|X|≠|Y|，则有w(G-X)=Y>X ，也就是说：对于V(G)的非空顶点集S ，有：w(G-S)>S 成立，则可以得出G 是非Hamilton 图。
4.12设G 是有度序列(d1,d2,...,dn)的非平凡简单图，这里d 1≤d 2≤...≤d n ，证明：若不存在小于(n+1)/2的正整数m ，使得d m 证明：在G 之外加上一个新点V ，把它和G 的其余各点连接，得图G1： G1的度序列为：(d 1+1,d 2+1...d n+1,n)，由已知：不存在小于(n1)/2的正整数m ，使得d m +1 ≤m 且d n-m+1 于是由度序列判定定理知：G1是Hamilton 路，则G 有Hamliton 路。 二、第五章作业 5.1（1）证明：每个k 方体都有完美匹配（k ≥2）; （2）求K 2n 和K n,n 中不同的完美匹配的个数。 证明：（1）证明每个k 方体都是k 正则偶图即可。事实上，由k 方体的构造：k 方体有2k 个顶点，每个顶点可以用长度为k 的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。如果我们划分k 方体的2k 个顶点，把坐标之和为偶数的顶点归入X ，其余归入Y 。显然，X 中顶点互不邻接，Y 中顶点也如此。所以k 方体是偶图。又不难知道k 方体的每个顶点度数为k ，所以k 方体是k 正则偶图。由推论得：k 方体存在完美匹配。 解：（2）利用归纳法求K 2n 和K n,n 中不同的完美匹配的个数。K 2n 的任意一个顶点有2n-1中不同的方法被匹配。所以K 2n 的不同完美匹配个数等于(2n-1)K 2n-2，如此递推下去，可以归纳出K 2n 的不同完美匹配个数为：(2n-1)!!；利用同样的方法可归纳出Kn,n 的不同完美匹配个数为：n!。 5.2证明：一棵树最多只有一个完美匹配。 证明：若不然，设M1和M2是树T 的两个不同的完美匹配，那么M1?M ≠2，容易知道：T[M1?M2]每个非空部分顶点度数为2，即它存在圈，于是推出T 中有圈，矛盾。所以一棵树最多只有一个完美匹配。 5.6证明：K2n 的1-因子分解的数目为(2n)!/2n n!。 证明：由结论知：K 2n 不同完美匹配的个数为(2n-1)!!。所以，K2n 的1-因子分解 数目为(2n-1)!!个。即：(2n-1)!!=(2n)!/2n n! 5.7将K 9表示为四个生成圈之和。 解：K 4n+1=K 2(2n)+1，所以，可以分解成2n 个边不重的2因子之和。而K 9=K 2*4+1。 所以K 9可以表示为四个边不重的2因子之和，对于每个分解出的因子的路径为： P i =V i V i-1+V i +1V i -2+V i +2V i-3...V in V in 则K 9的四条路径为： P 1=V 1V 8V 2V 7V 3V 6V 4V 5 P 2=V 2V 1V 3V 8V 4V 7V 5V 6 P 3=V 3V 2V 4V 1V 5V 8V 6V 7 P 4=V 4V 3V 5V 2V 6V 1V 7V 8 则生成圈Hi 是V 2n+1与Pi 的两个端点连线生成的。所以可将K9表示为四个生成圈之和。 5.13所谓n ×n 矩阵的一条对角线是指两两不同行不同列的n 个矩阵元素组成的集。对角线的权是指它的n 个元素的和。找出下列矩阵具有最小权的对角线： ??????? ?????????8 9 7 5 47 10 13 6 66 9 12 5 84 7 5 6 711 10 8 5 4 解：首先从第一行第一列开始，找出矩阵中的最小元素，发现为坐标是(1,1)的4， 将其所在的行和列删除，得到的矩阵为 ????? ???????4 7 5 66 9 12 57 10 13 68 9 7 5 再从此矩阵的第一行第一列开始，找出矩阵中的最小元素，发现为原坐标是(2,5)的4。依次类推，继续得到坐标是(3,2)的5，(5,3)的7，(4,4)的10。所以最小权为：4+4+5+7+10=30。 5.19证明:对n ≥1,K 4n+1有一个4-因子分解。 证明:K4n+1=K2(2n)+1所以，可以分解为2n 个边不重的2因子之和。而任意2个2因子可以并成一个4因子。所以，共可以并成n 个4因子。即K 4n+1可以分解为n 个4因子的和。 电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D 6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G 离散数学作业5 离散数学图论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {}f {}c e ,． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结点 ． 5．设G= 第四章 3(1).有欧拉闭迹和H圈 (2).有欧拉闭迹但没有H圈 (3).有H圈无欧拉闭迹 (4).无欧拉闭迹且没有H圈 4：证：若G不是H图，由chvatal定理知，G度弱于某个图，故： = 这与题目已知条件相矛盾，故G是H图。 8：证：不失一般性，设G是连通图，是G的2k个奇点，连接，得到，则得到图，则是欧拉图，设C是中 的欧拉闭迹，删除C中的，即可得到k条边不重复的迹，使得 . 10(1)若G不是二连通图，那么G不连通或者有割点u，则w，故G是 非H图。 (2). 若G是具有二分类的偶图，且，若假设则，故 G是非H图。 11：设R是G中的H路，则对于每个真子集S，有w，又： w w，故w. 12：设u是G外一点，将u和G中的每个点连接得到图，则G的度序列为 ，故有题意知，不存在小于的正整数m，使得 ，故由Chvatal定理知，图是H图，则G有 H路。 15：(1)由图的闭包定义可知，构作一个图的闭包，可以通过不断在度和大于等于n的非邻接顶点加边得到。故图的闭包算法如下： 第一步：令； 第二步：在中求顶点，使得： 第三步：如果,则转到第四步；否则，停止，则可得到G 的闭包。 第四步：令，转到第二步。 复杂性分析：由其算法我们可得出其总运算量为： 故该算法能够在多项式时间内被解决，故该算法是一个好算法。 (2).设计算法如下： 第一步：在闭包构造中，将加入的边依次加入次序记为 ，在中任意取出一个H圈，令k=N; 第二步：若不在中，令；否则转到第三步。 第三步：设，令；求中两个相邻点u和v使得， u，v依序排列在上，且有：，令： 第四步：若k=1，转到第五步；否则，令k=k-1,转第二步； 第五步：停止。为G的H圈。 算法的复杂性分析：因为该算法进行了N次循环，每次循环中找到满足要求的邻接顶点u和v至多需要n-3次判断，所以总的运算量：N(n-3)。是一个好算法。 第五章 1：(1)证：k方体有2k个顶点，每个顶点可以用长度为k的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。 若划分k方体的2k个顶点，把坐标之和为偶数的顶点归入X，否则归入Y。显然，X中顶点互不邻接，Y中顶点也如此。所以k方体是偶图。又k方体的每个顶点度数为k,所以k方体是k正则偶图。所以由推论可知：k方体存在完美匹配。 (2).解K 2n 的任意一个顶点有2n-1中不同的方法被匹配。所以K 2n 的不同完美匹 配个数等于(2n-1)K 2n-2,如此推下去，可以归纳出K 2n 的不同完美匹配个数为： (2n-1)!!。同理，K n, n 的不同完美匹配个数为：(n)!。 2：若不然，设M 1与M 2 是树T的两个不同的完美匹配，那么M 1 ΔM 2 ≠Φ,且T[M 1 ΔM 2 ] 每个顶点度数为2，即它存在圈，于是推出T中有圈，矛盾。故一棵树中最多只有一个完美匹配。 7：解：设 作如下四条路： 故其四个生成圈如下： 电子科技大学二零零六至二零零七学年第一学期期末考试半导体物理课程考试题卷（ 120分钟）考试形式：闭卷考试日期200 7年 1 月 14日 注：1、本试卷满分70分，平时成绩满分15分，实验成绩满分15分； 2.、本课程总成绩=试卷分数+平时成绩+实验成绩。 课程成绩构成：平时分，期中分，实验分，期末分 一、选择填空（含多选题）（2×20=40分） 1、锗的晶格结构和能带结构分别是（ C ）。 A. 金刚石型和直接禁带型 B. 闪锌矿型和直接禁带型 C. 金刚石型和间接禁带型 D. 闪锌矿型和间接禁带型 2、简并半导体是指（ A ）的半导体。 A、(E C -E F )或(E F -E V )≤0 B、(E C -E F )或(E F -E V )≥0 C、能使用玻耳兹曼近似计算载流子浓度 D、导带底和价带顶能容纳多个状态相同的电子 3、在某半导体掺入硼的浓度为1014cm-3, 磷为1015cm-3，则该半导体为（ B ）半导体；其有效杂质浓度约为（ E ）。 A. 本征， B. n型， C. p型， D. 1.1×1015cm-3, E. 9×1014cm-3 4、当半导体材料处于热平衡时，其电子浓度与空穴浓度的乘积为（ B ），并且该乘积和（E、F ）有关，而与（ C、D ）无关。 A、变化量； B、常数； C、杂质浓度； D、杂质类型； E、禁带宽度； F、温度 5、在一定温度下，对一非简并n型半导体材料，减少掺杂浓度，会使得（ C ）靠近中间能级E i ；如果增加掺杂浓度，有可能使得（ C ）进入（ A ），实现重掺杂成为简并半导 体。 A 、E c ； B 、E v ； C 、E F ； D 、 E g ； E 、E i 。 67、如果温度升高，半导体中的电离杂质散射概率和晶格振动散射概率的变化分别是（C ）。 A 、变大，变大 B 、变小，变小 C 、变小，变大 D 、变大，变小 8、最有效的复合中心能级的位置在（D ）附近，最有利于陷阱作用的能级位置位于（C ）附近，并且常见的是（ E ）陷阱。 A 、E A ； B 、E B ； C 、E F ； D 、 E i ； E 、少子； F 、多子。 9、一块半导体寿命τ=15μs ，光照在材料中会产生非平衡载流子，光照突然停止30μs 后，其中非平衡载流子将衰减到原来的（ C ）。 A 、1/4 B 、1/e C 、1/e 2 D 、1/2 10、半导体中载流子的扩散系数决定于该材料中的（ A ）。 A 、散射机构； B 、复合机构； C 、杂质浓度梯度； C 、表面复合速度。 11、下图是金属和n 型半导体接触能带图，图中半导体靠近金属的表面形成了（D ）。 A 、n 型阻挡层 B 、p 型阻挡层 C 、p 型反阻挡层 D 、n 型反阻挡层 12、欧姆接触是指（ D ）的金属－半导体接触。 A 、W ms =0 B 、W ms ＜0 C 、W ms ＞0 D 、阻值较小并且有对称而线性的伏－安特性 13、MOS 器件中SiO 2层中的固定表面电荷主要是（ B ），它能引起半导体表面层中的能带（ C ）弯曲,要恢复平带，必须在金属与半导体间加（ F ）。 A ．钠离子； B 硅离子.；C.向下；D.向上；E. 正电压；F. 负电压 二、证明题：（8分） 由金属－SiO 2－P 型硅组成的MOS 结构，当外加的电压使得半导体表面载流子浓度n s 与内部多数载流子浓度P p0相等时作为临界强反型层条件，试证明：此时半导体的表面势为： 证明：设半导体的表面势为V S ，则表面的电子浓度为： 200exp()exp()S i S s p p qV n qV n n KT p KT == （2分） 当n s =p p0时，有：20exp( ),S p i qV p n KT = （1分） 习题一： ● 。 证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 ● 5.证明：四个顶点的非同构简单图有11个。 证明：设四个顶点中边的个数为m ，则有： m=0: m=1 ： m=2： m=3： m=4： (a) v 23 4 (b) m=5： m=6： 因为四个顶点的简单图最多就是具有6条边，上面所列出的情形是在不同边的条件下的不同构的情形，则从上面穷举出的情况可以看出四个顶点的非同构简单图有11个。 ● 11.证明：序列（7,6,5,4,3,3,2）和（6,6,5,4,3,3,1） 不是图序列。 证明：由于7个顶点的简单图的最大度不会超过6，因此序列（7,6,5,4,3,3,2）不是图序列； （6,6,5,4,3,3,1）是图序列 1 1 12312(1,1,,1,,,)d d n d d d d d π++=---是图序列 （5,4,3,2,2,0）是图序列，然而（5,4,3,2,2,0）不是图序列，所以（6,6,5,4,3,3,1）不是图序列。 ● 12.证明：若 ，则包含圈。 证明：下面仅对连通图的下的条件下进行证明，不连通的情形可以通过分成若干 个连通的情形来证明。设 , 对于中的路 若与邻接，则构成一个闭路。若是一条路，由于，因 此，对于，存在与之邻接，则构成一个圈。 ● 17.证明：若G 不连通，则连通。 证明：对于任意的 ,若与属于G 的连通分支，显然与在中连通； 图论第二次作业Newly compiled on November 23, 2020 图论第二次作业 一、 第四章 （1）画一个有Euler 闭迹和Hamilton 圈的图； （2）画一个有Euler 闭迹但没有Hamilton 圈的图； （3）画一个有Hamilton 圈但没有Euler 闭迹的图； （4）画一个既没有Euler 闭迹也没有Hamilton 圈的图； 解：（1）一个有Euler 闭迹和Hamilton 圈的图形如下： （2）一个有Euler 闭迹但没有Hamilton 圈的图形如下： （3）一个有Hamilton 圈但没有Euler 闭迹的图形如下： （4）一个既没有Euler 闭迹也没有Hamilton 圈的图形如下： 证明：若G 没有奇点，则存在边不重的圈C 1,C 1,···,C m ,使得 )()()()(21m C E C E C E G E ???=。 证明：将G 中孤立点除去后的图记为1G ，则1G 也没有奇点，且2)(1≥G δ，则1G 含圈1C ，在去掉)(11C E G -的孤立点后，得图2G ，显然2G 仍无奇度点，且2)(2≥G δ，从而2G 含圈2C ，如此重复下去，直到圈m C ，且)(m m C E G -全为孤立点为止，于是得到)()()()(21m C E C E C E G E ???=。 证明：若 （1）G 不是二连通图，或者 （2）G 是具有二分类),(Y X 的偶图，这里Y X ≠， 则G 是非Hamilton 图。 证明：（1）因为G 不是二连通图，则G 不连通或者存在割点v ，有2)(≥-v G w ，由相关定理得：若G 是Hamilton 图，则对于v(G)的任意非空顶点集S ，有：S S G w ≤-)(，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。 （2）因为G 是具有二分类),(Y X 的偶图，又因为Y X ≠，在这里假设Y X ≤，则有X Y X G w >=-)(，也就是说：对于v(G)的非空顶点集S ，有：S S G w >-)(成立，则可以得出G 是非Hamilton 图。 设G 是有度序列),,,(21n d d d ???的非平凡简单图，这里n d d d ≤???≤≤21，证明：若不存在小于2 )1(+n 的正整数m ，使得m d m <且m n d m n -<+-1，则G 有Hamliton 路。 证明：在G 之外加上一个新点v ，把它和G 的其余各点连接，得图G 1： 电子科技大学二零 九 至二零 一零 学年第 一 学期期 末 考试 半导体物理 课程考试题 B 卷 （ 120分钟） 考试形式： 闭卷 考试日期 2010年 元月 18日 一、填空题: （共16分，每空1 分） 1. 简并半导体一般是 重 掺杂半导体，这时用不可忽略。 3. 5. 在半导体中同时掺入施主杂质和受主杂质，它们具有 杂质补偿 的作用， 在制造各种半导体器件时，往往利用这种作用改变半导体的导电性能。 6. ZnO 是一种宽禁带半导体，真空制备过程中通常会导致材料缺氧形成氧空位， 存在氧空位的ZnO 半导体为 N/电子 型半导体。 9. 有效质量 概括了晶体内部势场对载流子的作用，可通过回旋共振实验来 测量。 10. 某N 型Si 半导体的功函数W S 是，金属Al 的功函数W m 是 eV ， 该半导体和 金属接触时的界面将会形成 反阻挡层接触/欧姆接触 。 11. 有效复合中心的能级位置靠近 禁带中心能级/本征费米能级/E i 。 12. MIS 结构中半导体表面处于临界强反型时，表面少子浓度等于内部多子浓度， 13. 金属和n 型半导体接触形成肖特基势垒，若外加正向偏压于金属，则半导体 二、选择题（共15分，每题1 分） 1. 如果对半导体进行重掺杂，会出现的现象是 D 。 A. 禁带变宽 B. 少子迁移率增大 C. 多子浓度减小 D. 简并化 2. 已知室温下Si 的本征载流子浓度为310105.1-?=cm n i 。处于稳态的某掺杂Si 半导体中电子浓度315105.1-?=cm n ，空穴浓度为312105.1-?=cm p ，则该半导体 A 。 A. 存在小注入的非平衡载流子 B. 存在大注入的非平衡载流子 C. 处于热平衡态 D. 是简并半导体 张拉拉 应届毕业生| 男 居住地：成都 电话：139********（手机） E-mail：Zhanglala@https://www.wendangku.net/doc/a57999044.html, 最高学历 学历：本科 专业：电子信息工程 学校：成都电子科技大学 -------------------------------------------------------------------------------- 自我评价 语言能力：四级：606 (优秀) 六级：568（优秀）TOEFL:91(满分120) GRE：1310（满分1600）电脑能力：熟练掌握Office办公软件及使用SPSS，MATLAB工具软件 四川省计算机二级（C语言）全国计算机二级（C语言）全国计算机三级（网络技术）。 所获奖项 某年人民一等奖学金 某年人民一等奖学金 某年电子科技大学改革开放三十年演讲比赛第一名（1/75） 某年电子科技大学挑战主持人大赛第一名 某年四川省演讲比赛三等奖 某年全国大学生数学建模大赛国家二等奖 某年电子科技大学第九届数学建模大赛一等奖（3/242） 某年电子科技大学校词汇竞赛一等奖 某年国家业余一级运动员 社会经验 出江中学志愿者、 AIESEC（国际经济学商学学生联合会）副主席 SIFE（国际大学生企业家联盟）成员 心理健康中心“心语热线”接线员 两次家教和一次自己开办补习班的经历 绿洲小学环保教育主讲教师 校内职务 某年电子科大SIFE（国际大学生企业家联盟）团队队长 带领团队核心成员组织成员招募培训，构建团队组织架构，进行校内外的推广， 项目分析策划，参加全国创新公益大赛，荣获SIFE中国精英成员。 与项目经理协作策划执行“聚源中学征信教育”项目，“Drink me”杂志项目， 参与项目的前期调研分析，推广策划，负责整个项目过程的监督，聚源项目获得 泰格伍兹基金500美元的资助，杂志项目打造中国第一本合法校际联刊制刊物并 获得央视报道和社会关注，个人成为杂志项目终生荣誉社长。 某年电子科技大学校数学建模队主力成员（14队队长） 担任全文论文（共30页）工作并学习担当全程数据分析处理。 图论及其应用答案电子科 大 Newly compiled on November 23, 2020 习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两 个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通， 而在G 中u 与v 连通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从 u 与到v 的路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 电子科技大学二零零九至二零一零学年第 二 学期期 末 考试 数字逻辑设计及应用 课程考试题 A 卷（120分钟）考试形式：闭卷 考试日期2010年7月12日 课程成绩构成：平时 20 分， 期中 20 分， 实验 0 分， 期末 60 分 一、To fill your answers in the blanks （1’×25） 1. If [X]10= - 110, then [X]two's-complement =[ 10010010 ]2, [X]one's-complement =[ 10010001 ]2. (Assumed the number system is 8-bit long) 2. Performing the following number system conversions: A. [10101100]2=[ 000111010010 ]2421 B. [1625]10=[ 0100100101011000 ]excess-3 C. [ 1010011 ]GRAY =[ 10011000 ]8421BCD 3. If ∑=C B A F ,,)6,3,2,1(, then F D ∑=C B A ,,( 1，4，5，6 )=C B A ,,∏(0，2，3，7 ). 4. If the parameters of 74LS-series are defined as follows: V OL max = 0.5 V , V OH min = 2.7 V , V IL max = 0.8 V , V IH min = 2.0 V , then the low-state DC noise margin is 0.3V ,the high-state DC noise margin is 0.7V . 5. Assigning 0 to Low and 1 to High is called positive logic. A CMOS XOR gate in positive logic is called XNOR gate in negative logic. 6. A sequential circuit whose output depends on the state alone is called a Moore machine. 7. To design a "001010" serial sequence generator by shift registers, the shift register should need 4 bit as least. 8. If we use the simplest state assignment method for 130 sates, then we need at least 自动化专业本科人才培养方案 一、专业代码与名称 专业代码：080602 专业名称：自动化 二、学制与学位 修业年限：四年 授予学位：工学学士 三、培养目标 经过系统的教育和教学活动，使学生具有扎实的基础、宽广的知识面和较强的实践动手能力，培养学生的创新精神和团队意识，使其在掌握自动化和控制工程领域先进技术的基础上，具有提出和解决带有挑战性问题的能力，不断提高自身的综合素质。同时，发展学生个性，培养学生具有健全人格，使其成为德智体美全面发展的高素质人才。 四、基本要求 本专业学生主要学习自动控制原理、计算机控制系统、传感器原理、过程控制系统、线性系统理论、电力电子技术、系统工程导论等专业知识，并接受1～2个学科专业方向的基本训练。毕业后可从事国民经济、国防和科研各部门的运动控制、过程控制、机器人智能控制、导航制导与控制，现代集成制造系统、模式识别与智能系统、系统工程理论与实践、新型传感器、电子与自动检测系统、复杂网络与计算机应用系统等领域的科学研究、技术开发、教学及管理等工作。 毕业生应获得以下几个方面的知识和能力： 1．扎实的数理基础，较好的人文社会科学和管理科学基础，以及外语综合能力； 2．系统掌握本学科领域必需的技术基础理论知识，包括电路理论、电子技术、信号与系统、自动控制理论、计算机软硬件、电力电子学、电力系统自动化等。 3．较强的工程实践能力，较熟练的计算机应用能力； 4．本学科领域内1～2个专业方向的知识与技能，了解本学科前沿的发展趋势； 5．较强的工作适应能力，一定的科学研究、技术开发和组织管理的实际工作能力。 五、专业特色 1、在科研、教学、实验和毕业设计环节与计算机技术、网络通信等专业有机结合，培养适应面宽广的“多才”专业； 2、理论与实践并重，培养学生的实际动手能力，不断提高学生的工程素质和专业基础，训练工程型人才； 3、开展各类竞赛辅助教学，培养学生的团队意识，引导学生发现问题并寻找解决问题的办法，不断提升学生的创新能力。 六、主干学科与主干课程 1、主干学科：检测技术及自动化装置、控制科学与工程 2、主干课程：自动控制原理、计算机控制系统、传感器原理、过程控制系统 3、双语教学课程：信号与系统、信息论导论、电力系统自动化、线性系统理论、数字 逻辑设计及应用 七、主要实践教学环节 1、实验：微型计算机系统原理及接口技术，电子技术实验基础I/II，现代电子技术综 合实验，电力电子技术，集成电路应用实验I/II，信号与系统，过程控制系 统，计算机控制系统，电机与拖动基础，传感器原理，自控原理基础实验， 单片机与PLC，数字系统设计，调速与随动，企业供配电系统，嵌入式系统 设计，现代控制技术综合实验，数字图像处理，现场总线控制系统，电力系 统自动化，信息论导论 2、上机：软件技术基础，现代工程设计制图，数值计算方法，自控原理基础实验，高 级语言程序设计，控制系统计算机仿真，计算机网络，现代控制技术综合实 验，人工智能导论，数字信号处理，系统工程导论 3、课程设计：电路分析基础，单片机与PLC，线性系统理论，现代控制技术综合实验 计算机控制系统，传感器原理，自控原理基础实验，单片机与PLC，数字系 统设计，企业供配电系统，嵌入式系统设计 4、实习实训：实习实训环节包括军事训练、基础工程训练、电工电气技术实训、电装 实习、综合课程设计、生产实习、毕业设计 习题四： 3.（1）画一个有Euler 闭迹和Hamilton圈的图； （2）画一个有Euler闭迹但没有Hamilton圈的图； （3）画一个有Hamilton圈但没有Euler闭迹的图； （4）画一个即没有Hamilton圈也没有Euler闭迹的图； 解：找到的图如下： (1)一个有Euler 闭迹和Hamilton圈的图； (2)一个有Euler闭迹但没有Hamilton圈的图； (3) 一个有Hamilton圈但没有Euler闭迹的图; (4)一个即没有Hamilton圈也没有Euler闭迹的图. 4.设n阶无向简单图G有m条边，证明:若,则是图。证明: G是H图。 若不然，因为G是无向简单图，则,由定理1：若G是的非单图，则G 度弱于某个.于是有： 2,1()()(2)(1)(1)2 11 1(1)(2)(1)(21)221 1.2m n E G E C m n m n m m m n m m m n m n ??≤= +---+-??-??=+------- ? ?? -??≤+ ??? 这与条件矛盾！所以G 是H 图。 8.证明：若G 有 个奇点，则存在条边不重的迹 ,使得 . 证明：不失一般性，只就G 是连通图进行证明。设G=(n, m)是连通图。令v l ，v 2，…,v k ,v k+1,…,v 2k 是G 的所有奇度点。在v i 与v i+k 间连新边e i 得图G*（1≦i ≦k).则G*是欧拉图，因此，由Fleury 算法得欧拉环游C.在C 中删去e i （1≦i ≦k).得k 条边不重的迹Q i （1≦i ≦k): 12()() () ()k E G E Q E Q E Q = 10.证明：若： （1）不是二连通图，或者 （2）是具有二分类的偶图，这里 , 则是非Hamilton 图。 证明：（1）不是二连通图，则不连通或者存在割点,有,由于课本 上的相关定理：若是Hamilton 图，则对于 的任意非空顶点集，有： ,则该定理的逆否命题也成立，所以可以得出：若不是二连通图， 则是非Hamilton 图 (2)因为是具有二分类 的偶图，又因为 ，在这里假设 ,则有,也就是说：对于 的非空顶点集，有： 成 立，则可以得出则是非Hamilton 图。 11.证明：若有Hamilton 路，则对于V 的每个真子集S ，有 . 电子科技大学二零一零至二零一一学年第一学期期末考试 1．对于大注入下的直接辐射复合，非平衡载流子的寿命与（D ） A. 平衡载流子浓度成正比 B. 非平衡载流子浓度成正比 C. 平衡载流子浓度成反比 D. 非平衡载流子浓度成反比 2．有3个硅样品，其掺杂情况分别是： 甲．含铝1×10-15cm-3乙.含硼和磷各1×10-17cm-3丙.含镓1×10-17cm-3 室温下，这些样品的电阻率由高到低的顺序是（C ） A.甲乙丙 B. 甲丙乙 C. 乙甲丙 D. 丙甲乙 3．题2中样品的电子迁移率由高到低的顺序是（ B ） 4．题2中费米能级由高到低的顺序是（ C ） 5. 欧姆接触是指（ D ）的金属一半导体接触 A. W ms = 0 B. W ms < 0 C. W ms > 0 D. 阻值较小且具有对称而线性的伏安特性 6．有效复合中心的能级必靠近( A ) A.禁带中部 B.导带 C.价带 D.费米能级 7．当一种n型半导体的少子寿命由直接辐射复合决定时，其小注入下的少子寿命正比于（C ） A.1/n0 B.1/△n C.1/p0 D.1/△p 8．半导体中载流子的扩散系数决定于其中的( A ) A.散射机构 B. 复合机构 C.杂质浓变梯度 D.表面复合速度 9．MOS 器件绝缘层中的可动电荷是（ C ） A. 电子 B. 空穴 C. 钠离子 D. 硅离子 10．以下4种半导体中最适合于制作高温器件的是（ D ） A. Si B. Ge C. GaAs D. GaN 二、解释并区别下列术语的物理意义（30 分，7+7+8+8，共4 题） 1. 有效质量、纵向有效质量与横向有效质量（7 分） 答：有效质量：由于半导体中载流子既受到外场力作用，又受到半导体内部周期性势场作用。有效概括了半导体内部周期性势场的作用，使外场力和载流子加速度直接联系起来。在直接由实验测得的有效质量后，可以很方便的解决电子的运动规律。(3分) 纵向有效质量、横向有效质量：由于k空间等能面是椭球面，有效质量各向异性，在回旋共振实验中，当磁感应强度相对晶轴有不同取向时，可以得到为数不等的吸收峰。我们引入纵向有效质量跟横向有效质量表示旋转椭球等能面纵向有效质量和横向有效质量。(4分) 2. 扩散长度、牵引长度与德拜长度（7 分） 答：扩散长度：指的是非平衡载流子在复合前所能扩散深入样品的平均距离。由扩散系数 图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020 习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} 图论第二次作业 一、第四章 4.3（1）画一个有Euler闭迹和Hamilton圈的图； （2）画一个有Euler闭迹但没有Hamilton圈的图； （3）画一个有Hamilton圈但没有Euler闭迹的图； （4）画一个既没有Euler闭迹也没有Hamilton圈的图；解：（1）一个有Euler闭迹和Hamilton圈的图形如下： （2）一个有Euler闭迹但没有Hamilton圈的图形如下： （3）一个有Hamilton圈但没有Euler闭迹的图形如下： （4）一个既没有Euler闭迹也没有Hamilton圈的图形如下： 4.7 证明：若G 没有奇点，则存在边不重的圈C 1,C 1,···,C m ,使得 )()()()(21m C E C E C E G E ???=。 证明：将G 中孤立点除去后的图记为1G ，则1G 也没有奇点，且2)(1≥G δ，则1G 含圈1C ，在去掉)(11C E G -的孤立点后，得图2G ，显然2G 仍无奇度点，且2)(2≥G δ，从而2G 含圈2C ，如此重复下去，直到圈m C ，且)(m m C E G -全为孤立点为止，于是得到)()()()(21m C E C E C E G E ???=。 4.10 证明：若 （1）G 不是二连通图，或者 （2）G 是具有二分类),(Y X 的偶图，这里Y X ≠， 则G 是非Hamilton 图。 证明：（1）因为G 不是二连通图，则G 不连通或者存在割点v ，有2)(≥-v G w ，由相关定理得：若G 是Hamilton 图，则对于v(G)的任意非空顶点集S ，有：S S G w ≤-)(，则该定理得逆否命题也成立，所以可得：若G 不是二连通图，则G 是非Hamilton 图。 （2）因为G 是具有二分类),(Y X 的偶图，又因为Y X ≠，在这里假设Y X ≤，则有X Y X G w >=-)(，也就是说：对于v(G)的非空顶点集S ，有：S S G w >-)(成立，则可以得出G 是非Hamilton 图。 4.12 设G 是有度序列),,,(21n d d d ???的非平凡简单图，这里n d d d ≤???≤≤21，证明：若不存在小于 2 )1(+n 的正整数m ，使得m d m <且m n d m n -<+-1，则G 有Hamliton 路。 证明：在G 之外加上一个新点v ，把它和G 的其余各点连接，得图G 1： G 1的度序列为：),1,,1,1(21n d d d n +???++，由已知：不存在小于2 )1(+n 的正整数 电子科技大学计算机网络期末试题 .单项选择题（10分）： 1. 在OSI参考模型中，数据链路层的数据服务单元是（ A.帧 B.报文 C.分组 D.比特序列 2. 下列各项中数据单元关系描述错误的是（ A. (N+1 ) _PDU W( N) _SDU< (N-1 ) _SDU B.B. ( N+1 ) _PDU< ( N) _PDU< ( N-1 ) _PDU C. (N+1 ) _SDU< (N) _PDU W( N-1 ) _SDU D.D. (N+1 ) _PDU< ( N ) _PCI< ( N-1 ) _PCI 3. 若信道的复用是以信息在一帧中的时间位置（时隙）来区分，不需要另外的 信息头来标志信息的身份，则这种复用方式为（ A.异步时分复用 B.频分多路复用 C.同步时分复用 D.码分多路复 4. 下列不属于应用层协议的是（ A.UD P B. SNMP C. TELNET D. HTT P 5. 下列叙述错误的是（ A.路由器可以分割冲突域 B.路由器和网桥均能扩展工作站平均带宽 C.网桥可以分割广播域 D.共享式集线器一个端口只能支持一个MAC 地址 二.填空题（24分）： 1. 计算机网络的两大基本功能是 2. 计算机网络从逻辑上划分为 3. 网络协议三要素分别为: 4. 计算机网络中常用的信道分为两大类，其中有线信道所用的传输介质主要是 ，另一类无线信道包括 5. 调制解调器把 为调制，而把 称为解调。 6」Pv6 对IPv4的改进主要在 7.在OSI模型中，端到端的四层是: 三.简答题（20分）： 1.请按照TCP/IP参考模型简述该模型的层次结构及各层的基本功能。 2.简述无连接服务和面向连接服务及其优缺点。 习题四： 3. (1)画一个有Euler闭迹和Hamilton圈的图； (2) 画一个有Euler闭迹但没有Hamilton圈的图； (3) 画一个有Hamilton圈但没有Euler闭迹的图； (4) 画一个即没有Hamilton圈也没有Euler闭迹的图; 解：找到的图如下： (1)一个有Euler闭迹和Hamilton圈的图； (2)—个有Euler闭迹但没有Hamilton圈的图; ⑶一个有Hamilton圈但没有Euler闭迹的图; (4)一个即没有Hamilton圈也没有Euler闭迹的图. 4. 设n阶无向简单图G有m条边，证明：若2 ) * ',则G是血加此"图。证明：G是H图。 若不然，因为G是无向简单图，则n芝3,由定理％若G是n芝3的非单图，则G 、一 ...C … 度弱丁某个阵".于是有： - - 1 2 E(G)| E(C m,n ) - m (n 2m)(n m 1) m(m 1) 1. 这与条件矛盾！所以G 是H 图 若G 有个奇点，则存在k 条边不重的迹Q1?Q 矿心，使得 E(G) = E(Q 】)U E(Q J U E(Q 3) U …U E(Q k ) 证明：不失一般性，只就 G 是连通图 进行证明。设 G=(n, m)是连通图。令 虬 V 2,…,v,V k+1,…,v 是G 的所有奇度点。在V i 与v i+k 问连新边e i 得图G* (1三隹k). 则G*是欧拉图，因此，由Fleury 算法得欧拉环 游C 在C 中删去e i (1m M k).得 k 条边不重的迹Qi (1 MiMk): E(G) E(Q1^E(Q2^^E(Qk) 10. 证明：若： (1) G 不是二连通图，或者 (2) G 是具有二分类|(X,Y)的偶图，这里|X” |Y| 则G 是非Hamilton 图。 证明：(1) G|不是二连通图，则G 不连通或者存在割点v ,俨任-v) >2 ,由丁课本 上的 相关定理：若G 是Hamilton 图，则对丁*勇)的任意非空顶点集S,有： w(G- S) < |S|,则该定理的逆否命题也成立，所以可以得出：若不是二连通图， 则G 是非 Hamilton 图 (2)因为是具有二分类(XI)的偶图，乂因为|X|丰1丫1,在这里假设|X| < |Y|,则有 w(G- X) = |Y|>|X|，也就是说：对北(G)|的非空顶点集S,有：w(G-S)>||S|成 立，则可以得出 则G 是非Hamilton 图。 11. 证明：若有Hamilton 路，则对丁 V 的每个真子集S,有w(G - S) ' |S | +】. 证明：G 是H 图，设C 是G 的H 圈。则对V(G)的任意非空子集S,容易知道： (C S) S 1 1 -(m 1)(m 2) (m 1)(n 2m 1) 8.证明 离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {f} ． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 等于出度 ． 5．设G=电子科技大学研究生试题《图论及其应用》(参考答案)
电大离散数学作业答案05作业答案
图论第二次作业
电子科技大学半导体物理期末考试试卷试题答案
答案(电子科大版)图论及其应用第一章
图论第二次作业
电子科技大学半导体物理期末考试试卷B试题答案
【最新个人简历模板】成都电子科技大学
图论及其应用答案电子科大
电子科技大学期末数字电子技术考试题a卷-参考答案教学内容
(完整版)成都电子科技大学自动化专业本科培养方案
电子科技大学-图论第二次作业
电子科技大学半导体物理期末考试试卷试题答案
图论及其应用答案电子科大
图论第二次作业
电子科技大学计算机网络期末试题
电子科技大学-图论第二次作业
离散数学图论部分形成性考核书面作业4答案