特殊的简单图（完全图） 11 若简单图G中任意两点均相邻，则称为完全图。 记为K,其中n是图中顶点数。 ▣K中每个顶点皆为n-1度，总边数为n(n-1)/2。 口边数达到上限的简单图。 K K3 K4 Ks
若简单图G中任意两点均相邻，则称为完全图。 记为Kn ,其中n是图中顶点数。 Kn中每个顶点皆为n-1度，总边数为n(n-1)/2。 边数达到上限的简单图。 K3 K1 K2 K4 K5 11 特殊的简单图（完全图）
特殊的简单图（圈图与轮图) 12 Cycle Wheel ☒ W; Wa W
C3 C4 C5 W3 W4 W5 Cycle Wheel 12 特殊的简单图（圈图与轮图）
特殊的简单图（立方体图） 13 n-cube 110 111 10 11 100 10 010 011 00 01 000 001 21 22 23 正则图：顶点度相同的简单图
Q1 0 1 Q2 10 11 00 01 Q3 100 101 000 001 110 111 010 011 n-cube 正则图：顶点度相同的简单图 13 特殊的简单图（立方体图）
子图 14 口设G=<E>,G=<,E>,如果cEcE,则称G 是G的子图。 口如果cV,或者EcE,则称为真子图。 0 诱导（导出）子图：可以由顶点集的子集，或者由 边集的子集导出一个子图
设G=<V,E>, G’=<V’,E’>, 如果V’V, E’E, 则称G’ 是G的子图。 如果V’V, 或者E’ E, 则称为真子图。 诱导(导出)子图：可以由顶点集的子集，或者由 边集的子集导出一个子图。 14 子图
图的运算 15 o加新边：G+e 口减边或边集：G-e 口减点或点集：G-（同时删除与v关联的边) 口边的收缩：G/e G y
加新边:G+e 减边或边集：G-e 减点或点集: G-v （同时删除与v关联的边） 边的收缩: G/e 15 图的运算