组合数学

第十二讲数学竞赛中的图论问题

§0 (综述)
§1 (图的基本概念与应用)
§2 (特殊图) (本页)
§3 (染色问题)
§4 (竞赛中的问题)

§2 特殊图

　　每个顶点度数都相等的简单图称为正则图．阶图如果是正则的，则称它为完全图，记为．换句话说，如果简单图的任何两个顶点都邻接，则称为完全图．如果图的顶点集能划分成两个子集，使的任何一条边的两个端点都分别属于两个不同的子集，则称为二分图．连通而无回的图称为树．包含 Euler 环游的图称为图．包含 Hamilton 回路的图称为图．本书正文中所介绍的多种多样的特殊图类是图论的重要研究对象，每个图类都有一些特有的性质．此外像通路、回路等都是图的具有特定性质的子图．数学竞赛中的不少问题正是丛某个侧面反映了各种图和子图的特有的性质．

　　例 4 某团体的所有成员中，任意两个相互认识的人都没有公共的熟人，而任意两个互不认识的人都恰有两个公共的熟人．证明，该团体中每个人所认识的人数都相同．（南斯拉夫数学竞赛题）

　　证我们把该团体的每个成员用一个顶点表示，如果两个人相互认识，那么就在相应的两个顶点间连上一条边，这样做成一个简单图．于是该问题的图论形式是：如果在简单图中，任何两个相邻顶点都没有公共邻接点，而任何两个不相邻顶点都恰有两个共同的邻接点，那么是正则图．

　　设 , 是的任意两个顶点．

　　（i）若 , 相邻．用分别表示 , 的邻接点集．任取，由题设与不相邻，于是与有两个公共邻点，其中一个是，另一个设为，则 .（图 5）

图5

　　令与对应，则得与之间的对应，再令与对应，于是得到与之间的对应．不难证明，这个对应是一一对应．因此

　　（ii）若 , 不相邻．由题设，与有公共邻点，设是其中之一，于是

　　综上，由 , 的任意性，可知是正则图．即该团体中每个人所认识的人数都相同．

　　例 5 某厂生产以六种单色纱线为原料的双色布．如果每种颜色的纱线至少与其它颜色的纱线搭配过．证明，可以挑出三种双色布，恰好使用了六种纱线, （匈牙利奥林匹克数学竞赛题）

　　证用每个顶点表示一种纱线，若两种颜色纱线搭配生产一种双色布则在相应顶点间连上一条边，这样得到一个 6 阶简单图，顶点为

　　因为，所以不妨设又因为，所以必有不同于的邻接点，不妨设为．对于顶点来说，如果，那么，，即为所求．否则的话，由于不与邻接，因而必与中的三个顶点邻接．不妨设与邻接．再看，由于不与邻接，因而与中至少三个点邻接．若与邻接，则，，为所求．若不与邻接，则它与都邻接，这时，，即为所求（图 6）．

图6

　　例 6 舞会上先生、女士各有人．如果没有一位先生同所有女士跳过舞，但每位女士至少同一位先生跳过舞．证明，必有两对舞伴、和、．他们中没有与跳过舞，也没有与跳过舞．（26 届美国大学生数学竞赛题）

　　证作二分图，使的顶点集分为两个子集，, 中的顶点代表先生，中顶点代表女士，代表舞伴的两个顶点之间用边连接．

　　在中取一点，使最大．由题设，因此中必有与不相邻．又由题设，至少同中的一个顶点相邻，设该点为．中除外，与相邻的点尚有个，由的选择，，因此在中与相邻的点内必有不与相邻者，用记这样一个点，于是、和、即为所求（图 7）．

图 7

　　例 7 十名学生参加一次考试，试题十道．已知没有两个学生做对的题目相同．证明，在这十道题中可以找到一道试题，将这道试题取消后，每两个学生做对的题目仍然不会完全相同．

　　证用十个顶点代表十名学生．假定命题不成立，那么当第题取消后，就有一对学生，做对的题目完全相同．因此不妨设原来比只多做对了第题．我们在这样一对点与间连一条边，并在边上标注．照此办理，就得到一个有 10 个顶点，10 条的边的图．图的每条边上注有相应的题号．由图的基本性质可知，如果一个图的边数不少于顶点数，那么它一定有回路．设为一个回路，那么当沿此回路前进时，每通过一条边就相当于做对的题目增加（或减少）了一道．由于各边的编号不同，意味着增减的题号都不相同．由出发经过一个回路后又回到，最后与原来做对的题目完全相同，这显然是矛盾的．因而结论成立．

　　前面所说的图都是无向图，也就是说，连接两个顶点的边是没有方向的．然而在许多实际问题中，要求图的边带有一定的方向，如交通网络中有些通道是单行道，灌溉网中水流有确定的方向等等．如果把这些问题用图来表示，那就要求连接相应的顶点的边有一定的方向，这就产生了有向图的概念．有向图除了具有与无向图的性质相应的一些性质外，还具有一些特有的性质．譬如，再本书第八章定理 3中，取，即可构造出下列问题．