第六章图与劂络分析 §1.图的基本概念与模型 §2.树图和图的最小部分树 §3.最短路问题 §4.网络的最大流 §5.最小费用流
§ 1．图的基本概念与模型 § 2．树图和图的最小部分树 § 3．最短路问题 § 4．网络的最大流 § 5．最小费用流 第六章 图与网络分析
§1.图的基本概念与模型 个图(grph)是由一些结点互项点( nodes or vertices)以及连接点的边(eges)构成。记做G={V,E}, 其中V是顶点的集合,E是边的集合。 给图中的点和边赋以具体的含义和权值,我们称这样 的图为网给图(赋权图) 图中的点用v表示,边用e表示,对每条边可用它所 联结的点表示,如图,则有: 2=[v1,2或e2=[v2,v
§1．图的基本概念与模型 一个图（graph）是由一些结点或顶点（nodes or vertices ）以及连接点的边（edges）构成。记做G = {V,E}， 其中 V 是顶点的集合，E 是边的集合。 给图中的点和边赋以具体的含义和权值，我们称这样 的图为网络图（赋权图） 图中的点用 v 表示，边用 e 表示，对每条边可用它所 联结的点表示，如图，则有： e1 = [v1 , v1 ]， e2 = [v1 , v2 ]或e2= [v2 , v1 ]
端点,关联边,相邻 若边c可表示为e=[,,称v和是边c的端点, 同时称边e为点v和v的关联边,若点v,v与同一条 边关联,称点v和v相若边e与有公共端点,称 边2和c据 环,多重边,简单图 如果边e的两个端点相重,称该 边为环,如果两个点之间的边多于 条,称为具有多重边,对无环 无多重边的图称为篇单图。 y3gy
端点，关联边，相邻 若边 e 可表示为e = [vi , vj ]，称 vi 和 vj 是边 e 的端点， 同时称边 e 为点 vi 和 vj 的关联边，若点 vi , vj 与同一条 边关联，称点 vi 和 vj 相邻；若边 ei 与 ej 有公共端点，称 边 ei 和 ej 相邻； 环，多重边，简单图 如果边 e 的两个端点相重，称该 边为环，如果两个点之间的边多于 一条，称为具有多重边，对无环、 无多重边的图称为简单图
次,奇点,偶点,孤立点 与某个点相关联的边的数目,称为该点的次(或度 线度),记作小次为奇数的点称为奇点,次为偶数 的点称为/点,次为零的点称为孤立点。 如图: 奇点为v;,n 偶点为v1,v2,v4,v6 孤立点为v
次，奇点，偶点，孤立点 与某个点相关联的边的数目，称为该点的次（或度、 线度），记作 d(v)。次为奇数的点称为奇点，次为偶数 的点称为偶点，次为零的点称为孤立点。 如图： 奇点为 v5 ， v3 偶点为 v1 , v2 , v4 , v6 孤立点为 v6
链,圈,路,回路,连通图 图中有些点和边的交替序列={v,1,n,2,…,ek, ,若其各边e1,e2,…,k各不相同,且任意vin1,v(2 ≤t≤)都相邻,称为链,如果链中所有的顶点v,n1, vk也不相同,这样的链成为路,起点和终点重合的 链称为圈,起点和终点重合的路称为回路,若在一个图 中,每一对顶点之间至少存在一条链,称这样的图为连 通图,否则称该图为不连通的
链，圈，路，回路，连通图 图中有些点和边的交替序列 μ={v0 , e1 , v1 , e2 , … , ek , vk }，若其各边 e1 , e2 , … , ek 各不相同，且任意 vi,t-1 , vit (2 ≤ t ≤ k)都相邻，称 μ 为链，如果链中所有的顶点 v0 , v1 , … , vk也不相同，这样的链成为路，起点和终点重合的 链称为圈，起点和终点重合的路称为回路，若在一个图 中，每一对顶点之间至少存在一条链，称这样的图为连 通图，否则称该图为不连通的