离散数学王元元习题解答

千里之行，始于足下。第2页/共2页精品文档推荐离散数学王元元习题解答第三篇图论

第八章图

图的基本知识

内容提要

8.1.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个顶点的

彻底图常记作K

n

。

（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结点的度

定义在无向图中，结点v的度（degree）d(v)是v作为边的端点的数目。在有向图中，结点的度d(v)是v的出度d+(v)（out-degree）与入度d-(v)（in-degree）的和；v的出度是v作为有向边起点的数目，v的入度是v作为有向边终点的数目。

定理对任意图G，设其边数为m,顶点集为{v

1，v

2

，…，v

n

}，这么

∑==

n

i

i

m

v

d

1

2

)

(

定理图的奇数度顶点必为偶数个。

定理自然数序列（a

1,a

2

,…,a

n

）称为一具度序列，假如它是一具图的

顶点的度的序列。（a

1,a

2

,…,a

n

）为一度序列，当且仅当∑

=

n

i

i

a

1

为一偶数。

定义一度的顶点称为悬挂点（pendantnodes）。

定义各顶点的度均相同的图称为正则图（regulargraph）。各顶点度均为k的正则图称为k-正则图。

8.1.3图运算及图同构

由于图由结点集、边集及关联映射组成，所以对图可作种种与集合运算相类似的运算。

定义设图G1＝，G2＝，称G1为G2的子图（subgraph），假如V1?V2，E1?E2，Ψ1?Ψ2。称G1为G2的真子图，假如G1是G2的子图，且G1?G2。称G1为G2的生成子图（spanningsubgraph），假如G1是G2的子图，且V1=V2。

定义设图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ˉ=K

－G

n

定义设图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)=(u,v),对G作边e切割得G’＝，其中，V’＝V?{v’}，E’=(E－{e})?{e1,e2},Ψ’=(Ψ－{})?{，}

（4）顶点v贯穿运算。设G中顶点v恰为边e1,e2的端点，且Ψ(e1)=(u,v)，Ψ(e2)=(w,v)。对G作顶点v贯穿得G’＝，其中V’=V－{v},E’=(E－{e1,e2})?{e},Ψ’=(Ψ－{,})?{}。

切割与贯穿是互逆的，两者常被称为同胚运算。

定义设G1＝，G2＝为两个图，称G1与G2同构（isomorphic），假如存在双射f：V1→V2，双射g：E1→E2，使得对每一边e?E1，

Ψ1(e)＝(u,v)（或）当且仅当Ψ2(g(e))=(f(u),f(v))（或

）

当限于讨论简单图时，能够用顶点的偶对表示边，即当Ψ(e)＝(u,v)

时，边e用(u,v)来表示。这时两图同构的条件能够简化为

(u,v)?E1当且仅当(f(u),f(v))?E2

习题解答

练习

1、想一想，一只昆虫是否也许从立方体的一具顶点动身，沿着棱爬行、

它爬行过每条梭一次且仅一次，同时最后回到原地为啥

解不会。可将立方体的一具顶点看作图的一具顶点，把立方体的棱

看作图的边，这么该图的四个顶点基本上三度的，所以不会从一具顶点

动身，遍历所有的边一次且仅一次，同时最后回到原顶点。

2、请设想一张图，它的64个顶点表示国际象棋棋盘的64个方格，顶

点间的边表示:在这两个顶点表示的方格之间能够举行“马步”的行

走。试指出其顶点有哪几类（依其度分类），每类各有多少个顶点。

解其顶点有5类：二度顶点合计4个,三度顶点合计8个,四度顶点,

合计20个,六度顶点,合计16个顶点,八度顶点,合计16个顶点。

3、（l）证明：n个顶点的简单图中不可能有多于

2)1

(-

n

n

条边。（2）n个顶点的有向彻底图中恰有2n条边。

证（l）n个顶点的简单彻底图的边数总和为

2)1

(

1

2

)2

(

)1

