当前位置：文档库 › 图论例讲问题解答

图论例讲问题解答

图论例讲（问题解答）陶平生

1、设有2n 阶简单图G ，若其每个顶点的度数皆不小于n ，证明：从G 中必可选出n 条边，其端点互不相同．

证：我们最大限度地选出k 条两两无公共端点的边，若k n =，则命题已得证；现在设k n <，这k 条边记为1234212k k PP P P P P - ，，

,，在剩下的其它边中，必须是每条边至少有一个端点与122,k P P P ，

,中的一个点重合，不然的话，我们又可以将这样的一条边添加进去，使得这种边数多于k 条，与k 的最大性矛盾！

今考虑图G 在上述端点集{}122,k P P P ，,之外的一对顶点,A B ，它们本身不会相连，由于每个顶点的度数皆不小于n ，而1n k ≥+，即点,A B 共同向点集{}122,k P P P ，,至少发出了22k +条边（称这种边为红边），于是k 条边1234212k k PP P P P P - ，，

,中必有一条，它的两个端点关联了至少三条红边（如果这k 条边中的每一条边都至多关联两条红边，那么红边的总条数将不超过2k ，矛盾！）．

现在设，边212k k P P -关联了三条红边，

得到两种关联模式，如图所示．

每种模式下，我们都可以去掉边212k k P P -以及一条红边，而保留两条无公共端点的红边，这样，图G 中两两无公共端点的边成为1k +条，又与k 的最大性矛盾！

因此k n <的假设被否定，所以k n =，结论得证．

2、某地网球俱乐部的20名成员举行14场单打比赛，每人至少上场一次，证明：必有六场比赛，其中的12名参赛者各不相同．（美国1989）

证：用20个点1220,,,V V V 表示这20名成员，如果两名成员比赛过，则在相应的两点之间连一条边，于是得到图G ．

据题意，G 有14条边，设顶点i V 的度数为i d ，则1,1,2,,20i d i ≥= ，

而122021428d d d +++=?= ．在每个顶点i V 处抹去1i d -条边（或者说，在每点i V 所发出的边中取1i d -条染成红色），由于同一条边可能被其两个端点所抹去（染红），所以抹去的边（红边）至多有1220(1)(1)(1)28208d d d -+-++-=-= 条，因此在抹去这些边后，所得的图G '中至少含有1486-=条边，且图G '中每个顶点的度数至多是1，从而这6条边所邻接的12个顶点各不相同，即这6条边所对应的6场比赛，其中的12名参赛者各不相同．

3、设G 为n 阶图，且没有长为4

