图论第二十五节课

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1本次课主要内容本次课主要内容(一一)、与色数有关的几类图、与色数有关的几类图(二二)、完美图简介、完美图简介与色数有关的几类图和完美图与色数有关的几类图和完美图 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 1、临界图、临界图(一一)、与色数有关的几类图、与色数有关的几类图 定义定义1 若对图若对图G的任意真子图的任意真子图H，都有，都有 ，则，则称称G是临界图。点色数为是临界图。点色数为k的临界图称为的临界图称为k临

2、界图。临界图。()( )HG3临界图临界图4临界图临界图非临界图非临界图 注：临界图由狄拉克在注：临界图由狄拉克在1952年首先提出并研究。上面年首先提出并研究。上面的的4临界图是临界图是Grotzsch在在1958年提出的。年提出的。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 定理定理1 临界图有如下性质临界图有如下性质 (1) k色图均有色图均有k临界子图；临界子图； (2) 每个临界图均为简单连通图；每个临界图均为简单连通图； (3) 若若G是是k临界图，则临界图，则k-1k-1。 证明：证明： (1)是显然的。是显然

3、的。 (2) 因为删掉环或平行边中的一条边并不破坏原有的顶因为删掉环或平行边中的一条边并不破坏原有的顶点正常着色，所以每个临界图是单图；又因为删掉色数点正常着色，所以每个临界图是单图；又因为删掉色数较小的分支，剩下部分的图的色数和原图色数相等，所较小的分支，剩下部分的图的色数和原图色数相等，所以，临界图必须是连通图。以，临界图必须是连通图。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 (3) 若不然，若不然， k-1 k-1。 设设d(v)=。因为。因为G G是是k k临界图，所以临界图，所以G-vG-v是是k-1k-1可正常

4、顶可正常顶点着色的。设点着色的。设是是G-vG-v的的k-1k-1正常顶点着色方案，显然，正常顶点着色方案，显然，它可以扩充为它可以扩充为G G的的k-1k-1正常点着色方案。这与正常点着色方案。这与G G是是k k临界图临界图相矛盾。相矛盾。 推论：每个推论：每个k色图至少有色图至少有k个度不小于个度不小于k-1的顶点。的顶点。 证明：因证明：因G是是k色图，所以，它包含色图，所以，它包含k临界子图临界子图G1,所以所以有：有：(G(G1 1)k-1,)k-1,即即G G1 1中至少有中至少有k k个顶点，其度数不小于个顶点，其度数不小于k-1k-1。所以，。所以，G G中中至少有至少有k个

5、度不小于个度不小于k-1的顶点。的顶点。 例例1 利用上面推论证明：对任意图利用上面推论证明：对任意图G，有：，有：()()1GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 证明：设证明：设G的点色数为的点色数为 。由推论，。由推论，G中至少有中至少有 个顶点，其度数不小于个顶点，其度数不小于()()1GG ()G()G()1G 所以，所以， ，即：，即：()()1GG 例例2 求证：临界图没有割点。求证：临界图没有割点。 证明：设证明：设G是是k临界图。如果临界图。如果G有割点有割点v, 设设G1,G2,Gr是是G-v的分

6、支。又设第的分支。又设第i个分支顶点集为个分支顶点集为Vi (1ir)ir)。 设设Hi=GViv, (1ir)。则。则Hi是是k-1可正常点着色可正常点着色的，现对每个的，现对每个Hi进行进行k-1正常点着色，且正常点着色，且v都分配同一种颜色，都分配同一种颜色，那么，将着色后的那么，将着色后的Hi合在一起，得到合在一起，得到G的的k-1正常点着色方正常点着色方案，这与案，这与G是是k色图矛盾。所以临界图没有割点。色图矛盾。所以临界图没有割点。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 例例3 求证：仅有的求证：仅有的1临

7、界图是临界图是k1;仅有的仅有的2临界图是临界图是K2;仅仅有的有的3临界图奇圈。临界图奇圈。 证明：由于证明：由于1色图是空图，所以色图是空图，所以1临界图只能是临界图只能是K1;2色色图是偶图，所以，图是偶图，所以，2临界图只能是临界图只能是K2; 3色图必然含有奇圈，色图必然含有奇圈，而奇圈的色数是而奇圈的色数是3，所以，所以，3临界图只能是奇圈。临界图只能是奇圈。 例例4 求证：布鲁克斯定理等价于下述命题：若求证：布鲁克斯定理等价于下述命题：若G是是k临临界图界图(k4), 且不是完全图，则且不是完全图，则2mn(k-1)+1,其中其中m为为G的的边数而边数而n为顶点数。为顶点数。 证

