文档介绍：§
§
§
§
§
第六章图与网络分析
§
一个图(graph)是由一些结点或顶点( nodes or vertices )以及连接点的边(edges)构成。记做G = {V,E},其中 V 是顶点的集合,E 是边的集合。
给图中的点和边赋以具体的含义和权值,我们称这样的图为网络图(赋权图)
图中的点用 v 表示,边用 e 表示,对每条边可用它所联结的点表示,如图,则有:
e1 = [v1 , v1],
e2 = [v1 , v2]或e2= [v2 , v1]
端点,关联边,相邻
若边 e 可表示为e = [vi , vj],称 vi 和 vj 是边 e 的端点,同时称边 e 为点 vi 和 vj 的关联边,若点 vi , vj 与同一条边关联,称点 vi 和 vj 相邻;若边 ei 与 ej 有公共端点,称边 ei 和 ej 相邻;
环,多重边,简单图
如果边 e 的两个端点相重,称该边为环,如果两个点之间的边多于一条,称为具有多重边,对无环、无多重边的图称为简单图。
次,奇点,偶点,孤立点
与某个点相关联的边的数目,称为该点的次(或度、线度),记作 d(v)。次为奇数的点称为奇点,次为偶数的点称为偶点,次为零的点称为孤立点。
如图:
奇点为 v5 , v3
偶点为 v1 , v2 , v4 , v6
孤立点为 v6
链,圈,路,回路,连通图
图中有些点和边的交替序列μ={v0 , e1 , v1 , e2 , …, ek , vk},若其各边 e1 , e2 , …, ek 各不相同,且任意 vi,t-1 , vit (2 ≤ t ≤ k)都相邻,称μ为链,如果链中所有的顶点 v0 , v1 ,
…, vk也不相同,这样的链成为路,起点和终点重合的链称为圈,起点和终点重合的路称为回路,若在一个图中,每一对顶点之间至少存在一条链,称这样的图为连通图,否则称该图为不连通的。
完全图,偶图
一个简单图中若任意两点之间均有边相连,称这样的图为完全图,含有 n 个顶点的完全图,其边数有 1/2[n(n-1)] 条。
如果图的顶点能分成两个互不相交的非空集合 V1 和V2 , 使在同一集合中任意两个顶点均不相邻,称这样的图为偶图(也称二分图),如果偶图的顶点集合V1 和V2 之间的每一对顶点都有一条边相连,称这样的图为完全偶图,完全偶图中V1 含m 个顶点,V2 含有 n 个顶点,则其边数共 m · n 条。
子图,部分图
图 G1={V1 , E1} 和 G2={V2 , E2},如果有和
,称 G1 是 G2 的一个子图,若有
则称 G1 是 G2 的一个部分图。注意部分图也是子图,但子图不一定是部分图。
子图:
部分图
§
树图(简称树,记作 T(V, E))是简单连通图。(无圈,无重边)
一. 树的性质
性质1. 任何树中必存在次为1 的点。
次为1的点称为悬挂点,与之关联的边称为悬挂边。
性质2. 具有 n 个顶点的树恰有(n-1)条边。
性质3. 任何具有n 个点、(n - 1)条边连通图是树。
说明:
1. 树中只要任意再加一条边,必出现圈。
2. 树中任意两点之间有且只有一条通路,从树中任意删掉一条边,就不再连通。
二. 图的最小部分树
如果 G1 是 G2 的部分图,又是树图,则称 G1 是 G2 的部分树(或支撑树)。树图的各条边称为树枝(假定各边均有权重),一般图 G2 含有多个部分树,其中树枝总长最小的部分树,称为该图的最小部分树(也称最小支撑树)。
定理1. 图中任一个点 i ,若 j 是与 i 相邻点中距离最近的,则边[ i , j ] 一定包含在该图的最小部分树中。
推论. 把图的所有点分成 V 和两个集合,则两集合之间连线的最短边一定包含在最小部分树内。
三. 避圈法和破圈法
寻找最小部分树的方法主要有避圈法和破圈法两种。
避圈法步骤:
1. 从图中任选一点 vi ,让 vi ∈V ,图中其余点均包含在中;
2. 从 V 与的连线中找出最小边,这条边一定包含在最小部分树中,不妨设这条边为[vi , vj]将其加粗,标记为最小部分树中的边。
3. 令 V∪vj→V, - vj→;
4. 重复2、3两步,一直到图中所有点均包含在 V 中。