的圈；证明：其边数(14n q ??≤????

．证明：设G 的顶点为12,,,n V V V ???，且设顶点j V 的度为j a ，1,2,,j n =???，则12n j j a

q ==∑．现考察与顶点j V （1,2,,j n =???）相邻的任两个顶点所构成的顶点对，则对

2k-12k

2k 2k-1

于每个顶点j V ，这样不同的顶点对有2j

a C 个，并且任两个顶点对互不相同（事实上，若对于i j ≠，顶点i V 的某顶点对与j V 的某顶点对相同，则存在,k l V V k l ≠与,i j V V 均相邻，这样

i k j l VV V V 形成一个长度为4的圈，与题意矛盾.），而总的顶点对至多为2n C 个，故

221

j n a n j C C =≤∑，故()222211111122n n n n j j j j j j j j n n a a a a q q n n ====??-≥-≥-=- ???∑∑∑∑ 即

(

(1144

n n q ≤≤，而q 为整数，故

(14n q ??≤????． 4、任意给定() 2n n ≥个互不相等的n 位正整数，证明：存在{}1,2,,k n ∈ ，使得将它们的第k 位数字都删去后，所得到的n 个1n -位数仍互不相等.

证：设这n 个n 位数为12,,,n a a a .

用反证法，若对于每个{}1,2,,k n ∈ ，删去这组数的第k 位数字后，所得到的n 个1n -位数12,,,k k nk a a a 中，都至少有两个数相等，设ik jk a a =，因原来相应的两数i j a a ≠，则

, i j a a 被删去的第k 位数字必不相同，称这样的一对数, i j a a 为“具有性质k P ”

（, i j a a 只有第k 位数字不同，其它位置上的数字对应相同）.

今用n 个点12,,,n v v v 分别表示这n 个数，若某一对数, i j a a 具有性质k P ，{}1,2,,k n ∈ ，则令相应的点, i j v v 相邻，于是得n 阶图G .

据反证法所设知，图G 中至少有n 条边，故必有圈，不妨设此圈为121r v v v v ，（否则可将这n 个数重新编号；又对于互不相等的若干个n 位正整数，同时将每个数的第, i j 位数字对换位置，并不改变本题的性质），那么前r 个数为：

112341 r r n a x x x x x x x -=

212341 r r n a y x x x x x x -=

312341 r r n a y y x x x x x -=

412341 r r n a y y y x x x x -=

…… …… …………

112341r r r n a y y y y x x x --=

12341 r r r n a y y y y y x x -=

这里，不同的字母表示不同的数字，据此知，删去各数（自左向右）的第r 位数字后，所得

的两个1n -位数rr a 与1r a 并不相等，其中，

123411 rr r r n a y y y y y x x -+= ，1123411r r r n a x x x x x x x -+=

也就是说，圈121r v v v v 中的边1r v v 并不存在，矛盾.

因此，图G 中不可能有圈，故图G 中的边至多有1n -条，这与反证法的假设相矛盾，从而结论得证.

5、设G 为n 阶图()5n ≥，其边数4e n ≥+，证明G 中存在两个无公共边的圈. 证：对n 归纳，当5n =时，9e ≥，这相当于从5k 中至多去掉一条边，结论显然成立. 设()6n k k <≥时结论成立，当n k =时，k 阶图G 的边数4e k ≥+，由于G 的边数≥顶点数，其中必有圈.

若G 中存在一个长为3或4的圈1C ，则从图G 中删去圈1C 上所有的边，剩下的k 阶子图1G 中，依然满足：边数≥顶点数，其中又有圈2C ，显然，1C 与2C 都是G 中的圈，且无公共边.

以下假设，G 中的每个圈长至少为5.

若G 中有点0v ，其度数()01d v ≤，则删去点0v 以及它所关联的边，剩下的1k -阶子图2G 中，有1k -个顶点，至少()14k -+条边，据归纳假设，2G 中有不含公共边的两个圈，它们当然也是G 中的圈.

若G 中有点0v ，其度数()02d v =，设与0v 邻接的两个点是12, v v ，显然12, v v 不相邻（因G 中无三角形），此时，删去点0v 及其所发出的两条边，同时添加边12v v ，所得的图3G 中，有1k -个顶点，至少()14k -+条边，据归纳假设，3G 中有不含公共边的两个圈1C 与

2C . 再将边12v v 去掉，

恢复被删去的点0v 及其所发出的两条边0102, v v v v ，回到图G ，则G 中也有不含公共边的两个圈（这是由于，若3G 中的这两个圈1C 与2C 都不含边12v v ，则这两个圈1C 与2C 也是G 中的圈；若3G 中的这两个圈中有一个，例如2C ，含有边12v v ，从该圈中去掉12v v ，并代之以边0102, v v v v ，得到圈0C ，则0C 与1C 是G 中不含公共边的两个圈）.

若G 中所有的点i v ，其度数()3i d v ≥，1,2,,i k = ，如果G 的边数4k >+，我们就从G 中删去一些边，使得边数恰好为4k +，记此图为4G .

在图4G 中，若4G 中有一顶点的度数3<，则据前面的讨论，结论已经得证；

若4G 中每个顶点的度数皆3≥，则4G 中各顶点的度数之和3k ≥，故4G 中的边数32k ≥，即有342

k k +≥，由此得，8k ≤. 而在此时，只要能证得，在4G 中必有三角形或四边形，这种三角形或四边形当然也在G 中，这将与原先的假设（G 中的每个圈长至少为5）相矛盾.

事实上，由于4G 中的边数4k +≥顶点数k ，故4G 中必有圈，设C 为极小圈，则圈C 的点与点之间不能再有其它边相连，否则圈C 将被分成更小的圈，矛盾；设极小圈C 的长为r ，则2r k ≤-.(由于每个顶点的度数皆3≥，若r k =，则圈C 的点与点之间将有其它边相连，于是圈C 被分成更小的圈，矛盾；若1r k =-，圈121r C vv v v = 上的每个点都要与圈外的一点0v 相邻，于是得到三角形012v v v ，矛盾)；于是，当5k =或6k =时，4G 中的极小圈C 的长4r ≤.

当7k =时，有5r ≤，若极小圈C 为五边形12345v v v v v ，另两点为,u v ，五边形的五个顶点共向,u v 发出至少5条边，则,u v 中必有一点，例如u ，要向五边形的顶点发出至少3条边，其中必有两个相邻顶点，例如12v v 都与u 相邻，于是得到三角形12uv v （更小的圈），矛盾，因此4r ≤；当8k =时，有6r ≤，若极小圈为六边形123456v v v v v v ，六个顶点共向圈外的两点,u v 发出至少6条边，则其中有一点，例如u ，要向六边形的顶点发出至少3条边，于是点u 要向顶点组{}{}135246,,, ,,v v v v v v 中的一组发出至少2条边，设u 与13,v v 相邻，则得到四边形123v v v u ，矛盾；若极小圈C 为五边形12345v v v v v ，另三点为,,u v w ，五边形的五个顶点共向,,u v w 发出至少5条边，必有一点，例如u ，要向五边形的顶点发出至少2条边，由于五边形的任两个顶点，要么相邻，要么中间只隔一个顶点，因此得到一个含有点u 的三角形或者四边形，矛盾,因此4r ≤.

综合以上讨论，可知本题结论成立.

6、若简单图G 有21n +个顶点，至少31n +条边(2)n ≥，证明：G 中必有偶圈．证：由于图G 的边数不小于顶点数，则G 中必有圈，今逐次这样地去掉图中的一些边：使得每去掉一条边，就破坏一个圈，这样的操作至少可以进行1n +次，也就是至少可以去掉1n +条边，破坏至少1n +个圈，即是说，图G 中的圈至少有1n +个．

这1n +个圈中，必有两个圈有公共边，事实上如果任两个圈都无公共边，由于每个圈至少有3条边，则图G 至少有3(1)33n n +=+条边，矛盾！

今设12,C C 是图G 中两个有公共边的圈，则1C 至少有一条边不在2C 中，2C 至少有一条边

不在1C 中，若12,C C 含有公共边e 的最长公共道路为0()C A B = ，若设道路0C 有r 条边，圈1C 有1r 条边（包括公共路），圈2C 有2r 条边（包括公共路），（即圈12

,C C 的长分别是12,r r ）

．若去掉道路0()C A B = 间的所有的边（即圈12,C C 的上述公共边），则圈12,C C 的剩下部分仍可合并为一个圈，记为*C ，圈*C 的长为122r r r +-；

注意三个圈*12,,C C C 长的和等于122()r r r +-，它是一个偶数，故三个加项

12,r r 和122r r r +-中必有一个是偶数，即G 中有偶圈．

7、一次足球邀请赛共安排了n 支球队参加，每支球队预定的比赛场数分别是

12,,,n m m m ，如果任两支球队之间至多安排了一场比赛，则称12(,,,)n m m m 是一个有效安排；证明：如果12(,,,)n m m m 是一个有效安排，且12n m m m ≥≥≥ ，则可取掉一支球队，并重新调整各队之间的对局情况，使得112312(1,1,,1,,,)m m n m m m m m ++--- 也是一个有效安排．

证：设预定比赛i m 场的队为i A ，1,2,,i n = ；

（01）、如果1A 的1m 场比赛，其对手恰好就是1231,,,m A A A + ，那么，直接去掉1A （当然1A 所参与的所有比赛也就被取消了），则剩下的队23,,,n A A A 之间的比赛，以 112312(1,1,,1,,,)m m n m m m m m ++--- 为有效安排．

（02）、如果球队23,,,n A A A 中，有些队并未安排与1A 比赛，设在1231,,,m A A A + 中，

自左至右，第一个未安排与1A 比赛的队是j A ，由于1A 要赛1m 场，那么在1231,,,m

A A A + 之外必有一个队安排了与1A 比赛，设为1,(1)k A m k n +<≤，

由于j k m m >，故必有一个队s A ，它被安排了与j A 比赛而未安排与k A 比赛，如图所示．今对原安排作如下调整：

取消1,k A A 两队间、,j s A A 两队间的比赛，

改为1,j A A 两队间，,s k A A 两队间进行比赛，

其它比赛安排不变；

s j k j

s k

经过这一次调整之后，所有球队的比赛场数不变，且是一个有效安排．而第一个不与1A 比赛的队的序号，至少后移了一个位置；故经有限次这样的调整之后，就化成了情形（01），因此结论得证．

8、十个城市之间有两个航空公司服务，其中任意两个城市之间都有一条直达航线（中间不停），所有航线之间都是可往返的．

证明：至少有一个航空公司可以提供两条互不相交的环形旅行线路，其中每条线路上的城市个数都为奇数．

（与其等价的图论说法是：10阶完全图10K 的边红蓝2-染色，则必存在两个无公共顶点的同色奇圈（顶点个数为奇数的圈，且这两个圈的边或者同为红色，或者同为蓝色））．

证：首先注意，六阶完全图的边红蓝2-染色，据拉姆赛定理，必存在单色三角形123VV V ，除去这个三角形外，在余下的七点之中，又有一个单色三角形456V V V ，若这两个三角形具有相同的颜色，证明已经完成；不然的话，若这两个三角形，一个是红色的，一个是蓝色的，在这两个三角形的顶点之间有9条连线，其中至少有5条同色，设为蓝色；因此，有一个红色三角形，从它的某个顶点发出两条蓝边，蓝边的端点是蓝色三角形的两个顶点；

这样，我们找到两个三角形，其中，一个是红色边的，一个是蓝色边的，它们具有一个公共的顶点，（总共佔用了5个顶点）；今考虑剩下的5个顶点：

若它们组成的完全图5K 中含有一个单色三角形，则证明已经完成；

若此完全图5K 中不含单色三角形，我们来证明，此时5K 的10条边，必定形成一个红色五边形和一个蓝色五边形．这是由于，5K 中不含单色三角形，则每

点必定都是发出两条红边，两条蓝边；因为，若点A 发出三条蓝边 ,,AB AC AD ，则点,,B C D 之间便不能再有蓝边，于是得到红色三角

形BCD ，矛盾！现在设点发出的两条蓝边是,AB AE ，则边BE 必为红色；而点B 还需再发出一条蓝边，一条红边，设BC 为蓝，BD 为红；由此即推得，AC 必为红，DE 必为蓝；于是AD 为红， CD 为蓝，CE 为红．于是得蓝色五边形ABCDE 和红色五边形ACEBD ．

从而命题得证．

9、在一次学术讲演中有五名数学家参加，会上每人均打了两次旽，且每两人均有同时在打旽的时刻，证明：一定有三人，他们有同时在打旽的时刻．

证：以1210,,,V V V 这10个点表示五位数学家的十次打旽，当,i j V V 两个旽有共同的时刻，则令点,i j V V 相邻，这样我们就得到一个10阶图G ，由于每两个数学家都有同时打旽的时刻，从而图G 的边数至少是2

510C =，而G 的顶点数为10，故G 中必有圈． E

设在此圈中，k V 是最先结束的一个旽，

与k V 相邻的两个顶点是11,k k V V -+，因11,k k V V -+这两个旽与k V 有共同的时刻，故当旽k V 结束的前一瞬间，11,k k V V -+这两个旽还在继续，这表明，三个旽11,,k k k V V V -+有共同进行的时刻，而这三个旽显然是属于三个人的（若两个旽属于同一个人，又有共同的时刻，只能算成一个旽，矛盾！）．

10、() 2n n n ?≥矩阵A 中，每行及每列的元素中各有一个1和一个1-，其余元素皆为0；证明：可以通过有限次行与行的交换以及列与列的交换，化为矩阵B ，使得 0A B +=.（即A 中的每个数都变成了其相反数）

证：2n =时结论显然成立;以下考虑3n ≥时的情况.记n n ?矩阵第i 行、j 列交叉位置上的元素为{} ,0,1,1ij ij a a ∈-，又用i V 表示矩阵的第i 行，j e 表示第j 列，（ ,i j V e 仅表示位置，不代表具体元素与向量），

今构作一个以12,,,n V V V 为顶点，12,,,n e e e 为边的有向图G 如下：当第k 列的1在第i 行，1-在第j 行，（即 1, 1ik jk a a ==-），则连一条由点i V 指向点j V 的有向边k e ，于是，G 的每个顶点都恰好具有1个出度和1个入度（即发出一个箭头和收到一个箭头），因此，从图G 的任一顶点出发，沿箭头方向前进，必将回到原出发点，（这是由于，除出发点外，每经过一个点，就将耗去一个入度和一个出度，因此不能回到途经的点）. 这样，图G 或者本身是一个n 阶有向圈，或者是若干个不交的有向圈的并，（其中k 个点的有向圈恰有k 条有向边，3k ≥.当3n ≥时，这种图G 与适合条件的矩阵A 一一对应）. 若后者情况出现时，如果删去某个圈所涉及的行和列，并不影响其余圈的状态；或者说，若仅对某个圈所涉及的行和列进行所述的变换，不会改变其它行和列中1和1-的位置. 于是我们仅须考虑只有一个圈(即G 为n 阶圈)的情况.示例如下：

对应的圈1C 为：

我们注意到：()

1. 每当交换矩阵中的两行位置，等价于圈中仅交换相应两个顶点的位置，

（边的位置保持不动）； ()11

. 每当交换矩阵中的两列位置，等价于圈中仅交换相应两条边的位置，（仅交换两条边的代号，边的箭头方向以及顶点的位置保持不动）.

于是，我们可先对圈1C 的顶点作两两对换，得到圈2C ，使得沿箭头方向前进时，所经历的各点恰与圈1C 中各点的方向相反．（例如在圈1C 中，诸点的顺序为1243651VV V V V V V ；而

6V 534 0 1 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 11 0 0 0 0 1A -? - -=---????? ? ? ? ? ??

在圈2C 中，诸点的顺序为1563421VV V V V V V ）.

圈2C ：圈3C ：

再对圈2C 的边作两两对换，（每次仅交换一对边的代号，边的箭头方向及顶点的位置保持不动）.使得每条边所关联的顶点与圈1C 中的情况相同.于是得到圈3C .与圈3C 所对应的矩阵B ，其每个元素恰为矩阵A 中相应位置上元素的相反数.

因此 0A B +=. 即所证的结论成立．

11、有七种颜色的珍珠，共计14颗，其中每种颜色的珍珠各两颗；今把这些珍珠分装于七个珠盒中，使得每个珠盒中各有一对不同颜色的珍珠；

(1)、证明：不论各盒中的珍珠怎样搭配，总可以将这七个珠盒分别放置于一个正七边形的七个顶点之上，使得七边形的任两个相邻顶点处所放置的盒中，四颗珍珠互不同色．

(2)、如将以上条件与待证结论中的“七”一律改为“五”，14改为10，则情况如何？

(1)、证：用点127,,,v v v 分别表示这七种颜色，如果一个i v 色的珍珠和一个j v 色的珍珠装在同一盒中(i j ≠)，则在点i v 与j v 间连一条边，这样就得到一个图G ，（点i v 与j v 之间有可能连出两条边），由于同一色的珍珠有两颗，每颗珠都需与一颗其它颜色的珍珠共盒，则图G 的每点恰好发出两条边；

自G 的任一点A 出发，沿一条边走到点B ，再由B 沿另一条边走到C ，…，如此下去，最后必定回到出发点A ，（这是由于，途中经过的每个点P 都有两条边，若能沿一条边进入点P ，则必沿另一条边可离开点P ，而由点P 不能再回到途中已经过的点，因为这种点所发出的两条边都已走过，因此只能到达新点或回到出发点，而新点终将逐渐耗尽，最后必定回到出发点A ），这样就得到一个圈．

去掉这个圈，若剩下还有点，依上述方法，又将得到新的圈，若称两点的圈为“两边形”，则图G 的结构只有如下四种情况：

()01、一个七边形： ()0

2、一个五边形，一个两边形： B 6v 4754

3v 74V 364V 36

()03、一个四边形，一个三角形： ()0

4、一个三角形，两个两边形：对于每种情况，我们都对相应的边作出适当编号，并将这些边所对应的珠盒放置于七边形的顶点之上，如右图所示．

因此所证结论成立． (2)、当14颗七色珠改为10颗五色珠后，结论不成立，例如，

对于五色12345,,,,v v v v v ，我们若将10颗珠这样装盒： ()()()()()112223331445545,,,,,,,,,e v v e v v e v v e v v e v v =====，

则无论怎样摆放于正五边形的顶点上，都不能满足条件．（因为123,,e e e 中，任两盒都有同色的珠，无论怎样摆放于正五边形的顶点上，必有两盒相邻）．

12、给定31个正整数1231,,,a a a ，若其中至少有94对数互质，证明：其中必存在四个数,,,a b c d ，满足：(,)(,)(,)(,)1a b b c c d d a ====．

证：用点1231,,,A A A 分别代表这31个正整数，若(,)1i j a a =，则令相应点,i j A A 相邻，于是得31阶简单图G ，设点i A 的度数为i d ，据条件，图G 至少有94条边，不妨设，图G 恰有94条边，否则我们就去掉其中一些边，并不影响问题的性质；与点i A 相邻的点有i d 个，它们构成2(1)2

i i i d d d C -=个“点对”，据条件， 1231294188d d d +++=?= ；若记 312

i d i M C ==∑，则 31312111122i i i i M d d ===-∑∑ 3121

1942i i d ==-∑，由柯西不等式，31312222111112()1889422316231i i i i d d ==≥=?=??∑∑，因此，223129415793155313094943131312M C ???≥?-=>==，故在1231,,,A A A 中必有两个点,A C ，其所邻接的点中，具有相同的一个“点对”，设为,B D ，即ABCD 为四边形，从而，

(,)(,)(,)(,)1a b b c c d d a ====．

6e 4

6e 7

3v 43

6467

13、奥运会排球预选赛有n 支球队参加，其中每两队比赛一场，每场比赛必决出胜负，如果其中有k （3k n ≤≤）支球队12,,,k A A A ，满足：1A 胜2A ，2A 胜3A ，…，1k A -胜k A ，k A 胜1A ，则称这k 支球队组成一个k 阶连环套；

证明：若全部n 支球队组成一个n 阶连环套，则对于每个k （3k n ≤≤）及每支球队i A ()1i n ≤≤，i A 必另外某些球队组成一个k 阶连环套.

证明：以12,,,k A A A 为顶点，如球队i A 胜j A ，则在两点间连一有向边：i j A A →，如此得n 阶竞赛图G ．据条件，G 的n 个顶点可以排成一个n 阶有向圈，设为： 121n A A A A →→→→ ，于是G 的任两点可沿箭头方向相互到达．

先证明，任一球队i A 必在某个三阶连环套中，用,i i S T 分别表示被i A 击败了的球队集合和击败了i A 的所有球队集合，由于G 双向连通，必有,j i k i A S A T ∈∈，使j k A A →，于是,,i j k A A A 组成三阶连环套；

假若已证得，对于()3k k n ≤<，图中存在以i A 为一顶点的k 阶连环套

()121i k C A A A A A = ，圈C 之外的点的集合为M ；

若M 中有一点P ，它所表示的球队既击败了圈C 中的某个队k A ，又被圈C 中的另一个队j A 所击败，点,k j A A 把圈C 分成两条有向路12,C C ，其中一条，

例如1C ，它与有向路j k A P A →→组成有向圈，如图所示．

依次考虑路2C ：12,,,,j j j k A A A A ++ 上各点与点P 间的邻接情况，必有相邻的两点1,j r j r A A +++，满足j r A P +→而1j r P A ++→，今去掉边1j r j r A A +++→，而将路1j r j r A P A +++→→插入其间，便得到一个含有顶点i A 的1k +阶连环套；

若M 中的任一点P ，它所表示的球队要么击败了圈C 中的每个队，要么被圈C 中的每个队所击败，则集M 可分为两个不交的子集S 与T ，其中S 中的任一队，战胜了圈C 中所有的队，而T 中的任一队，负于圈C 中所有的队；由于图G 双向连通，故在集T 中必有点u ，集S 有点v ，使v u →，今在圈C 中任意去掉一个点j A ，()

j i A A ≠，而用路v u →代替，便得到一个含有顶点i A 的1k +阶连环套；故结论对于1k +成立，由归纳法，结论成立． 14、某公司有17个人，每个人都正好认识另外的4个人，证明：存在两个人，他们彼

此不相识且没有共同的熟人．（第26届独联体数学奥林匹克）

证明：以17个点表示公司的17个人，如果两人,x y 相识，则令其相邻，于是得到17阶简单图G ；据条件，对于每个顶点x ，()4d x =，我们需证明，存在顶点,P Q ，满足： ,P Q 不相邻，且不同与第三顶点相邻．

反证法，假设G 中的任意两点，或者相邻，或者同与第三点相邻，今考察其中任一点x ，因为()4d x =，故有点,,,A B C D 与x 相邻，讨论不同的情况：

01、如果,,,A B C D 四点之间有某两点相邻，例如AB 相邻，因()4d x =，与A 相邻的另

两点是,E F （允许是,C D ），此外至少有10个点与A 不相邻，它们构成集合M ，

P M ?∈，因,P A 不相邻，则由假设，它们应同与第三点相邻，但与A 相邻且度数尚未满4的点只有,,B E F ，故P 必与,,B E F 之一相邻；

因为P 是M 中的任意点，故M 中的10个点必与,,B E F 之间至少连出10条边，从而 ,,B E F 中有一点至少向M 中的点发出4条边，这样，该点的度数5≥（因该点也与A 相邻），发生矛盾！

02、据01的讨论知，,,,A B C D 中的任两点不相邻，又若,,,A B C D 四点中有某两点，例如,A B ，它们除了都与x 相邻外，还都与另一点y 相邻，因为()4d A =，与A 相邻的另外两点是,E F ，此外至少有9点与A 不相邻，它们构成集合M ，P M ?∈，P 必与,E F ， Y 之一相邻，但()4d Y =，故与Y 相邻的点，除,A B 外，至多还有M 中的两点，因此，M 中至少有7点要向,E F 之一发出边，于是,E F 中必有一点向M 引出至少4条边，则该点的度数大于4，矛盾！

据01，0

2的讨论可知，,,,A B C D 四点之间两两不相邻，且除与x 相邻外，它们两两

x M y x

也不同与另外的点相邻，但,,,A B C D 的度数皆为4，因此除与x 外，它们各与另外三个不同的点相邻，如图二，这样已有16条边，其余还有

17416182?-=条边，并且图中已有17个顶点，不会再有另外的顶点，而且据与01相同的讨论可知，与A 相邻的四点（包括x 及

另三个未标记号的点123,,A A A ），彼此之间不能相邻．

因此，这18条边的每一条，只能在,,,i i i i A B C D 间连结，每连一条，便得到一个含有5条边，且经过x 的圈，这样共得18个圈（每圈都过x ），

由于顶点x 的任意性，经过其余16个点中任一个点也有18个那样的圈（共1718?个），每一个圈过5个顶点，因此每个圈重复计算了五遍．于是圈的个数等于17185

?，这不可能，故所设不真，从而证得了命题． 15、若8阶简单图不含四边形，那么，其边数的最大值是多少？（92CMO -）解一：右图是具有八个顶点，十一条边的简单图，其中没有四边形，

今证明，11便是合于条件的最大值．

为此，只要证，具有12条边的简单图中必存在四边形．

先指出两个事实：

01、如果点A 与点12,,,k V V V 都相邻，B 是异于A 的一个顶点

（B 也可以是{}12,,,k V V V 中的点），如果在{}12,,,k V V V 中有某一“点对”与B 相邻，则图中有四边形．

02、四个顶点的图中，如有五条边，就必有四边形．（相当于一个四面体中去掉一条边）．现在设，G 具有八个顶点，十二条边的简单图，我们来证明，G 中必有四边形．反证法，假若G 中没有四边形，用128,,,d d d 分别表示G 中八个顶点的度数，注意到，8121224i i d

==?=∑，则有{}128max ,,,3d d d ≥ ．讨论不同的情况：

情形一、若{}128max ,,,3d d d = ，这时G 中每个顶点的度数都是3，任取一个顶点1A ，与1A 有边相邻的顶点设为234,,A A A ，其余四个顶点为1234,,,B B B B ；

据01及反证法假设，{}1234,,,B B B B 中的点与{}

234,,A A A 中的点之间相连的边至多只有四条，而{}234,,A A A 中的点相连的边至多只有一条，，所以在{}1234,,,B B B B 这些点中相连的边至少有123414---=条（由02可知，也只能有四条），我们只考虑这四个顶点以及连结它们的4条边，这时其中必有某一顶点的度数是1（如果这四个顶点的度数都是2，

就成为一个四边形），从而有顶点度数为3，即{}1234,,,B B B B 中必有一点（不妨设为1B ），与其它三点都有边相连，而{}1234,,,B B B B 中的点与{}234,,A A A 中的点相连的边数为4，

1B 必与{}234,,A A A 中的某一点有边相连，这样，图G 中1B 的度数将是4，这与假设矛盾！

情形二、{}128max ,,,4d d d = ，取一个度数为4的顶点A ，设与A 有边相连的顶点为 1234,,,A A A A ，其余三顶点为123,,B B B ，据01及反证法假设，{}1234,,,A A A A 内部的边至多是2条，点集{}123,,B B B 与{}

1234,,,A A A A 之间的边至多3条，而{}123,,B B B 内部的边也显然至多3条，由于总的边数是12条，因此上述各种边数恰为2,3,3；于是，在

{}1234,,,A A A A 内部的边恰好是2条，且这两条边不能有公共顶点（否则将出现四边形），不妨设这两条边为112l A A =，234l A A =；{}123,,B B B 中的每一点都与{}1234,,,A A A A 中的某一点有边相连，这种边有三条，称为“红边”，

且因121323,,B B B B B B 都是G 的边，这三条红边中，

必有两条的端点同时落在12,l l 两边之一上，设为1l 上，它收到来自12,B B 发来的边；如果这两条红边都关联1l 上的同

一点（例如1A ），那么1123A B B B 构成四边形；如果这两条红

边关联1l 上的不同点12,A A ，那么1212A A B B 构成四边形；都与所设矛盾！

情形三、{}128max ,,,4d d d > ，取一个度数最大的顶点A ，与A 邻接的点集记为S ，其余顶点集记为T ，令{}128max ,,,k S d d d == ，m T =，,S T 之间的边数至多m 条，

T 内部的边至多2m C 条，S 内部的边至多2k ??????

条，这样，图G 的边数不超过 22722m m k k k m C C ????+++=++????????

，当5,6,7k =时，都不可能使边数为12．综上，知所求的最大值为11．

解二、将n (4)n ≥阶简单图中，没有四边形的图的边数的最大值记为n S ，易见44S =，下面考虑5n =的情况，在有5个顶点，6条边的简单图中，由于各顶点的度数之和为12，必有某顶点的度数不大于2，如果其中有一个顶点的度数为1，则可去掉这个顶点，化为有

4个顶点以及5条边的图，其中必有四边形；所以只要考虑每个顶点的度数皆不小于2的情况；如果图中有某顶点A 的度数为3，由A 引出的边为,,AB AC AD ，另一顶点E ，因其度数不小于2，则与,,B C D 三点中至少两点相邻，可见也有四边形，

如果图中有某顶点P 的度数为4，由P 引出的四条边为,,,PA PB PC PD ，因,,,A B C D 各点的度数皆不小于2，由于度数总和为12，则,,,A B C D 各点的度数皆等于2，这时的确可以没有四边形；如图所示：

在5n =时，如果一个图至少有7条边，则必有一个顶点的度数不大于2；去掉这个顶点（及其所发出的边）化为4个点，至少5条边的情况，据前所知，其中必有四边形；因此56S =，并且具有6条边而没有四边形的5阶图只有上图所示的情况．

进而可推出，67S =；因为在具有6个顶点，8条边的图中，总有一个顶点的度数不大于2，设为P ；若()1d P =，去掉点P ，化为有5个顶点，7条边的图，据上知，其中有四边形；若()2d P =，去掉点P ，化为有5个顶点，6条边的图，且在这种情况下，没有四边形的图只有一种形式：

（其余情况都有四边形）

在此基础上恢复所去掉的那个顶点及两条边，这两条边不论如何作，也总会产生四边形，即具有6个顶点，8条边的图必有四边形；

因此67S =；

另外，具有6个顶点，7条边而无四边形的图存在，例如，进而可推出，79S =；因为在具有7个顶点，10条边的图中，总有一个顶点的度数不大于2，

去掉此顶点，化为具有6个顶点，至少8条边的图，据67S =可知，其中必有四边形，因此7顶10边的图中必有四边形；

而对于7顶9边的图，没有四边形的图是存在的，例如：

因此79S =．

今证明，811S =，首先，具有8个顶点，11条边而无四边形的图存在，例如，

再证，具有8个顶点，12条边的图必有四边形．

反证法，若存在这样的图没有四边形，如果有一点的度数不大于2，去掉该

点，化为具有7个顶点，至少10条边的图，据以上，其中必有四边形；与所设矛盾，因此各点度数不小于3，因为8个顶12边的图，度数总和为24，于是每顶点度数恰为3，

这时图中必有三角形（事实上，若无三角形，任取点A ，若A 发出的三边为,,AB AC AD ，则,,B C D 间不能有边，与B 相邻的另两顶点将是其余的点，异于,,,A B C D 的点集设为 {}1234,,,E E E E E =，即与B 相邻的另两顶点在E 中，对于,C D 也是如此，也就是说，集 {},,B C D 与集E 间的边有6条，故E 中必有一点，例如1E ，至少向点集{},,B C D 发出了两条边，设为11,E B E C ，于是1ABE C 为四边形，矛盾！）

设ABC 是图中的一个三角形，由于每顶点度数恰为3，则,,A B C 每点各向形外还发出了一条边，今去掉三角形ABC ，总共去掉6条边，剩下5顶6边的图，若没有四边形，据前所述，只有唯一的形式：

然而这时有一顶点的度数为4，这与图中“每顶点度数恰为3”矛盾！故所设不真，因此 8顶12边的图必有四边形．从而本题所求的边数最大值为11．

16、10名选手参加乒乓球赛，每两个选手对赛一局．如果选手i 胜选手j ，选手j 胜选手k ，选手k 胜选手i ，则称为有一个三角形．设i W 和i L 分别表示第i 个选手胜和败的局数，又如果选手i 胜选手j 时，总有8i j L W +≥．求证：这次球赛恰有40个三角形．

解：用点1210,,,v v v 表示这10名选手，如果i v 胜j v ，则在相应两点间连一条有向弧：

i j v v →，如此得10阶有向图G ，()(),i i i i d v w d v L +-==，且9,1,2,,10i i W L i +== ．

不妨设，1210W W W ≥≥≥ ，则 1210L L L ≤≤≤ ；由于图G 共有45条边，每条边产生一个出度和一个入度，故101011

45i i i i W L ====∑∑，从而 1105,4W W ≥≤，1104,5L L ≤≥．

据条件，当i v 胜j v ，有8i j L W +≥，则10i j W L +≤．

今证明，1210,,,W W W 只在5和4两个数中取值．

()1、先证明，15W =；

反证法，假若16W ≥，则13L ≤，若j v 是被1v 击败的任一人，由18j L W +≥得，5j W ≥，又由104W ≤知，10v 不属于被1v 击败的人，从而10v 击败了1v ，于是被1v 击败的选手（至少6人），属于集合{}239,,,v v v ；又由10104,5W L ≤≥，击败10v 的人（至少5个）必在集

合{}239,,,v v v 中，其中必有一人r v ，他既被1v 击败，又击败了10v ，由“1v 击败r v ”知， 5r W ≥，故4r L ≤；由“r v 击败10v ”知，108r L W +≥，得104W ≥，结合前面104W ≤得 104W =．这样，1210,,,W W W 的取值情况是，{}1296,,,W W W ≥ 中至少有六数5≥，其余的数4≥，104W =，所以101

48i i W =≥∑，矛盾．故所设不真，从而1

5W ≤，前面已有， 15W ≥，所以15W =．

用同样的方法可得，105L =，从而104W =．

由121054W W W =≥≥≥= ，设其中有k 个5，10k -个4，据()455410k k =+-得5k =，所以1256105,4W W W W W ======= ．进而有

1256104,5L L L L L ======= ．

()2、称题意中的三角形为“连环套三角形”

，由于在图G 中，“连环套三角形”个数+“非连环套三角形”个数310120C ==；先求“非连环套三角形”个数：

因为从一点发出的每一对“出度”（或者每一对“入度”）确定一个“非连环套三角形”，而对于图G 中任一点P ，它或者有5个“出度”、4个“入度”；（或者有5个“入度”、4个

“出度”），共组成25C 个“出度对”，24C 个“入度对”（或者25C 个“入度对”，24C 个“出度

对”），共得以P 为一顶点的225416C C +=个“非连环套三角形”

，如不计重复，则10个点共产生160个“非连环套三角形”；

由于每个“非连环套三角形”，含有一个“出度对”和一个“入度对”，故被计算了两遍，因此，“非连环套三角形”共有160802

=个，从而“连环套三角形”个数为1208040-=个． 17、一次体育比赛共设有()2 2n n ≥个项目，每个选手恰好报名参加其中的两个项目，而任两个人都至多有一个相同的项目，假定对于每个{}1,2,,1k n ∈- ，不超过k 人报名的项目少于k 个.

证明：存在2n 个选手，使得每个项目都恰好有其中的两人参加.

证：用2n 个点表示这2n 个项目，若其中某两个项目被同一人选报，则令相应的两点相邻（即一条边表示一个选手），于是得到2n 阶简单图G ，且图G 满足“性质P ”：{}1,2,,1k n ?∈- ，度数k ≤的顶点至多1k -个.

只要证，图G 含有哈密顿圈（经过图G 每个顶点的圈），即G 为哈密顿图.

反证法，若图G 中不含哈密顿圈，则集合

H ={G G 是具有性质P 的2n 阶非哈密顿图}

不是空集，从而H 中有极大元0G （边数最多的），于是：

()1.因为0G 非哈密顿图，故其中必有不相邻的顶点，而对于任一对不相邻顶点,u v ，由0G 的极大性，添加边uv 后所得的图1G 便成为哈密顿图，即图1G 中有一个含有边uv 的哈密顿圈，于是在0G 中有一条以u 、v 为起、终点的哈密顿路：

122n v v v （其中12,n u v v v ==）.

()2.对于0G 中任一对不相邻顶点,u v ，度数()(), d u d v 中至少有一个1n ≤-. 事实上，因顶点,u v 不相邻，据()1知，0G 中有一条以u 、v 为起终点的哈密顿路：

122n v v v （其中12,n u v v v ==），假若()(), d u n d v n ≥≥，若()d u r n =≥，

与u （即1v ）相邻的r 个顶点记为12,,,r k k k v v v ()1222r k k k n =<<<< ，则对于每个1,2,,j r = ，顶点1j k v -都不与2n v （即v ）相邻，否则在0G 中就有哈密顿圈：

1212211j j k n n k v v v v v v v -- ，这与0G 的选择矛盾.

所以 ()()()21211d v n r n n n ≤--≤--=-，而这又与()d v n ≥的假设矛盾.

()3.据()2知，0G 中必有度数1n ≤-的顶点，即集合

()(){},1v v V G d v n E =∈≤-不是空集，设1v 是集E 中度数最大的一个点，

记()(){}

1max 1d v m d v v n ==∈E ≤-，据性质P 知，集E 中至多有2n -个点，从而在0G 中至少有2n +个点的度数皆n ≥，于是在这2n +个点中必有一个不与1v 相邻的点（因为与1v 相邻的点只有m 个，而1m n ≤-），设该顶点为2n v ，（于是()2n d v n ≥）.

既然1v 与2n v 不相邻，据0G 的极大性，有一条经过0G 所有顶点的哈密顿路：

122n v v v ，在这条哈密顿路上，与1v 相邻的m 个点记为12,,,m k k k v v v ，

()1222m k k k n =<<<< . 据()2的证法知，对每个11,2,, , j

k j m v -= 都不与2n v 相邻，而据性质P 中1k m n =≤-的情形知，在12111,,,m k k k v v v --- 这m 个点中，至少有一个

点的度数1m ≥+（因1m n ≤-，据性质P ，度数m ≤的顶点至多1m -个），设1t k v -是这样一个点，即()11t k d v m -≥+，又由m 的定义（m 是集E 中所有点的最大度数，而集E 中含有0G 中度数1n ≤-的所有点），既然()

11t k d v m -≥+，故该点不在集E 中，故进而知()1t k d v n -≥，又据前所选择，()2n d v n ≥，于是得到两个不相邻的顶点，其度数皆n ≥，从而与()2矛盾.

故原假设不真，因此图G 中有哈密顿圈，即本题的结论成立.

18、在一个九人小班中，已知没有4个人是相互认识的；求证：这个班能分成4个小组,使得每个小组中的人是互不认识的.

证：以九个点表示这九个人，如果某两人相识，则在相应两点间连红线，如不相识，则连蓝线，如此得九阶两色完全图G .

引理一：九阶红蓝两色完全图G 中，若不存在红色4K ，则必存在蓝色3K .

引理一证明：若G 中有一点1V 发出的蓝线4≥条，设为1,2,3,4,5i VV i =，据条件，2345,,,V V V V 之间至少有一条蓝边，例如23V V ，则123VV V 构成蓝色3K ，

若G 中每点发出的蓝线3≤条，即每点发出的红线5≥条，由于G 中“红度”奇顶点个数为偶数，其中必有一点1V 发出的红线6≥条，设1j VV 为红线()2,3,4,5,6,7j =，而由234567V V V V V V 组成的两色6K 中，据Ramsey 定理，必有单色3K ，且必是蓝色的.(若234V V V 为红色3K ，则1234VV V V 组成红色4K ，不合条件).

引理二：六阶红蓝两色完全图1G 中，有5条蓝边，且构成蓝

色5-圈，其余的边皆为红边；2G 为蓝色三角形，现将1G 的六

点与2G 的三点间两两连线红蓝染色，如此得九阶红蓝两色完全

图G ，如果G 中不存在红色4K ，则必可将G 中的九个点分为

四组，在每一组的点中，两两连线皆为蓝色．

引理二的证明：为表述方便，将红、蓝边分别用虚、实线表示，并将1G 的蓝色5-圈画成正五边形12345A A A A A ，2G 为蓝色三角形123VV V ，

（如图所示）. 五边形的五条对角线与五边形的中心0A ，共作成五个红色3K ，2G 的每个顶点i V ，向这每个红色3K 顶点发出的三条边中，必有一条蓝边.

2121

()1.若2G 的每个顶点i V 都与0A 有蓝边相邻，则分组{}0123,,,A V V V ，{}12,A A ， {}{}345,,A A A 合于条件；

()2.若2G 中只有两个顶点12,V V 与0A 有蓝边相邻，而3V 与0A 无蓝边相邻，由于上述五边形的每个顶点只能控制两个红色3K ，则3V 至少要与12345A A A A A 中的三点有蓝边相邻，于是必有两个相邻顶点，例如12A A 向3V 发出蓝边，这时分组

{}{}{}{}123120345,,,,,,,,A A V V V A A A A 合于条件；

()3.若2G 中只有一个顶点1V 与0A 有蓝边相邻，而23,V V 与0A 无蓝边相邻，则 23,V V 各至少要与12345A A A A A 中的三点有蓝边相邻，其中必有一点，例如1A 向23V V 发出蓝边，则分组{}{}{}{}011232345,,,,,,,,A V A V V A A A A 合于条件；

()4.若2G 中的每一顶点都不与0A 蓝边相邻，则123,,V V V 各至少要与12345A A A A A 中的三点有蓝边相邻，则或者有一点，例如1A 向123VV V 都发出蓝边，这时有分组 {}{}{}{}112323450,,,,,,,,A V V V A A A A A ；或者一点例如1A ，向2G 中的一边例如 12VV 发出蓝边，另有两个相邻顶点，例如23A A 向3V 发出蓝边，这时有分组 {}{}{}{}112233450,,,,,,,,A V V A A V A A A .引理得证.

回到本题，据引理一，设123VV V 为蓝色3K ；其余六点记为,,,,,A B C D E F ，在由,,,A B C D 组成的4K 中，必有蓝边，设为AB ；在由,,,C D E F 组成的4K 中，必有蓝边，设为CD ；其余两点,E F ，如连有蓝边，则有分组{}{}{}{}123,,,,,,,,V V V A B C D E F ；今设EF 为红边，考虑由ABCDEF 六点组成的图0G ：

()i 如在0G 中，自,E F 发出的边都为红边，由于四点组

{}{}{}{},,,ACEF ADEF BCEF BDEF 中都有蓝边，

则,,,AC AD BC BD 都是蓝边，因,AB CD 为蓝边，

于是{},,,A B C D 为蓝色4K ， F

这时有分组{}{}{}{}123,,,VV V ABCD E F

().ii 若,E F 都向{},,,A B C D 发出蓝色边，据对称性，本质不同的情况有三种：（甲）.,EA FB 为蓝边，这时有分组{}{}{}{}123,,,VV V EA

FB CD （乙）.,EA FD 为蓝边，考虑四点组{}EBFC ，如BC 为蓝边，则有分组

{}123,VV V {}{}{},,EA DF BC ；如BE 为蓝边，则有分组{}123,VV V {}{}{},,ABE CD F ；如EC 为蓝边，化为情形（甲）.

（丙）.,EA FA 为蓝边，考虑四点组{}{},EBFC EBFD ，当,BC BD 为蓝边，则有分组{}123,VV V {}{}{},,BCD FA

E ，其它蓝边情况前面均讨论过. ().iii 若,E

F 中，F 不发蓝边，止有E 发蓝边，本质不同的情况有三种：

（甲）.E 只发一条蓝边，不妨设为,EA 考虑四点组{}{},EBFC EBFD ，得,BC BD 为蓝边，此时有分组 {}123,VV V {}{}{},,BCD AE F

（乙）.E 只发两条蓝边，本质不同的情况有两种：若,EA EC 为蓝边，考虑四点组{}EBFD ，得BD 为蓝边，则ABDCE 为蓝色五边形，据引理二及前面的讨论，知结论成立；若,EA EB 为蓝边，则有分组 {}123,VV V {}{}{},,ABE CD F

（丙）.E 至少发出3条蓝边，则必有蓝色三角形ABE (或CDE )此时有分组 {}123,VV V {}{}{},,ABE CD F .综上，得结论成立.

19、图G 中，若某四点之间恰有一条边，则称这样的四点组为G 的一个“单纯组”，对于所有的50阶图G ，求“单纯组”数目的最大值．

解：任取G 中的一条边ab ，并另行复制G 的两个版本12, G G ；

在1G 中关注点a ：对于1G 中异于,a b 的每个点c ，作如下调整，如果ca 间已连有边，则补连cb 边，（若cb 已连边，则不必再施该步骤）；如果ca 间未连边，则撤销cb 边，（若cb 未连边，则不必再施该步骤）；对每个点c 都作这样的处理后，1G 便化为图A ，称A 为G 的“A -型替换图”；

在2G 中关注点b ：对于2G 中异于,a b 的每个点c ，作如下调整，如果cb 间已连有边，则补连ca 边，（若ca 已连边，则不必再施该步骤）；如果cb 间未连边，则撤销ca 边，（若ca 未连边，则不必再施该步骤）；对每个点c 都作这样的处理后，2G 便化为图B ，称B 为G 的“B -型替换图”；

今用()S G 表示图G 中“单纯组”的个数，我们来证明:

图论算法及其MATLAB程序代码

图论算法及其MATLAB 程序代码求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法：设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j)

图论张先迪李正良课后习题答案

习题一作者---寒江独钓 1.证明：在n 阶连通图中 (1) 至少有n-1条边； (2) 如果边数大于n-1，则至少有一条闭迹； (3) 如果恰有n-1条边，则至少有一个奇度点。证明: (1) 若G 中没有1度顶点，由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 若G 中有1度顶点u ，对G 的顶点数作数学归纳。当n=2时，结论显然；设结论对n=k 时成立。当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k. (2) 考虑G 中途径： 121:n n W v v v v -→→→→L 若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。于是： 1i i j i v v v v +→→→→L 为G 中一闭途径，于是也就存在闭迹。 (3) 若不然，G 中顶点度数至少为2，于是由握手定理： ()2()21v V G m d v n m n m n ∈= ≥?≥?>-∑ 这与G 中恰有n-1条边矛盾！ 2.(1)2n ?12n 2?12n ?1 (2)2n?2?1 (3) 2n?2 。证明 :u 1的两个邻接点与v 1的两个邻接点状况不同。所以，两图不同构。 4.证明下面两图同构。 u 1 v 1

证明:作映射f : v i ? u i (i=1,2….10) 容易证明，对?v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b)) (1≤ i ≤ 10, 1≤j ≤ 10 ) 由图的同构定义知，图(a)与(b)是同构的。 5.指出4个顶点的非同构的所有简单图。分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。 (a) v 2 v 3 u 4 u (b)

图论及其应用答案电子科大

图论及其应用答案电子科大 This model paper was revised by the Standardization Office on December 10, 2020

习题三：证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通，而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价：（1） G 是块（2） G 无环且任意一个点和任意一条边都位于同一个圈上；（3） G 无环且任意三个不同点都位于同一条路上。（1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。（2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。（3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}

