|
《组合网络理论》教学大纲
(
2008
年09月01日
--
2009年01月16日)
本课程大纲以《组合网络理论》（徐俊明，科学出版社，2007）为依据。课堂教学以概念和理论为主，介绍组合网络的基本问题、方法和理论。课后安排少量必作习题，课堂未涉及的部分均为自学内容。通过此课程的学习，了解和掌握组合网络的基本概念、理论和方法，学会将网络问题转化为图论问题，提高发现问题和解决问题的能力,着手介入研究工作。为确保达到这个目的，课余预习、复习思考和自学时间应不少于课堂教学时间的2倍。请关注有关通知。
1).
开课，导引，课程意义，国内外理论研究和应用进展，最主要的参考书和参考杂志。
2).
内容是第一章。掌握网络拓扑结构与图的关系，了解度量网络拓扑结构性能的图论参数和图论概念和参数的网络意义。复习将在本课程用到的基本图论概念和结果。本章分两次课，主要是课后复习，重点是新概念。
3).
内容是第1章（续）。平均距离，子图嵌入，路由选择，容错性与连通度。网络设计原则。
4).
内容是第2章(分1.5次课完成)，线图方法，基本性质和一些著名网络拓扑的设计。重点掌握线图连通度和直径的结论，Euler性和Hamilton性之间的关系，多重线图的概念、性质和论证方法。
5).
内容是第3章（分2.5次课完成）。无向线图的边连通度和点可迁图。
6).
内容是第3章。边可迁图，图的原子和点可迁图的连通度。重点掌握边可迁与点可迁之间的关系，图的原子结构性质，可迁图连通度的基本结果。
7).
内容是第3章（续）。Cayley方法，基本性质和一些著名网络拓扑的设计。重点掌握Cayley图的概念的基本性质，Cayly图的原子和连通度基本结果及其论证方法。
8).
内容是第4章（分2次课完成）。笛卡儿乘积方法，基本性质和一些著名网络拓扑的设计。重点掌握笛卡儿乘积基本性质、连通度和直径及其论证方法。
9).
内容是第4章（续）。重点掌握可迁图和Cayley图的笛卡儿乘积性质,一些著名的网络。
10).
内容是第5章，网络拓扑设计的一个基本问题－（d, k）问题。重点了解无向图和有向图的(d,
k) Moore界及其相关的论证方法。
11).
内容是第6章，超立方体网络。重点掌握超两个等价定义、基本性质、连通度、直径、路长、2叉数的嵌入及其论证方法，几种广义超立方体网络的定义及其基本性质。分两次课完成。
12).
内容是第6章（续）。
13).
内容是第7章，De Bruijn网络。重点掌握三个等价定义、基本性质、连通度、直径、路长及其论证方法。分两次课完成。
14).
内容是第7章（续）。
15).
内容是第8章，Kautz网络。重点掌握超三个等价定义、基本性质、连通度、直径、路长及其论证方法。
16).
内容是第9章，重点是双环网络的设计中的问题和几何方法。
17).
内容是第11章，网络中路由选择。重点掌握度量路由选择优劣的两个参数：点转发指数和边转发指数和它们的基本结果及其论证方法。分2次课完成。
18).
内容是第11章（续）。重点掌握度量容错网络中路由选择优劣的一个参数：路由延迟，和它们的基本结果及其论证方法。
19).
内容是第12章，网络中的边添加问题。重点掌握路中添加边问题的网络背景、基本结果和论证方法。
20).
内容是第12章，网络中的边减少问题。边容错直径，确定边容错直径的两个参数f(t,k)和g(t,k)，它们的基本结果和它们与边增加问题之间的关系。点容错直径问题。
21).
内容是第13章，并行系统网络中Menger型问题。重点掌握有界路长、Menger数、有界连通度和Rabin数概念的网络背景和基本结果及其论证方法。分2次课完成。
22).
内容是第13章（续）。
23).内容是第14章，网络宽直径。重点掌握宽直径的概念、网络背景和基本结果及其论证方法。的分2次课完成。
24).
内容是第14章（续）。
25).
内容是第15章，并行系统网络中(l, w)独立数和(l, w)控制数。重点掌握其概念、网络背景和基本结果及其论证方法。
26).
内容是第15章（续）。
27).
内容是第16章，网络的限制连通度。重点掌握边限制连通度的概念、网络背景和点可迁图基本结果及其论证方法。分2次课完成。
28).
内容是第16章（续）。
29).
期终总结。布置期终复习和考试事宜。
期终考试时间：2009年01月06日（星期二）下午2：30-4：30；考试地点：数学系15008教室。
|
