文档介绍：§
§
§
§
第六章图与网络分析
图与网络分析 Graph Theory work Analysis
引言
十八世纪的哥尼斯堡城中流过一条河(),河上有 7 座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏:一个游者怎样才能一次连续走过这 7 座桥,回到原出发点,而每座桥只允许走一次。没有人想出走法,又无法说明走法不存在,这就是著名的“哥尼斯堡 7 桥”难题。
2
图与网络分析 Graph Theory work Analysis
引言
“哥尼斯堡 7 桥”难题最终在 1736 年由数学家 Euler 的一篇论文给予了完满的解决,这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的,直到 1936 年匈牙利数学家 önig写出了图论的第一本专著《有限图与无限图的理论》。
在图论的发展过程中还有两位著名科学家值得一提,他们是克希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出了重要的贡献,而化学家凯莱在对碳氢化合物的同分异构体的数量进行计数时推动了图论中树的计数问题的研究。
3
图与网络分析 Graph Theory work Analysis
图论与网络分析理论所研究的问题十分广泛,内容极其丰富。正如一位数学家所说:“可以说,图论为任何一个包含了某种二元关系的系统提供了一种分析和描述的模型。”
注意: 图论中所研究的图并非几何学中的图,也不是绘画中的图。在这里我们所关心的仅仅是图中有多少个点,点与点之间有无线来连接,也就是说我们研究的是某个系统中的元素——点,以及这些元素之间的某种关系——连线。
4
§
一个图(graph)是由一些结点或顶点( nodes or vertices )以及连接点的边(edges)构成。记做G = {V,E},其中 V 是顶点的集合,E 是边的集合。
给图中的点和边赋以具体的含义和权值,我们称这样的图为网络图(赋权图)
图中的点用 v 表示,边用 e 表示,对每条边可用它所联结的点表示,如图,则有:
e1 = [v1 , v1],
e2 = [v1 , v2]或e2= [v2 , v1]
基本概念
弧:任两点间带箭头的连线a=(vi,vj)
无向图:点及边构成的图(简称图),记G=(V,E)
有向图:点及弧构成的图,记D=(V,A)
顶点数和边数:在G(或D)中,V中元素的个数称为G(D)的顶点数,记为p(G)或P(D),E中元素的个数称为边数,记为q(G)或q(D)
端点,关联边,相邻
若边 e 可表示为e = [vi , vj],称 vi 和 vj 是边 e 的端点,同时称边 e 为点 vi 和 vj 的关联边,若点 vi , vj 与同一条边关联,称点 vi 和 vj 相邻;若边 ei 与 ej 有公共端点,称边 ei 和 ej 相邻;
环,多重边,简单图
如果边 e 的两个端点相重,称该边为环,如果两个点之间的边多于一条,称为具有多重边,对无环、无多重边的图称为简单图。
次,奇点,偶点,孤立点,悬挂点,悬挂边
与某个点相关联的边的数目,称为该点的次(或度、线度),记作 d(v)。在有向图中,以vi为始点的边的条数称为vi的出次d+(vi),在有向图中,以vi为终点的边的条数称为vi的入次d-(vi)
次为奇数的点称为奇点,次为偶数的点称为偶点,次为零的点称为孤立点。次为1的点称为悬挂点,与悬挂点相连的边称为悬挂边
如图:
奇点为 v5 , v3
偶点为 v2 , v4 , v6
孤立点为 v6
定理1:图G=(V,E)中,所有点次之和=边数的2倍
定理2:任意一图G中,奇点的个数为偶数
链,圈,路,回路,连通图
图中有些点和边的交替序列μ={v0 , e1 , v1 , e2 , …, ek , vk},称μ为联结v0到vk的链,起点和终点重合的链称为圈,如果( v0, a1 , v1 , a2 , …, ak , vk)是有向图中的一条链,称之为从v0到vk的一条路,起点和终点重合的路称为回路,
初等链:链中无重复点
简单链:链中无重复边
初等圈:圈中无重复点
简单圈:圈中无重复边
简单路:边不重的路
初级路:点不重的路
简单回路:边不重的回路
初级回路:点不重的回路
以后除特别交代外,均指初等
连通图,子图,部分图
若在一个图中,每一对顶点之间至少存在一条链,称这样的图为连通图,否则称该图为不连通的。
图 G1={V1 , E1} 和 G2={V2 , E2},如果有和
,称 G1 是 G2 的一个子图,若有
则称 G1 是 G2 的一个支撑子图。注意