一笔画问题是图论中一个著名的问题

一笔画问题是图论中一个著名的问题。一笔画问题起源于柯尼斯堡七桥问题。数学家欧拉在他1736年发表的论文《柯尼斯堡的七桥》中不仅解决了七桥问题，也提出了一笔画定理，顺带解决了一笔画问题[1]。一般认为，欧拉的研究是图论的开端。与一笔画问题相对应的一个图论问题是哈密顿问题。目录[隐藏] 1 问题的提出 2 一笔画定理 2.1 定理一 2.2 定理二 3 例子 3.1 七桥问题 3.2 一个可以一笔画的例子 4 一笔画问题与哈密顿问题 5 参见 6 参考来源 [编辑] 问题的提出一笔画问题是柯尼斯堡问题经抽象化后的推广，是图遍历问题的一种。在柯尼斯堡问题中，如果将桥所连接的地区视为点，将每座桥视为一条边，那么问题将变成：对于一个有着四个顶点和七条边的连通图G(S,E)，能否找到一个恰好包含了所有的边，并且没有重复的路径。欧拉将这个问题推广为：对于一个给定的连通图，怎样判断是否存在着一个恰好包含了所有的边，并且没有重复的路径？这就是一笔画问题。用图论的术语来说，就是判断这个图是否是一个能够遍历完所有的边而没有重复。这样的图现称为欧拉图。这时遍历的路径称作欧拉路径（一个圈或者一条链），如果路径闭合（一个圈），则称为欧拉回路[1]。一笔画问题的推广是多笔画问题，即对于不能一笔画的图，探讨最少能用多少笔来画成。 [编辑] 一笔画定理对于一笔画问题，有两个判断的准则，它们都由欧拉提出并证明[1]。 [编辑] 定理一有限图G是链或圈的充要条件是：G为连通图，且其中奇顶点的数目等于0或者2。有限连通图G是圈当且仅当它没有奇顶点[2]。证明[2][3]：必要性：如果一个图能一笔画成，那么对每一个顶点，要么路径中“进入”这个点的边数等于“离开”这个点的边数：这时点的度为偶数。要么两者相差一：这时这个点必然是起点或终点之一。注意到有起点就必然有终点，因此奇顶点的数目要么是0，要么是2。充分性：如果图中没有奇顶点，那么随便选一个点出发，连一个圈C1。如果这个圈就是原图，那么