8、明：证明：(1) 由布鲁克斯定理推例由布鲁克斯定理推例4中命题。中命题。 因因G是是k临界图临界图,所以所以G是连通单图，又是连通单图，又k4, 所以所以G不能不能是奇圈，再由是奇圈，再由G不是完全图，所以由布鲁克斯定理有不是完全图，所以由布鲁克斯定理有 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 定理定理2(布鲁克斯，布鲁克斯，1941) 若若G是连通的是连通的单图，并且它既不是奇圈，又不是完全单图，并且它既不是奇圈，又不是完全图图 ()()GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1

9、 0.5 0 0.5 1 n 8 k。 再由再由k临界图的性质，有临界图的性质，有k-1.k-1.所以：所以：()2( )(1)v V Gmd vn (1)(1)knk(1)1n k (2) 由例由例4中命题推布鲁克斯定理。中命题推布鲁克斯定理。 因为连通单图因为连通单图G不是奇圈，也不是完全图。设不是奇圈，也不是完全图。设G的的k临临界子图是界子图是H。 情形情形1， H是奇圈。是奇圈。 在这种情况下，由于在这种情况下，由于G不是奇圈，所以，不是奇圈，所以，H之外必然之外必然有边和有边和H相连，即相连，即(G)3,(G)3,另一方面，另一方面，k(G)=k(H)=3,k(G)=k(H)=3,

10、所所 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 以，以，k(G)(G);(G); 情形情形2， H是完全图是完全图Hk 在这种情况下，由于在这种情况下，由于G是连通的非完全图，那么在是连通的非完全图，那么在H之外，必然有边和之外，必然有边和H相连，即相连，即K(H)=k(G);K(H)=k(G); 情形情形3， H既不是奇圈又不是完全图，由例既不是奇圈又不是完全图，由例3知道，知道，k4。H满足例满足例4中条件。中条件。 所以，由例所以，由例4中的结论有：中的结论有：() ()2()()( ()1)1H n Hm Hn Hk

11、 H()( ()1)1n Hk G 所以，有：所以，有：1()( ()1)()Hk Gn H 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 即证明：即证明：()()Gk G 2、唯一可着色图、唯一可着色图 对图的顶点进行正常着色，实际上给出图的顶点集合对图的顶点进行正常着色，实际上给出图的顶点集合的一种划分，不同的着色方案，给出的划分一般不同。的一种划分，不同的着色方案，给出的划分一般不同。但是，也存在一类特殊图，对于任意的最优着色方案，但是，也存在一类特殊图，对于任意的最优着色方案，导出的顶点划分却是相同的。为此，我们给出如

12、下定义。导出的顶点划分却是相同的。为此，我们给出如下定义。 定义定义2 设简单标定图设简单标定图G的点色数是的点色数是k, 如果在任意的如果在任意的k正正常点着色方案下，导出的顶点集合划分唯一，称常点着色方案下，导出的顶点集合划分唯一，称G是唯一是唯一k可着色图，简称唯一可着色图。可着色图，简称唯一可着色图。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 例例5 考察下面考察下面3色图是否是唯一色图是否是唯一3可着色图。可着色图。v3v2v1G1v1G2v5v4v3v2G3v5v4v3v2v1 解：解：(1) 对于对于G1来说

13、，来说，G1的任意的任意3正常着色方案导出的正常着色方案导出的顶点划分均是顶点划分均是v1, v2v3，所以，所以，G1是唯是唯一一3可着色图；可着色图； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12v1G2v5v4v3v2 (2) 对于对于G2来说，来说，G2的任意的任意3正常着色方案导出的顶点正常着色方案导出的顶点划分均是划分均是v1, v2，v4v3,v5，所以，所以，G2是是唯一唯一3可着色图；例如：可着色图；例如：v1G2v5v4v3v2v1G2v5v4v3v2 (3) 对于对于G3来说，来说，G3不是唯一不是唯一3

