图论2017答案电子科大

2005年研究生期末试题(120分钟)

《图论及其应用》

一、填空(15分，每空1分)

1、 已知图G有10条边，4个度数为3的顶点，其余顶点的度数均小于2，则

G中至少有___8___个顶点 .

2、 m条边的简单图G中所有不同的生成子图(包括G和空图)的个数为

__2m____.

3、 4个顶点的非同构的简单图有__11___个. 4、 图G1的最小生成树各边权值之和为__28___.

4 7 6 4 1 6 5 3 9

2 1

5 10 图G1

5、若W是图G中一条包含所有边的闭通道，则W在这样的闭通道中具有最短长度的充要条件是：

(1) 每一条边最多重复经过_1__次；

(2) 在G的每一个圈上，重复经过的边的数目不超过圈的长度的_一半___.

5,__C15___. 6、5阶度极大非哈密尔顿图族有__C27、在图G2 中，图的度序列为(44443322)，频序列为(422)，独立数为3，

团数为4，点色数为4，边色数为4，直径为3.

图G2

二、选择(15分)

(1)下列序列中，能成为某简单图的度序列的是( C )

(A) (54221) (B) (6654332) (C) (332222)

（2

2005年研究生期末试题(120分钟)

《图论及其应用》

一、填空(15分，每空1分)

1、 已知图G有10条边，4个度数为3的顶点，其余顶点的度数均小于2，则

G中至少有___8___个顶点 .

2、 m条边的简单图G中所有不同的生成子图(包括G和空图)的个数为

__2m____.

3、 4个顶点的非同构的简单图有__11___个. 4、 图G1的最小生成树各边权值之和为__28___.

4 7 6 4 1 6 5 3 9

2 1

5 10 图G1

5、若W是图G中一条包含所有边的闭通道，则W在这样的闭通道中具有最短长度的充要条件是：

(1) 每一条边最多重复经过_1__次；

(2) 在G的每一个圈上，重复经过的边的数目不超过圈的长度的_一半___.

56、5阶度极大非哈密尔顿图族有__C2,__C15___.

7、在图G2 中，图的度序列为(44443322)，频序列为(422)，独立数为3， 团数为4，点色数为4，边色数为4，直径为3.

图G2

二、选择(15分)

(1)下列序列中，能成为某简单图的度序列的是( C )

(A) (54221) (B) (6654332) (C) (332222)

（2

习题一

1. （题14）：证明图1-28中的两图是同构的 图1-28

证明 将图1-28的两图顶点标号为如下的(a)与(b)图

u1 v1

u6 u5 v6 v10 v5 v2 u2 u8 v7 u10 u3 v8 v9 u4 u u 79 v4 v3 (b) (a)

作映射f : f(vi)?ui (1? i ? 10)

容易证明，对?vivj?E((a)),有f(vivj)?uiuj?E((b)) (1? i ? 10, 1?j? 10 ) 由图的同构定义知，图1-27的两个图是同构的。

?n?2. （题6）设G是具有m条边的n阶简单图。证明：m =??2??当且仅当G是

??完全图。

证明 必要性 若G为非完全图，则? v?V(G),有d(v)? n-1 ? ? d(v) ? n(n-1) ? 2m?n(n-1)

?n?? m ? n(n-1)/2=??2??, 与已知矛盾！

???n? 充分性 若G为完全图，则 2m=? d(v) =n(n-1) ? m= ??2??。

??3. （题9）证明：若k正则偶图具有二分类V= V1∪V2，则 | V1| = |V2|。

证

★★电子科技大学师资现状＆近几年各学院人才引进情况★★

电子科技大学师资队伍建设这几年力度很大，现把我所了解的情况贴出来。 欢迎大家讨论，并请知情者补充。

电子科技大学师资总揽：

一、教职工3200余人，专任教师1700余人,博士导师243人，教授290人，副教授612人

二、院士：6名

中国科学院院士：刘盛纲 林为干 陈星弼 李小文 李朝义 | 中国工程院院士：李乐民

三、IEEE(OSA) Fellow 4名 刘盛纲 柳清伙 李烨 郑建成

四、长江学者：15名

特聘教授饶云江（1999年）李小文（2000年）张怀武（2001年）刘新芝（2001年）李言荣（2004年）刘濮鲲（2004年）谢 康（2004年）蒋亚东（2005年）潘和平（2000年）尧德中（2006年） 讲座教授李 烨（2005年）柳清伙（2005年）肖 强（2005年）郑建成（2006年）王平安（2006年）

五、国家杰出青年科学基金获得者：9名

唐小我（1997年）饶云江（2000年）刘濮鲲（2001年）张怀武（2004年）李言荣（2004年）蒋亚东（2004年）谢 康（2005年）尧德中（2005年）马建国（2006年）

六、新世纪百千万人才工程：9名

数值分析实验作业

实验报告

一、实验内容:

（1）对高阶多多项式

20

p(x) (x 1)(x 2) (x 20)

(x k)

k 1

编程求下面方程的解

p(x) x

19

0

并绘图演示方程的解与扰动量 的关系。

（2）对n 2~20，生成对应的Hilbert矩阵，计算矩阵的条件数；通过先确定解获得常向量b的方法,确定方程组

Hnx b

最后，用矩阵分解方法求解方程组，并分析计算结果。 （3）对函数

f(x)

11 25x

2

x [ 1,1]

的Chebyshev点

xk cos(

(2k 1) 2(n 1)

)

k 1,2,...,n 1

编程进行Lagrange插值，并分析插值结果。

