第一章 图的基本概念
第一章图
教学安排的说明
章节题目：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算
学时分配：共2课时
本章教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈），会进行图的运算，会用图论的方法描述一些简单的实际问题．
其它：由于离散数学中已介绍过相关内容，本章以复习为主
课 堂 教 学 方 案
课程名称：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算
授课时数：2学时
授课类型：理论课
教学方法与手段：讲授法
教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈），
会进行图的运算，会用图论的方法描述一些简单的实际问题．
教学重点、难点：
（1） 理解图、简单图、子图以及图的同构等概念，并能够用图表示简单
的现实问题；
（2） 掌握途径、链和道路的概念及其区别；
（3） 理解图的连通性概念；
（4） 掌握图的四种运算。
教学内容：
第一章 图
§1.1图的概念
引例
例1.下面是五城市之间的航线图，若两城市间有航线，则连线，否则不连如图1.1（a ）：由图中可知，北京与广州间没有航线，而大连到上海间有航线
北京 大连 上海 广州 昆明 9 6 4 8 10 （a ） （b ）
图1.1
例2.数4，6，8，10，9五个数，若有公因子则连线，，否则不连，如上图1.1(b) 通常人们认为，过去我们所学的微积分是属于连续数学，而本章所要讨论的图论是离散数学的重要分支．
首先要注意，我们这里所讨论的图论中的“图”，并不是以前学过的通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统．也就是说，几何图形是表述物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系．因此在图论中，顶点之间的距离、弯曲、以及顶点间的位置关系都是无关紧要的，即图的概念是抽象化的,它是数学中经常采用的抽象直观思维方法的典型代表．
下面给出图作为代数结构的一个定义。
图的定义:一个图是一个三元组〈)(G V ，)(G E ，G ?〉，其中)(G V 是一个非空的点集合，)(G E 是有限的边集合，G ?是从边集合E 到点集合V 中的有序偶或无序偶的映射。
例3 图G =〈)(G V ，)(G E ，G ?〉，其中)(G V =},,,{d c b a ，)(G E =},,,,,{654321e e e e e e ，
),()(1b a e G =?，),()(2c a e G =?，),()(3d b e G =?，),()(4c b e G =?，),()(5c d e G =?，),()(6d a e G =?。
图1.2
由于在不引起混乱的情况下，图的边可以用有序偶或无序偶直接表示。因此，图也
可以简单的表示为：
,
G E
=
,其中，V是非空点集，E是连接点的边集。
若边i e与点无序偶
)
,
(
k
j
v
v
相关联，则称该边为无向边（Undirected Edge）。若边i e与
点有序偶
>
<
k
j
v
v,
相关联，则称该边为有向边（Directed Edge），其中j
v
称为i e的
起点（Initial Vertex），k v称为i e的终点（Terminal Vertex）。
定义：每一条边都是无向边的图称为无向图（Undirected Graph），每一条边都是有向边的图称为有向图（Directed Graph），本课主要介绍无向图
（无向图的定义）图的定义;一个图（Graph）G定义为一个偶对()
,V E
，记作
()
,
G V E
=
。其中：
1）V是一个集合，其中的元素称为顶点
2）E是无序积V V
?中的一个子集合，其元素称为边，
我们分别用
()
V G
和
()
E G
表示的G顶点集合与边的集合。如果
()
V G
和
()
E G
都是
有限集合，则称为G有限图。本书只研究有限图。
以下从边和顶点及其关系对图的有关基本概念加以介绍：
从“点”的角度考虑，
有限图中顶点的个数称作图的阶
没有任何边的图称为空图,记作φ,
只有一个顶点的图叫做平凡图.
在一个图中，不与任何点相邻接的点，称为孤立点（Isolated Vertex）。
关联于同一点的一条边称为自闭途径或环（Loop）。如图1.3中的1e与2e，1e与4e 是邻接边，5
e是环。
一个有p 个顶点和q 条边的图称为(),p q 图,一个(),p q 图,若它的p 个顶点标以不同的名称,则称为标定的,否则称为非标定的..
图1-3
二分划：图G 顶点集合()V G 分成两个不相交且并为()V G 的两个子集1V 和2V ,记为()12,V V
二部图：若G 有二分划()12,V V ，且G 的每一条边的一个端点在1V 中，另一个端点
在2V 中，则称G 为二部图，记作
()12,;G V V E =。 完全二部图：若()12,;G V V E =，12,,
V m V n ==且1V 中每一个点与和2V 中每一个点都邻接，则称G 为完全二部图，记作：,m n K
完全图:任意两个点间都有边相连的简单图称为完全图（Complete Graph ）。n 个点
的无向完全图记为n K 。显然n 个点的无向完全图n K 的边数为2n C 。图1-4分别给出
了1个点、2个点、3个点、4个点和5个点的无向完全图。
15K K -的图示
图1-4
图1-5
从“边”的角度考虑， 若连接同一对顶点的边数大于1，则称这样的边为多重边，其边数称为边的重数。 从“边”和“点”的关系考虑，
如图1.6(c)点A 与边AB 、AC 关联，点A 与点B 、C 邻接;边AB 与AC 邻接
含有重边的任何图，称为多重图（Multigraph ）。不含有重边和环的图称为简单图（Simple Graph ）。
(c)
图1-6
如图1-6()a 、(b )不是简单图,(c)不是简单图
从“度”的角度考虑，
图的同构
在图论中我们只关心点间是否有连线，而不关心点的位置和连线的形状。因此，对于给定的图而言，如果将图的各点安排在不同的位置上，并且用不同形状的弧线或直线表示各边，则可以得到各种不同图形。所以，由于这种图形表示的任意性，可能出现这样的情况：看起来完全不同的两种图形，却表示着同一个图。
图1-7
为了描述看起来不同，而其结构完全相同的图，引入了图的同构的概念。
图的同构：设>= >=<''',E V G 是两个图，如果存在着一一对应':V V →?使得E v v j i >∈<,（或E v v j i ∈),(）当且仅当')(),(E v v j i >∈ C B ' ))(),((E v v j i ∈??），，记作'G G ?。也称G 与'G 是同构的。显然图1-7是同构的。 通过定义可以看出，对于同构的图G 与'G 来说，存在着一一对应，将V 中的点对 应到' V 中的点，将E 中的边对应到'E 中的边，且保持着关联关系，即边e 关联着点i v 和j v ，当且仅当e 对应到'E 中的边'e 也关联着i v ，j v 对应到'V 中的点)(),(j i v v ??。在有向图的情况下，这种对应关系不但应该保持点间的邻接关系，而 且还应保持边的方向。 图1-9 同构图示例 图1-10 与群、格、布尔代数一样，利用这个等价关系可以把图分解成等价类，使得同类中的图相互同构，而不同类中的图互不同构。这样，我们就可以在图的同构类中选一个图来代表它们。由于图本质上与点和边的标记无关，因此，选出的这个图常常略去点和边的标记，这个图就称为无标记图。如图1-10所示的(a )、(b )、(c )、(d )四个图形均相互同构，它们属于同一个同构的等价类。而图1-10(d )就是该类的一个无标记图。 三、例题精讲 寻找一种简单而有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。 握手定理得应用 10个人参加会议，会后统计出各人的朋友数为 （ⅰ）3，3，3，3，5，6，6，6，6，6； （ⅱ）1，1，3，3，3，3，5，6，8，9. 证明:两组统计数据都有误. 【分析】该问题仅仅是统计每个人的朋友数，并且隐含了人与人之间或是朋友或不是朋友这种二元关系，这正好符合用图论方法研究问题的特征。可用10个点1021,,,A A A 表示这10个点，若两人是朋友关系，就在相应点之间联结一条边，从而可形成一个图，而每个人的朋友数就转化为相应顶点的度数。从而可以利用图论中关于顶点度数的有关概念和性质进行解决。 §1.2 子图 给定任意一个含有n 个点的图G ，我们总可以把它补成一个具有同样点的完全图，方法是把那些没有联上的边添加上去。 定义给定一个图G ，由G 中所有点和所有能使G 成为完全图的添加边组成的图，称为图G 相对于完全图的补图（Complement ），或简称为G 的补图，记作G 。 如图1-14中(a )和(b )互为补图。 图1-14 下面为了给出子图的概念，首先介绍图的两种操作。 删边：删去图G 的某一条边，但仍保留边的端点。 删点：删去图G 的某一点以及与该点所关联的所有的边。 例如，图1-16(a )删去边1e 和2e 后所得的图为图1-16(c )。图1-16(a )删去点4v 后所 得的图为图1-16(d )。 定义:设,G E =和,G E '''=是两个图。 （1）若E E ?'，V V ?'，则称'G 是G 的子图（Subgraph ）。 （2）若'G 是G 的子图，且E E ?'或V V ?'，则称'G 是G 的真子图。 （3）若E E ?'且V V ='，则称'G 是G 的生成子图或支撑子图（Spanning Subgraph ）。 （4）若'G 是G 的子图，且'G 中没有孤立点，则称'G 为图G 的由边集'E 导出的子图（Derived Subgraph ）。 （5）设V V ?'，在图G 中删去'V 中所有点后所得的图称为图G 的由点集'V V -导出的子图。 例如，图1-16 (b )、(c )、(d )都是图1-16(a )的子图，也是真子图。图1-16 (b )、 (c )是图1-16(a )的生成子图。图1-16(b )和图1-16(c )互为补图。图1-16(c )是图1-16(a )的由边集3456{,,,}e e e e 导出的子图，图1-16(d )是图1-16(a )的由边集136{,,}e e e 导出的子图。图1-16(d )是图1-16(a )的由点集136{,,}v v v 导出的子图。 图1-16 子图实际上就是从原来的图中适当地去掉一些点和边所形成的新图，它的点和边必须含在原来的图中，以反映图的局部。 §1.3顶点的度 在无向图>= 此外，我们记)}(|)(max{ )(G V v v d G ∈=?，)}(|)(min{)(G V v v d G ∈=δ，分别称为图>= 下面的定理是欧拉在1936年给出的，称为握手定理，它是图论中的基本定理。 定理 每个图中，点度数的总和等于边数的两倍。即∑∈V v v d )(=E 2 证明 因为每条边必关联两个点，而一条边给予关联的每个点的度数为1。因此，在一个图中，点度数的总和等于边数的两倍。 定理:在任何图中，度数为奇数的点必定是偶数个。 由于∑∈2)(V v v d 是偶数之和，必为偶数，而E 2是偶数，所以∑∈1)(V v v d 是偶数，而1V 为奇数度点的集合，故V v ∈?，)(v d 为奇数，但奇数个奇数之和只能为奇数，故1 V 是偶数。 例6 （1）已知图G 中有11 条边，1 个4 度点，4 个3 度点，其余点的度数均不大于2，问G 中至少有几个点？ （2）数列1,3,3,4,5,6,6 能否是一个无向简单图的度数列? 解:（1）由握手定理，G 中的各点度数之和为22，1 个4 度点，4 个3 度点共占去12 度,还剩6 度；若其余点全是2 度点，还需要3 个点，所以G 至少有8个点。 （2）如果存在这样一个无向简单图，那将它的一个6 度点去掉，得到的简单无向图的度数列为0，2，2，3，4，5； 再将这一图的5 度点去掉得到的简单图具有度 数列0，1，1，2，3。但这一图有3 个奇数度点，这与定理1.1.3相矛盾。 例7: 在一场足球比赛中，传递过奇数个球的队员人数必定为偶数个。 解把参加球赛的队员抽象为点，两个互相传球的队员用边相连，这样得到的图就是球赛中传递球的简单的数学模型，由定理即知结论正确。 §1.4 道路与连通性 一、路与回路的概念（视频课堂：路与回路的概念） 1，通路与通路的长度 设图G＝ 2．回路 起点和终点重合的通路． 3．边不重复的通路(回路)称简单通路(回路)；结点不重复的通路(回路)称基本通路(回路)． 4．有关图中路存在的结论 (1) 在具有n个结点的简单图G= (2) 在一个具有n个结点的图G= v j到结点v k必有一条长度小于n的通路． (3) 在具有n个结点的图G= (4) 在具有n个结点的图G= 例2 给定图G = (1)从A 到F 的所有简单通路； (2)从A 到F 的所有基本通路； (3)G 中两条简单回路和基本回路． 解 (1)简单通路(边不重复的通路)有： A (A , B )B (B , C )C (C , F )F ；A (A , B )B (B , E )E (E , F )F ； A (A , D )D (D , E )E (E , F )F ；A (A , D )D (D , E )E (E , B )B (B , C )C (C , F )F ． (2)基本通路(结点不重复的通路)有： A (A , B )B (B , C )C (C , F )F ；A (A , B )B (B , E )E (E , F )F ； A (A , D )D (D , E )E (E , F )F ；A (A , D )D (D , E )E (E , B )B (B , C )C (C , F )F ． (3)简单回路(边不重复的回路)有： A (A , B )B (B , E )E (E , D )D (D , A )A ；A (A , B )B (B , C )C (C , F )F (F , E )E (E , D )D (D , A )A ． 基本回路(结点不重复的回路(始点与终点除外))有： A (A , B )B (B , E )E (E , D )D (D , A )A ；A (A , B )B (B , C )C (C , F )F (F , E )E (E , D )D (D , A )A ． 在无向图（或有向图）的研究中，常常考虑从一个点出发，沿着一些边连续移动而到达另一个指定点，这种依次由点和边组成的序列，便形成了途径的概念。 在图的研究中，途径与闭途径是两个重要的概念，而图是否具有连通性则是图的一个基本特征。 定义:给定图,G E =，设0v ，1v ，…，m v V ∈，边1e ，2e ，…，m e E ∈，其中，i e 是关联于点1-i v ，i v 的边，交替序列0v 1e 1v 2e …m e m v 称为连接0v 到m v 的途径 (Walk)。称为()0,m v v 途径，0v 和m v 分别称为途径的起点(Initial Vertex)和终点(Terminal Vertex)，途径中边的数目称为该途径的长度。当0v =m v 时，称其为闭途径Circuit)。 由于无向简单图中不存在重复边与自闭途径，每条边可以由点对唯一表示，所以在无向简单图中一条途径0v 1e 1v 2e …m e m v 由它的点序列0v ，1v ，…，m v 确定，所以简单图的途径可以只用点序列表示表示为0v 1v …m v 。如图1-17()a 表示的简单图中，途径145ae be ce d 可写成abcd 。 在上述定义的途径与闭途径中，点和边不受限制，即点和边都可以重复出现。下面我们讨论途径与闭途径中点和边受限的情况。 定义:在一条途径中，若出现的所有的边互不相同，则称其为链；若出现的点互不相同，则称其为道路(Path)。 由定义可知，道路一定是链，但反之不一定成立。 定义:在一条闭途径中，若出现的所有的边互不相同，则称其为环路(Simple Circuit)；若链中除0v =m v 外，其余点均不相同，则称其为圈(Cycle)。长度为奇数的圈称为奇圈；长度为偶数的圈称为偶圈。 图1-17 例如在图1-17中，375625485v e v e v e v e v 是起点为5v ，终点为3v ，长度为4的一条途 径。24375625485v e v e v e v e v e v 是链但不是道路。321126584v e v e v e v e v 既是道路又是链。265732112v e v e v e v e v 是圈。 利用途径的概念可以解决很多问题，下面是一道智力游戏题。 例8 “摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？ 解 河左岸允许出现的情况有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）之间画一直线，得到图1-18 图1-18 这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的链。容易看出，只有两条链符合要求，即： （1）人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空； （2）人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。 对于链（1）的安排为：人带羊过河；人回来；带狼过河；放下狼再将羊带回；人再带菜过河；人回来；带羊过河。 对于链（2）的安排为：人带羊过河；人回来；带菜过河；放下菜再将羊带回；人再带狼过河；人回来；带羊过河。 上述的两种方案都是去4次、回3次，且不会再有比这更少次数的渡河办法了。 下面讨论图的连通性及相关性质。 定义:在无向图G 中，点u 和v 之间若存在一条途径，则称点u 和点v 是连通的 (Connected )。 如果认为点u 与其自身也是连通的，则G 中两点之间的连通关系是一个等价关系，在此等价关系下， 点集合V 可以形成一些等价类，不妨设等价类为21,V V ，…，n V ，使得点j v 和k v 是连通的，当且仅当它们属于同一个i V 。我们把子图)(1V G ，)(2V G ，…，)(n V G 称为图G 的连通分支(Connected Component )，我们把图G 的连通分支数记作()W G 。 二、连通、连通图及连通分支数的概念（视频课堂：连通、连通图及连通分支数的概念） 1．连通与连通图 无向图G 中，结点u , v 存在通路，则u , v 是连通的，G 中任意结点u , v 都是连通的，G 是连通图. 2．连通分支W (G ) 设G ＝ 注意：这里的等价类V 1，V 2，…，V m 是由结点间的连通关系（它是一种等价关系）对结点集V 作的一个划分，即可将结点集V 分成非空子集V 1, V 2,…,V m ，使得两个结点v j 与v k 是连通的，当且仅当它们属于同一个V i ．连通关系的商集为{V 1, V 2,…, V m }定义若图G 只有一个连通分支，则称图G 是连通图(Connected Graph)；否则，称图G 是非连通图或分离图(Disconnected Graph)。 五、实例 例1给定图G= 所选通（回）路都不一定是唯一的 (1) 长度为4的简单通路：v1 (v1, v4) v4 (v4, v3)v3 (v3,v7) v7 ( v7, v4)（边不重复的通路 (2)长度为5的基本通路：v1(v1, v5) v5(v5, v2)v2(v2, v6)v6(v6, v8)v8(v8, v4)v4(结点不重复的通 路) (3) 长度为7的回路：v1(v1, v4)v4(v4, v3)v3 (v3,v7)v7( v7, v8)v8(v8, v6)v6(v6, v5)v5(v5, v1)v1 (4)长度为5的基本回路：v1(v1, v5) v5(v5, v6) v6(v6,v7v7( v7, v4) v4(v4, v1)v1(除起点和终点外，结点不重复的通路 如图4中，找出结点v1到v4的路径、简单路径、基本路径，以及起点与终点均是v1的回路、简单回路与基本回路． [思路]按定义，路径是图中连接两个结点的点与边的交替序列．简单路径是一条经过的边均互不相同的路径．基本路径是一条经过的点均互不相同的路径．回路是终点与始点相重合的路径．简单回路是没有相同边的回路． 解结点v1到v4的路径有许多条，如有v1e2v3e5v4、v1e1v2e3v3e5v4、v1e2v3e3v2e1v1 e2v3e5 v4．只要起点是v1，终点是v4，按照图中的结点的连接关系找到的点与边系列均为v1到v4的路径． 结点v1到v4的简单路径有多条，如有v1e2v3e5v4、v1e1v2e3v3e5v4等，而路径v1e2v3e3 v2e1v1 e2v3e5v4．中因为有重复的边e2，所以不是简单路径． 结点v1到v4的基本路径有4条，即v1e2v3e5v4、v1e2v3e3v2e4v4、v1e1v2e4v4、v1e1v2e3 v3e5v4． 起点与终点均是v1的回路有无数条，如v1e2v3e3v2 e1v1、v1e2v3e3v2 e1v1 e2v3e3v2 e1v1等．只要起点与终点均是v1，按照图中的结点的连接关系找到的路径均为v1到v4的回路． 起点与终点均是v1的简单回路有多条，如v1e2v3e3v2 e1v1、v1e2v3e6v3e3v2 e1v1等，而回路v1e2v3e3v2 e1v1 e2v3e3v2 e1v1不是简单回路，因为其中有重复边e2． 起点与终点均是v1的基本回路有2条，即v1e2v3e3v2 e1v1、v1e2v3e5v4 e4v2 e1v1．简单回路v1e2v3e6v3e3v2 e1v1不是基本回路，因为其中有重复点v3 你完成这道题了吗？现在你可以点击[详解] 了解自己的分析是否正确. ． 例9 如图1-19所示，图1-19(a)是一个连通图，图1-19(b)是一个具有3个连通分支的非连通图。 图1-19 连通图和非连通图示例 每一个连通分支中任何两个点是连通的，而位于不同连通分支中的任何两个点是不连通的。即每一个连通分支都是原图的最大的连通子图。对于图的连通性，常 常由于删除了图中的点和边而影响了图的连通性。例如，在连通图1-20()a中，删除边e，则由图()a变成了图(b)，而图(b)不再是连通图。 图1-20 定义在图G中，点u到点v的最短道路的长度称为u到v的距离，记作 , d u v 。如 果u到v没有途径，则 , d u v =∞ +。它满足下列性质： ,0 d u v≥ ,0 d u u= ,,, d u v d v w d u w +≥ 。 第三章 多维随机变量及其分布习题答案 3. 220,(1)(1),4,(,),0.5940, x y x y e e c F x y --<<+∞?--==? ? 其它 . 4. 2012.4(2),()0,X x x x f x ≤≤?-=??，其它201 2.4(34),()0,Y y y y y f y ≤≤?-+=? ? 其它. 5. ???=,0,4),(y x f ,),(其它G y x ∈???+=,0,48)(x x f X ,05.0其它<≤-x ?? ?-=, 0,22)(y y f Y 其它10<≤y . 6. (1) (|)(1),0,1,;,m m n m n P Y m X n C p p n m n -===-=≤否则(|)0P Y m X n ===; (2)(,)(1)/!,0,1,;,m m n m n n P Y m X n C p p e n n m n λλ--===-=≤否则(|)0P Y m X n ===. 7. 10. ⑴0y ≥时|0 ,(|)0 0,x X Y x e f x y x -≥?=? 11. ⑴放回抽样 ⑵ 不放回抽样 X 的条件分布律与上相同，再结合联合分布律可以看出: 放回抽样时独立，不放回抽样时不独立。 12. 1c = ; 当10x -<<时，|1/2,||(|)0, Y X x y x f y x -<-?=? ? 其它 ; 当| |1y <时，|1/(1||),1|| (|)0,X Y y x y f x y --<<-?=? ? 其它 . 13. ⑴ (2|2)5/16,(3|0)1/5P X Y P Y X ====== ； ⑶ ⑷ . ;0.375 . 16. ? ? ?<≥-=--00 ,0,)1()(6/3/z z e e z f z z Z . 17. ⑴(2)30 3!,()00,t T t t e f t t ->?=?≤? ；⑵(3)50()00,t T t t e f t t ->?=?≤?. 第一节钢结构的一些基本概念 结构是由构件组成的 构件的种类：梁、柱、板、墙体、桁架、网架、悬索 变力性能：拉、压、弯、剪、扭、疲劳、裂缝扩展(断裂) 杆件系统：梁、柱、桁架、网架都属杆件系统 结构计算的内容包括： 强度 稳定 结构在静力或动力荷载作用下的变形 振动 疲劳 其中：强度，稳定和变形在结构设计中常要予以计算。振动是在设计跨度大而轻的楼层和楼梯时考虑，主要是防止因人行走或使用时结构产生令人不适的振动。疲劳计算仅在多次反复荷载下才予以考虑。 § 1 强度 强度：可指杆件的强度或结构的强度。 一．杆件的强度：杆件抵抗破坏的能力。 荷载引起的外力≤构件的承载力(由材料强度，构件截面的大小和形状确定) 影响因素： 荷载：大小，作用方式(拉、压、弯、剪、扭，静力或动力) 材料：屈服强度、极限强度、弹性模量等 构件截面的大小和形状：截面越大，承载力越大。粗绳比细绳能承受更大的拉力。 性层的两侧远方。因此工形截面的抗弯承载能力要比面积相同、宽度相等的矩形 沿Y轴方向，也就是抵抗绕X轴的弯曲(强轴弯曲)，有较大的强度，同时也有较 层沿Y轴。截面面积总是有效地分布在中性轴的两侧远方。 二、结构的强度：是结构抵抗破坏的能力。 结构是由杆件组成的，但结构中某根杆件的破坏并不一定意味着结构破坏。 结构的破坏与结构的稳定有直接关联，通常说结构失稳了就意味着结构破坏了。这个问题在结构稳定中再予以介绍。 § 2 刚度 简单结构或构件在荷载作用下的变形，可近似地表示为： △＝Q/B 式中△为结构或构件的变形，Q为荷载效应，B为结构或构件的刚度 由此可见，刚度愈大，变形愈小，刚度是衡量结构或构件抵抗变形的能力。 一、杆件的刚度：杆件抵抗变形的能力 轴向刚度：杆件抵抗轴向拉伸和压缩变形的能力 弯曲刚度：杆件抵抗弯曲变形的能力 扭转刚度：杆件抵抗扭转变形的能力 荷载引起的构件变形≤规范容许的构件变形值(通常以不影响结构正常使用为依据) 影响因素： 1．荷载：大小，作用方式(拉、压、弯、剪、扭)引起杆件相应的变形。 2．材料：弹性模量、屈服强度、屈服后材料的变形能力等。 3．杆件的长度、截面大小和形状：一般地说，杆件愈长，刚度愈小，变形愈大。例如，杆件在拉伸荷载作用下的轴向变形与杆件长度成正比，而 梁在跨中集中荷载作用下的挠度与梁长的三次幂成正比。截面尺寸愈小，杆件刚度愈小，变形愈大。截面形状对构件的强度有影响，对杆件刚度 第一章 图的基本概念 第一节 图和有向图 定义1.1 一个无向图图（graph ）G 是指一个二元组),(E V ，其中集合V 中的元素称为顶点（或点,或端点, 或结点）（or vertice, or node, or point), 集合E 中元素为V 中元素组成的无序对，称为边 (edge). 注意：1. 上述集合E 中的元素可以相同，有的文献称这样的集合为多重集。 2. 图),(??称为空图，它有时在举反例的时候用到，且有时将一个结论推广到包含空图时会引起不必要的麻烦, 故本书中假设所讨论的图都不是空图。 3. 在一个图=G ),(E V 中，为了表示V 和E 分别是G 顶点集合边集，常将V 和E 分别记为)(G V 和)(G E . 我们经常用图形来表示一个图。用小圆圈或实心点表示图的顶点，用线段把无序对中两个顶点连接起来表示边。其中顶点的位置，连线的曲直、是否相交等都无关紧要. 例如，=G ),(E V ，V =}{54321,,,,v v v v v ，=G }{),(),,(),,(),,(),,(),,(544231212111v v v v v v v v v v v v ，G 的图形如下. 3v 4v e 2 5v 1v 2v 1e 图. 1. 设=G ),(E V . 若V 为有限集，则称G 为有限图（finite graph ）；若V 为单点集，则称G 为平凡图 (trivial graph ). 为方便起见，常用e i 表示边，例如在图1中2e 表示边),(31v v , 而1v ,3v 称为2e 的端点. 两个顶点相同的边称为环 (loop), 具有相同顶点的多条边称为重边 (multiple edge), 不含环和重边的图称为简单图 (simple graph). 例如在图1中1e 为环, 32,e e 为重边，所以此图不是简单图. 定义1.2 设图G 的顶点集为)(G V ={}n v v v ,...,,21，边集为)(G E ={}m e e e ,...,,21.G 的邻接矩阵（adjacency matrix ）)(G A 是一个n n ?矩阵，元素j i a ,为端点的边的数目。G 的 第一章一些基本概念 讲课之前问问大家EXCELL用得怎么样？会使用公式编辑吗？ 调出上标、下标：工具→自定义→命令→格式→右边找到X2、X2拖出来 调出公式编辑器：工具→自定义→命令→插入→右边找到公式编辑器，拖出来 SPSS是“社会科学统计软件包”(Statistical Package for the Social Science)的简称,是一种集成化的计算机数据处理应用软件。SPSS是世界上公认的三大数据分析软件之一(SAS、SPSS和SYSTAT)。 §1.1 统计是什么？ ?统计是人类思维的一个归纳过程 ?站在一个路口，看到每过去20辆小轿车时，也有100辆自行车通过，而且平均每10个轿车载有12个人，于是，你认为小汽车和自行车在这个路口的运载能力为24:100 ?这是一个典型的统计思维过程 ?一般来说，统计先从现实世界收集数据（信息），如观测路口的交通，然后，根据数据作出判断，称为模型。模型是从数据产生的，模型也需要根据新的信息来改进。 ?不存在完美的模型，模型的最终结局都是被更能够说明现实世界的新模型所取代。统计学可以应用于几乎所有的领域: 精算，农业，动物学，人类学，考古学，审计学，晶体学，人口统计学，牙医学，生态学，经济计量学，教育学，选举预测和策划，工程，流行病学，金融，水产渔业研究，遗传学，地理学，地质学，历史研究，人类遗传学，水文学，工业，法律，语言学，文学，劳动力计划，管理科学，市场营销学，医学诊断，气象学，军事科学，核材料安全管理，眼科学，制药学，物理学，政治学，心理学，心理物理学，质量控制，宗教研究，社会学，调查抽样，分类学，气象改善，博彩等。 ?一句话， ?统计学（statistics）是用以收集数据，分析数据和由数据得出结论的一组概念、原则和方法。 ?以归纳为主要思维方式的统计，不是以演绎为主的数学。 ?统计可应用于各个不同学科，在有些学科已经有其特有的方法和特点；如生物统计(biostatistics)、经济计量学(econometrics)以及目前很热门的生物信息(bioinformation)和数据挖掘(Data Mining)的方法主体都是统计。 §1.2 现实中的随机性和规律性，概率和机会 ?从中学起，我们就知道物理学的许多定律，例如v=v0+at; F=ma等等 ?但是在许多领域，很难用如此确定的公式或论述来描述一些现象。 ?一些现象既有规律性又有随机性(randomness) ?肺癌患者中（主动或被动）吸烟的比例较大，这体现了规律性 ?而绝非每个吸烟的人都会患肺癌，这体现了随机性 ?再如，一般来说，白种人身材比黄种人要高些，这就是规律性 ?但对于具体的一个白人和一个黄种人，就很难说谁高谁矮了，这体现随机性 ?什么是概率(probability)？新闻中最常见的是“降水概率” ?从某种意义说来，概率描述了某件事情发生的机会。显然，这种概率不可能超过百分之百，也不可能少于百分之零。 ?概率是在0和1之间（也可能是0或1）的一个数，描述某事件发生的机会。 ?有些概率是无法精确推断的。比如你明天感冒的概率 第一章 基本概念 §1.1 集 合 1.指出下列各命题的真假. (1)}1{1∈; (2)}1{1?; (3)}1{1=; (4)}1{}1{∈; (5)}1{}1{?; (6)}}1{,1{}1{∈; (7)}1{∈?; (8)}1{??; (9)}1{??; (10)?∈?; (11)???; (12)???. 解 命题)1(,(5),(6),(8),(9)和(11)为真命题,其余都是假命题. 2.设},,,,,,,{h g f e d c b a U =,},,,{h e c a M =,},,,,{g f e d a N =,求N M , N M ,N M \,M N \,''N M ,''N M . 解 },,,,,,{h g f e d c a N M = ;},{e a N M = ;},{\h c N M =; },,{\g f d M N =; },,,,,{''h g f d c b N M = ;}{''b N M = . 3.设B A ,是两个集合,若B A B A =,证明:B A =. 证明 假设B A B A =.则A B A B A B B A B A A ?=??=? .因此B A =. 4.设C B A ,,是三个集合,若C A B A =,C A B A =,证明:C B =. 证明 考察任意的B x ∈:若A x ∈,则由C A B A =可知C x ∈;若A x ?,则由C A B A =可知C x ∈.由此可见,C B ?.同理可证,B C ?.所以C B =. 5.证明下列三命题等价: (1)B A ?;(2)A B A = ;(3)B B A = . 证明 我们有 B A A B A A A A B A =??=?? B B A B B B A B A =??=? )( B A ??. 所以命题(1),(2)和(3)两两等价. 6.设C B A ,,是三个集合,证明: (1))(\\B A A B A =; (2)B A B A A =)\(\; (3))\()\()(\C A B A C B A =; (4))\()\()(\C A B A C B A =; (5))(\)()\(C A B A C B A =; (6))(\)()\()\(B A B A A B B A =. 证明 (1)对于任意的元素x ,我们有 )(\\B A A x B A x A x B x A x B A x ∈??∈??∈?∈且且. 所以)(\\B A A B A = (2)对于任意的元素x ,我们有 B A x B x A x B A x A x B A A x ∈?∈∈??∈?∈且且\)\(\. 第十四章图的基本概念 14.1 图 (2) 一．无向图与有向图 (2) 1．无序积与多重集 (2) 2．无向图与有向图的定义及表示法 (2) 二．简单图与多重图 (4) 1．顶点的度数 (5) 2．握手定理 (5) 四．图的同构 (8) 1．两图同构的定义 (8) 2．图之间的同构关系是等价关系 (8) 五．完全图与正则图 (9) 1．完全图 (9) 2．正则图 (9) 六．子图与补图 (9) 1．子图 (9) 2．补图与自补图 (12) 14.2 通路与回路 (15) 一．通路与回路的定义 (15) 二. n阶图中通路与回路的性质 (17) 14.3 图的连通性 (17) 一、无向图的连通性 (17) 二、无向图中顶点之间的线程线及距离 (18) 三、无向图的连通度 (18) 四、有向图的连通性及其分类 (20) 五、扩大路径法及极大路径 (21) 六、二部图及判别定理 (22) 14.4 图的矩阵表示 (26) 一、无向图与有向图的关联矩阵 (26) 二、有向图的邻接矩阵 (27) 三、有向图的可达矩阵 (29) 典型习题 (29) 14.5 图的运算 (33) 14.1 图 主要内容 无向图与有向图。 简单图与多重图。 顶点的度数与握手定理。 图的同构。 完全图与正则图。 子图与补图。 学习要求 熟练掌握握手定理及其推论的内容及其应用。 掌握图同构的概念。 加深对简单图、完全图、正则图、子图、补图等概念的理解。 一．无向图与有向图 1．无序积与多重集 设A，B为任意的两个集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B. 为方便起见，将无序积中的无序对{a,b}记为(a,b),并且允许a=b.需要指出的是，无论a,b是否相等，均有(a,b)=(b,a),因而A&B=B&A. 元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2,3,1,1. 2．无向图与有向图的定义及表示法 定义14.1一个无向图是一个有序的二元组 第一章 热力学基本概念 英文习题 1. Expressing temperature rise in different units During a heating process, the temperature of a system rises by 10℃. Express this rise in temperature in K, ℉ and R. 2. Absolute pressure of a vacuum chamber A vacuum gage connected to a chamber reads 5.8 psi at location where the atmosphere pressure is 14.5 psi. Determine the absolute pressure in the chamber. 3. Measuring pressure with a manometer A manometer is used to measure the pressure in a tank. The fluid used has a specific gravity of 0.85, and the manometer column height is 55 cm, as shown in Fig.1-1. If the local atmospheric pressure is 96 kPa, determine the absolute pressure within the tank. 4. Measuring pressure with a multi-fluid manometer The water in a tank is pressurized by air, and the pressure is measured by a multi-fluid manometer as shown in Fig. 1-2. The tank is located on a mountain at an altitude of 1400 m where the atmospheric pressure is 85.6 kPa. Determine the air pressure in the tank if h 1=0.1 m, h 2=0.2 m, and h 3=0.35 m. Take the densities of water, oil, and mercury to be 1000 kg/m 3, 850 kg/m 3, and 13 600 kg/m 3 respectively. 5. Effect of piston weight on pressure in a cylinder The piston of a vertical piston-cylinder device containing a gas has a mass of 60 kg and a cross-sectional area of 0.04 m 2, as shown in Fig.1-3. The local atmosphere pressure is 0.97 bar, and the gravitational acceleration is 9.81 m/s 2. (a) Determine the pressure inside the cylinder. (b) If some heat is transferred to the gas and its volume is doubled, do you expect the pressure inside the cylinder to change? 6. Burning off lunch calories A 90-kg man had two hamburgers, a regular serving of French fries, and a 200-ml Coke for lunch. Determine how long it will take for him to burn the lunch calories off (a) by watching TV and (b) by fast swimming. What would your answers be for a 45-kg man? 7. Burning of a candle in an insulated room A candle is burning in a well-insulated room. Taking the room (the air plus the candle) as the system, determine (a) if there is any heat transfer during this FIGURE 1-1 FIGURE 1-2 FIGURE 1-3 FIGURE 1-4 图论与网络流理论 （Graph Theory and Network Flow Theory） 高随祥 中科院研究生院专业基础课 学时/学分：60/3 本课程适合基础数学、应用数学、计算数学、运筹学与控制论、概率论与数理统计各专业的硕士学位研究生作为专业基础课，也可供物理学、化学、天文学、地学、生物科学、计算机科学与技术、计算机软件、管理科学与工程以及通信、信号等学科专业的硕士研究生选修。主要讲授图论与网络流理论的基本概念、方法和定理，介绍该领域重要的问题以及典型的算法，展示图论与网络流模型及方法的广泛应用。为学习者将来从事有关方面的理论研究打下基础，也为进行应用性研究提供一种有力的工具。 内容提要 第一章 图的基本概念 图的基本概念；二部图及其性质；图的同构；关联矩阵与邻接矩阵。 路、圈与连通图；最短路问题。 树及其基本性质；生成树；最小生成树。 第二章 图的连通性 割点、割边和块；边连通与点连通；连通度；Whitney定理；可靠通信网络的设计。 第三章 匹配问题 匹配与最大匹配；完美匹配；二部图的最大匹配；指派问题与最大权匹配。 第四章 欧拉图与哈密尔顿图 欧拉图；中国邮递员问题；哈密尔顿图；旅行商问题。 第五章 支配集、独立集、覆盖集与团 支配集、点独立集、点覆盖集、边覆盖集与团的概念及其求法。 第六章图的着色问题 点着色；边着色；平面图；四色猜想；色多项式；色数的应用。 第七章网络流理论 有向图；网络与网络流的基本概念；最大流最小割定理；求最大流的标号算法；最小费用流问题；最小费用最大流；网络流理论的应用。 主要参考书 [1] J.A. Bondy and U.S. Murty, Graph theory with applications, 1976, 有中译本（吴望名等译）。 [2] B.Bollobas, Modern graph theory (现代图论)，科学出版社，2001。 [3] 蒋长浩，图论与网络流，中国林业出版社，2001。 [4] 田丰，马仲蕃，图与网络流理论，科学出版社，1987。 [5] 徐俊明，图论及其应用，中国科技大学出版社，1998。 [6] 王树禾，图论及其算法，中国科技大学出版社，1994。 [7] 殷剑宏，吴开亚，图论及其算法，中国科技大学出版社，2003。 考核方式：平时成绩＋期末闭卷笔试 第一章图 教学安排的说明 章节题目：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算 学时分配：共2课时 本章教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈），会进行图的运算，会用图论的方法描述一些简单的实际问题． 其它：由于离散数学中已介绍过相关内容，本章以复习为主 课 堂 教 学 方 案 课程名称：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算 授课时数：2学时 授课类型：理论课 教学方法与手段：讲授法 教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈）， 会进行图的运算，会用图论的方法描述一些简单的实际问题． 教学重点、难点： （1） 理解图、简单图、子图以及图的同构等概念，并能够用图表示简单 的现实问题； （2） 掌握途径、链和道路的概念及其区别； （3） 理解图的连通性概念； （4） 掌握图的四种运算。 教学内容： 第一章 图 §1.1图的概念 引例 例1.下面是五城市之间的航线图，若两城市间有航线，则连线，否则不连如图1.1（a ）：由图中可知，北京与广州间没有航线，而大连到上海间有航线 北京 大连 上海 广州 昆明 9 6 4 8 10 （a ） （b ） 图1.1 例2.数4，6，8，10，9五个数，若有公因子则连线，，否则不连，如上图1.1(b) 通常人们认为，过去我们所学的微积分是属于连续数学，而本章所要讨论的图论是离散数学的重要分支． 首先要注意，我们这里所讨论的图论中的“图”，并不是以前学过的通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统．也就是说，几何图形是表述物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系．因此在图论中，顶点之间的距离、弯曲、以及顶点间的位置关系都是无关紧要的，即图的概念是抽象化的,它是数学中经常采用的抽象直观思维方法的典型代表． 下面给出图作为代数结构的一个定义。 图的定义:一个图是一个三元组〈)(G V ，)(G E ，G ?〉，其中)(G V 是一个非空的点集合，)(G E 是有限的边集合，G ?是从边集合E 到点集合V 中的有序偶或无序偶的映射。 例3 图G =〈)(G V ，)(G E ，G ?〉，其中)(G V =},,,{d c b a ，)(G E =},,,,,{654321e e e e e e ， ),()(1b a e G =?，),()(2c a e G =?，),()(3d b e G =?，),()(4c b e G =?，),()(5c d e G =?，),()(6d a e G =?。第一章 概率论的基本概念习题答案
第一节 钢结构的一些基本概念
图的基本概念
第一章 一些基本概念
第一章 基本概念
离散数学结构 第14章 图的基本概念
第一章 热学基本概念
图论讲义第1章-图的概念
第一章 图的基本概念