经典图论问题

5经典图论问题 5.1 一笔画问题一笔画算法即是从起点a开始选择关联边（第一这条边不是往回倒，第二这条边在前面延伸路上没有出现过）向前延伸，如果到达终点b，得到a—b迹，判断路上的的边数是否为图的总边数，是就终止，否则选择迹上某个关联边没有用完的顶点v，用同样方式再搜索v—v的闭迹，添加到a—b迹上，即得到a—v---v—b迹，如果这个迹的边数还没有达到总边数，则再选择迹上某个关联边没有用完的顶点。。。。。。逐步扩展即可。

二、弗罗莱（Fleury ）算法任取v 0∈V(G)，令P 0=v 0；设P i =v 0e 1v 1e 2…e i v i 已经行遍，按下面方法从中选取e i+1：（a ）e i+1与v i 相关联；（b ）除非无别的边可供行遍，否则e i+1不应该为G i =G-{e 1,e 2, …, e i }中的桥（所谓桥是一条删除后使连通图不再连通的边）；（c ）当（b ）不能再进行时，算法停止。 5.2 中国邮递员问题（CPP ）规划模型：设ij x 为经过边j i v v 的次数，则得如下模型。 ∑∈= E v v ij ij j i x z ?min ∑ ∑ E ∈E ∈∈=j i i k v v i v v ki ij V v x x , E ∈∈≤j i ij v v N x ,1 ..t s

