第一章图的基本概念 本次课主要内容 (一)、完全图、偶图与补图 (二)、顶点的度与图的度序列
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 第一章 图的基本概念 本次课主要内容 (二)、顶点的度与图的度序列 (一)、完全图、偶图与补图
(一)、完全图、偶图与补图 1、每两个不同的顶点之间都有一条边相连的简单图称为 完全图. 在同构意义下，个顶点的完全图只有一个，记为K. K K3 K 容易求出： m(Kn)=号n(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 2 (一)、完全图、偶图与补图 1、每两个不同的顶点之间都有一条边相连的简单图称为 完全图 . 在同构意义下，n个顶点的完全图只有一个，记为Kn K2 K3 K5 容易求出： 1 ( ) ( 1) 2 m K n n n = −
2、所谓具有二分类(X,)的偶图（或二部图）是指一个图， 它的点集可以分解为两个（非空）子集X和Y,使得每条边的一个 端点在X中，另一个端点在Y中. 完全偶图是指具有二分类(X,Y)的简单偶图，其中X 的每个顶点与Y的每个顶点相连，若X=m,Y后，则这样 的偶图记为Km,n 图1 图 图1与图2均是偶图，图2是K23
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 2、所谓具有二分类（X, Y）的偶图（或二部图）是指一个图， 它的点集可以分解为两个(非空)子集X和Y，使得每条边的一个 端点在X中，另一个端点在Y中. 完全偶图是指具有二分类（X, Y）的简单偶图，其中X 的每个顶点与Y的每个顶点相连，若|X|=m，|Y|=n，则这样 的偶图记为 K m, n 图1 图2 图1与图2均是偶图，图2是K2,3
偶图是一种常见数学模型。 例1学校有6位教师将开设6门课程。六位教师的代号是 x1(i=1,2,3,4,5,6,六门课程代号是y(i1,2,3,4,5,6。已知， 教师x能够胜任课程y2和y3;教师x2能够胜任课程y和ys; 教师x3能够胜任课程y2;教师x4能够胜任课程y和y3; 教师x能够胜任课程y,和yo;教师x,能够胜任课程y和y6。 请画出老师和课程之间的状态图。 Y3
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 偶图是一种常见数学模型。 例1 学校有6位教师将开设6门课程。六位教师的代号是 xi（i=1,2,3,4,5,6)，六门课程代号是yi （i=1,2,3,4,5,6)。已知， 教师x1能够胜任课程y2和y3；教师x2能够胜任课程y4和y5； 教师x3能够胜任课程y2；教师x4能够胜任课程y6和y3； 教师x5能够胜任课程y1和y6；教师x6能够胜任课程y5和y6。 请画出老师和课程之间的状态图。 x1 x x5 x2 x3 4 x6 y1 y y3 y4 2 y5 y6
H色0 3、对于一个简单图G=(V,E),令集合 E,={wlu≠v,w,v∈V} 则称图H=(V,EE)为G的补图，记为H=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 5 3、对于一个简单图G =（V, E），令集合 E uv u v u v V 1 = , , 则称图H =（V，E1 \E）为G的补图，记为 H G= H G= 例如，下面两个图互为补图。 G1 G2