文档介绍：§1-1 图论的初步知识
北京邮电大学
电子工程学院
俎云霄
图论属于数学的一个分支,它是一个年轻但却迅速成熟的学科,它主要是研究事物之间的客观规律。

图论的起源——哥尼斯堡桥问题
从任一陆地出发走遍七座桥(而且只走一次)再回到原地是否可行?
1736年Euler(欧拉:圣彼得堡大学的数学教授)证明
无解。
古普鲁士有条Pregel河穿越哥尼斯堡城,河上有七座桥将四块陆地相连。
连通图每点连接的边数为偶数才能有解。
图论的一些基本概念
应用图论讨论电路的结构及其联接性质,对电路进行分析, 称为网络图论(网络拓扑学)。
拓扑(topology):几何或联接性质。
图(Graph):电路(网络)的图由支路(线段)和节点(点)组成,用G表示。每一支路代表一个电路元件或一些电路元件的某种组合,每一支路都连接在图中的两个节点之间。
标准支路组合
电路图
拓扑图G
在电路分析中,图中边上的箭头即表示该边所代表的支路电压、电流方向。
有向图(directed graph):给图中的每一条支路都规定了方
向的图。否则,称为无向图( undirected graph)
如果用n表示节点数,b表示支路数,则图中n=3,b=4。
图论的一些基本概念
连通图(connected graph):图G中任意两节点之间至少存在一
条通路的图。否则称为不连通图(unconnected graph)。
连通图
不连通图
图论的一些基本概念
图G
子图G1
图论的一些基本概念
子图(subgraph):图G中的一部分称为其子图。
子图G2
路径(path):从图G的某一节点出发,沿着一些支路连续移动,
从而到达另一指定的节点或原节点,则这样一系列的支路便
构成了图G的一条路径。
图论的一些基本概念
回路(loop):起点和终点重合的路径便构成了一个回路。
图G
图论的一些基本概念
树(tree-T) :树是连通图G的一个连通子图;包含图G的所
有的节点;不包含任何回路。
T2
T1
树支:组成树的支路。
连支:其余的支路。
树支数:
连支数:
割集C(1,3,5,4)
割集(cutset) :图G的割集是G的一些支路集合,把这些支
路移去将使G分离为两个部分,而如果少移去其中一条支
路,图仍将是两通的。即割集是使图分为两部分的最少边
集。
图论的一些基本概念