图论问题选讲答案.doc

《图论问题选讲答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、图论问题讲义答案例1．空间6点，无3点共线，每两点连1条线，染红或蓝．⑴求证：必存在1个以其中三点为顶点的三角形．三边同色；⑵求证：必存在2个以其中三点为顶点的三角形．三边同色．证明：只证第⑵题：设这6个点各连出了di(i＝0，1，2，…，5)条红线及5－di条蓝线，则它们组成了di(5－di)个异色角．di(5－di)＝0，4，6．即di(5－di)≤6．从而图中的异色角≤6×6＝36个．由于一个三角形，若为同色三角形，则异色角数＝0，若不是同色三角形，则异色角数＝2．于是异色三角形数≤＝18．由于共有C＝20个三角形．故至少有2个同色三角形．

2、⑶空间5点，无3点共线，每两点连1条线，染红或蓝，是否一定存在1个以其中三点为顶点的三角形．三边同色？解：不一定，如图，五边形ABCDE中，染了5条红边5条蓝边，其中没有同色三角形．⑷把数1，2，3，4，5任意分成两组，试证明：在这两组数中，总有一组数中存在两个数，它们的差(的绝对值)也在这一组中．解：任取6个点，分别标上1，2，3，4，5，6．每两点连一条线，并在这条线上注上这两点差的绝对值．就得到一个K4，且每条线上所注数字只能是1，2，3，4，5．若数1，2，3，4，5已分成了A、B两组，某条线上的数分入了A组，则把这条线染红，分入了B组，

3、则相应的线染蓝，由于K6的线二染色，必出现同色三角形，即该同色三角形上的三个数分入了同一组，设这个同色三角形的三个顶点的数为a、b、c(a＞b＞c)，则三条线上的数为a－b，b－c，a－c．于是a－b，b－c，a－c分入同一组，即这三个数满足题目要求．例2．6人相互认识或相互不认识，只有当其中4人围坐一圈，相邻2人都互相认识或都互相不认识时，这4人才能坐在一起打牌，问能否找到4人，这4人能够在一起打牌．解用6个点表示这6个人，如果其中某两个人互相认识，则在表示这两个人的点之间连一条红线，否则即连一条蓝线．每点连出5条线，其中必有一种颜色线≥3条，

4、即或红线≥3条或蓝线≥3条．把连出红线≥3条的点称为A类点，连出蓝线≥3条的点称为B类点，则A类点或B类点中必有一类的点数≥3，不妨设A类点数≥3，且v1，v2，v3为A类点，⑴设v1，v2间连蓝线：由于v1，v2都连出了至少3条红线，故其余4点中都分别有3点与此2点连了红线，于是其余4点中必有2点与v1，v2都连红线，不妨设v3，v4与v1，v2都连了红线，则v1，v3，v2，v4四点连出同色四边形．(图1)⑵设v1，v2，v3之间都连红线．由于v1，v2，v3的每一个都至少连出了3条红线，故它们每一个都要与v4，v5，v6中的至少一个连红线．

5、①若v4，v5，v6中有某一点与此三点中的某两点都连红线，例如v4与v1，v2都连红线，则v1，v3，v2，v4这4点连出同色四边形．(图2)②若v4，v5，v6中的每个点都只与v1，v2，v3这三点中的某一点连红线，如图3，则在其余的线中只要有任一条线连红线，就有红色四边形出现．③若v4，v5，v6中的每一点与v1，v2，v3这三点中的某一点连红线，而所有其余的线都是蓝线，则出现蓝色四边形．(图4)例3．给定空间中的9个点，任意4点不共面，每两点间连一线段．求最小的n值，使当对其中任意n条线段用红、蓝两色之一任意染色时，都一定出现一个三边同色的

6、三角形．解：设染色的线段至少有33条，则因9个点之间两两连线有C＝36条，故不染色的线段至多有3条．设点A引出不染色的线段，则去掉点A及所引出的线段．在剩下的点及线段中，若还有点B引出不染色的线段，同样地再将B及引出的线段去掉，依次进行．因不染色的线段至多3条，所以至多去掉3个顶点，则还剩下6个顶点，其两两连线都染上了红色或蓝色．即得到k6（6阶完全图）图的2-染色．熟知，存在同色三角形．其次，存在一个9顶点32条边的图，把图的边2－染色，可使图中无同色三角形．如图所示，将9个点分成5组A＝{V1，V2}、B＝{V3，V4}、C＝{V5，V6}、

7、D＝{V7，V8}、E＝{V9}，两组间连一条红线表示从这两组中任取一点都连有红线；两组间连一条蓝线表示从这两组中任取一点都连有蓝线；每一组内部的点之间不连线．该图构成有9个顶点，有C－4＝32条边，且不存在2－染色的同色三角形．从而，欲求的最小n值为33．例4．在8´8棋盘的方格中分别填写1，2，…，82，每格一个数．证明：必有两个相邻方格(有公共边的方格)，方格中的两个数的差至少为5．⑴证：取每个方格的中心，凡是相邻的两个方格，就把相应的中心连一条线．这样得到了一个图G(图中红线组成的图即为图G)．图G的的直径=14，，故图G中任意两点的距离

8、≤14．若相邻两个方格中填的数相差＜5，则差≤4，于是图G中所填两个数的差≤14×4＝56．但图中填了1与64，此二数必有一条链相连，此