Question

离散数学问题

一个计算机网络由6个计算机组成，每台计算机至少连接到1台其他计算机，证明网络中至少有2台计算机直接连接相同数目的其他计算机！

Answer 1

分析：把题目说明转化为图，所要证明的结论就是至少有2个顶点的度数是相等的。
解：以顶点v1,v2,v3,v4,v5,v6代表6台计算机，如果两台计算机相连，则对应的两个顶点之间有边，如此建立一个图G。由题意，G是无向简单图，是连通图。
G连通，则每个顶点的度数都大于零。G是无向简单图，则每个顶点的度数都小于6。G有6个顶点，度数只有1,2,3,4,5这5个取值，那么至少有2个顶点的度数相等。
所以，网络中至少有2台计算机直接连接相同数目的其他计算机。

追问

我们还没学到图论部分，不是很理解无向简单图连通图之类的概念，能不能用计数那章的鸽巢原理之类的来证明，麻烦你了！

追答

假设6台计算机分别编号a1,a2,a3,a4,a5,a6。根据题意，每一台计算机连接的其余计算机的个数在1与5之间。如果记连接计算机数为1,2,3,4,5的计算机的集合分别是A1,A2,A3,A4,A5。问题就变成了把a1,a2,a3,a4,a5,a6放到集合A1,A2,A3,A4,A5中去，根据鸽巢原理，至少有一个集合的元素数大于1。所以，网络中至少有2台计算机直接连接相同数目的其他计算机！

Answer 2

额，，，，不懂

追问

哥们，你是来刷分的吧！