证明含N个（N>1）处理器的网络,至少有两个处理器跟相同数目的处理器相邻.

Question

证明含N个（N>1）处理器的网络,至少有两个处理器跟相同数目的处理器相邻.

Answer 1

证明；用鸽盒原理,
1）不存在孤立的处理器情况.
把N个（N>1）处理器的网络转换成图,N个处理器代表N个顶点,每个处理器与其他处理器相邻代表该顶点的度数.对于N个顶点的图,每个顶点度数最大值为N-1,把N个顶点当做鸽子,顶点度数最大值N-1当做鸽盒,根据鸽盒原理,把N个鸽子放入N-1个鸽盒中,必然有两个鸽子放入同一个鸽盒中,当鸽盒最大值为N-1时,至少有两个鸽子会放入相同鸽盒,至少有两个处理器跟相同数目的处理器相邻得证.
2）存在x个孤立处理器的情况.
X个顶点孤立,有N-x个顶点是连通的,N-x个顶点中每个顶点度数最大为N-x-1,在此情况下,与（1）的证明一样.