离散数学王元元习题解答 (9) VIP免费

1第三篇图论第八章图8.1图的基本知识内容提要8.1.1图的定义及有关术语定义8.1图（graph）G由三个部分所组成：（1）非空集合V(G)，称为图G的结点集，其成员称为结点或顶点（nodesorvertices）。（2）集合E(G)，称为图G的边集，其成员称为边(edges)。I（3）函数ΨG：E(G)→(V(G)，V(G))，称为边与顶点的关联映射（associatvemapping）。这里（V(G)，V(G)）称为VG的偶对集，其成员偶对（pair）形如（u，v），u，v为结点，它们未必不同。ΨG(e)=(u,v)时称边e关联端点u，v。当(u,v)用作序偶时(V(G)，V(G))=V(G)V(G)，e称为有向边，e以u为起点,以v为终点,图G称为有向图（directedgraph）；当(u,v)用作无序偶对时，(u,v)=(v,u)，称e为无向边（或边），图G称为无向图（或图）。图G常用三元序组,或来表示。显然，图是一种数学结构，由两个集合及其间的一个映射所组成。定义8.2设图G为。（l）当V和E为有限集时，称G为有限图，否则称G为无限图。本书只讨论有限图。（2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足Ψ(e1)=Ψ(e2)的不同边e1,e2,为重边,或平行边。（3）当Ψ(e)＝(v,v)（或）时，称e为环（loops）。无环和重边的无向单图称为简单图。当G为有限简单图时，也常用（n，m）表示图G，其中n=V，m=E。（4）Ψ为双射的有向图称为有向完全图；对每一(u，v)，uv，均有e使Ψ(e)＝(u,v)的简单图称为无向完全图，简称完全图，n个顶点的完全图常记作Kn。（5）在单图G中，Ψ(e)＝(u,v)（或）时，也用(u,v)(或)表示边e，这时称u，v邻接e,u,v是e的端点（或称u为e的起点，v为e的终点）;也称e关联结点u,v。不是任何边的端点的结点都称为孤立结点，仅由孤立结点构成的图（E=）称为零图。（6）当给G赋予映射f：V→W，或g：E→W，W为任意集合，常用实数集及其子集,此时称G为赋权图，常用或或表示之。f(v)称为结点v的权，g(e)称为边e的权。8.1.2结点的度定义8.3在无向图中，结点v的度（degree）d(v)是v作为边的端点的数目。在有向图中，结点的度d(v)是v的出度d+(v)（out-degree）与入度d-(v)（in-degree）的和；v的出度是v作为有向边起点的数目，v的入度是v作为有向边终点的数目。定理8.1对任意图G，设其边数为m,顶点集为{v1，v2，…，vn}，那么niimvd12)(定理8.2图的奇数度顶点必为偶数个。2定理8.3自然数序列（a1,a2,…,an）称为一个度序列，如果它是一个图的顶点的度的序列。（a1,a2,…,an）为一度序列，当且仅当niia1为一偶数。定义8.4一度的顶点称为悬挂点（pendantnodes）。定义8.6各顶点的度均相同的图称为正则图（regulargraph）。各顶点度均为k的正则图称为k-正则图。8.1.3图运算及图同构由于图由结点集、边集及关联映射组成，因此对图可作种种与集合运算相类似的运算。定义8.6设图G1＝，G2＝，称G1为G2的子图（subgraph），如果V1V2，E1E2，Ψ1Ψ2。称G1为G2的真子图，如果G1是G2的子图，且G1G2。称G1为G2的生成子图（spanningsubgraph），如果G1是G2的子图，且V1=V2。定义8.7设图G1＝，G2＝，且Ψ1与Ψ2是相容的，即对任一x，若Ψ1(x)=y1,Ψ2(x)=y2，则y1=y2，从而Ψ1Ψ2为一函数。（1）G1与G2的并，记为G1G2＝G3＝，其中V3=V1V2，E3=E1E2，Ψ3=Ψ1Ψ2。（2）G1与G2的交,记为G1G2=G3=，其中V3=V1V2，E3=E1E2，Ψ3=Ψ1Ψ2。（3）若G1为G2的子图，则可定义G2对G1的差，记为G2－G1＝G3＝，其中E3=E2–E1，V3＝V2，Ψ3=Ψ2E3。（4）G1与G2的环和，记为G1G2，G1G2＝(G1G2)－(G1G2)（5）若G为简单图，则可定义G的补，记为G¯，若V(G)=n，则G¯=Kn－G定义8.8设图G＝（1）G－e表示对G作删除边e的运算，G－e=，其中E’＝E－{e}，Ψ’=ΨE’。（2）G－v表示对G作删除顶点v的运算，G－v=，其中V’=V－{v}，E’＝E－{ee以v为端点}，Ψ’＝ΨE’。（3）边e切割运算。设G中Ψ(e)...