链:点边交错系列,记为: 圈: 无重复点无重复边 初等链 初等圈有重复点无重复边 简单链铤迈均不相同 简单圈:圈中边均不相同。e5 例:右图 脑O2
运筹学 链：点边交错系列， 记为： 圈： 的链。 初等链：点 均不相同。 初等圈：点 均不相同。 简单链：链中边均不相同。 简单圈：圈中边均不相同。 例：右图 ( , , ,..., , , ) 1 1 2 k 1 k k vi ei vi vi ei vi − k vi = vi 1 k vi vi vi , ,..., 1 2 1 2 1 , ,..., i i i k− v v v v1 v2 v3 v4 e1 e2 e3 e4 e5 e6 e7 无重复点,无重复边 有重复点,无重复边
连通图:任意两点之间至少有一条链。 不连通图: 连通分图:对不连通图,每一连通的部 分称为一个连通分图。 支撑子图:对G=(V,E),若 G=(V,E),使V=V,E≤E,则G是G的 一个支撑子图(生成子图) Gv:图G去掉点v及v的关联边的图 □合
运筹学 连通图：任意两点之间至少有一条链。 不连通图： 连通分图：对不连通图，每一连通的部 分称为一个连通分图。 支撑子图：对G=（V，E），若 G`=(V`,E`), 使V`=V, E` E, 则G`是G的 一个支撑子图（生成子图）. G-v: 图G去掉点v及v的关联边的图
有向图的有关概念 基础图:对D=(V,A,去掉图上的箭头 始点和终点:对方向可以不同2的始点 为a的终点 链:点弧交错序列若在其基础图中对应 一条链,则称为D的一条链 圈,初等链初等圈:类似定义 □合
运筹学 有向图的有关概念 基础图: 对D=(V, A), 去掉图上的箭头. 始点和终点: 对弧a=(u,v), u为a的始点, v 为a的终点. 链: 点弧交错序列, 若在其基础图中对应 一条链, 则称为 D的一条链. 圈, 初等链,初等圈: 类似定义. 方向可以不同
道路若(n,4,2,a2,M4n,n)是D中 的一条链,且a=(,m)=1,2…k1称 之为从V到的一条道路。 回路:,=ν的路 方向相同 初等路:道路中点不相同 初等回路:回路中点不相同 简单有向图:无自环,无多重弧 多重有向图:有多重弧 □合
运筹学 道路:若 是D中 的一条链，且 ，t=1,2,…,k-1,称 之为从 到 的一条道路。 回路: 的路. 初等路: 道路中点不相同. 初等回路: 回路中点不相同. 简单有向图: 无自环, 无多重弧. 多重有向图: 有多重弧. , , , ,..., , , ) 1 1 2 2 1k 1 k 1 k vi ai vi ai vi ai vi （ − − k vi = vi 1 ( , ) +1 = t t t ai vi vi 1 vi k vi 方向相同
2.树 2.1树及其性质 2.2图的支撑树(生成树) 2.3最小支撑树问题 2.4根树及其应用 □合
运筹学 2. 树 2.1 树及其性质 2.2 图的支撑树（生成树） 2.3最小支撑树问题 2.4 根树及其应用