(-

=

+

+

+

-

+

-

nn

n

n

（2）n个顶点的有向彻底图的边数总和为

2

n

n

n

n

n

n

n=

?

=

+

+

+

+

4、证明:在任何n(n≥2)个顶点的简单图G中，至少有两个顶点具有

相同的度。

证假如G有两个孤立顶点，这么它们便是具有相同的度的两个顶点。

假如G恰有一具孤立顶点，这么我们可对有n–1个顶点但没有孤立顶点的G’（它由G删除孤立顶点后得到）作下列讨论。

别妨设G没有孤立顶点，这么G的n个顶点的度数应是：1，2，3，…，n–1这n–1种

也许之一，所以必然有两个顶点具有相同的度。

5、图是一具迷宫,其中数字表示通道、和死胡同(包括目标)。请用一具图来表示那个迷宫(用结点表示通道、和死胡同(包括目标)),用边表示它们之间的可直截了当到达关系。

图解

6、在晚会上有n个人，他们各自与自个儿相识的人握一次手。已知每人

与不人握手的次数基本上奇数，咨询n是奇数依然偶数。为啥

解n是偶数。用n个顶点表示n个人，顶点间的一条边表示一次握手，可构成一具无向图。若n是奇数，这么该图的顶点度数之和为奇数（奇数个奇数的和），这是不会的，所以n是偶数。

7、n个都市间有m条相互连接的直达公路。证明：当

2

)

2)(1(-->nnm时，人们便能经过这些公路在任何两个都市间旅行。

2118

3

17

4

520211

615

证用n个顶点表示n个都市，顶点间的边表示直达公路，据题意需证这n个都市的公路网络所构成的图G是连通的。反设G别连通，这么可设G由两个别相关的子图（没有任何边关联分不在两个子图中的顶点）G1，G2组成，分不有n1，n2个顶点，从而，n=n1+n2，n1≥1，n2≥1。由于各子图的边数别超过2

)

1(-iinn(见练习之3)，所以G的边数m满脚：

))1()1((2

1

)1(2122111-+-=-≤∑=nnnnnnmkiii

))1)(1()1)(1((2

1

21--+--=

nnnn)2)(1(2

1

)2)(1(2

1

21--=-+-=

nnnnn

与已知2

)

2)(1(-->

nnm矛盾，故图G是连通的。

（本题是定理的特例，固然也能够应用这一定理和它的证明办法来解题。）

*8、（1）证明：序列（7，6，5，4，3，3,2），（6，5，5，4，3，2，2）以及（6，6，5，4，3，3，1）都别是简单图的度序列。

（2）若自然数序列（d1,d2,…,dn）满脚d1>d2>…>dn，这么当它为一简单图的度序列时必有（a）∑=n

iid1为偶数；

（b）对任一k，1≤k≤n,∑=k

iid1

≤k(k-1)+

∑+=n

kii

dk1

),min(。

证（1）由于7个顶点的简单图中不会有7度的顶点，所以序列（7，

6，5，4，3，3,2）别是简单图的度序列。序列（6，5，5，4，3，2，2）中有三个奇数，所以它别是简单图的度序列。序列（6，6，5，4，3，3，1）中有两个6，若它是简单图的度序列，这么应有两个顶点是6度顶点，于是它们都要与其它所有顶点邻接，该图就不可能有一度的顶点，与序列中末尾的1冲突。故（6，6，5，4，3，3，1）也别是简单图的度序列。

证（2）∑=n

iid1为偶数是显然的。

思考图中的k个顶点（k=1,2,…,n）,这k个顶点的生成子图的度数总和≤k(k-1)，而其余n–k个顶点vk+1,vk+2,…,vn,可使v1,v2,…,vk增加的度数不可能超过

∑+=n

kii

dk1

),min(

所以我们有∑=k

iid1

≤k(k-1)+

∑+=n

kii

dk1

),min(。

9、画出图中图的补图及它的一具生成子图。

图

解补图生成子图

10、一具简单图，假如同构于它的补，则该图称为自补图。（1）给出一具4个顶点的自补图。（2）给出一具5个顶点的自补图。（3）是否有3个顶点或6个顶点的自补图

（4）证明一具自补图一定有4k或4k＋1个顶点（k为正整数）。解（1）4个顶点的自补图：（2）5个顶点的自补图：

（3）没有。

（4）证设G为自补图，有n个顶点。我们已知n个顶点的彻底图有

2)

1(-nn条边，所以G应恰有4

)1(-nn条边。故或者n是4的整数倍，或者n–1是4的整数倍，即图G一定有4k或4k＋1个顶点（k为正整数）。