R
记 为 G＝ （ V， E）
华北电力大学电子与信息工程学院
2004-07-29
第5/14页
5. 什么是端点，何谓关联 端点
通信网理论基础
如有有一条边
e k 与点对 ( v i , v j ) 相对应， e k (v i , v j )
则 v i , v j 是 e k 的端点，记为
关联
如果 e k ( v i , v j )， 则称 v i , v j 与边 e k 关联
e1
0 1 1 0
e
2
0 1 1 0
e3
1 0 1 0
e
4
0 0 1 1
e5
1 0 0 1
e6
华北电力大学电子与信息工程学院
2004-07-29
第26/14页
17. 什么是网络，何谓容量
通信网理论基础
网络:
设 N (V , E ) 为有向图 .它有两个不相交的顶点 其中 , x 中的顶点称为源 , y 中的顶点称为宿 子集 : x , y . , 其他顶点称为中间顶点 C , 称 N 为一个网络 . .
v1
R 时，则称
G 为无向图
e1 e2
e6
e3
v2
v4
e4
e5
v3
华北电力大学电子与信息工程学院
2004-07-29
第8/14页
8. 什么是有向图
通信网理论基础
设图 G (V , E )。当 v i 对 v j 存在某种关系 不等价于 v j 对 v i 存在关系 R 时，则称
R
G 为有向图 (vi , v j ) (v j , vi )
V ' V , E ' E 称 G ' 是 G 的子图 : G ' G
真子图
生成子图
设 G ' G , 但 E ' E . 称 G ' 为 G 的真子图
包含原图所有端点的子图
最大连通子图
若G’是图G的一个连通子图.若再加上属于原图G中的任何一 个其他元素,图G’就失去了连通性,成为非连通图.则G’为图G 的最大连通子图
G
华北电力大学电子与信息工程学院
2004-07-29
第25/14页
16.9 求下图的基本割集矩阵 例子（有向图）
通信网理论基础
v1
e6 4 .7
3 .5
v4
e1 v2
5
e4 e2 5 .6 e3 7 G2
e5 4 v3
v1 1 v2 1 A0 ( G 2 ) v3 0 v4 0
1简述通信系统的模型,并简要介绍各部分的作用
通信网理论基础
信源
变换器
信道
反变换器
信宿
噪声
信 变换器－信号适合在信道中传输 噪声源－各种干扰等效结果 信 道－信号传输媒质 2004-07-29 第1/14页 信 宿－信息接收者 源－信息源
反变换器－适合接收者
华北电力大学电子与信息工程学院
2.1简述通信网基本结构及其特点
S 2 {e 3 , e 2 }
S 4 {e 6 , e 2 , e5 }
S 3 {e 4 , e5 }
华北电力大学电子与信息工程学院
2004-07-29
第24/14页
16.8 求下图的基本割集矩阵 例子（无向图）
v1 e1
3
通信网理论基础
8 .5 e5
1 0 e7 6 8
v2 5 e2 v3
即图 G 中任一条边
e k 对应一有序点对
v1
e1 e2
e6
e3
v2
v4
e4
e5
v3
华北电力大学电子与信息工程学院
2004-07-29
第9/14页
9. 什么是有权图
通信网理论基础
7.有权图
设图 G (V , E )，每 1条边 e k 或者每个端点 p k 称为权值
v1
v i 赋以一个实数
p k。
非连通图
e1 是 割 边 集
不
{e5 }
{ e1 , e 5 } 是
再看 { e1 , e 5 }的真子集之
e1
割集
e2
e5 e6 e3
非连通图
e5
不
是割边集
2004-07-29 第23/14页
华北电力大学电子与信息工程学院
16.7 求下图的基本割集.续
通信网理论基础
同理，求得基本割集:
S 1 { e1 , e 5 }

