连通图一定有支撑树。 树边，连枝。
5.1.3 割集
割集指的是某些端集或边子集。对连通 图，去掉此类子集，图变为不连通。
定义5.3 割端与割端集 设v是图G的一个端，去掉v和其关联边后，
G的部分数增加，则称v是图G的割端。 去掉一个端集合后，G的部分数增加，这 个端的集合称为割端集。
点连通度
被称为图G的支撑子图。
若 ， 称
E1 E, V1 {v V | v是E1中某边的端点}
图 是G中由 G1 (V1, E1)
E1
生成的子图，记
为 G[E1]。
图的连通性
考虑边的一个序列，相邻二边有公共端，如(v1， v2)， (v2，v3)， (v3，v4)， (vi，vi+1)，这 个边序列称为链，链简单说就是一个连续轨迹。
没有重复边的链称为简单链；没有重复端的链 称为初等链或道路；
若链的起点与终点重合，称之为圈；若道路的 起点与终点重合,称之为初等圈。一般重点讨论 道路和初等圈。
连通图
任何二端间至少存在一条链的图，为连 通图。否则，就是非连通图。
非连通图G有三个连通分支
G
图的例子
完全图 K n 两部图 欧拉图 正则图
对于连通图, 在众多的割端集中至少存在 一个端数最少的割端集，称为最小割端 集。
最小割端集的端数目，称为图的点连通 度或连通度，连通度用 表示。
线连通度
定义5.4 割边与割边集 设e是图G的一条边，去掉e后，G的部分
数增加，则称e是图G的割边。去掉一个 边集合后，G的部分数增加，这个边的集 合称为割边集。
1 关联阵
设图G有n个端，m条边，则全关联阵 A0 [aij ]nm ,其中
在无向图中aaiijj
1, 若e j与vi关联 0, 若e j与vi不关联
在有向图中
a a
ij ij
1, e j与vi关联,离开vi 1, e j与vi关联, 指向vi
aij 0, e j与vi不关联
某边的端为 vi，v j，称这边和端 vi，v j 关联， 这个边也可记为: (vi，v j )或 ei, j 。
简单图
一些概念 无向图 ，有向图，空图，孤立点图，自
环，重边。 一个不含自环和重边的图称为简单图，
以后如果没有特别声明主要讨论简单图。
顶点的度
对无：d(vi )。
定义5.5反圈：给定图G (V , E)，若S，T V， 记[S,T ]G {(u,v) E：u S,v T}; 特别，当T V \ S时，将[S，T ]G 记为（ G S）或（S)。
设X是V的非空真子集，若（ G X） ，称（ G X）为由X确定的反圈。
5.1.4 图的矩阵表示
下面将给出图的矩阵表示，主要介绍关 联阵和邻接阵。
e5
e4
图5.3 基本圈和基本割集
基本圈和基本割集的应用
基本圈和基本割集有许多应用，首先通 过集合的对称差运算, 由基本割集可以生 成新的割集或它们的并集,事实上可以证 明生成所有的割集；基本圈也有类似的 性质。
例5.2 通过基本圈和基本割集分析求解电 网络。
反圈
下面给出一个重要的概念，反圈。
例5.1欧拉(Euler) 7桥问题。 电网络分析问题。（基尔霍夫）
图的定义
定义5.1 所谓一个图G，是指给了一个端点集 合V，以及边的集合或V中元素的序对集合E， 图一般用 G (V , E)来表示。
如果图G有n端m条边，可将V和E表示 为 V {v1, v2 ,..., vn} ， E {e1, e2 ,..., em} 。
5.1.2树
定义5.2 无圈的连通图称为树。 性质5.2 除单点树，至少有两个度数为1
的端(悬挂点)。 性质5.3 任意树的边数m和端数n满足
m n 1
树的等价性质
定理5.1 给定一个图T， 若 |V | n ，| E | m ，则下面论断等价：
（1）T是树； （2）T无圈，且 m n 1 ； （3）T连通，且 m n 1 。
树的性质
性质5.3：若T是树，则： （1）T是连通图，去掉任何一条边，图
便分成两个且仅仅两个连通分支；
（2）T是无圈图，但添加任何一条边， 图便会包含一个且仅仅一个圈。
性质5.4：设T是树，则任何两点之间恰 好有一条道路；反之，如图T中任何两点 之间恰好有一条道路，则T为树。
支撑树
如果树T是连通图G的子图，TG，且T 包含G的所有端，称T是G的支撑树或主 树。
性质5.1对无向图 G (V , E)
如果 | V | n | E | m
有
n
d (vi ) 2m
i 1
子图
给定图 ，若 ，
G (V , E)
V1 V , E1 {(u, v) E | u, v V1}
称图 是G中由 G1 (V1, E1)
V1
生成的子图，记
为 G[V1] 。若 E2 E1, ，称 G2 (V1, E2 ) 为G的子 图。特别若子图的端点集合为V,这个图
第五章 网络拓扑结构分析
本章目的
网络拓扑结构分析是很基本，也是很重 要的问题。
拓扑结构是通信网规划和设计的第一层 次问题。
通信网的拓扑结构可以用图论的模型来 代表，本章分析的主要问题为最小支撑 树、最短路径和网络流量安排等问题。
5.1 图论基础 5.1.1图的定义和基本概念
图论是应用数学的一个分支，有着丰富 的内容，本节介绍它的一些概念和结论。
每一条连枝决定的圈是基本圈。 确定了连通图的一个支撑树后，每条树边可以
决定一个基本割集。 对于支撑树，去掉树上任何一条边，树便分为
两个连通分支，从而将原图的端分为两个集合， 这两个集合之间的所有边形成一个极小边割集， 这个边割集称为基本割集。
基本圈和基本割集的例
基本圈和基本割集
e1
e2
e6
e3
割边集中边数最少的割边集，称为最小 割边集。最小割边集的边数目，称为线 连通度，线连通度用 表示。
连通度的简单性质
性质5.5 对于任意一个连通图 G (V,E) ， 若 ， |V | n | E | m ， 为最小度，则
2m
n
基本割集和基本圈
对于任何一个连通图G，设T为G的一个支撑树，