图与网络分析 (Graph Theory and Network Analysis)课件.ppt

《图与网络分析 (Graph Theory and Network Analysis)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图与网络分析(GraphTheoryandNetworkAnalysis)图与网络的基本知识最短路问题树及最小树问题最大流问题最小费用最大流问题BDACABCD哥尼斯堡七桥一笔画问题一、图与网络的基本概念（一）、图EADCB1、一个图是由点和连线组成。（连线可带箭头，也可不带，前者叫弧，后者叫边）在图论中，通常用点表示具体的或抽象的事物，而用边表示事物之间的某种联系。一个图是由点集和中元素的无序对的一个集合构成的二元组，记为G=(V，E)，其中V中的元素叫做顶点，V表示图G的点集合；E中的元素叫做边，E表示图G的边集合。v1v2v3v4v5v6e1e2e3

2、e4e5e6e7e8e9e10例图12、如果一个图是由点和边所构成的，则称其为无向图，记作G=(V，E)，连接点的边记作[vi,vj]，或者[vj,vi]。3、如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向vj的弧，记作(vi,vj)。v4v6v1v2v3v5V={v1,v2,v3,v4,v5,v6}，A={(v1,v3),(v2,v1),(v2,v3),(v2,v4),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)}图24、一条边的

3、两个端点是相同的,那么称为这条边是环。6、一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。7、每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。5、如果两个端点之间有两条以上的边，那么称为它们为多重边。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。8、以点v为端点的边的个数称为点v的度（次），记作。图中d(v1)=4，d(v6)=4（环计两度）定理1

4、所有顶点度数之和等于所有边数的2倍。定理2在任一图中，奇点的个数必为偶数。所有顶点的入次之和等于所有顶点的出次之和。有向图中，以vi为始点的边数称为点vi的出次，用表示；以vi为终点的边数称为点vi的入次，用表示；vi点的出次和入次之和就是该点的次。9、设G1=（V1,E1），G2=（V2,E2）如果V2V1,E2E1称G2是G1的子图；如果V2=V1,E2E1称G2是G1的支撑子图。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6

5、e7e9e10e11(c)支撑子图（二）、连通图1.链：点、边交替或点弧交替的序列。用μ表示。{v1,(v1,v2),v2,(v2,v5,)v5}2.简单链：没有重复边的链。V2V6V1V4V5V3V7V8对于简单链可由顶点表示，如上链v1→v2→v53．初等链：顶点也不相同的简单链。v1→v2→v5→v4→v34．圈（闭链）：起点终点一致的链。（与环不同，环只有一条边）v1→v2→v3→v4→v15．连通图：若图G中任意二点之间至少有一条链连接，则图G称为连通图，否则称为不连通图。不连通图G每个连通的部分称为G的一个连通分图。（两个连通分图）在实际应用中

6、，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧，对应一个数，称为弧上的“权”。通常把这种赋权的图称为网络。图8－6　赋权无向图图8－7　赋权有向图（三）赋权图v16v2v45v3315v574图8-6v1v2365v45v3v57421图8-7（三）、图的矩阵表示对于网络（赋权图）G=（V，E），其中边有权，构造矩阵，其中：称矩阵A为网络G的权矩阵。设图G=（V，E）中顶点的个数为n，构造一个矩阵，其中：称矩阵A为网络G的邻接矩阵。例权矩

7、阵为：邻接矩阵为：v5v1v2v3v4v64332256437二、树及最小树问题已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。v1v2v3v4v5v61、一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点。树的性质：（1）数必连通，但无回路（圈）。（2）n个顶点的树必有n-1条边。（3）树中任意两个顶点之间，恰有且仅有一条链（初等链）。（4）树连通，但去掉任一条边，必变为不连通。（5）树无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。v1v2v3v4v5v62、设图

8、是图G=(V,E)的一支撑子图，如果图是一个树,那么称K是G的一个