本次课的重点第九章无向图与有向图⑴与结点u和v相联系的边ei记为无序对uv或vu。⑵图G的结点数目n称为图的阶，称G为n阶图。⑶如果e=uv是G的一条边，就说u和v是邻接的，边e和结点u及v相关联的。⑷如果边e1和e2与同一个结点u关联，就说e1和e2是邻接的。2.多重图：如果图G的至少一对不同结点间有多条边相关联，则称G是多重图。这些边称为这对结点间的平行边。3.广义图：如果图G的至少一条边只与一个结点关联，则称G是广义图。这些边称为环。4.有向图：如果图G的边是有方向的，则称G是有向图。如果边e是从结点u指向结点v，则把边记为e=(u,v)，并称e是u的出边，v的入边。二、无向图的(结)点度1.定义：图G中结点v的度记为d(v),其值等于与v关联的边数,一个环按2计。图G中最大的结点度记为，最小结点度记为。例：见下图：下图中结点度如下：d(v1)=6，d(v2)=4，d(v3)=4，d(v4)=4，d(v5)=2，d(v6)=4。=6，=22.图论基本定理：对任何n个结点m条边的图G=(V,E)，则uVd(u)=2m。证明要点:因为每条边都为它所关联的两个结点贡献1度。3.推论：奇数度结点的个数为偶数。证明要点：设G中奇数度结点组成V1，偶数度结点组成V2，那么uV1d(u)+uV2d(u）=2m，由此可以得到证明。三、有向图的(结)点度1.定义：有向图G中结点v的出度记为d+(v),其值等于v的出边数目；结点v的入度记为d-(v),其值等于v的入边数目。图G中最大的结点出度记为+，最大的结点入度记为-，最小的结点出度记为+，最小结点入度记为-。例：见下图：在下图中，d+(v1)=2,d+(v2)=1,d+(v3)=3,d+(v4)=1,d+(v5)=1,d-(v1)=1,d-(v2)=2,d-(v3)=1,d-(v4)=3,d-(v5)=1,+=3,+=1,-=3,-=12.定理：对任何n个结点m条边的图G=(V,E)，uVd+(u)=uVd-(u)=m证明要点:因为每条有向边都为它所关联的两个结点各贡献1出度和1入度。四、几类简单图1.零图：=0的图。1阶的零图称为平凡图。2.k度正则图：每个结点的度都是k的简单图。零图可以看成0度正则图。3.完全图：任何一对不同结点都互相邻接的简单图。n阶完全图记为Kn。n阶完全图的边数=n(n-1)/2。n阶完全图可以看成n-1度正则图。有向的n阶完全图边数=n(n-1)每对节点之间仅有一条有向边的有向简单图称为竞赛图。4.二部图：如果图G=(V,E)的结点集V可以分划成两个子集合V1和V2，使每条边都与V1的一个结点和V2的一个结点关联，则称G为二部图。一部结点数为m,另一部结点数为n的完全二部图Km,n,是指每部中每个结点都和另一部中全部结点邻接的二部图。因此完全二部图Km,n有mn条边。五、图的子图和补图产生子图有两种途径：一是从原图中删去一些结点或一些边得到；二是从原图中利用某些结点或某些边诱导出来。但是删除结点时，要同时删除这些结点关联的边；利用结点诱导出子图时，只能取出只与这些结点关联的边；利用边诱导子图时，只能取出与这些边关联的结点。例如：下面的图中H1可以看成是由G删去结点集{w，x}得到的，也可以看成是由结点集{u,v}或者由边集{uv}诱导得到的。前者记为G-{w，x}，后者记为G({u,v})或G({uv})。至于H2，则是由删边得到的。2.补图：设G=(V,E)是n阶简单图，Kn是以V为结点集的完全图，如果简单图H=(V,E1)满足E1={eeKneE}，则称H为G的补图。G的补图记为G。G也可以看成是由Kn删去G中的边得到的。六、图的同构定义：设G=(V1,E1)、H=(V2,E2)都是图，如果存在双射：V1V2，使对任何uvE1当且仅当(u)(v)E2，则说G同构于H，并记为GH。同构的图必具有相同的结点数和边数。同构图的对应结点之度相等。对应结点的邻接结点也对应。作业:习题十1、4、6、9、10