习题三：
● 证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意及, G 中的路必含.
证明：充分性: 是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对12,u V v V ?∈?∈，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。 必要性：取12,u V v V ∈∈，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e 是割边。
●
3.设G 是阶大于2的连通图，证明下列命题等价： （1）
G 是块 （2）
G 无环且任意一个点和任意一条边都位于同一个圈上； （3）
G 无环且任意三个不同点都位于同一条路上。
： 是块，任取的一点，一边，在边插入一点，使得成为两条边，由此得到新图，显然的是阶数大于3的块，由定理，中的u,v 位于同一个圈上，于是
中u 与边都位于同一个
圈上。
： 无环，且任意一点和任意一条边都位于同一个圈上，任取的点u ，边e ，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v ，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，12,x v y v ∈∈，点在每一条的路上，则与已知矛盾，是块。 ●
7.证明：若v 是简单图G 的一个割点，则v 不是补图的割点。 证明：是单图的割点，则有两个连通分支。现任取, 如果不在的
同一分支中，令是与
处于不同分支的点，那么，与在的补图中连通。若在的同一分支中，则它们在的补图中邻接。所以，若是的割点，则不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给
出相应的最小点割和最小边割。
解：()12G κ= 最小点割 {6,8}
1()2G λ= 最小边割{（6,5），（8,5）}
()25G κ= 最小点割{6,7,8,9,10}
2()5G λ= 最小边割{（2,7）…（1,6）}
●
13.设H 是连通图G 的子图，举例说明：有可能k(H)> k(G).
解： 通常. 整个图为，割点左边的图为的的子图， ，则. e
H
电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：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
西安电子科技大学高等职业技术学院 “高等数学”教学大纲 一、教材内容的范围及教学时数 根据教育部高职高专规划教材之高等数学，其内容的范围包括：一元函数微积分学及其应用, 一元函数积分学及其应用，向量代数与空间解析几何，多元函数积分学，无穷级数，常微分方程。 教学时数：144学时课程类别：必修学分：9 学期：第一、二学期使用范围：工科所有专业及电子商务专业 二、教学的目的及要求 要求学生全面的掌握高等数学所涉及的基本概念，基本理论和基本运算能力的技巧，具有大专学习所必需的抽象思维能力、逻辑推理能力、空间想象能力以及综合运用所学知识分析问题和解决问题的能力。具体要求可分为较高要求和一般要求两个层次: 较高要求需要学生深入理解、巩固掌握、熟练应用，其中概念、理论用“理解”一词表述；方法、运算用“掌握”一词表述；一般要求也是不可缺少的，只是在要求上低于前者，其中概念、理论用“了解”一词表述；方法、运算用“会”或“了解”一词表述。 1．函数、极限、连续及具体要求 （1）理解函数的概念，掌握函数的表示方法 （2）了解函数的有界性、单调性、奇偶性和周期性 （3）理解复合函数概念，了解反函数和隐函数的概念 （4）掌握基本初等函数的性质及图像 （5）会建立简单应用问题的函数关系式 （6）理解数列极限和函数极限的概念，理解函数的左右极限的概念以及极限存在与左右极限之间的关系 （7）掌握极限的性质与四则运算法则 （8）掌握极限存在的两个重要准则，并会利用其求极限 （9）掌握两个重要极限的方法 （10）理解无穷小、无穷大的阶的概念 （11）理解函数连续性的概念，会判断间断点的类型 （12）了解初等函数连续性的闭区间上的连续性质（最大值、最小值和解介值定理）会解答相关的应用问题 2．一元函数微分学及具体要求 （1）理解导数的概念及其几何意义，会求平面曲线的切线与法线方程 （2）了解导数的物理意义，会用导数描述一些物理量 （3）理解函数的可导性与连续性之间的关系 （4）掌握导数的四则运算法则和复合函数的求导法则，会求反函数的导数 （5）掌握基本初等函数的求导公式，了解初等函数的可导性
1.（该题目硕士统招生做）请用框架法和语义网络法表示下列事件。（10分） 2015年2月20日上午11点40分，广东省深圳市光明新区柳溪工业园附近发生山体滑坡，经初步核查，此次滑坡事故共造成22栋厂房被掩埋，涉及公司15家，截至目前已安全撤离900人，仍有22人失联。 答：框架表示法（5分）：（给分要点：确定框架名和框架槽，根据报道给出的相关数据填充，主要内容正确即可给分，不必与参考答案完全一致） <山体滑坡> 时间：2015年2月20日上午11点40分 地点：广东省深圳市光明新区柳溪工业园附近 掩埋厂房：22栋 涉及公司数目：15家 安全撤离人数：900人 失联人数：22人 语义网络表示法（5分）：（给分要点：确定语义网络的节点及其连接关系，根据报道内容进行填充，主要内容正确即可给分，不必与参考答案完全一致） 1. （该题目全日制专业学位硕士做）请用一种合适的知识表示方法来表示下面知识。（10分） How Old Are YOU是微软推出的一款测年龄应用，该应用架设在微软服务平台Azure上，该平台具有机器学习的开发接口，第三方开发者可以利用相关的接口和技术，分析人脸照片。
（给分要点：采用合适的知识表示方法，正确即可给分，不必与参考答案完全一致） 答：
习题一： ● 。 证明:作映射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 的连通分支，显然与在中连通；
西安电子科技大学本科课程考试试卷2008—2009学年第一学期《单片机原理与接口技术》 课程A卷 专业年级：07电信命题教师：郭文川审题教师： 考生班级：学号：考生姓名： 一、填空题：（每空1分，共20分） 1、MCS—5l单片机的最大程序寻址空间是64 KB，该空间的地址范围从0000H 至0FFFFH，系统上电及复位后，程序入口地址为0000H。 2、若由程序设定PSW中的RS1、RS0=01，则工作寄存器R0~R7的直接地址为08H~0FH。 3、MCS-51单片机的I/O端口采用统一编址方式。、 4、一个8位D/A转换器其分辨率为_ 1/256 ，若该8位D/A转换器的基准电压为5V， 则数字量100对应得模拟量为 1.953V（5*100/256V）。 5、单片机系统中经常采用的地址译码技术包括线选法和译码法。 6、INTEL 8051 CPU 是8 位的单片机，其内部有4 KB的ROM。 7、指出下列各指令中源操作数的寻址方式。 （1）MOVC A，@A+DPTR （变址寻址） （2）XCH A，@R0；（寄存器间接寻址） （3）MOV C，P1.0 （位直接寻址） （4）JC LOOP （相对寻址） 8、判断下列各条指令的书写格式是否有错，并指出原因。 （1）MUL R0，R1 （错，乘法指令用A×B ） （2）MOV A, @R7 （错，@R7非法）
（3）MOV A, #3000H （错，累加器A为8位存储器） （4）MOV R1, C （错，C为进位位不能送给寄存器R1） 二、选择题：（每题1分，共10分） 1．当MCS-51单片机接有外部存储器时，P2口可作为 D 。 A．数据输入口 B. 数据的输出口 C．准双向输入／输出口D．高8位地址线 2．单片机的并行接口中，作为数据线使用的并行口是 A 。 A．P0 B. P1 C. P2 D. P3 3．MCS—5l单片机的堆栈区是设置在 C 中。 A．片内ROM区B．片外ROM区 C．片内RAM区 D. 片外RAM区 4．片内RAM的20H～2FH为位寻址区，所包含的位地址是。 A．00H～20H B. 00H～7FH C．20H～2FH D．00H～FFH 5．在寄存器间接寻址方式中，间址寄存器中存放的数据是。 A．参与操作的数据B．操作数的地址值 C．程序的转换地址D．指令的操作码 6．当需要从MCS-51单片机程序存储器取数据时，采用的指令为。 A. MOV A, @R1 B.MOVC A, @A + DPTR C. MOVX A, @ R0 D.MOVX A, @ DPTR 7. 能够用紫外光擦除ROM中程序的只读存储器称为。 A.掩膜ROM B.PROM C.EPROM D.EEPROM 8. 在片外扩展一片2716程序存储器芯片要地址线。 A.8根 B.13根 C.11根 D.20根 9. 定时器/计数器工作方式1是。 A. 8位计数器结构 B. 2个8位计数器结构 C. 13位计数结构 D. 16位计数结构 10．T0中断的中断入口地址为。 A. 0003H B. 000BH C. 0013H D. 001BH 三、分析程序，写出结果（每空3分，共18分） 1、已知（A）=83H，（R0）=17H，（17H）=34H，执行下列程序段后(A)= 0CBH 。
图论及其应用答案电子科 大 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的块，则两条边的三个不同点在同一条路上。
一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。
9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为
电子信息科学与技术专业培养方案 一、培养目标及规格 电子信息科学与技术专业旨在培养爱国进取、创新思辨、具有扎实的数理、计算机及外语基础，具备电子信息方面的基本知识和技能，具有较强的无线电物理与微波、毫米波技术相结合的能力，具有较好的科学素养及一定的研究、开发和管理能力，具有创业和竞争意识，具有国际视野和团队精神，能适应技术进步和社会需求变化的行业骨干和引领者。 电子信息科学与技术专业针对不同发展要求的学生，确定专业学术型、工程实践型、就业创业型三种人才培养规格。 1.“专业学术型”：在学习的奠基阶段，强调打好数理、计算机及外语基础；在积累成长阶段针对专业学术型的学生进行电子信息基本知识和技能，无线电物理与微波、毫米波技术等方面初步培养；在能力强化阶段进一步加强技术创新和综合设计能力训练并对在该学科方向开展科学研究做好准备。毕业生可报电磁场与微波技术、无线电物理、无线通信等专业的研究生继续深造。 2.“工程技术型”：培养具有良好的数理基础和专业基础知识的技术创新与综合设计人才。掌握熟练的专业技能，具有工程素质，动手能力强，毕业生可从事工程技术应用与开发设计工作。 3.“就业创业型”：培养不但具有良好的数理基础和专业基础知识而且具备良好的外语沟通能力，知识更新能力，技术创新能力以及管理能力的人才。掌握较好的专业技能及工程素养，动手能力强。毕业生可以从事工程技术应用和管理工作。 二、基本要求 （一）知识结构要求 本专业按照4年制进行课程设置及学分分配。知识结构要求如下： 一、二年级主要学习公共基础课程，主要掌握高等数学、大学物理、外语和电路分析基础等基础知识。三、四年级主要学习专业基础课和专业课，主要包括电磁场与电磁波、微波技术、和微波遥感专业基础知识。使学生通过学习掌握扎实的数理基础和电子信息科学与技术专业方面的专门知识。 1. 公共基础知识：具有扎实的高等数学、大学物理、英语、计算机、人文社会科学基础知识。 2. 学科基础知识：掌握电路分析基础、信号与系统、模拟电子技术基础、数字电路与逻辑设计、微机原理与系统设计、数学物理方程、数值计算方法的相关专业知识。 3. 专业知识：掌握天线原理、量子力学、电磁场理论、电波传播概论、通信原理、微波技术基础的专业知识。 4. 实践类知识：具有电波测量实验、电子电磁技术实验、专业特色实验（微波应用）等的专业知识。 5. 能力素质知识：了解电波传播相关专业的最新动态，微波、毫米波天线技术方面的
电子科技大学研究生试卷 （考试时间： 至 ，共_____小时） 课程名称 图论及其应用 教师 学时 60 学分 教学方式 讲授 考核日期_2007__年___月____日 成绩 考核方式： （学生填写） 一．填空题(每题2分，共12分) 1．简单图G=(n,m)中所有不同的生成子图(包括G 和空图)的个数是___2m __个； 2．设无向图G=(n,m)中各顶点度数均为3，且2n=m+3,则n=_ 6__; m=_9__； 3．一棵树有i n 个度数为i 的结点，i=2,3,…,k,则它有2+(i ?2)∑n i i 个度数为1的结点； 4．下边赋权图中，最小生成树的权值之和为__20___; 5、某年级学生共选修9门课。期末考试时，必须提前将这9门课先考完，每天每人只在下午考一门课，则至少需要___9__天才能考完这9门课。 二．单项选择(每题2分，共10分) 1．下面给出的序列中，不是某简单图的度序列的是( D ) (A) (11123); (B) (22222); (C) (3333); (D) (1333). 2． 下列图中，是欧拉图的是（ D ） 学 号 姓 学 …………………… 密……………封…………… 线……………以……………内……………答…… ………题… …………无……………效…………………… v 5 v v 6A B
3．下列图中，不是哈密尔顿图的是（B） A B C D 4．下列图中，是可平面图的图的是（B） A B C D 5．下列图中，不是偶图的是（B） C A B D 三、 (8分)画出具有7个顶点的所有非同构的树 解：m=n?1=6 …… 四，用图论的方法证明：任何一个人群中至少有两个人认识的朋友数相同(10分) 证明：此题转换为证明任何一个没有孤立点的简单图至少有两个点的度数相同。 参考教材P5。 五．(10分) 设G为n 阶简单无向图，n>2且n为奇数，G与G的补图G中度数为奇数的顶点个数是否相等？证明你的结论 证明：根据补图定义d G(v i)+d G(v i)=n?1。相等。 由频序列相同证明有同样奇数的顶点个数。 参考教材P5。
西安电子科技大学试卷 考试时间120 分钟试卷编号参考答案 班级学号姓名任课老师姓名 请按下述要求正确答题： 1. 在试卷指定位置上正确写入你的班级、学号、姓名和任课老师姓名。 2．全部试卷共 11 页。试卷必须交回，否则以零分计。 3．试题解答必须写在试卷上，若试卷上写不下可以写在试卷的背面，写在草稿纸上的解答一律无效。 4．本试卷的试题共有五道大题，需要全部解答。 5．解答前务必阅读清楚题意，及解答要求，否则导致不能正确评分概由自己负责。 一、单项选择题（每小题1分，共10分） １．访管指令所引起的中断属于（ C ）中断。 A．外中断B．I/O中断C．软中断D．程序中断２．资源静态分配法破坏了死锁产生的（B）条件来预防死锁的发生。 A．互斥控制B．保持和等待 C．不可剥夺控制D．循环等待 ３．虚拟存储的基础是程序局部性理论，它的基本含义是（ B ）。 A．代码的顺序执行B．程序执行时对内存访问的不均匀性 C．变量的连续访问D．指令的局部性 ４．关于SPOOLING系统（D）的描述是错误的。 A．不需要独占设备 B．加快了作业执行的速度 C．使独占设备变成了共享设备
D．利用了处理器与通道并行工作的能力 ５．设系统中有m个同类资源数，n为系统中的并发进程数，当n个进程共享m个互斥资源时，每个进程的最大需求数是w，试问下列情况下系统会死锁的是（D）。 A．m=4，n=3，w=2 B．m=2，n=2，w=1 C．m=5，n=2，w=3 D．m=4，n=3，w=3 ６．文件系统中实现按名存取的功能是通过查找（B）来实现的。 A．磁盘空间B．文件目录C．磁盘控制器D．位示图７．下面的叙述中，（D）不是设备管理中引入缓冲机制的主要原因。 A．缓和CPU和I/O设备间的速度不匹配问题 B．减少对CPU的中断频率和放宽对CPU响应时间的限制 C．提高CPU和I/O设备间的并行性 D．节省系统内存 ８．下列操作系统强调交互性的系统是（B）。 A．批处理系统B．分时系统C．实时系统D．网络操作系统 ９．响应比高者优先作业调度算法是通过计算时间和（D）来实现的。 A．输入时间B．完成时间C．周转时间D．等待时间１０．在可变分区管理方案中，若采用“最佳适应”分配算法，通常将空闲区按（A ）排列。 A．容量递增B．容量递减C．地址递增D．地址递减二、填空题（每空格1分，共15分） 1．把作业装入内存时完成地址变换的方式称静态地址再定位，而在作业执行期间（访问到指令或数据）才进行地址变换的方式称为动态地址再定位。 2．死锁产生的四个必要条件是互斥执行、保持和等待、不可剥夺和循环等待。
图论及其应用答案电子科 大 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）}
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f
西安电子科技大学卓越工程师教育培养计划校内课程大纲 《工程优化方法》 课程名称：工程优化方法/Engineering Optimization Methods 课程代码：0721005 课程类型：必修 总学时数：46学时 学分：3分 开课单位：理学院数学科学系 适用专业：适用于理、工等专业的卓越工程师硕士 课程的性质与目标 最优化方法是一门新兴的应用数学，是运筹学的核心部分，在工程科技、经济金融、管理决策和国防军事等众多领域具有广泛的应用。工程优化方法基于最优化的原理，着重介绍实用性、有效性强的各种实用优化算法。通过本课程的课堂学习和一定的上机实践使学生对工程优化方法的基本原理、算法的基本步骤、应用要点等有一个基本认识和初步掌握，培养和提高用优化方法解决某些实际问题的初步技能，为应用优化软件包解决实际工程问题奠定基础。 ?能够掌握最优化的基本原理、基本方法和应用技能 ?能够用工程优化方法解决简单的实际问题 ?能够熟练应用优化软件包进行计算 学时安排 课堂教学：学时：40 研讨课：学时：6 实践课：学时：10 总学时数：学时:46+10 教学方法 以课堂教学为主，采用板书与多媒体相结合的教学方式，讲授工程优化方法课程的基本原理和方法，既保证讲授内容的清晰，又兼顾师生的交流与互动。在对具体原理和基本方法的推导和证明时，采用板书讲解方式，以便学生能一步步跟上教师的思路。通过课后作业和上机实验加深学生对工程优化方法的理解，培养学生的应用能力，通过动手实践让学生理解从书本理论到分析问题、解决实际问题的过程，从而培养学生解决实际问题的能力。
先修课程 高等数学、线性代数、C语言程序设计、Matlab语言 课程综合记分方法 各部分的比重分别为： 平时成绩 20 % 实验成绩 30 % 期末考试 50 % 总计 100% 教科书 陈宝林. 最优化理论与算法.北京：清华大学出版社，2005. 推荐参考书 1.唐焕文，秦学志编著. 实用最优化方法(第三版).大连：大连理工大学出版社，2004. 2.袁亚湘，孙文瑜. 最优化理论与方法. 北京：科技出版社，2001. 3.J. Nocedal & S. J. Wright, Numerical Optimization（影印版）,北京：科学出版社，2006. * *本表注：对于表中第二列所列技能应对照附录A 理解。目标栏内以A, B, C, D 来表示对此条能力要求达到的程度，A 为最高要求，无要求则留空。接触指在教、学活动中有所提及但没有训练和测试要求；训练指有明确要求并有测试项目；应用指在教、学中有所应用而不论是否曾给与相关训练或考核。
离散数学图论部分综合练习 一、单项选择题 1.设图G 的邻接矩阵为 ??? ???? ? ????? ???01010 1001000001 1100100110 则G 的边数为( ). A.6 B.5 C.4 D.3 2.已知图G 的邻接矩阵为 , 则G 有( ). A.5点,8边 B.6点,7边 C.6点,8边 D.5点,7边 3.设图G ＝
图三 7.设有向图(a )、(b )、(c )与(d )如图四所示,则下列结论成立的就是 ( ). 图四 A.(a )就是强连通的 B.(b )就是强连通的 C.(c )就是强连通的 D.(d )就是强连通的 应该填写:D 8.设完全图K n 有n 个结点(n ≥2),m 条边,当( )时,K n 中存在欧拉回路. A.m 为奇数 B.n 为偶数 C.n 为奇数 D.m 为偶数 9.设G 就是连通平面图,有v 个结点,e 条边,r 个面,则r = ( ). A.e －v ＋2 B.v ＋e －2 C.e －v －2 D.e ＋v ＋2 10.无向图G 存在欧拉通路,当且仅当( ). A.G 中所有结点的度数全为偶数 B.G 中至多有两个奇数度结点 C.G 连通且所有结点的度数全为偶数 D.G 连通且至多有两个奇数度结点 11.设G 就是有n 个结点,m 条边的连通图,必须删去G 的( )条边,才能确定G 的一棵生成树. A.1m n -+ B.m n - C.1m n ++ D.1n m -+ 12.无向简单图G 就是棵树,当且仅当( ). A.G 连通且边数比结点数少1 B.G 连通且结点数比边数少1 C.G 的边数比结点数少1 D.G 中没有回路. 二、填空题 1.已知图G 中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G 的边数就是 . 2.设给定图G (如图四所示),则图G 的点割 集就是 . 3.若图G=
西安电子科技大学网络教育 2010学年上学期期末考试模拟题2 课程名称： _机械工程材料_ 考试形式：闭卷 学习中心：_________ 考试时间： 90分钟 姓名：_____________ 学号： 一、填充题（共30分，每空一分） 1.弹性模量E值表征材料＿＿＿＿＿＿＿＿＿＿＿＿。弹性模量的大小主要取决 于材料的＿＿＿＿＿＿。它除随温度升高而逐渐降低外，其他强化材料的手段 如热处理、冷热加工、合金化等对弹性模量的影响＿＿＿＿＿。 2. 常将铸铁分为如下五大类：＿＿＿＿＿，＿＿＿＿＿，＿＿＿＿＿，＿＿＿＿ ＿，＿＿＿＿＿。 3.高聚物性能的一个主要缺点是＿＿＿＿＿。 4. 复合材料的增强体材料常用＿＿＿＿＿、＿＿＿＿＿以及它们的粒子和片状物； 而常用的基体材料有＿＿＿＿＿、＿＿＿＿＿、＿＿＿＿＿、＿＿＿＿＿等。 5. 材料的工艺性能是指材料加工成零件的＿＿＿＿＿＿＿＿＿＿。 6. 从形态来看纳米材料可分为＿＿＿＿＿、＿＿＿＿＿、＿＿＿＿＿三种。 7.珠光体是＿＿＿＿＿和＿＿＿＿＿组成的两相机械混合物，常用符号＿＿＿＿ 表示。 8.常见的冷加工工艺有：＿＿＿＿、＿＿＿＿、＿＿＿＿、＿＿＿＿。 常见的热加工工艺有：＿＿＿＿、＿＿＿＿、＿＿＿＿、＿＿＿＿。 二、问答题（共70分） 1. （8分）简述枝晶偏析现象，如何消除枝晶偏析。 2. （5分）合金的相结构有哪几种？ 3. （5分）冷塑性变形对金属性能的影响表现在哪些方面？ 4. （5分）金属的冷热塑性加工的区别是什么？Fe 的冷热塑性加工的区别点是多 高？ 5. （8分）说明钢热处理时影响奥氏体形成的因素有哪些? 6. （5分）退火的目的有哪些？ 7. （8分）解释淬火并说明其目的。 8. （8分）解释冷处理并说明其目的。 9. （4分）根据钢与可控气氛间发生的化学反应情况可控气氛热处理的可控气氛有 哪几种？
一、填空 20% 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。
9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为
课程教学大纲 课程编号：G00TE1204 课程名称：凸优化及其在信号处理中的应用 课程英文名称：Convex Optimization and Its Applications in Signal Processing 开课单位：通信工程学院 教学大纲撰写人：苏文藻 课程学分：2学分 课内学时：32学时 课程类别：硕士/博士/专业学位 课程性质：任选 授课方式：讲课 考核方式：作业，考试 适用专业：通信与信息系统、信号与信息处理 先修课程： 教学目标： 同学应： 1.掌握建立基本优化模型技巧 2.掌握基本凸分析理论 3.掌握凸优化问题的最优条件及对偶理论 4.认识凸优化在信号处理的一些应用 英文简介： In this course we will develop the basic machineries for formulating and analyzing various optimization problems. Topics include convex analysis, linear and conic linear programming, nonlinear programming, optimality conditions, Lagrangian duality theory, and basics of optimization algorithms. Applications from signal processing will be used to complement the theoretical developments. No prior optimization background is required for this class. However, students should have workable knowledge in multivariable calculus, real analysis, linear algebra and matrix theory.
图论第三次作业 一、第六章 2.证明： 根据欧拉公式的推论，有m ≦l*(n-2)/(l-2), (1)若deg(f)≧4,则m ≦4*(n-2)/2=2n-4; (2)若deg(f)≧5,则m ≦5*(n-2)/3,即：3m ≦5n-10; (3)若deg(f)≧6,则m ≦6*(n-2)/4,即：2m ≦3n-6. 3.证明： ∵G 是简单连通图，∴根据欧拉公式推论，m ≦3n-6; 又，根据欧拉公式：n-m+φ=2,∴φ=2-n+m ≦2-n+3n-6=2n-4. 4.证明： (1)∵G 是极大平面图，∴每个面的次数为3， 由次数公式：2m==3φ, 由欧拉公式：φ=2-n+m, ∴m=2-n+m,即：m=3n-6. (2)又∵m=n+φ-2,∴φ=2n-4. (3)对于3n >的极大可平面图的的每个顶点v ，有()3d v ≥，即对任一一点或者
子图，至少有三个邻点与之相连，要使这个点或子图与图G 不连通，必须把与之相连的点去掉，所以至少需要去掉三个点才能使()(H)w G w G <-，由点连通度的定义知()3G κ≥。 5.证明： 假设图G 不是极大可平面图，那么G 不然至少还有两点之间可以添加一条边e ，使G+e 仍为可平面图，由于图G 满足36m n =-，那么对图G+e 有36m n '=-，而平面图的必要条件为36m n '≤-，两者矛盾，所以图G 是极大可平面图。 6.证明： (1)由()4G δ=知5n ≥当n=5时，图G 为5K ，而5K 为不可平面图，所以6n ≥，（由()4G δ=和握手定理有24m n ≥，再由极大可平面图的性质36m n =-，即可得6n ≥）对于可平面图有()5G δ≤，而6n ≥，所以至少有6个点的度数不超过5. (2)由()5G δ=和握手定理有25m n ≥，再由极大可平面图的性质36m n =-，即可得12n ≥，对于可平面图有()5G δ≤，而12n ≥，所以至少有12个点的度数不超过5. 二、第七章 2.证明： 设n=2k+1,∵G 是Δ正则单图，且Δ>0, ∴m(G)==>k Δ,由定理5可知χˊ(G)=Δ(G)+1.