二、实验过程：

实验一： a. 实验方案：

先创建一个20*50的零矩阵X，然后利用Matlab中的roots（）和poly（）函数将50个不同的ess扰动值所产生的50个解向量分别存入X矩阵中。然后再将ess向量分别和X的20个行向量绘图。即可直观的看出充分小的扰动值会产生非常大的偏差。即证明了这个问题的病态性。

b. 实验程序： >> X=zeros(20,50); >> ve=zeros(1,21);

>> ess=linspace(0,0.00001,50);k=1;

数值分析实验作业

实验报告

一、实验内容:

（1）对高阶多多项式

20

p(x) (x 1)(x 2) (x 20)

(x k)

k 1

编程求下面方程的解

p(x) x

19

0

并绘图演示方程的解与扰动量 的关系。

（2）对n 2~20，生成对应的Hilbert矩阵，计算矩阵的条件数；通过先确定解获得常向量b的方法,确定方程组

Hnx b

最后，用矩阵分解方法求解方程组，并分析计算结果。 （3）对函数

f(x)

11 25x

2

x [ 1,1]

的Chebyshev点

xk cos(

(2k 1) 2(n 1)

)

k 1,2,...,n 1

编程进行Lagrange插值，并分析插值结果。

二、实验过程：

实验一： a. 实验方案：

先创建一个20*50的零矩阵X，然后利用Matlab中的roots（）和poly（）函数将50个不同的ess扰动值所产生的50个解向量分别存入X矩阵中。然后再将ess向量分别和X的20个行向量绘图。即可直观的看出充分小的扰动值会产生非常大的偏差。即证明了这个问题的病态性。

b. 实验程序： >> X=zeros(20,50); >> ve=zeros(1,21);

>> ess=linspace(0,0.00001,50);k=1;

电子科大《信号与系统》答案

电子科大信号与系统答案

Chapter 2

2.1 Solution:

Because x[n]=(1 2 0 –1)0, h[n]=(2 0 2) 1, then

(a).

So, y1[n] 2 [n 1] 4 [n] 2 [n 1] 2 [n 2] 2 [n 4]

(b). according to the property of convolutioin:

y2[n] y1[n 2]

(c). y3[n] y1[n 2]

2.3 Solution:

y[n] x[n]*h[n]

k

x[k]h[n k]

1k 2()u[k 2]u[n k 2] k 2

n 2

11

()0 ()(n 2) 2 1

1 ()k 2u[n] u[n]

1k 221 2

1

2[1 ()n 1]u[n]

2

the figure of the y[n] is:

2.5

Solution:

电子科大《信号与系统》答案

We have known: x[n] Then,

....0 n 9....0 n N 1， 1，

, h[n] ,(N 9)

....elsewhere....elsewhere 0， 0，

x[n] u[n] u[n 10], h[n] u[n

考研

信号与系统

Signals and systems

第四章 连续时间信号与系统的傅立叶分析 Fourier analysis of continuous time signals and systems1

考研

4.1 LTI连续时间系统的频率响应LTI系统

f (t )

h(t )

y (t )

F f (t ) F ( )

F y (t ) Y ( )

LTI连续时间系统的线性常系数微分方程描述：y ( N ) (t ) aN 1 y ( N 1) (t ) a1 y (1) (t ) a0 y(t ) bM f ( M ) (t ) b0 f (t )

(4.1.1)时域微分特性( j ) N Y ( ) aN 1 ( j ) N 1Y ( ) a0Y ( ) bM ( j ) M F ( ) b0 F ( )2

考研

4.1 LTI连续时间系统的频率响应LTI系统

f (t )

h(t )

y (t )

y ( N ) (t ) aN 1 y ( N 1) (t ) a1 y (1) (t ) a0 y(t ) bM f ( M )

一、第1章软件工程概述

1. Software deteriorates rather than wears out because(软件通常是变坏而不是磨损的原因是)

A:Software suffers from exposure to hostile environments(软件暴露在不利的环境中)

B:Defects are more likely to arise after software has been used often(软件错误更容易在使用后被发现)

C:Multiple change requests introduce errors in component interactions(在组件交互中需求发生变化导致错误)

D:Software spare parts become harder to order(软件的备用部分不易组织) 2. Today the increased power of the personal computer has brought about an

abandonment of the practice of team development of software.(

第9组

京沪线客货列车调度的优化模型

摘要 本文通过合理的假设，设计出客货车安全运行的计算规则，建立了京沪线客货车调度的优化模型。

首先，在模型一中，对现行列车时刻表进行分析，按照安全要求，确定目标函数，制定约束条件，确定可行域，找出最优解，从而得出从济南到徐州段的下行线最多可安排货车79列，上行60列。并绘制出相应的“列车运行图”。

其次，在模型二中，我们建立了增开临时客车的线性规划模型。用隐枚举法求解得到北京至上海、北京至南京、天津至上海、北京至合肥、天津至青岛的五对临时客车在京沪线区间的列车时刻表及运行图。

最后，在模型三中，对列车晚点问题进行实时的调度。我们采用分类讨论法，按速度不同将列车分成四类，确定不同列车组的调度方案，选取从北京驶出的T25至K101/104共5辆列车进行模型检验，并就该调度方案的实际意义进行了分析。

我们对上述三个模型进行了评价，并给出了模型的改进方向。

第 1 页 共 17 页

第9组

一、问题分析

我国铁路自1997年以来先后进行了5次大提速，以前客车的最高时速为60至80公里/小时,到2004年