第三部分图与网络分析 图与网络分析部分内容框架 图 图与网络的基本概念 连通图 图的矩阵表示 树与最小树 最短路问题 图论在网络分析的应用 最大流问题 最小费用最大流问题 第四章图与网络分析 §1.图与网络的基本概念 、图及其分类 本章研究的图与平面几何中的图不同,我们只关心图中有多少个点, 点与点之间有无线连接,至于连线的方式是直线还是曲线,点与点的相对 位置如何,都是无关紧要的。下面介绍有关图的基本概念 1图,图是点和线所组成的图形,即图是一个有序二元组(VE),记为 G=(V,E),其中V={v,v;v}是p个点的集合,E={ene,e}是q条边的 集合。V中的元素v称为顶点,E中的元素ek称为边。 如图1所示:
20 第三部分 图与网络分析 图与网络分析部分内容框架 图与网络的基本概念 图 连通图 图的矩阵表示 树与最小树 最短路问题 图论在网络分析的应用 最大流问题 最小费用最大流问题 第四章 图与网络分析 §1. 图与网络的基本概念 一、图及其分类 本章研究的图与平面几何中的图不同，我们只关心图中有多少个点， 点与点之间有无线连接，至于连线的方式是直线还是曲线，点与点的相对 位置如何，都是无关紧要的。下面介绍有关图的基本概念。 1.图，图是点和线所组成的图形，即图是一个有序二元组(V,E)，记为 G=(V,E)，其中 V={v1,v2,…vp}是 p 个点的集合，E={e1,e2,…eq}是 q 条边的 集合。V 中的元素 vi 称为顶点，E 中的元素 ek 称为边。 如图 1 所示： 图 与 网 络 分 析
V3 图1 V=(v1, V2, V3, V4, V5, E(el, e2, e3, e4, es, e6) 其中el={v,vn},e2={v,v2},e3={v,w3} e4={v3,v4},es= 对于边(vy),则称vv两点相邻,也称v,v为边(vv)的端点 若两条边有一个公共端点u,则称这两边是相邻的,也称这两边为点u 的关联边 若两端之间多于一条边的,称为多重边。如图1中的e4、es 若一条边的两个端点相同,则称此为环(自回路)。如图1中的el 2简单图与多重图,不含环和多重边的图称为简单图,含有多重边的 图称为多重图。上图就是一个多重图。 3.无向图与有向图。G=(VE)中,若所有的边均有 ek=(vv)=(Vy,V)k=1,2…q,则称G为无向图,记为G=(V,E)。若图中边(v,v) 的端点是有序的,即表示以v为始点v为终点。则称该图为有向图,记为 D=(V,A)。在有向图中,把边称为弧。因此,A表示G中弧的集合 4图的同构
21 图 1 V={v1,v2,v3,v4,v5},E={e1,e2,e3,e4,e5,e6} 其中 e1={v1,v1},e2={v1,v2},e3={v1,v3} e4={v3,v4},e5={v3,v4},e6={v1,v4} 对于边(vi,vj)，则称 vi,vj 两点相邻，也称 vi,vj 为边(vi,vj)的端点。 若两条边有一个公共端点 u，则称这两边是相邻的，也称这两边为点 u 的关联边。 若两端之间多于一条边的，称为多重边。如图 1 中的 e4、e5。 若一条边的两个端点相同，则称此为环（自回路）。如图 1 中的 e1。 2.简单图与多重图，不含环和多重边的图称为简单图，含有多重边的 图称为多重图。上图就是一个多重图。 3. 无向图与有向图。 G=(V,E) 中 ， 若 所 有 的 边 均 有 ek=(vi,vj)=(vj,vi),k=1,2,…q，则称 G 为无向图，记为 G=(V,E)。若图中边(vi,vj) 的端点是有序的，即表示以 vi 为始点 vj 为终点。则称该图为有向图，记为 D=(V,A)。在有向图中，把边称为弧。因此，A 表示 G 中弧的集合。 4.图的同构。 v1 v4 v2 v3 (a) (b) e1 V1 e3 e4 e5 e6 V3 V5 V2 e2 V4
上面图(a)与图(b)初看起来似乎是不同的两个图,如果我们正确的确定 它们顶点之间的对应关系: Vb V3 Vd. v4 那么,它们边与边间的对应关系就有: (V1,v2H(Vc, Vb), (V1, V3)-(Vc, Va)(v1, v4(Vc, va) (v2, v3)-(Vb, Vd), (v3, v4)--(Vd, va) 从以上分析可以得出:图(a)和图(b实质上是一个图,只不过表现的形 式不同。 设图G=(VE)与G=(V,E),若它们的顶点存在一一对应,且保持同样 相邻关系,则称G和G'同构,记为G≡G。 5顶点的次。以点ⅴ为端点的边数称为点v的次,记为d(v)。图1中 d(v2)=1,d(v3)=3d(v1)=5。 次数为1的点称为悬挂点,连结悬挂点的边称为悬挂边 次数为0的点称为孤立点,如图1中的点vs 次为奇数的点称为奇点,次为偶数的点称为偶点。 在任何图中,顶点的次数与边数有如下性质: (1)∑d()=2q(其中p为G中顶点数,q为边数) 2)次为奇数的顶点必为偶数个 在有向图D=(VA)中,以v为始点的边数称为点v的出次,记为dt(v) 以v为终点的边数称为点v的入次,记为d(v)。显然d(v)=dt(v)+d(v) 且∑d(v,)=∑d(m,) 5网络。在实际问题中,只用图来描述所研究对象之间的关系往往是 不够的。与图联系在一起,通常还有与点或边有关的某些数量指标,通常 称之为“权”。权可以表示为:距离、费用、通过能力(数量)等。称含 有数量指标的赋权图为网络。与无向图和有向图相对应,网络可分为无向
22 上面图(a)与图(b)初看起来似乎是不同的两个图，如果我们正确的确定 它们顶点之间的对应关系： v1 vc,v2 vb,v3 vd,v4 va 那么，它们边与边间的对应关系就有： (v1,v2) (vc,vb),(v1,v3) (vc,vd)(v1,v4) (vc,va), (v2,v3) (vb,vd),(v3,v4) (vd,va)。 从以上分析可以得出：图(a)和图(b)实质上是一个图，只不过表现的形 式不同。 设图 G=(V,E)与 G=(V,E)，若它们的顶点存在一一对应，且保持同样 相邻关系，则称 G 和 G同构，记为 G G。 5.顶点的次。以点 v 为端点的边数称为点 v 的次，记为 d(v)。图 1 中， d(v2)=1,d(v3)=3,d(v1)=5。 次数为 1 的点称为悬挂点，连结悬挂点的边称为悬挂边。 次数为 0 的点称为孤立点，如图 1 中的点 v5。 次为奇数的点称为奇点，次为偶数的点称为偶点。 在任何图中，顶点的次数与边数有如下性质： (1) = = p i d vi q 1 ( ) 2 （其中 p 为 G 中顶点数，q 为边数） (2)次为奇数的顶点必为偶数个。 在有向图 D=(V,A)中，以 vi 为始点的边数称为点 vi 的出次，记为 d + (vi), 以 vi 为终点的边数称为点 vi 的入次，记为 d - (vi)。显然 d(vi)=d+ (vi)+d- (vi)。 且 + − = i i i i d (v ) d (v )。 5.网络。在实际问题中，只用图来描述所研究对象之间的关系往往是 不够的。与图联系在一起，通常还有与点或边有关的某些数量指标，通常 称之为“权”。权可以表示为：距离、费用、通过能力（数量）等。称含 有数量指标的赋权图为网络。与无向图和有向图相对应，网络可分为无向
网络和有向网络,分别记为G=(VE,W)和D=(V,A,W) 、连通图 1链。在无向图G=(VE),称一个点和边交替的序列{v,eiva,en vi,v}为连接ⅶi和ⅶt的一条链。简记为{vi,vn,…wn}。其中 el=(Vk,vk+1)k=1,2,…t-1。 点边序列中只有重复的点而无重复边者称为简单链。 点边序列中没有重复的点和重复边者称为初等链。 e10 图3 图4 如图3中:S1={V,5,V1,s,V4,V3}是一条连结v6和v3简单链。 S2={v6,Vs,V1,V4v3}是一条条连结v6和v3的初等链 首尾相接的链称为圈。 2路。在有向图D=(V,A)中,称链{v,v;v}为一条从ⅶ到v的路。 若v=V,则称之为回路。 在图4中S1={V6,Vs,V1,sV4,}是一条从v6和v3的路 S2={v1,V2,V4,vsvn}是一条回路。 3.连通图。如果一个图中任意两点间至少有一条链相连,则称此图为 连通图。 任何一个连通图都可以分为若干个连通子图,每个连通子图称为由原 图的分图。图5中的(b)就是(a)的三个分图
23 网络和有向网络，分别记为 G=(V,E,W)和 D=(V,A,W)。 二、连通图 1.链。在无向图 G=(V,E)，称一个点和边交替的序列{vi1,ei1,vi2,ei2,… vit-1,vit} 为连接 vi1 和 vit 的一条链。简记为 {vi1,vi2, … vit} 。其中 eik=(vik,vik+1),k=1,2,…t-1。 点边序列中只有重复的点而无重复边者称为简单链。 点边序列中没有重复的点和重复边者称为初等链。 v1 v2 v1 v2 v5 v4 v5 v4 图 3 图 4 如图 3 中：S1={v6,v5,v1,v5,v4,v3}是一条连结 v6和 v3简单链。 S2={v6,v5,v1,v4,v3}是一条条连结 v6和 v3的初等链。 首尾相接的链称为圈。 2.路。在有向图 D=(V,A)中，称链{vi1,vi2,…vit}为一条从 vi1 到 vit 的路。 若 vi1=vit，则称之为回路。 在图 4 中 S1={v6,v5,v1,v5,v4,v3}是一条从 v6和 v3的路。 S2={v1,v2,v4,v5,v1}是一条回路。 3.连通图。如果一个图中任意两点间至少有一条链相连，则称此图为 连通图。 任何一个连通图都可以分为若干个连通子图，每个连通子图称为由原 图的分图。图 5 中的(b)就是(a)的三个分图。 v v3 v6 3 v6 e3 e2 e1 e3 e2 e1 e11 e10 e7 e e9 10 e9 e7 e6 e4 e8 e6 e8 e4 e5 e5
图5 图6 三、图的矩阵表示 用矩阵表示图对于研究图的性质及应用常常是较方便的。图的矩阵表 示方法有多种,这里介绍其中两种常用矩阵。 1权矩阵。网络G=(VE,W),其边(v)的权重为W,构造矩阵 A=(an)hxm,其中 W(v,")∈ ∞其它 称矩阵A为网络G的权矩阵。其中主对角线上的元素a均为零。 如图6的权矩阵为 A 9034 3085 60 2邻接矩阵。对于图G=(VE)构造一个矩阵A=(a)hm, 其中 (v,")∈E 0其它 则称矩阵A为图G的邻接矩阵。当G为无向图时邻接矩阵为对称的
24 (a) (b) 图 5 图 6 三、图的矩阵表示 用矩阵表示图对于研究图的性质及应用常常是较方便的。图的矩阵表 示方法有多种，这里介绍其中两种常用矩阵。 1.权矩阵。网络 G=(V,E,W)，其边(vi,vj)的权重为 Wij，构造矩阵 A=(aij)nxn，其中 = 其它 W v v E a ij i j ij ( , ) 称矩阵 A 为网络 G 的权矩阵。其中主对角线上的元素 aij 均为零。 如图 6 的权矩阵为 = 7 5 6 0 4 4 8 0 6 2 3 0 8 5 9 0 3 4 0 9 2 4 7 A 2.邻接矩阵。对于图 G=(V,E)构造一个矩阵 A=(aij)nxn， 其中 = 0 其它 1 (v ,v ) E a i j ij 则称矩阵 A 为图 G 的邻接矩阵。当 G 为无向图时,邻接矩阵为对称的。 v1 v6 v5 v4 v3 v2 v1 v6 v5 v3 v4 v1 v1 v2 v3 v4 v5 2 4 3 5 7 6 9 8 4 。 。 。 。 。 。 。 。 。 。 。 。 v2
V4 o V5 图7 如图7的邻接矩阵为 000 01110 0000 001 000 0000 给出了一个图的邻接矩阵就等于给出了图的全部信息,可以从邻接矩 阵中得到图的很多重要性质。如 (1)A=(a)中第i行中的1的数目等于v点的出次dt(v),第j列中 的数目等于v点的入次d(v) (2)路径问题。如果图7是路径图,则由邻接矩阵就可算出G中任 点与其它点之间是否有路可通?若有路,走几步可以达到该点? 下面通过邻接矩阵的计算来求解v→vs和v-→V6有无路可能 先求A2 011000011000011010 001000001000010010 0 00100100 0011101 A 010001010001|001010 101011011 0000101000010010101 其中a=∑aa 可以理解aia=1时,当且仅当a和aj同时等于1,所以ana=1表 示从v到v有一条路,而A2=an42)则表示从v到v可两步到达
25 v2 v4 v3 v5 图 7 如图 7 的邻接矩阵为 = 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 A 给出了一个图的邻接矩阵就等于给出了图的全部信息，可以从邻接矩 阵中得到图的很多重要性质。如 （1）A=(aij)中第 i 行中的 1 的数目等于 vi 点的出次 d + (vi)，第 j 列中 1 的数目等于 vi 点的入次 d - (vi)。 （2）路径问题。如果图 7 是路径图，则由邻接矩阵就可算出 G 中任 一点与其它点之间是否有路可通？若有路，走几步可以达到该点？ 下面通过邻接矩阵的计算来求解 v1→v5 和 v1→v6有无路可能。 先求 A2 = = = 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 2 (2) A aij 其中 = = 6 1 (2) i ai j aik akj 。 可以理解 ai1a1j=1 时，当且仅当 ai1 和 a1j 同时等于 1，所以 ai1a1j=1 表 示从 vi 到 vj 有一条路，而 A2=aij(2)则表示从 vi到 vj 可两步到达。 v v6 1
a12}=1,说明v到ⅴs有一条路,可两步到达。 a162)=0,表明v到v6两步不能到达。继续计算A3 0000 21021 A3=A2.A 021121 01101 由于a163)=1,表明从ⅵ三步可达v6,若要了解这条路沿途经过哪些顶 点到达v6,只要回溯前面计算过程中的a16③这个数是怎样产生的,就可知 道。因为a163是由A2中的第一行与A中的第六列相应各数乘加而得,即 是由a152)=1和a6=1相乘而得。同理a1s2=1是由a1=1与aBs=1相乘而得。 因此有v→v3→s→v6。 §2.树与最小树 、树及其性质 连通且不含圈的无向图称为树,记为T(V,E) 设图T=(VE,顶点数为P,边数为q,则以下关于树的说法是等价的 1T是一棵树; 2T无圈,且qp-1; 3T连通,且q=p-1 4T无圈,但每加一新边即得唯一的一个圈: 5T连通,但每舍去一边就不连通 6T中任意两点,有唯一链相连。 、图的生成树 若图G的生成子图是一棵树,则称该树为G的生成树
26 a15(2)=1，说明 v1到 v5有一条路，可两步到达。 a16(2)=0，表明 v1到 v6两步不能到达。继续计算 A3 = = = 0 1 1 0 1 1 0 2 1 1 2 1 0 2 0 1 1 1 0 2 1 0 2 1 0 1 1 1 0 1 0 2 1 1 1 1 ( ) 3 2 (3) A A A aij 由于 a16(3)=1，表明从 v1 三步可达 v6，若要了解这条路沿途经过哪些顶 点到达 v6，只要回溯前面计算过程中的 a16(3)这个数是怎样产生的，就可知 道。因为 a16(3)是由 A2 中的第一行与 A 中的第六列相应各数乘加而得，即 是由 a15(2)=1 和 a56=1 相乘而得。同理 a15(2)=1 是由 a13=1 与 a35=1 相乘而得。 因此有 v1→v3→v5→v6。 §2. 树与最小树 一、树及其性质 连通且不含圈的无向图称为树，记为 T(V,E)。 设图 T=(V,E)，顶点数为 P，边数为 q，则以下关于树的说法是等价的。 1.T 是一棵树； 2.T 无圈，且 q=p－1； 3.T 连通，且 q=p－1； 4.T 无圈，但每加一新边即得唯一的一个圈； 5.T 连通，但每舍去一边就不连通； 6.T 中任意两点，有唯一链相连。 二、图的生成树 若图 G 的生成子图是一棵树，则称该树为 G 的生成树
图8 图8中(b)就是(a)的生成树。 图G=(VE)有生成树的充要条件是G为连通图 三、最小树问题 在给定连通赋权无向图G=(V,E,W)中,求G的生成树T=(VE),使E 各边权WC0)的总和最小的问题称为最小树问题。其数学模型为: W(T=min > w (v,v)∈T 其中T*称为最小树。 许多网络问题都可归结为最小树问题,如设计长度最小的公路网把若 干城市联通;设计用料最省的电话线网把有关单位联系起来。求最小树有 以下两种方法: (1)用“避圈法”(Kπ rusal算法)求最小树。其基本思想是:开始选 条权最小的边,以后每步从未选的边中选取一条权最小的边,使它与已选 边不构成圈,直至选够q-1条边止 (2)用“破圈法”(管梅谷算法)求最小树。其方法步骤是: 1°先从图G任取一个圈,并从圈中去掉一条权最大的边。若在同 圈中有几条都是权最大边,则任选其中一边去掉。 2°在余下的子圈中,重复上述步骤,直至没有圈止。 例
27 (a) (b) 图 8 图 8 中(b)就是(a)的生成树。 图 G=(V,E)有生成树的充要条件是 G 为连通图。 三、最小树问题 在给定连通赋权无向图 G=(V,E,W)中，求 G 的生成树 T=(V,E)，使 E 各边权 Wij(0)的总和最小的问题称为最小树问题。其数学模型为： W T = min Wij ( ) * (vi,vj)T 其中 T*称为最小树。 许多网络问题都可归结为最小树问题，如设计长度最小的公路网把若 干城市联通；设计用料最省的电话线网把有关单位联系起来。求最小树有 以下两种方法： （1）用“避圈法”(Kruskal 算法)求最小树。其基本思想是：开始选一 条权最小的边，以后每步从未选的边中选取一条权最小的边，使它与已选 边不构成圈，直至选够 q－1 条边止。 （2）用“破圈法”(管梅谷算法)求最小树。其方法步骤是： 1°先从图 G 任取一个圈，并从圈中去掉一条权最大的边。若在同一 圈中有几条都是权最大边，则任选其中一边去掉。 2°在余下的子圈中，重复上述步骤，直至没有圈止。 例 ° ° ° ° ° ° ° ° ° e1 l1 l6 e6 l7 e7 e2 e4 l2 e3
§3.最短路问题 最短路问题是网络理论中应用最广泛的问题之一,许多优化问题可以 使用这个模型,如管道铺设,设备更新,线路安排等。在第三章我们曾介 绍了最短路问题的动态规划解法,但某些最短路的问题构造动态规划基本 方程较困难,而图论方法则直观有效 给定D=(V,A,W),其中w∈W,表示弧(v,v)的权(可以是费用、时间 距离等)。设ⅴ和v是D中任意两顶点,求一条路,使它是从ⅴ到v的 所有路中总权最小的路。其数学模型为: W(P)=mn∑W (v,v)∈P W」≥0情况下,求最短路的 Di jkstra标号法 1该法的基本思想是基于以下原理:若序列{v,v,…vk,…v}是从w到 vt的最短路,则序列{vs,wi,…Vk}必为从vs到vk的最短路。 2 Dijkstra标号法的基本思想是采用两种标号:T标号与P标号,T标 号为临时性标号( Temporary Label,P标号为永久性标号( Permanent labe 从v开始,逐步向外探寻最短路。给ⅵ点P标号时,表示从v到ⅵ点的最 短路权,ⅵ的标号不再改变。给v点T标号时,表示从vs到w点的最短路 权上界的估计。凡没有得到P标号的点都有T标号。标号法每一步都是把 某一T标号点改为P标号,当终点vt得到P标号时,计算全部结束。如果 点ⅴ不能由T标号变为P标号,则说明ws到v不存在路 3.步骤: (1)给v以P标号,P(ⅴ)=0,其余各点给T标号,且T(v)=+ (2)若v点为刚得到P标号的点,考虑T标号点v(v,v)∈A。对v的T 标号进行如下的更改 T(vimin(T(v), P(vi)+wii (4.1)
28 §3. 最短路问题 最短路问题是网络理论中应用最广泛的问题之一，许多优化问题可以 使用这个模型，如管道铺设，设备更新，线路安排等。在第三章我们曾介 绍了最短路问题的动态规划解法，但某些最短路的问题构造动态规划基本 方程较困难，而图论方法则直观有效。 给定 D=(V,A,W)，其中 wijW，表示弧(vi,vj)的权（可以是费用、时间、 距离等）。设 vs 和 vt 是 D 中任意两顶点，求一条路，使它是从 vs 到 vt 的 所有路中总权最小的路。其数学模型为： W P = min Wij ( ) * (vi,vj)P 一、Wij0 情况下，求最短路的 Dijkstra 标号法 1.该法的基本思想是基于以下原理：若序列{vs,vi1,…vik,…vt}是从 vs 到 vt 的最短路，则序列{vs,vi1,…vik}必为从 vs 到 vik的最短路。 2.Dijkstra 标号法的基本思想是采用两种标号：T 标号与 P 标号，T 标 号为临时性标号(Temporary Label)，P 标号为永久性标号(Permanent Label)。 从 vs 开始，逐步向外探寻最短路。给 vi 点 P 标号时，表示从 vs 到 vi 点的最 短路权，vi 的标号不再改变。给 vi 点 T 标号时，表示从 vs 到 vi 点的最短路 权上界的估计。凡没有得到 P 标号的点都有 T 标号。标号法每一步都是把 某一 T 标号点改为 P 标号，当终点 vt 得到 P 标号时，计算全部结束。如果 点 vj 不能由 T 标号变为 P 标号，则说明 vs 到 vj 不存在路。 3.步骤： (1)给 vs 以 P 标号，P(vs)=0，其余各点给 T 标号，且 T(vi)=+。 (2)若 vi 点为刚得到 P 标号的点，考虑 T 标号点 vj,(vi,vj)A。对 vj 的 T 标号进行如下的更改： T(vj)=min{T(vj),P(vi)+wij} (4.1)
(3)比较所有具有T标号点,把最小者改为P标号,即 P(vjo=min T(vi) 为T标号 若全部点均为P标号。则停止。否则以v代v,返回(2) 例,用 Dijkstra标号法求下图由v到各顶点的最短路。 (图9) 解:标号过程如图10中(a)-(e),其中方框表示P标号,里面的数字 表示从v到该点的最短路长。圆圈表示T标号,其中的数字表示从v到该 点最短路长的上界 (a)P(v1)=0,T(v2)=1 (b)P(v)=0,P(v2)1 T(v3)=4 T(v3)=3,T(4)=4 (c)P(v1)=0,T(v2)=1 (dP(vl)=0,P(v2)=1 P(V3)=3,T(V4)=4 P(v3)=3,P(
29 (3)比较所有具有 T 标号点，把最小者改为 P 标号，即 P(vjo)=min{T(vj)} vj 为 T 标号 若全部点均为 P 标号。则停止。否则以 vjo 代 vi，返回(2) 例，用 Dijkstra 标号法求下图由 v1 到各顶点的最短路。 v2 v5 v1 v3 v6 （图 9） 解：标号过程如图 10 中(a)－(e)，其中方框表示 P 标号，里面的数字 表示从 v1 到该点的最短路长。圆圈表示 T 标号，其中的数字表示从 v1 到该 点最短路长的上界。 v2 + v2 + v1 v1 v3 + v3 + (a) P(v1)=0,T(v2)=1 (b)P(v1)=0,P(v2)=1 T(v3)=4 T(v3)=3,T(v4)=4 v2 + v2 + v1 v1 v3 v6 v3 v6 (c) P(v1)=0,T(v2)=1 (d)P(v1)=0,P(v2)=1 P(v3)=3,T(v4)=4 P(v3)=3,P(v4)=4 ° ° ° ° ° ° 2 3 3 2 1 1 1 2 4 2