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

第三篇图论之羊若含玉创作
第八章图
8.1 图的根本知识
内容提要
图的界说及有关术语
界说8.1 图（graph）G由三个部分所组成：
（1）非空聚集V(G)，称为图G的结点集，其成员称为结点
或极点（nodes or vertices）.
（2）聚集E(G)，称为图G的边集，其成员称为边(edges). I
（3）函数ΨG：E(G)→(V(G)，V(G))，称为边与极点的联系关
系映射（associatve mapping）.
这里（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称为有向图（directed graph）；当(u,v)用作无序偶对时，(u,v)=(v,u)，称e为无向边（或边），图G称为无向图（或图）.
图G经常使用三元序组< V(G)，E(G)，ΨG>,或< V，E，Ψ>
来暗示.显然，图是一种数学构造，由两个聚集及其间的一个
映射所组成.
界说8. 2 设图G为< V，E，Ψ>.
（l）当V和E为有限集时，称G为有限图，不然称G为无限图.本书只讨论有限图.
（2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称知足Ψ(e1)= Ψ(e2)的不合边e1,e2,为重边,或平行边.
（3）当Ψ(e)＝(v,v)（或<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>）时，也用(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为赋权图，经常使用< V,E,Ψ,f >或< V,E,Ψ,g >或< V,E,Ψ,f,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, 极点集为{v 1，v 2，…，v n }，那么
图的奇数度极点必为偶数个.
定理8.3 自然数序列（a 1,a 2,…,a n ）称为一个度序列，如果它是一个图的极点的度的序列.（a 1,a 2,…,a n ）为一度序列，当且仅当∑=n
i i a 1为一偶数.
界说8.4 一度的极点称为悬挂点（pendant nodes ）.
界说8.6 各极点的度均相同的图称为正则图（regular graph ）.各极点度均为k 的正则图称为k-正则图.
图运算及图同构
由于图由结点集、边集及联系关系映射组成，因此对图可作种种与聚集运算相相似的运算.
界说8.6 设图G1＝<V1，E1，Ψ1>，G2＝<V2，E2，Ψ2>，称G1为G2的子图（subgraph ），如果V1V2，E1E2，Ψ1 Ψ2.称G1为G2的真子图，如果G1是G2的子图，且G1 G2.称G1为G2的生成子图（spanning subgraph ），如果G1是G2的子图，且V1 = V2.
界说8.7设图G1＝<V1，E1，Ψ1>，G2＝<V2，E2，Ψ2>，且Ψ1与Ψ2是相容的，即对任一x，若Ψ1(x)=y1, Ψ2(x)=y2，则y1= y2，从而Ψ1Ψ2为一函数.
（1）G1与G2的并，记为G1G2＝G3＝<V3，E3，Ψ3>，其中V3=V1V2，E3=E1E2，Ψ3= Ψ1Ψ2.
（2）G1与G2的交,记为G1G2 =G3 = <V3，E3，Ψ3>，其中V3=V1V2，E3=E1E2，Ψ3= Ψ1Ψ2.
（3）若G1为G2的子图，则可界说G2对G1的差，记为G2－G1＝G3＝<V3，E3，Ψ3>，其中E3 =E2 –E1，V3＝V2，Ψ3 = Ψ2E3.
（4）G1与G2的环和，记为G1G2，
G1G2＝(G1G2)－(G1G2)
（5）若G为简略图，则可界说G的补，记为G¯，若V(G)= n，则
G¯= K n－G
界说8.8设图G＝<V，E，Ψ >
（1）G－e暗示对G作删除边e的运算，G－e = <V，E’，Ψ’ >，其中E’＝E－{e}，Ψ’= ΨE’.
（2）G－v暗示对G作删除极点v的运算，G－v = <V’，E’，Ψ’ >，其中V’= V－{v}，E’＝E－{e e以v为端点}，Ψ’＝ΨE’.
（3）边e切割运算.设G中Ψ(e) = (u,v),对G作边e切割得
G’＝<V’，E’，Ψ’ >，其中，V’＝V{v’}，E’= (E－{e}){e1,e2}, Ψ’= (Ψ－{<e,(u,v)>}){<e1, (u,v’)>，<e2,(v’,v)>}
（4）极点v贯通运算.设G中极点v恰为边e1,e2的端点，且Ψ(e1) = (u,v)，Ψ(e2) = (w,v).对G作极点v贯通得G’＝<V’，E’，Ψ’ >，其中V’=V－{v}, E’=(E－{e1,e2}){e}, Ψ’=( Ψ－{<e1,(u,v)>,<e2,(w,v)>}){<e, (u,w)>}.
切割与贯通是互逆的，两者常被称为同胚运算.
界说8.9 设G1＝<V1，E1，Ψ1>，G2＝<V2，E2，Ψ2>为两个图，称G1与G2同构（isomorphic），如果存在双射f：V1→V2，双射g：E1→E2，使得对每一边e E1，
Ψ1(e)＝(u,v)（或<u,v>）当且仅当Ψ2(g(e)) =(f(u),f(v))（或< f(u),f(v)>）
当限于讨论简略图时，可以用极点的偶对暗示边，即当Ψ(e)＝(u,v)时，边e用(u,v)来暗示.这时两图同构的条件可以简化为(u,v)E1当且仅当(f(u),f(v))E2
习题解答
演习8.1
1、想一想，一只虫豸是否可能从立方体的一个极点出发，
沿着棱爬行、它爬行过每条梭一次且仅一次，并且最终
回到原地？为什么？
解不成能.可将立方体的一个极点看作图的一个极点，把立
方体的棱看作图的边，那么该图的四个极点都是三度的，因此不成能从一个极点出发，遍历所有的边一次且仅一次，并且最终回到原极点.
2、请设想一张图，它的64个极点暗示国际象棋棋盘的64
个方格，极点间的边暗示:在这两个极点暗示的方格之间可以进行“马步”的行走.试指出其极点有哪几类（依其度分类），每类各有若干个极点.
解其极点有5类：二度极点合计4个,三度极点合计8个,四度极点,合计20个,六度极点, 合计16个极点,八度极点, 合计16个极点.
3、（l）证明：n个极点的简略图中不会有多于
2)1
(
n
n条边.（2）n个极点的有向完全图中恰有2n条边.
证（l）n个极点的简略完全图的边数总和为
（2）n个极点的有向完全图的边数总和为
4、证明: 在任何n (n≥2)个极点的简略图G中，至少有两个极点具有相同的度.
证如果G有两个孤立极点，那么它们等于具有相同的度的两个极点.
如果G 恰有一个孤立极点，那么我们可对有n – 1 个极点但没有孤立极点的G ’（它由G 删除孤立极点后得到）作下列讨论.
无妨设G 没有孤立极点，那么G 的n 个极点的度数应是：1，2，3，…，n –1 这n –1种
可能之一，因此确定有两个极点具有相同的度.
5、图8.10是一个迷宫,其中数字暗示通道、和死胡同(包含目的) .请用一个图来暗示这个迷宫(用结点暗示通道、和死胡同(包含目的)),用边暗示它们之间的可直接到达关系. 解
6
..为什么？ 解 n n 是偶数.
7、n 个城市间有m 条相互衔接的直达公路.证明：当2
)2)(1(-->n n m 时，人们便能通过这些公路在任何两个城市间观光.
证 用n 个极点暗示n 个城市，极点间的边暗示直达公路，据题意需证这n 个城市的公路网络所组成的图G 是连通 4
的.反设G 不连通，那么可设G 由两个不相关的子图（没有任何边联系关系分离在两个子图中的极点）G1，G2组成，分离有n 1，n 2个极点，从而，n = n 1+n 2，n 1≥1，n 2≥1.
由于各子图的边数不超出2
)1(-i i n n ()，因此G 的边数m 知足： 与已知2
)2)(1(-->n n m 抵触，故图G 是连通的. （本题是定理8.8的特例，当然也可以应用这一定理和它的证明办法来解题.）
*8、（1）证明：序列（7，6，5，4，3，3, 2），（6，5，5，4，3，2，2）以及（6，6，5，4，3，3，1）都不是简略图的度序列.
（2）若自然数序列（d 1,d 2,…,d n ）知足d 1>d 2>…>d n ，那么当它为一简略图的度序列时必有
（a ）∑=n
i i d 1为偶数；
（b ）对任一k ，1≤k ≤n , ∑=k i i d 1≤ k(k-1)+∑+=n
k i i d k 1),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
i i d 1为偶数是显然的.
斟酌图中的k 个极点（k=1,2,…,n ）,这k 个极点的生成子图的度数总和 ≤ k(k-1)，而其余n –k 个极点v k+1,v k+2,…,v n , 可使 v 1,v 2,…,v k 增加的度数不会超出
因此我们有∑=k i i d 1≤ k(k-1)+∑+=n
k i i d k 1),min(.
9、画出图8.11中图的补图及它的一个生成子图.
图8.11
解 补图 生成子图
10、一个简略图，如果同构于它的补，则该图称为自补图.
（1）给出一个4个极点的自补图.
（2）给出一个5个极点的自补图.
（3）是否有3个极点或6个极点的自补图？
（4）证明一个自补图一定有4k 或4k ＋1个极点（k 为正整数）.
解 （1）4个极点的自补图： （2）5个极点的自补图：
（3）没有.
（4）证 设G 为自补图，有n 个极点.我们已知n 个极点的完全图有 2)1(-n n 条边，因此G 应恰有4
)1(-n n 条边.故或者n 是4
的整数倍，或者n –1是4的整数倍，即图G 一定有4k 或4k ＋1个极点（k 为正整数）.
11、（l ）证明图 8.12中（a ）与（b ）同构.
(a) (b) 图8.12 （2）给出所有不合构的4个结点的简略图的图示. （l ）证在图（a ）图（b ）间树立双射h v A
B D I J
C E G H F h(v)
α β δ ι η χ φ ϕ κ γ 可逐一验证 (不赘)
(u,v)E(a)当且仅当 (h(u),h(v))E(b)
（2）所有不合构的4个结点的简略图的图示有如下11个：
*12、K n 暗示n 个极点的无向完全图.
（l ）对K 6的各边用红、蓝两色着色，每边仅着一种颜色，红、蓝任选.证明：无论怎样着色，图上总有一个红色边组成的K 3或一个蓝色边组成的K 3.
（2）用（l ）证明下列事实：任意6小我之间或者有三小我相互认识，或者有3小我相互都不认识.
证（l ）斟酌K 6的极点V ，与之联系关系的边有5条，其中至少有3条着同一颜色.无妨设均着红色，这三边的另一个端点分离是u1,u2,u3(如图所示).再斟酌联系关系u1,u2,u3的三条边.如果它们中有一条着红色的边，那么我们就已经得到一个 A α β
D C B χ
E F δ ε κ φ γ
G H η
I J ι ϕ
红色边组成的K 3，如果它们中没有着红色的边，那么我们就可以或许得到一个蓝色边组成的K 3.
证（2）用六个极点暗示6小我，极点间红色边暗示人员间相互认识，极点间蓝色边暗示人员间相互不认识，便产生一个边着红、蓝两色的完全图K 6.应用（1）的结论，可以断定6小
我之间或者有三小我相互认识，或者有3小我相互都不认识.
8.2 路径、回路及连通性
内容提要
8.2.1 路径与回路
界说8.10 图G 的极点v 1到极点v l 的拟路径（pseudo path ）是指如下极点与边的序列：
v 1 ,e 1 ,v 2 ,e 2 ,v 3 ,… ,v l -1 ,e l -1 ,v l
其中v 1 ,v 2 ,v 3 ,… ,v l -1 ,v l 为G 的极点e 1 ,e 2 ,…,e l -1 为G 的边，且e i ( i= 1,2,… ,l -1)以v i 及v i+1为端点，（对有向图G ，e i 以v i 为起点，以v i+1为终点），拟路径的边数l －1称为该拟路径的长度.当e i ( i= 1,2,…, l -1)各不相同时，该拟路径称为路径（walk ），又当v i (i = 1,2,… ,l )各不相同时(除v 1与v l )，则称此路径为通路（Path ）.v 1＝v l 的路径称为闭路径（closed walk ）；v 1= v l 的通路称为回路（circuit ）.
当讨论限于简略图或无平行边的有向图时，上述拟路径、路径、通路等可用极点序列来暗示，例如用（v 1 ,v 2 ,v 3 ,… ,v l -1 ,v l ）代替式v 1 ,e 1 ,v 2 ,e 2 ,v 3 ,… ,v l -1 ,e l -1 ,v l .
v
u2
u1
u3
定理8.4 在有n个极点的图G中，如果有从极点u到v（u v）的拟路径，那么从u到v必有路径，并且必有长度不大于n – 1 的通路.
定理8. 5在具有n个极点的图G中，如果有从v到v的闭路径，那么确定有一条从v到v的长度不大于n的回路.
8.2.2 连通性
界说8.11称图中极点u到v是可达的（accesible），如果u = v，或者有一条u到v的路径.
界说8.12称无向图G是连通的（connected），如果G的任何两个极点都是相互可达的.称有向图G是强连通的，如果G的任何两个极点都是相互可达的;称有向图G是单向连通的，如果G的任何两个极点中，至少从一个极点到另一个极点是可达的；称有向图G是弱连通的，如果G的有向边被看作无向边时是连通的.
图G’称为图G的连通分支（connected components），如果G’是G的子图，G’是连通的，并且不存在G的真子图G’’，使G’’是连通的，且G’’以G’为真子图.
界说8.14 设G’为有向图G的子图，若G’是强连通的（单向连通的、弱连通的），且G没有真子图G’’使G’为其真子图，而G’’强连通（单向连通、弱连通），那么称G’为G的一个强分图（单向分图、弱分图）.
定理8. 6 一个图G是不连通的，当且仅当G的极点集V可以
分成两个不交的非空子集V1和V2，使得任何边都不以V1的一个极点和V2一个极点为其两头点.
定理8.7 如果图G恰有两个不合的奇数度的极点u，v，那么u到v确定是可达的.
定理8.8若图G为具有n个极点、k个连通分支的简略图，
那么G至多有
2)1
)(
(+
-
-k
n
k
n条边.
Δ8.2.3 连通度
界说 8.15设S为连通图G的极点集V的子集，称S为G的点割集（cut-set ofnodes）,如果从G中删除S中的所有极点后得到的图不连通，但S的任何真子集均无这一特性.当点割集为单元素聚集｛v｝时，v称为割点（cut-nodes）.
界说8.16χ(G)称为G的点连通度（node-connectivity），界说如下：
设S为连通图G边集E的子集，称S为G的边割集（cut-set of edges），或割集，如果从G中删除S的所有边后所得的图是不连通的，但S的任何真子集均无这一特性.当割集为单元素集｛e｝时，称e为割边（cut-edges）.
界说8.18 λ(G)称为图G的边连通度（edge-connectivity），界说如下：
定理8.9 对任何简略无向图G，
χ(G)≤λ(G)≤δ(G)
定理8.10 设G为n个极点、m条边的简略连通图，那么
λ(G)≤n
m 2. 习题解答
演习8.2
1、 证明定理8.5.
证 设n 个极点的图G 中，有从v 到v 的闭路径，暗示为 （v,v 1,v 2,…,v k ,v ）
如果v,v 1,v 2,…,v k 中没有相同极点（因而未几于n 个），那么它等于一条从v 到v 的长度不大于n 的回路.如果v,v 1,v 2,…,v k 中有相同极点v i =v j ，例如
（v,v 1,…, v i ,…, v j , v j+1,…,v k ,v ）
那么删除v i 到v j 的闭路径，得到
（v,v 1,…, v i , v j+1,…,v k ,v ）
仍然为从v 到v 的闭路径.
如此不竭删除闭路径内相同极点组成的闭路径，最终必可得到一条从v 到v 的长度不大
于n 的回路.
2、 证明：在简略无向图G 中，从结点u 到结点v,如果既有奇数长度的通路又有偶数长
度的通路，那么G 中必有一奇数长度的回路.
证 设G 中，从结点u 到结点v 的奇数长度的通路为O ，偶数长度的通路为E.对O 和
E 的除结点u 和v 的相交结点的数目归纳k.
k=0,那么O和E恰好组成G的奇数长度的回路.
设奇数长度的通路与偶数长度的通路的相交结点的数目少于k时，命题成立.
设图G中，从结点u到结点v的奇数长度的通路与偶数长 u 1 2 … k v
度的通路有k个相交结点，如图所示：
斟酌结点u到结点k,如果从结点u到结点k,既有奇数长度的通路又有偶数长度的通路，
那么据归纳假设，其中有一奇数长度的回路，因而G中必有一奇数长度的回路.如果从结点u到结点k的两条通路均为偶数长度，或均为奇数长度，那么结点k到结点v必定既有奇数长度的通路又有偶数长度的通路，因而组成一奇数长度的回路.
3、证明：若简略无向图G是不连通的，那么G¯确定是连
通的.
证设简略无向图G是不连通的，那么G由两个不相关的子图（没有任何边联系关系分离在
两个子图中的极点）G1，G2组成，分离有极点，u1,u2,…,u k和v1,v2,…,v l.由于边
（u i,v j）均不在G中（i=1,2,…,k, j=1,2,…,l）
因此（u i ,v j）全部在G¯中，从而G¯是连通的.
4、有向图可用于暗示关系，图8.18暗示的二元关系是传递的吗？说说如何由有向图剖断关系的传递性.求图8.18暗示的
图8.18 解 u 到v 的路径，则必有从u 到v 的边.
图8.18暗示的二元关系的传递闭包如图8.18（b ）所示.构作有向图传递闭包的办法是：对图中任意两个结点u,v ，如果有从u 到v 的路径，则添加从u 到v 的边.
5、给出图8.19中有向图的强分图，单向分图和弱分图，作出它的凝集图.
图8.19 解 图8.19<{v 1,v 2},{<v 1<{v 3,v 4,v 5},{<v 3,v 5>,<v 4,v 3>,<v 4,v 5>,<v 5,v 4>}>,
<{v 6},{<v 6,v 6>}> ,
<{v 7,v 8,v 9},{<v 7,v 8>,<v 8,v 9>,<v 9,v 7>}>,
<{v 10},{}>
图8.19中有向图的单向分图有：
<{v 1,v 2,v 3,v 4,v 5,v 6},{<v 1,v 2>,<v 2,v 1>,<v 1,v 4>,<v 2,v 3>,<v 4,v 3>,<v 3,v 5>,<v 4,v 5>,<v 5,v 4>,<v 3,v 6>}> ,
<{v 7,v 8,v 9,v 10},{<v 7,v 8>,<v 8,v 9>,<v 9,v 7>,<v 7,v 10>}>
图8.19
6、有7人a ，b ，d ，e ，f ，g 分离精晓下列语言，问他们
7.
a 精晓英语.
b 精晓汉语和英语.
c 精晓英语、俄语和意大利语.
d 精晓日语和英语.
e 精晓德语和意大利语.
f 精晓法语、日语和俄语.
g 精晓法语和德语.
解 下图中7个极点暗示7小我，联系关系两个极点的边暗
示两小我同时精晓某一种语言： 由于该图是连通的，因此他们7人是可以自由攀谈（需要时借助他人作翻译）. 7、证明：一个有向图是单向连通的，当且仅当它有一条经由每一结点的路径.
证 充分性是显然的.
需要性：设有向图G 是单向连通的，P 是G 中的一条路径，起点为u 1,终点为u k .如下延长这一路径：
斟酌路径外的任意极点w,若
（1）有极点w 到u 1的路径,则我们如愿.
（2）有极点u k 到w 的路径,则我们如愿.不然，由于有向图{v 1
{v 3,v 4,v 5,v 8,v 9
{v 6
a
b d
c e g
f
是单向连通的，
（3）有极点w 到u k 的路径,和极点u k-1到w 的路径, 则我们如愿.不然，由于有向图是单向连通的，
（4）有极点w 到u k 的路径,和极点u k-2到w 的路径, 则我们如愿.不然，
（5）如此等等…，有极点w 到u k 的路径,和极点u 1到w 的路径, 则我们如愿.
如上不竭延长这一路径，直至产生一条经由每一结点的路径.
8、称d(u,v)为图G ＝<V , E, Ψ>中结点u ，v 间的距离：
d 称为图G 的直径，如果d ＝max{d(u,v)u,v V}.试求图8.20中图的直径，χ(G) ,λ(G),δ(G)，并指出一个点割集和一个边割集.
图8.20
解 d ＝3 ，χ(G)=3 ,λ(G)=3,δ(G)=3 .
9、极点v 是简略连通图G 的割点，当且仅当G 中存在两个极点v1，v2，使v1到v2的通路都经由极点v .试证明之. 证充分性是显然的.
需要性：设极点v 是简略连通图G 的割点，如果不存在两个极点v1，v2，使v1到v2的通路都经由极点v ，那么对任意两个极点v1，v2，都有一条通路不经由极点v ，因而删除极 u k-1 u 1 … u w w
u 1 u k-2 u k-1 … w
u …
点v不克不及使G不连通，与v是简略连通图G的割点抵触.故G中必存在两个极点v1，v2，使v1到v2的通路都经由极点v .
10、边e是简略连通图G的割边，当且仅当e不在G的任一回路上.试证明之.
证设e是简略连通图G的割边，其端点为u,v .删除边e 后，u,v应在两个不合的连通分支中.若e在G的一条回路上，那么删除边e后，u,v应仍在一条通路上，抵触.故e不在G的任一回路上.
反之，设e不在G的任一回路上，而e不是简略连通图G 的割边.那么G-{e}仍是连通的，故还有u到v的一条通路，从而这条通路连同边e组成G中的一条回路，抵触.因此边e是简略连通图G的割边
11、试用有向图描写下列问题的解：
或人m带一条狗d，一只猫c和一只兔子r过河.m每次游过河时只能带一只动物，而没人治理时，狗与兔子不克不及共处，猫和兔子也不克不及共处.问m怎样把三个动物带过河去？
（提示：用结点代表状态，状态用序偶<S1，S2>来暗示，这里S1，S2分离是左岸和右岸的人及动物聚集，例如初始状态为< {m,d,c,r} , >.
解描写上述问题的有向图如下：
12、有向图可以刻整齐个系统的状态转换，例如用图8.21中的有向图可以描写识别01010序列的状态转换系统.其中S 为初始状态，在此读入序列，然后依序列中符号转入后续状态（读到0进入S1，读到1进入S2，如此等等）.S4暗示读完序列01010应进入的最后状态，S5暗示读完一个非01010序列应进入的最后状态.
试自行构作识别序列01(10)10的有向图刻划的状态转换系统.
（上文中w 暗示空字或重复任意多次w 所得的字.） 图8.21 解 识别序列01(10)10的有向图刻划的状态转换系统如下： 内容提要 8. 3. 1欧拉图与欧拉路径 界说8.19 图G 称为欧拉图（Euler graph ），如果图G 上有一条经由G 的所有极点、所有边的闭路径.图G 称为欧拉路径（Euler walk ），如果图G 上有一条经由G 所有极点、所有边的路径.
无向图G 为欧拉图当且仅当G 连通，并且所有极点的度都是偶数.有向图G 为欧拉图，当且仅当G 是弱连通的，并且每个极点的出度与入度相等.
定理8.12 如果G 为欧拉图，那么G 可分成若干个（一个或几个）回路. 0
S 0 S1 1 S2 1 S3 0 S4
1 0 1 S5 <{d,r} , {m,c}>
<{c},{m,d,r}>< {m,c,r},{d} ><{r},{m,c,d}>
<{m,d,c,r}, ∅><{d,c}, {m,r}><{m,d,c}, {r}> <{m, r},{c,d}><∅,{m,d,c,r}>
<{d},{m,c,r}><{ m,d,r} , {c}><{r},{m, c,d}>
<{c,r} , {m,d}> S3
0 1
S S1 S2 S4 S5 0 1 1 0
1 0 1
S6
定理8.13无向图G为欧拉路径(非欧拉图)，当且仅当G连通，并且恰有两个极点的度是奇数.有向图G为欧拉路径(非欧拉图)，当且仅当G连通，并且恰有两个极点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多l.
.2 哈密顿图及哈密顿通路
界说8.20无向图G称为哈密顿图（Hamilton graph），如果G 上有一条经由所有极点的回路（也称这一回路为哈密顿回路）.称无向图有哈密顿通路(非哈密顿图)，如果G上有一条经由所有极点的通路(非回路).
设图G为具有n个极点的简略无向图，如果G的每一对极点的度数之和都不小于n–1 ，那么G中有一条哈密顿通路；如果G的每一对极点的度数之和不小于n，且n≥3，那么G为一哈密顿图.
定理8.15 当n为不小于3的奇数时，K n上恰有
21
n条互相均无任何公共边的哈密顿回路.
界说8.21图G称为可2-着色（2-chromatic），如果可用两种颜色给G的所有极点着色，使每个极点着一种颜色，而同一边的两个不合端点必须着不合颜色.
定理8.16设图G是可2-着色的.如果G是哈密顿图，那么着两种颜色的极点数目相等；如果G有哈密顿通路，那么着两种颜色的极点数目之差至多为一.
习题解答
演习8. 3
1、试作出四个图的图示，使第一个既为欧拉图又为哈密顿图；第二个是欧拉图而非哈密顿图；第三个是哈密顿图却非欧拉图；第四个既非欧拉图也非哈密顿图.
解（a ）既为欧拉图又为哈密顿图；（b ）是欧拉图而非哈密顿图；（c ）是哈密顿图却非欧拉图；（d ）既非欧拉图也非哈密顿图.
2、像第一题要求的那样对欧拉路径和哈密顿通路作出四个图.
解（a ）既有欧拉路径又有哈密顿通路；（b ）有欧拉路径
而无哈密顿通路；（
d ）既无欧拉路径也无哈密顿通路. 3、问n 为何种数值时，K n 既是欧拉图又是哈密顿图.问k
为何值时，k-正则图既是欧拉图又是哈密顿图.
解 n 为奇数时，K n 既是欧拉图又是哈密顿图.k 为大于或等于n/2的偶数时，k-正则图既是欧拉图又是哈密顿图.
4、证明：恰有两个奇数度极点u,v 的无向图G 是连通的,当且仅当在G 上添加边（u ，v ）后所得的图G*是连通的.
证 需要性是显然的.
设G*是恰有两个奇数度极点u,v 的无向图G 添加边（u ，v ）后所得，且是连通的,那么图G*是一个欧拉图（每一个极点都是偶数度的连通图），因此G*中删除边（u ，v ）后所得
（a ） (b) (c) (d)
（a ）
的图G仍是连通的.
5、参阅演习8.1第2题.问马能否从某处出发完成所有可能的跳步一次且仅一次后回到原地.
解演习8.1第2题中的图不是欧拉图(它有三个3度的极点)，因此马不成能从某处出发完成所有可能的跳步一次且仅一次后回到原地.
6、参阅演习8.1第2题.问马能否从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地.
解马可以从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地.具体跳步如下图所示:
幻方中数字n暗示第n个跳步的起点.下图则暗示跳步的图示.
幻方
7、试盘算K n（n≥3）中不合的哈密顿回路共有若干条.
解不合的哈密顿回路共有
2)!1
(-
n条.可以用依次选取每一条边来生成哈密顿回路.因为组成回路的第一条边的选择可能是n 种, 组成回路的第二条边的选择可能是n – 1 种, … ,组成回路的第n –1条边的选择可能是2种，组成回路的第n 条边的选择可能是1种，而每一哈密顿回路由此生成两次，因此不合的
哈密顿回路共有
2)!1
(-
n条.
8、十一个学生在一张圆桌旁共进晚餐，要求在每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不合.问这样共进晚餐能安插若干次.
解每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不
合的安插方法有
21
-
n种（依据定理8.15.）
9、判别图8.31中各图是否为哈密顿图，若不是，请说明来由，并答复它是否有哈密顿通路.
图8.31
解（a），(b) 是为哈密顿图.(c) 不是哈密顿图，也没有哈密顿通路.在图(c)中增加极点k ，并对其极点做二着色，组成图(d)（如下）.图(d) 不是哈密顿图，也没有哈密顿通路.因为图中白色极点比黑色极点多两个.故(c) 不是哈密顿图，也没有哈密顿通路.不然它的哈密顿回路或哈密顿通路确定经由极点k（k在（a） (b) (c)
两个二度极点之间的边上），从而图(d) 也是哈密顿图，也有哈密顿通路，抵触.
10、证明：对哈密顿图G= <V ，E ，Ψ>删除S （V ）中的
所有极点后，所得图G ’的连通分支数不大于S . 证设G1是
G 中的哈密顿回路，显然在G1中删除S （V ）中的所有极点后，所得图G 1’的连通分支数k1，不小
于在G 中删除S （V ）中的所有极点后，所得图G ’的连通分
支数k ，即k ≤k1.
由于G1是一条回路，在G1中删除S （V ）中的所有极点后，所得图G 1’的连通分支数k1不大于S
是显然的，即
k1≤
S
.因此
k ≤k1≤
S
11、设G 为（n ，m ）图.证明：如果221+≥-n C m ，那么G 为哈密顿图（提示：运用定理8.14）.
证设G 中有两个极点v1和v2的度数之和不大于n – 1 ，那么以v1和v2为端点的边未几于n – 1条.而其余极点之间的边的数目未几于2
)3)(2(--n n 条.故G 的总边数m 知足
与221+≥-n C m 抵触，故G 中任意两个极点的度数之和大于n .依据定理8.14，G 为哈密顿图.
12、设有n 个围成一圈跳舞的孩子，每个孩子都至少与其中
2
n
个是同伙.试证明，总
可安插得使每个孩子的双方都是他的同伙.
k
（d ）
证设n个孩子为n个极点，用边暗示极点间的同伙关系组
n个是同伙，因此G的成一个图G.由于每个孩子都至少与其中
2
n，从而G的任何两个极点的度数之和每一极点的度数至少是
2
至少是n.依据定理8.14，G为哈密顿图.即G有哈密顿回路，这标明，总可安插n个孩子围成一圈跳舞，使每个孩子的双方都是他的朋
内容提要
8.4.1 联系关系矩阵
界说8.22设G为（n，m）图，那么n m矩阵A=[a ij]，称为G的联系关系矩阵（incidence matrix），记为A(G).
定理8.17 若G为（n，m）连通简略图.那么A的秩为n – l （即其最大非零行列式的阶数为n – l）.
8.4.2 邻接矩阵
界说8.23 设G =<V，E，Ψ>为一无重边的有向图.其中V={v1,v2,…,v n}，那么n n矩阵A = [a ij]，
称为图G的邻接矩阵（adjacency matrix），记为A[G]
用A l暗示l个矩阵A的乘积.
（1）令A l= [)(l
a]，那么)(l ij a的意义是：G中从极点v i到v j的
ij
长度为l的拟路径恰为)(l
a条.
ij
（2）令A○Aι = [
b]，那么ij b的意义是：有ij b个极点v，使得
ij
v i到v，v j到v都有边（双方交于v）.因而
b暗示极点v i的出
ii
度.。