第三篇图论第八章图图的基本知识内容提要8.1.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个顶点的完全图常记作Kn。

（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 结点的度定义在无向图中，结点v的度（degree）d(v)是v作为边的端点的数目。

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

定理对任意图G，设其边数为m, 顶点集为{v1，v2，…，vn}，那么∑==niimvd12)(定理图的奇数度顶点必为偶数个。

定理自然数序列（a1,a2,…,an）称为一个度序列，如果它是一个图的顶点的度的序列。

（a1,a2,…,an）为一度序列，当且仅当∑=niia1为一偶数。

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

定义各顶点的度均相同的图称为正则图（regular graph）。

各顶点度均为k的正则图称为k-正则图。

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

定义设图G1＝<V1，E1，Ψ1>，G2＝<V2，E2，Ψ2>，称G1为G2的子图（subgraph），如果V1?V2，E1?E2，Ψ1? Ψ2。

称G1为G2的真子图，如果G1是G2的子图，且G1 ? G2。

称G1为G2的生成子图（spanning subgraph），如果G1是G2的子图，且V1 = V2。

定义设图G1＝<V1，E1，Ψ1>，G2＝<V2，E2，Ψ2>，且Ψ1与Ψ2是相容的，即对任一x，若Ψ1(x) = y1, Ψ2(x) = y2，则y1= y2，从而Ψ1?Ψ2为一函数。

（1）G1与G2的并，记为G1?G2＝G3＝<V3，E3，Ψ3>，其中V3 = V1?V2，E3 = E1?E2，Ψ3= Ψ1?Ψ2。

（2）G1与G2的交,记为G1?G2 = G3 = <V3，E3，Ψ3>，其中V3 = V1?V2，E3 = E1?E2，Ψ3= Ψ1?Ψ2。

（3）若G1为G2的子图，则可定义G2对G1的差，记为G2－G1＝G3＝<V3，E3，Ψ3>，其中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－Gn定义设图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)>}。

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

定义设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习题解答练习1、想一想，一只昆虫是否可能从立方体的一个顶点出发，沿着棱爬行、它爬行过每条梭一次且仅一次，并且最终回到原地为什么解不可能。

可将立方体的一个顶点看作图的一个顶点，把立方体的棱看作图的边，那么该图的四个顶点都是三度的，因此不可能从一个顶点出发，遍历所有的边一次且仅一次，并且最终回到原顶点。

2、请设想一张图，它的64个顶点表示国际象棋棋盘的64个方格，顶点间的边表示:在这两个顶点表示的方格之间可以进行“马步”的行走。

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

解其顶点有5类：二度顶点合计4个,三度顶点合计8个,四度顶点,合计20个,六度顶点, 合计16个顶点,八度顶点, 合计16个顶点。

3、（l）证明：n个顶点的简单图中不会有多于2)1(-nn条边。

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

证（l）n个顶点的简单完全图的边数总和为2)1(12)2()1(-=+++-+-n nnn（2）n个顶点的有向完全图的边数总和为2nnnnnnn=⨯=++++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(-->n n m 时，人们便能通过这些公路在任何两个城市间旅行。

2 1 1831745 20 21 16 15证 用n 个顶点表示n 个城市，顶点间的边表示直达公路，据题意需证这n 个城市的公路网络所构成的图G 是连通的。

反设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 (见练习之3)，因此G 的边数m 满足：))1()1((21)1(2122111-+-=-≤∑=n n n n n n m k i i i))1)(1()1)(1((2121--+--=n n n n )2)(1(21)2)(1(2121--=-+-=n n n n n与已知2)2)(1(-->n n m 矛盾，故图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）若自然数序列（d 1,d 2,…,d n ）满足d 1>d 2>…>d n ，那么当它为一简单图的度序列时必有 （a ）∑=ni i d 1为偶数；（b ）对任一k ，1≤k ≤n , ∑=ki i d 1≤ k(k-1)+∑+=nk i id k 1),min(。