5.3旅行推销员问题（TSP，货郎担问题）（NPC问题）定义：包含图G的所有定点的路（圈）称为哈密顿路（圈），含有哈密顿圈得图称为哈密顿图。分析：从一个哈密顿圈出发，算法一：（哈密顿圈的充要条件：一包含所有顶点的连通子图，二每个顶点度数为2）象求最小生成树一样，从最小权边加边，顶点度数大于3以及形成小回路的边去掉。算法二：算法三：

图论王树禾答案

图论第一次作业 By byh

|E(G)|,2|E(G)|2G υυ??≤ ??? ?? ??? 1.1 举出两个可以化成图论模型的实际问题略 1.2 证明其中是单图证明：（思路）根据单图无环无重边的特点，所以最大的情形为任意两个顶点间有一条边相连，即极端情况为。

?1.4 画出不同构的一切四顶单图 ?0条边：1条边： ?2条边：3条边： ?4条边：5条边：?6条边：

1.10G?H当且仅当存在可逆映射θ:V G→V H，使得uv∈E G?θuθv∈E H，其中G和H是单图。（证明充分性和必要性） ?必要性 ?若G?H，由定义可得，存在可逆映射θ:V G→V Hφ:E G→E(H)当且仅当ψ G e=uv时，ψHφe=θuθ(v)，所以uv∈E G? θuθv∈E H ?充分性 ?定义?:E G→E(H)，使得uv∈E G和θuθv∈E(H)一一对应，于是?可逆，且ψ e=uv的充要条件是ψHφe=θuθv，得G?H G

