《现代物流运筹学（第二版）》 课件 12.图的基本概念

图的基本概念《现代物流运筹学》主讲教师：王东辉图的基本概念近代图论的历史可追溯到18世纪的七桥问题—穿过Königsberg城的七座桥，要求每座桥通过一次且仅通过一次。这就是著名的“哥尼斯堡7桥”难题。Euler1736年证明了不可能存在这样的路线。Königsberg桥对应的图图的基本概念在一个人群中，对相互认识这个关系我们可以用图来表示。例(v1)赵(v2)钱孙(v3)李(v4)周(v5)吴(v6)陈(v7)e2e1e3e4e5(v1)赵(v2)钱(v3)孙(v4)李(v5)周(v6)吴(v7)陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。图的有关概念表示为：G=（V，E）V--点集合E--边集合简称图，由点和边组成。无向图：带箭头的联线，表示不对称关系。不带箭头的联线，表示对称关系。弧：反映对象之间关系的一种工具。图：表示两个对象之间的某种特定关系。连线：表示研究对象。点：有向图：由点和弧组成。边：无向图的有关概念有多重边的图。多重图：无环，无多重边的图。简单图：两点之间多于一条边。多重边：若u=v，e是环。环：e是点u，v的关联边。关联边：e=[u,v]∈E，则u,v是e的端点，称u,v相邻。端点：无向图的有关概念V1v2v3v4e1e2e5e4e6e3次为偶数的点。偶点：次为奇数的点。奇点：次为0的点。孤立点：悬挂点的关联边。悬挂边：次为1的点。悬挂点：例:如图示d(v1)=4，d(v4)=4以点v为端点的边数称为v的次。表示为：d(v)次：无向图的有关概念圈中边均不相同。简单圈：链中边均不相同。简单链：圈中无重复的点和边。

初等圈：链中无重复的点和边。初等链：如一条链中起点和终点重合。圈：点边交错序列。链：无向图的有关概念图G去掉点v及v的关联边的图。G-v：对G=（V，E），若Gˊ=(Vˊ，Eˊ),使Vˊ=V，Eˊ是E的子集，则Gˊ是G的一个支撑子图。支撑子图：对不连通图，每一连通的部分称为一个连通分图。连通分图：任意两点之间至少有一条链。连通图：有向图的有关概念有多重弧。多重有向图：无自环，无多重弧。简单有向图：圈中无重复的点和弧。初等圈（回路）：链中无重复的点和弧。初等链（道路）：如一条链中起点和终点重合。圈（回路）：点弧交错序列。链（道路）：对弧a=(u，v)，u为a的始点，v为a的终点。始点和终点：由点和弧组成。表示为：D=（V，A）V--点集合A--弧集合有向图：图的基本概念与模型子图，部分图(支撑子图)v3e7e4e8e5e6e1e2e3v1v2v4v5（G图）图G1={V1、E1}和图G2={V2，E2}如果有称G1是G2的一个子图。若有，则称G1是G2的一个部分图(支撑子图)。v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)图的基本概念与模型网络（赋权图）设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权，赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。