第十一讲组合数学之基本图论练习题1．在某国的一些城市之间有空中直达航线，求证：其中必有两个城市，与二者直接通航的城市数目相同。证明：设有空
中直达航线的城市共有n个，于是每个城市至少有1条航线，至多有n?1条航线，由抽屉原理知，用航线条数做抽屉，把n个城市放入这n?1
个抽屉中，必有一个抽屉中有两个城市，即与这两个城市直接通航的城市数目相同。2．怎样用最少数量的航空线路，连结50个城市，才能使
得从一共城市到另一个城市的旅行都至多需乘两次（换乘一次）飞机？解：固定一个城市，并将其他49个城市中的每一个都用一条航线与该城市相
连，就满足了要求，这样需要49条航线。令一方面，将50个城市都连起来，至少需要49条航线，所以最少需要49条航线。3．一条马路
上有6个车站，今有一辆汽车由a1驶向a6，沿途各站可自由上下乘客，但此辆汽车在任何时候至多可载客5人，试证：在此6站中必有两对（四
个不同的）车站A1，B1；A2，B2，使得没有乘客在A1站上而在B1站下（A1在B1之前），也没有乘客在A2站上而在B2站下（A2
在B2之前）。解：令Ckl表示在Ak站上而在Al站下的乘客数，那么我们只需证明在所有15个这样的数中可以找到两个0，且它们的k值和
l值均不相同即可。注意到其中的9个数：C14、C15、C16、C24、C25、C26、C34、C35、C36，它们全部加在一起
，表示汽车从A3站开出后，还没有到A4站时，车上的人数。由于有9个数，而车上只能载5个人，所以其中至少有4个为0，这4个0都有相同
的k值或l值，也就说明可以找到两个数Cpq、Crs，那么这两对车站ap、aq；ar、as即为所求。4．有八种化学药品A、B、C、D
、P、R、S、T，要放进贮藏室保管，出于安全原因，下列各组药品不能贮藏在同一室内：A（R，A（C，A（T，R（P，P（S，S（T，
T（B，B（D，D（C，R（S，R（B，P（D，S（C，S（D，问贮藏这八种药品至少需要多少间房间？解：用八个点A、B、C、D、P
、Q、R、S分别代表这八种药品，将不能放在同一室内的药品用边连结，如图所示。将A染为红色，于是B、S可以为红色；将C染为蓝色，则P
、T为蓝色；最后D、R为黄色。于是至少需要三个房间贮藏这八种化学药品。其中一个最优方案是A、B、S占一间，C、P、T占一间，D、
R占一间。5．证明：平面上有6个点，其中任意3点不共线，把这6个点的连线染成红色或蓝色，则会出现一个同色三角形。证明：先选定一个点
A，由它出发的连线有5条，这5条线中至少有3条是同色的（比如是红色的），那么不妨设AB、AC、AD都是红色的，对于B、C、D三个
点之间的连线，如果有一条是红色的，例如BC是红色，则△ABC是红色三角形；如果B、C、D之间没有红色的线，那么△BCD是蓝色三角
形。所以定理是正确的。6．俱乐部里有99人，每个人声称只愿意和他认识的人在一起打桥牌。证明如果每个人认识的人数大于66，总可以从这
99个人中找出4人，这4个人可以在一起打桥牌。如果每个人认识的人数小于或等于66，那就不一定能找出这样的四个人。解：做一个图，用9
9个点表示99个人，如果两个人不认识，就连一条边，如果每个人认识的人数大于66，那么对每个点连出的边小于等于31(98?67=3
1)，取出一个点A，再取出一个与它不相邻的点B，还剩97个点，与它们相邻的点不超过31×2=62个，所以还能找到C与它们不相
邻，进而同理找到点D和A、B、C不相邻，它们即为所求。如果小于等于66，取出三个各有33个顶点的完全图(98?65=33)，
那么找不出四个不相邻的顶点，也就是命题不成立。7．证明：如果一个图的顶点数为2n，且这个图中没有三角形，则这个图中至多有n2条边。
证明：数学归纳法：当n=1时，显然成立，如果当n=k时命题成立，则当n=k+1时，去掉两个相邻的点和它们连出来的边，则连出来
的边不可能多于2k条，因为剩下的点不能同时和这两个点相连，所以当n=k+1时，最多有k2+2k+1=(k+1)2条边，由数学归纳
法知对于一切自然数n，命题成立。8．称首尾相连但不含圈的一些边是一条链，最长的链的长度也就是这个图的直径，把这些链称为树的主干，证
明：对于一棵树中所有主干，它们都必然经过树的中心。证明：只证明同时有两个中心的情况，只有一个中心的情况是完全类似的。对于直径是2
k?1的图，它的任一点x的离径都大于等于k，这是因为取直径的两个端点a、b，由三角不等式可以知道x和a的距离加上x和b的距离大于等
于a和b的距离，所以图的半径（定义为中心的离径）也大于等于k，所以对于主干上的最中间的两个点，它们的离径都是k，这是因为如果有
到它们的距离大于k的，必然可以和主干的另一边组成大于2k?1的链，矛盾。综上所述可知任意主干中间的两个点必然是中心。9．证明：
若一共连通平面图的点数大于3，则必然存在一个点，它连的边数小于等于5.证明：首先我们证明一个欧拉定理的推论：E≤3V?6。考
虑每两个邻接区域共用一条边，而每个区域都至少由三条边围成，所以3F≤2E，代入欧拉定理V+F?E=2，得3V+3F?3E=
6，3V?6+3F=3E，所以3V?6≥E。然后用反证法证明原命题，若每个点连的边数都大于等于6，则总边数的2倍满足6V≤
2E，但2E≤6V?12，矛盾，所以原命题成立。10．证明：平面图均可以用五种颜色染色，使得相邻的区域不同色。证明：这个题可以
转化为图论问题，每个区域可以看做是一个点，相邻的区域就在点之间连线。用数学归纳法，假设当平面图的点数是k时成立，我们考虑n=k
+1时的情况。由上题的结论知道，存在一个点V0，连的边数小于等于5，考虑除掉这个点以外的图，这个图可以被染成五色，如果V0连的
边数小于等于4，则即可直接染色，因为它至多与4个颜色冲突，总有剩余的选择；如果连的边数等于5，考虑情况如下：如果V1、V2、V
3、V4、V5，连了5种颜色，则我们考虑染1色和3色的V1和V3，考虑原图中所有染了1色和3色的点和它们之间的边构成的子图，那么这个子图中如果V1和V3之间不连通（就是有一条路相连），则我们将含有V1的那个图中1色和3色对调，这样就得到了V1和V3同色，即可直接给V0染色。如果V1和V3连通，V2和V4之间连通，则会出现矛盾。终上所述，平面图均可用五种颜色染色。 |
|