1.12求证(a)?K m ,n =mn，(b)G是完全二分图，则?G≤1 4 v G2 ?(a)对于K m ,n ，将顶集分为X和Y，使得X∪Y=V K m,n， X∩Y= ?，X=m，Y=n，对于X中的每一顶点，都和Y中所有顶点相连，所以?K m,n =mn ?(b)设G的顶划分为X,Y，X=m,Y=v?m，则?G≤ ??K m ,v-m =v?m m≤v2 4

?证明： ?(a)第一个序列考虑度数7,第二个序列考虑6,6,1 ?(b)将顶点v分成两部分v’和v’’ ?v’ = {v|v= v i, 1≤ i≤ k}, ?v’’ = {v|v= v i, k< i≤ n} ?以v’点为顶的原图的导出子图度数之和小于 ?然后考虑剩下的点贡献给这k个点的度数之和最大可能为

图论算法及matlab程序的三个案例

图论实验三个案例单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②；实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma)

图论讲义第3章-匹配问题

第三章匹配理论 §3.1 匹配与最大匹配定义3.1.1 设G 是一个图, )(G E M ?，满足:对i e ?,M e j ∈，i e 与j e 在G 中不相邻，则称M 是G 的一个匹配。对匹配M 中每条边uv e =，其两端点 u 和 v 称为被匹配M 所匹配，而 u 和 v 都称为是M 饱和的(saturated vertex )。注:每个顶点要么未被M 饱和, 要么仅被M 中一条边饱和。定义3.1.2 设M 是G 的一个匹配, 若G 中无匹配M ′, 使得||||M M >′, 则称M 是G 的一个最大匹配；如果G 中每个点都是M 饱和的, 则称M 是G 的完美匹配(Perfect matching ). 显然, 完美匹配必是最大匹配。例如，在下图G 1中，边集{e 1}、{e 1,e 2}、{e 1,e 2,e 3}都构成匹配，{e 1,e 2,e 3}是G 1的一个最大匹配。在 G 2中，边集{e 1,e 2,e 3,e 4}是一个完美匹配，也是一个最大匹配。定义3.1.3 设M 是G 的一个匹配, G 的M 交错路是指其边M 和M G E \)(中交替出现的路。如果G 的一条M 交错路(alternating path)的起点和终点都是M 非饱和的，则称其为一条M 可扩展路或M 增广路(augmenting path)。定理 3.1.1(Berge,1957) 图G 的匹配M 是最大匹配的充要条件是G 中不存在M 可扩展路。证明:必要性:设M 是G 的一个最大匹配。如果G 中存在一个M 可扩展路P ,则将P 上所有不属于M 的边构成集合M ′。显然M ′也是G 的一个匹配且比M 多一条边。这与M 是最大匹配相矛盾。充分性:设G 中不存在M 可扩展路。若匹配M 不是最大匹配，则存在另一匹配M ′,使 ||||M M >′. 令 ][M M G H ′⊕=，(M M M M M M ′?′=′⊕∩∪称为对称差)。则H 中每个顶点的度非1即2(这是因为一个顶点最多只与M 的一条边及M ′的一条边相关联)。故H 的每个连通分支要么是M 的边与M ′的边交替出现的一个偶长度圈，要么是M 的边与M ′的边交替出现的一条路。由于||||M M >′，H 的边中M ′的边多于M 的边，故必有H 的某个连通分支是一条路，且始于M ′的边又终止于M ′的边。这条路是一条M 可扩展路。这与条件矛盾。证毕。

图论习题参考答案

二、应用题题0：（1996年全国数学联赛）有n （n ≥6）个人聚会，已知每个人至少认识其中的[n /2]个人，而对任意的[n /2]个人，或者其中有两个人相互认识，或者余下的n -[n /2]个人中有两个人相互认识。证明这n 个人中必有3个人互相认识。注：[n /2]表示不超过n /2的最大整数。证明将n 个人用n 个顶点表示，如其中的两个人互相认识，就在相应的两个顶点之间连一条边，得图G 。由条件可知，G 是具有n 个顶点的简单图，并且有（1）对每个顶点x ， )(x N G ≥[n /2]；（2）对V 的任一个子集S ，只要S ＝[n /2]，S 中有两个顶点相邻或V-S 中有两个顶点相邻。需要证明G 中有三个顶点两两相邻。反证，若G 中不存在三个两两相邻的顶点。在G 中取两个相邻的顶点x 1和y 1,记N G (x 1)＝{y 1,y 2,……,y t }和N G (y 1)={x 1,x 2,……,x k },则N G (x 1)和N G (y 1)不相交，并且N G (x 1)（N G (y 1)）中没有相邻的顶点对。情况一；n=2r ：此时[n /2]＝r ，由（1）和上述假设，t=k=r 且N G (y 1)＝V-N G (x 1)，但N G (x 1)中没有相邻的顶点对，由（2），N G (y 1)中有相邻的顶点对，矛盾。情况二；n=2r+1: 此时[n /2]＝r ，由于N G (x 1)和N G (y 1)不相交，t ≥r,k ≥r,所以r+1≥t,r+1≥k 。若t=r+1,则k=r ，即N G (y 1)=r ，N G (x 1)＝V-N G (y 1)，由（2），N G (x 1)或N G (y 1)中有相邻的顶点对，矛盾。故k ≠r+1，同理t ≠r+1。所以t=r,k=r 。记w ∈V- N G (x 1) ∪N G (y 1),由（2），w 分别与N G (x 1)和N G (y 1)中一个顶点相邻，设wx i0∈E, wy j0∈E 。若x i0y j0∈E ，则w ，x i0, y j0两两相邻，矛盾。若x i0y j0?E ，则与x i0相邻的顶点只能是(N G (x 1)-{y j0})∪{w},与y j0相邻的顶点只能是(N G (y 1)-{x j0})∪{w}。但与w 相邻的点至少是3，故N G (x 1)∪N G (y 1)中存在一个不同于x i0和y j0顶点z 与w 相邻，不妨设z ∈N G (x 1)，则z ，w ，x i0两两相邻，矛盾。题1：已知图的结点集V ={a ,b ,c ,d }以及图G 和图D 的边集合分别为： E (G )={(a ,a ), (a ,b ), (b ,c ), (a ,c )} E (D)={, , , , } 试作图G 和图D ，写出各结点的度数，回答图G 、图D 是简单图还是多重图？解： a d a d b c b c 图G 图D 例2图