每个人都握手的人数之最大值是多少?(“希望杯”邀请赛试题)
解 由题意,把参加聚会的人视为顶点,其集合记作V,对于
,v∈V,如
果u和v所表示的两个人握了手,则令u和v相邻,得到n阶简单图记作G.则图G中至少有一个顶点u,使得
.这表明,图G不是完全图.
要求的是,聚会中和其他所有的人都握手的人数的最大值,即求图G中度为n-1的顶点个数之最大值.于是即求所有n阶非完全的简单图G中度为n-1的顶点个数之最大值m.
由于图G是非完全图,所以至少有两个顶点u和v是不相邻的,因此d(u)≤n-2,d(v)≤n-2.这表明,m≤n-2.
取一个n-2阶完全图Kn-2,另取两个顶点u和v.令Kn-2中每个顶点都和u与v相邻,而u与v不相邻,得到的图记作Kn-2+u+v.很明显,图Kn-2+u+v不是完全图,而且d(u)=d(v)=n-2,并且对除u,v外任意的顶点x均有d(x)=n-1.这表明m=n-2.即聚会中和每个人都握手的人数之最大值是n-2.
例2 有一个团体,由1982个人组成,其中任意四个人中都至少有一个人认识其他三个人.问该团体中认识其他所有人的成员最少有多少?(上海市竞赛题)
解 把该团体的成员视为顶点,其集合记作V.对于u,v∈V,如果u,v所表示的两名成员彼此认识,则令u和v相邻,否则令u和v不相邻,得到的是一个1982阶简单图G.由已知条件可知,如果1982阶简单图G的任意四个顶点中都至少有一个顶点和其他三个顶点相邻.求图G中至少有多少个度为1981的顶点?
当图G为完全图时,图G的每个顶点的度都是1981.所以有1982个度为1981的顶点.
当图G为非完全图时,图G中必有两个不相邻的顶点u和v,显然有d(u)≤1980,d(v)≤1980.因此,图G中度为1981的顶点的个数≤1980.如果图G中除u和v外还有两个顶点x和y不相邻,则u,v,x和y中不存在和其他三个顶点都相邻的顶点,与图G所具有的性质矛盾.因此图G中除u和v外任意两个顶点都相邻.这说明,对G中除u和v外的任意顶点x,都有d(x)≥1979.如果G中除u和v外的任意顶点x都和u与v相邻,则d(x)=1981.此时,G中度为1981的顶点个数为1980.设G中除u和v外有个顶点x和u与v不都相邻,则
4
有题意,G中除u,v和x之外的任意顶点y和u、v与x都相邻.因此,(u)d≤1980,d(v)≤1980,d(x)≤1980,且d(y)=1981.所以G中度为1981的顶点个数为1879,.这表明,如果1982阶简单图G中任意四个顶点中必有一个顶点和其他三个顶点都相邻,则G中至少有1979个度为1981的顶点.
所以,该团体中认识其他所有人的成员最少是1979.
例3 有7为男生与7为女生参加一次舞会,会后统计出各人的跳舞次数为(按从小到大的顺序):
3,3,3,3,3,4,6,6,6,6,6,6,6,6 (1) 证明其中必有错误.(北京市竞赛题)
证明 用点表示人,如果两个人跳过一次舞,就在相应的两个点之间连一条线.跳舞次数的和就是图中各点的度的和,而(1)中有5个奇数,总和为奇数,这与定理1矛盾!
例4 在例3 中,如果统计的跳舞次数为3,3,3,3,3,5,6, 6,6,6,6,6,6,6,其中是否有错?这里约定男生不与男生跳舞,女生也不与女生跳舞.(北京市竞赛题)
解 我们用黑点表示男生,红点表示女生.在跳过舞的两个人之间用边相连(跳几次就连几次).根据约定,黑点之间互不相连,红点之间也互不相连.所得的图为二部图,显然
所有黑点的度之和=所有红点的度之和=图中的边数 (2) 但题中给出的14个数中仅有一个数5不被3整除,这样(2)的一边被3整除;另一边恰有一个数不被3整除,从而不被3整除.矛盾!
例5晚会上大家握手言欢,试证握过奇次手的人数是偶数.(全国初中数学竞赛试题) <