图的概念

引言--哥尼斯堡七桥问题十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有7座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这7座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡7桥”难题。•顶点(Vertex)表示研究对象－－物理实体、事物，一般用vi表示•边(Edge)表示两个对象之间的某种特定关系－－顶点间的连线，一般用ei表示图(Graph)顶点和边的集合G＝（V，E）V--点集合E--边集合1、什么是图1v2v3v4v1e2e3e4e5e6e7e例V={v1，v2，v3，v4}E={e1，e2，…，e7}v1v5v4v3v2e12e34e13e24e22e'13e45图6.1eije1e2e3e4e5v2v3v1v4v5v6e6e7e8e9阶：顶点的个数n关联：若某顶点与某条边连接，则称它们彼此关联孤立点：与任何边没有关联的顶点多重边：某两个顶点之间多于一条边多重图：具有多重边的图环：起点和终点为一个顶点的边简单图：无多重边，无环的图相邻：两顶点之间至少存在一条边次数：与某个顶点相关联的边的数目•无向图由顶点和边组成G=（V，E）•弧(Arc)顶点与顶点之间有方向的连线有向图：由点和弧组成G=（V，A）2、有向图和无向图例V={v1，v2,…,v6}A={a1，a2,…,a9}a1a2a3a4a5v2v3v1v4v5v6a6a7a8a9无向图有向图混合图连线为弧既有边又有弧连线为边•子图设：G1=(V1，E1)，G2=(V2，E2)若：V1V2，又E1E2则称G1是G2的子图3、子图e1e2e3e4e5v2v3v1G1e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9G2•生成子图（支撑子图）设：G1=(V1，E1)G2=(V2，E2)若：V1＝V2又E1E2则称G1是G2的生成子图基础图(母图)子图支撑子图•链点边交错系列，记为：•圈的链•简单链（圈）链（圈）中的边均不相同•初等链（圈）点均不相同•路初等链•回路初等圈),,,...,,,(1211kkkvevvevkvv1kvvv,...,,211v2v3v4v1e2e3e4e5e6e7e无重复点,无重复边有重复点,无重复边4、链、路、圈和回路路回路4528572111vevevevevQ44322112vevevevQ1956452113vevevevevQ简单链初等链初等圈5、连通图若一个图G的任意两点之间至少存在一条链，则称这个图G是一个连通图，否则称作不连通图。例如图中，v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。e1e2e3e4e5v2v3v1v4v5v6e6e7e8e9•K部图连通图不连通图二部图权程度的度量，数量描述线权给图的边赋以某一数值点权给图的顶点赋以某一数值网络赋权的图（边权图、点权图、混合图）6、加权图v1139538362v6v5v3v4v2对G中的每一条边相应的有一个数wij图与矩阵在图与网络分析的应用中，将面临一个问题——如何分析、计算一个较大型的网络，这当然需借助快速的计算工具——计算机。那么，如何将一个图表示在计算机中，或者，如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有——邻接矩阵、关联矩阵、权矩阵等。7、关联矩阵和邻接矩阵e10e1e2v1v2v3v5v4v8v6v7e3e4e6e5e7e9e12e11e8A=(aij)=v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000关联矩阵0若顶点i与边j不关联aij=1若顶点i与边j相关联B=（bij）nn=v1v2v3v4v5v6v7v8v1v2v3v4v5v6v7v80100100010101000010010020000011011100001000100100001110000201000e1e2v1v2v3v5v4v8v6v7e3e4e6e5e7e9e12e11e8邻接矩阵bij=连接顶点vi和vj的边数邻接矩阵示例图（1）的邻接矩阵是图（2）的邻接矩阵是0111010101110111010101110543215432101000000110001104321432134513421223451243•说明当图的顶点和边（弧）的编号确定之后，关联矩阵和邻接矩阵就与图建立了确定的一一对应关系，因而可用关联矩阵或邻接矩阵来表达图。一般来说，图的邻接矩阵比关联矩阵小，因而在存贮和计算时用得较多。二、树1、什么是树–树:连通的无圈图称为树，通常用字母T表示悬挂点树的性质■如果树的顶点数≥2，则它至少有两个悬挂点243512435124351■如果树的顶点个数为n，则边的个数为n-1■树中任意两个节点之间只有唯一的一条链■在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈定理：（树的六个等价定义）&T连通且无回路&无圈，且有n－1条边&连通，且有n－1条边&无圈，但增加一条边，可得到一个且仅一个圈&连通，但舍弃一条边，图便不连通&每一对顶点之间有一条且仅有一条初等链2、生成树（支撑树）•定义设图T是图G的一个生成子图,如果T是一棵树,则称树T是G的一个生成树（支撑树）图的生成树■由网络的所有节点（n个）和网络的n-1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦4231423142314231423142314231生成树的变换4231■网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树423142314231生成树2生成树3生成树1////生成树和线性规划的关系■网络的一个生成树对应于线性规划的一个基■生成树上的边对应于线性规划的基变量■生成树的弦对应于线性规划的非基变量■生成树的变换对应于线性规划单纯形法的进基和离基变换3、最小生成树•支撑树的权若T=(V,E)是G的一个支撑树,E中的所有边的权（）之和称为支撑树的权,记为w(T):TvvijjiwTw],[)(ijw•最小树（T*）在赋权图G的所有支撑树中，必有某个支撑树，其所有边的权的和最小，称为最小树。•求最小树的丢边法（破圈法）•求最小树的加边法（避圈法）)(min)(*TwTwT丢边法（破圈法）655172344v1v2v3v4v5v6思路：任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。v1v2v3v5e2e3e5e1e6e7e8v1v2e1v3e2e4e4v4v4v5e6加边法（避圈法）思路：从所有边中选出一条权最小的边，并把它纳入树中；在余下的未选边中，再选出一条最小且与已选入树中的边不构成圈的边，将其纳入树中；如此重复，直到树中含有n－1条边为止。图G1542453134421512生成最小树T生成最小树T1231211212312112破圈法避圈法避圈法的第二种表述便于编程使用步骤1、将图中所有的点分V为V两部分，V——最小生成树内点的集合V——非最小生成树内点的集合2任取一点vi，令vi∈V3取V中与V相连的边中一条最短的边(vi,vj)，连接(vi,vj)，令vj∈V4重复⑵，至所有的点均在V之内。例：用避圈法构造下图的最小生成树1.在点集中任选一点，不妨取S，令V={S}2.找到和S相邻的边中，权值最小的[S,A]3.V={S,A}4.重复第2，3步，找到下一个点。•定义1在连通无向图G中，若存在经过每条边恰好一次的一个圈或一条链，就称此圈或此链为欧拉圈或欧拉链。若图含一条欧拉圈，则称它为欧拉图。•定理1连通无向图G为欧拉图的充要条件是它的全部顶点都是偶次顶点•定理2连通无向图G为欧拉链的充要条件是它恰含两个奇次顶点欧拉图