三、完全图 定义在图G=<V,E>中,若所有结点的度数均有相 同度数d,则称此图为d次正则图。 定义一个(n,m)(n22)的简单无向图,若它 为n-1次正则图,则称该(n,m)图为无向简单 完全图,简称完全图,记为K。 有向完全图 定理设无向完全图G有n个顶点,则G有m(m-1)/2条 边 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 三、完全图 定义 在图G＝<V，E>中，若所有结点的度数均有相 同度数d，则称此图为d次正则图。 定义 一个(n，m)(n2)的简单无向图，若它 为n-1次正则图，则称该(n，m)图为无向简单 完全图，简称完全图,记为Kn。 有向完全图 定理 设无向完全图G有n个顶点，则G有n(n-1)/2条 边
例 例:如图(a)、(b)、(c)、(d)所示,它们分别 是无向的简单完全图K3,K4,K5和有向的简单 完全图K3 K4 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 例： 例：如图 (a)、(b)、(c)、(d)所示，它们分别 是无向的简单完全图K3，K4，K5和有向的简单 完全图K3
四、子图和补图 定义设有图G=<V,E和图G1=<V1,E>,若G和G1满足 若V1V,E1≌E,则称G1是G的子图,记为G≌G; 若G1cG,且G1≠G(即V1cV或E1cE),则称G1 是G的真子图,记为G1cG; Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定义 设有图G＝<V，E>和图G1＝<V1，E1>，若G和G1满足 ： 若V1V，E1E，则称G1是G的子图，记为G1G； 若G1G，且G1G(即V1V或E1E)，则称G1 是G的真子图，记为G1G； 四、子图和补图
四、子图和补图 定义若V1=V,E1三E,则称G1是G的生成子图,记 为G1gG; 定义设G=<V,E>为具有n个结点的简单图,从完 全图Kn中删去G中的所有的边而得到的图称为G 的补图(或G的补),记为G Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定义 若V1＝V，E1E，则称G1是G的生成子图，记 为G1G； 定义 设G＝<V，E>为具有n个结点的简单图,从完 全图Kn中删去G中的所有的边而得到的图称为G 的补图(或G的补)，记为 。 四、子图和补图 G
相对补图 定义G=<V,E>是图,G’=<V’,E〃>是 G的子图,E”=E一E’,V”是E”中边所 关联的所有顶点集合,则G”=<V”,E”>称为 G’关于G的相对补图。 关于完全图的子图的补图称为此子图的 绝对补图 Guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn 定义 Ｇ＝<Ｖ，Ｅ>是图，Ｇ’＝<Ｖ’ ，Ε’>是 Ｇ的子图，Ｅ”＝Ｅ－Ｅ’ ，Ｖ” 是Ｅ”中边所 关联的所有顶点集合，则Ｇ”＝<Ｖ” ，Ｅ”>称为 Ｇ’关于Ｇ的相对补图。 关于完全图的子图的补图称为此子图的 绝对补图。 相对补图