个人化：任何人、任何地点、任何时间
华北电力大学电子与信息工程学院
2004-07-29
第4/14页
4. 什么是图
通信网理论基础
设 有 端 点 集 V {v 1 , v 2 , , v n } 和 边 集 当 存 在 关 系 R， 使 得
E { e1 , e 2 , , e m }
V V E 成 立 时 ， 则 说 由 端 点 集V 和 边 集 E 组 成 图 G ，
华北电力大学电子与信息工程学院
2004-07-29
第13/14页
13. 何谓树，树枝，树干，树尖和有根树
通信网理论基础
任意两端间有且只有一条径的图称为树
树枝(branch):树中的边
树干:树枝的两个端点都至少 与两条边关联 树尖:树枝的一个端点(称为树 叶)仅与此边关联
树根
树干
有根树:指定树中的一个节点
华北电力大学电子与信息工程学院
2004-07-29
第7/14页
7. 什么是无向图
通信网理论基础
设图 G (V , E )。当 v i 对 v j 存在某种关系 即图 G 中任一条边 e k 对应一无序点对
R 等价于 v j 对 v i 存在关系 (vi , v j ) (v j , vi )
v1
通信网理论基础
v1
例:避圈法求解下 图的一棵生成树
v1
v2
v3
v4
v2
v3
v4
v5
v6
v5
v6
v1
不 出
v3
v1
v2
v3
v4
v2
v4
现 回 路
v2
v3
v4
v5
v6
v5
v6
v5
v6
v1
v1
v2
v3
v4
v2
v3
v4
v5
v6
华北电力大学电子与信息工程学院
2004-07-29
v5
v6
第17/14页
16.1 求下图的基本割集
( 2 ) 对所有的中间顶点
e6
v5 6 .4 e4
v4
e3
1
v1 1 v2 1 A0 ( G 1 ) v 3 0 v4 0 v5 0
e1
0 1 1 0 0
e2
0 0 1 1 0
e3
0 0 0 1 1
e4
1 0 0 0 1
e5
1 0 1 0 0
e6
1 0 0 1 0
e7
在边集 E ( N ) 上定义一个取非负整数
值的函数
函数 C 称为 N 的容量函数
, 函数 C 在边 e ij ( v i , v j )的值称为边 , C (i, j ) C ( j, i )
e ij 的容量 ,
记为 C ( e ij ) 或者 C ( i , j ). 一般而言
华北电力大学电子与信息工程学院
通信网理论基础
网形网 任 意 2个 节 点 间 均有线路相连 冗余度较大、稳定 性较好 线路利用率不高、 经济性较差
网孔形网 不完全的网形 网。大部分节点 间均有线路相连 线路利用率、经 济性改善 稳定性下降
星形网 辐射网，一个节点 作为辐射点，其余 节点均与之相连 传输链路少 稳定性差（中心节点 是瓶颈）
G T {e 2 , e 5 }
e1
e2
e5 e6 e3
非连通图
e4
{ e1 , e 5 } 是 割 边 集
是割集
华北电力大学电子与信息工程学院
2004-07-29
第22/14页
16.6 求下图的基本割集.续
首先看 { e 1 , e 5 }的真子集之
e1
通信网理论基础
{ e1 }
e2
e5 e6 e3
复合形网 网形网和星形网 复合而成
兼具网形网和星形 网的优点，常用
华北电力大学电子与信息工程学院
2004-07-29
第2/14页
2.2简述通信网基本结构及其特点.
通信网理论基础
总线形网 所有节点都连接 在总线上 传输链路少、增加 节点方便 稳定性差，网络范 围受限
环形网 所有节点按次序 连接成环 结构简单，稳定 性较高

端的入度
有向图中，进入或射入 端 v i的边数。记为： d
＋
(vi )
有向图中
端的度数
d ( vi ) d ( vi ) d ( vi )


华北电力大学电子与信息工程学院
2004-07-29
第11/14页
11. 什么是连通图
通信网理论基础
图G=(V,E)。若图中任意2点之间至少存在一条路径

通信网理论基础
G T {e 2 , e 5 }
e1
e2
e5 e6 e3
非连通图
e4
{ e1 ,Biblioteka e 5 }是割边集华北电力大学电子与信息工程学院