14、可着色图；因为：可着色图；因为：G3v5v4v3v2v1G3v5v4v3v2v1 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 下面给出唯一可着色图的几个特征。下面给出唯一可着色图的几个特征。 定理定理2(哈拉里，哈拉里，1968） 设设G是唯一是唯一k可着色图，可着色图，k2, 则：则： (1) k-1;k-1; (2) 在在G G的任意一种的任意一种k k着色中，着色中，G G的任意两个色组的并的的任意两个色组的并的导出子图是连通的。导出子图是连通的。 证明：证明： (1) 若不然，设若不然，设 k-1, 令令d(u) =

15、,则则 ( )1uN ukuN (u) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 设设是是G G的的k k着色方案，因为着色方案，因为 ，所以，所以，在在下，至少有一种颜色下，至少有一种颜色u u及其邻域均没有用到，设该色及其邻域均没有用到，设该色为为m,m,改变改变u u的颜色为的颜色为m,m,其余点的着色不变，这样得到其余点的着色不变，这样得到G G的的k k着色方案着色方案1 1. .显然，显然，与与1 1导出的导出的G G的顶点划分不同，这的顶点划分不同，这与与G G是唯一可着色图矛盾。是唯一可着色图矛盾。 ()1

16、uNuk (2) 若不然，则存在若不然，则存在G的的k k着色方案着色方案和和G G的两个色组的两个色组C C1 1与与C C2 2, ,使得使得H=GCH=GC1 1CC2 2 不连通。设不连通。设H H1 1与与H H2 2是是H H的两个分支。的两个分支。 因为因为G是唯一可着色图，所以，对任意点是唯一可着色图，所以，对任意点u和其邻域和其邻域N(u), 它们在它们在下，必然用完了下，必然用完了k k种颜色，否则，由种颜色，否则，由(1)(1)的的证明，得到证明，得到G G是非唯一可着色图。是非唯一可着色图。 这样，这样，H1与与H2中同时含有中同时含有C1和和C2中的顶点。中的顶点。

17、0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 如果交换如果交换C1V(H1)与与C2V(H1)中顶点颜色，得到中顶点颜色，得到G的的k着色着色1 1, ,显然，显然，与与1 1的色划分是不同的。这与的色划分是不同的。这与G G的着的着色唯一性矛盾。色唯一性矛盾。v1Gv5v4v3v2 例如，在下图例如，在下图G中，由黄色、红色色组导出的子图是中，由黄色、红色色组导出的子图是连通的。连通的。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 定理定理3 (夏特朗）每

18、个唯一夏特朗）每个唯一n (n2)可着色图是可着色图是(n-1)连通的。连通的。 证明：设证明：设G是唯一是唯一n可着色图可着色图(n2)。 情形情形1，如果，如果G是完全图，则是完全图，则G=Kn,显然显然G是是n-1连通的。连通的。 情形情形2，如果，如果G是非完全图，假若是非完全图，假若G不是不是(n-1)连通的，那连通的，那么其连通度么其连通度k(G)n-2n-2。于是。于是G G中存在点集中存在点集S S，S S=n-2, =n-2, 使得使得G-SG-S不连通。不连通。 设设是是G G的的n n着色方案。在该方案下，至少有两种颜色着色方案。在该方案下，至少有两种颜色c c1 1与与

19、c c2 2，S S中的顶点都没有使用。中的顶点都没有使用。 而由定理而由定理2的的(2), 着着c1与与c2色的点导出子图必连通。所以色的点导出子图必连通。所以,着着c1与与c2色的顶点在色的顶点在G-S中的同一个分支中，设该分支为中的同一个分支中，设该分支为G1. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 在在G-S中取一个不在中取一个不在G1中的点中的点u,将其染上将其染上c1色，这样得到色，这样得到G的另一个的另一个n着色方案。着色方案。 显然，两种着色方案导出的色划分不同，这与条件矛盾。显然，两种着色方案导出的色

20、划分不同，这与条件矛盾。 推论：设推论：设G是唯一是唯一n(n2)可着色图，可着色图，是任意一种是任意一种n n着色着色方案，方案，则由则由的的任意任意k个色组导出的子图是个色组导出的子图是(k-1)连通的。连通的。 证明：显然，任意证明：显然，任意k个色组导出子图是唯一个色组导出子图是唯一k可着色图，可着色图，由定理由定理3得到推论结论。得到推论结论。 注：注： (1) 唯一唯一1可着色图是零图；可着色图是零图； (2) 唯一唯一2可着色图是偶图；可着色图是偶图； 除此之外，没有简单的结论！除此之外，没有简单的结论！ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2

21、 1 0.5 0 0.5 1 n 18 定理定理4 每个唯一每个唯一4可着色可平面图都是极大可平面图。可着色可平面图都是极大可平面图。 证明：只需证明：证明：只需证明：m=3n-6即可。即可。 一方面：一方面：G是可平面图，有：是可平面图，有：m3n-6;3n-6; 另一方面：设另一方面：设G是唯一是唯一4可着色的可平面图，可着色的可平面图，是一种是一种4 4着色方案，色组记为着色方案，色组记为V Vi i(1i4).(1i4). 因为因为ij时，时，GViVVj j 是连通的，所以是连通的，所以: :( )1ijijm G VVnn 于是：于是：41()(1)36ijijim Gnnn 所以

22、，所以，m=3n-6,即即G是极大可平面图。是极大可平面图。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 定义定义3 若图若图G的点色数是的点色数是k，且，且G中不含有三角形，称中不含有三角形，称G是一个不含三角形的是一个不含三角形的k色图。色图。 3、不含三角形的、不含三角形的k色图色图 例如：例如：不含三角形的三色图不含三角形的三色图不含三角形的不含三角形的4色图色图 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 数学家狄拉克数学家狄拉克1953年在其论

23、文年在其论文“k色图的构造色图的构造”中提出一中提出一个问题：对于任意大的一个正整数个问题：对于任意大的一个正整数k, 是否存在一个图，不是否存在一个图，不包含三角形但色数是包含三角形但色数是k？ 上面问题分别由勃兰克上面问题分别由勃兰克.斯德卡兹斯德卡兹(1954), 米歇尔斯基米歇尔斯基(1955)独立作出了回答。独立作出了回答。 米歇尔斯基米歇尔斯基(1955)给出了由一个不含三角形的给出了由一个不含三角形的k色图色图Gk构造一个不含三角形的构造一个不含三角形的k+1色图色图Gk+1的方法。的方法。 构造方法：设构造方法：设Gk的顶点是的顶点是u1,u2,un, 添加点添加点v1,v2,

24、vn和点和点v。将将vi与与ui的所有邻点及的所有邻点及v相连，相连，1inin。如此得到的图就是一。如此得到的图就是一个不含三角形的个不含三角形的k+1k+1色图。色图。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 例例6，利用米歇尔斯基方法构造一个不含三角形的，利用米歇尔斯基方法构造一个不含三角形的4色图。色图。 解：注意到解：注意到C5是不含三角形的是不含三角形的3色图，于是由色图，于是由C5可以构造可以构造出不含三角形的出不含三角形的4色图。色图。不含三角形的不含三角形的3色图色图u4u3u2u1u5不含三角形的不含

25、三角形的4色图色图u1u2u3u4u5v1v2v3v4v5v 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22 注：利用米歇尔斯基方法构造一个不含三角形的注：利用米歇尔斯基方法构造一个不含三角形的k色图时，色图时，结果图与初始图有关。结果图与初始图有关。 例例7，设，设Gk是不含三角形的是不含三角形的k色图，顶点数为色图，顶点数为f(k), 而而Gk+1是是由米歇尔斯基方法构造出来的不含三角形的由米歇尔斯基方法构造出来的不含三角形的k+1色图，其顶点色图，其顶点数设为数设为f(k+1)。求出。求出f(k)的递推公式。的递推公式。

26、解：解：(1)( )1f kf k 定理定理5 (米歇尔斯基米歇尔斯基)对于任意正整数对于任意正整数k, 存在不含三角形的存在不含三角形的k色图。色图。 1961年，数学家年，数学家Erdos用概率方法证明了更一般结论：用概率方法证明了更一般结论： 定理定理6 (Erdos)对于任意正整数对于任意正整数m和和n, 存在一个围长超过存在一个围长超过m的的n色图。色图。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 1968年，罗瓦斯构造性地证明了上面定理年，罗瓦斯构造性地证明了上面定理6 注：定理注：定理6实际上是数学家凯利提出

27、的一个猜想。实际上是数学家凯利提出的一个猜想。(二二)、完美图简介、完美图简介 1、相关概念、相关概念 定义定义4 (1)单单 图图G的团：若单图的团：若单图G的一个顶点子集的一个顶点子集S在在G中的导出子图是完全图中的导出子图是完全图,则称则称S是是G的一个团；的一个团； (2) 单图单图G的团数：单图的团数：单图G的最大团包含的顶点数称为的最大团包含的顶点数称为G的团数，记为的团数，记为c l (G) ,即：即：()maxcl GS SG是 的团 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24 显然，图显然，图G的点色数与团

28、数的关系为：的点色数与团数的关系为： 定义定义5 设设G是一个图。若对是一个图。若对G的每个点导出子图的每个点导出子图H，均，均有有 ,则称则称G为完美图。为完美图。()()Gcl G()()Hcl H 例如例如Kn, 偶图是完美图，而不含三角形但含奇圈的图不偶图是完美图，而不含三角形但含奇圈的图不是完美图。是完美图。 因为不含三角形的但含奇圈的图的团数为因为不含三角形的但含奇圈的图的团数为2，但色数为，但色数为3，所以，它不能是完美图。所以，它不能是完美图。 注：完美图问题是点着色的进一步讨论题材，属于比较注：完美图问题是点着色的进一步讨论题材，属于比较高深和困难的问题。高深和困难的问题。

29、0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25 图图G的点独立数记为的点独立数记为(G)(G)或或。 定义定义6 设设G是一个图。由是一个图。由G中若干互不邻接的顶点作成中若干互不邻接的顶点作成的子集称为的子集称为G的一个点独立集；的一个点独立集；G中含顶点数最多的点独中含顶点数最多的点独立集称为立集称为G的最大独立集，其包含的顶点数称为独立数。的最大独立集，其包含的顶点数称为独立数。 对该问题的研究，早在对该问题的研究，早在1932年哥尼和加莱就已经涉及，年哥尼和加莱就已经涉及，但到了但到了1960年，完美图概念才被贝尔热正式

30、提出。所以，年，完美图概念才被贝尔热正式提出。所以，贝尔热是完美图研究的代表人物。贝尔热是完美图研究的代表人物。 注：关于图的覆盖与图的点独立数之间的关系，加莱得注：关于图的覆盖与图的点独立数之间的关系，加莱得到了一些很漂亮的结论。其中之一是：到了一些很漂亮的结论。其中之一是： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26 定理定理7 偶图的补图是完美图。偶图的补图是完美图。 分析：欲证分析：欲证 是完美图，要证明对任意是完美图，要证明对任意 有有 GHG()()Hcl G 由于由于 也是某偶图的补，所以只需要证明也是某偶图的

31、补，所以只需要证明H()()Gcl G 补充定理：设补充定理：设G是一个偶图，记是一个偶图，记h为为G的最大匹配包含的最大匹配包含的边数，的边数，i为为G的最大独立集包含的顶点数，的最大独立集包含的顶点数，j为构成覆盖为构成覆盖G的顶点的的顶点的G的最小点边集合，则：的最小点边集合，则：i = j = m+n-h。 2、关于色数的完美图的主要结论、关于色数的完美图的主要结论 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 27 定理定理8 图图G是完美图当且仅当对是完美图当且仅当对G的每个真导出子图的每个真导出子图H,存在一个独立集存

32、在一个独立集I，使得：，使得： 所以：所以： 偶图的补图是完美图。偶图的补图是完美图。()()Hcl GG()G 证明：在证明：在 的正常着色方案下，每个色组对应的正常着色方案下，每个色组对应G的一的一个顶点或者个顶点或者K2。这样，。这样， 应该是应该是G的最小点覆盖中包含的最小点覆盖中包含的点数和边数。由补充定理：它等于的点数和边数。由补充定理：它等于G中最大独立集包含中最大独立集包含的顶点数，即等于的顶点数，即等于 的团数。所以有：的团数。所以有：G()()cl HIcl H 证明略。证明略。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0

33、.5 1 n 28 定义定义7 设设S是图是图G的顶点集合的一个划分。如果的顶点集合的一个划分。如果S的每个的每个子集在子集在G中的导出子图均是完全图，称中的导出子图均是完全图，称S是是G的一个完全分的一个完全分类。类。G的最小完全分类所包含的元素个数称为的最小完全分类所包含的元素个数称为G的完全数，的完全数，记为记为(G),(G),即：即： 3、关于独立数的完美图、关于独立数的完美图()minGS SG为 的完全分类 注：注： 。这是因为独立集中任意一点应该属。这是因为独立集中任意一点应该属于于S中的某个顶点子集，同时，中的某个顶点子集，同时，S中每个顶点子集最多包含中每个顶点子集最多包含独立集中的一个元素。独立集中的一个元素。()()GG 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.