主要证明至少三人可以讲同一语言．

把９人看成９点v1,v2,v3,v4,v5,v6,v7,v8,v9
如两人会同一种语言就在两点间联线并着染相应的颜色．
便构成一个简单图Ｇ（每三点至少有一边）
用点Ｖ１分两种情况分析：
1)点v1与其他8点都相邻，（即有连线）由抽屉原则（至多三种语言）
得至少有两边同色，不妨设为（V1,V2),(V1,V3).显而易见v1v2v3为同色
三角形．即１，２，３三人讲同一语言．
2)点V1与其他8点中至于少一点（设v2)不相邻．因每三点至少有一边．
故V3......V9发出到v1 或V2的边至少有7条，且至少有4条是连接
同一点.设此点为v1,边为（v1,v3),(v1,v4),(v1,v5),(v1,v6).  因从v1出发
至多有三色边，故上述4边必有两条同色．设为（v1,v3),(v1,v4),则
三角形v1v3v4为同色．１．３．４三人讲同种语言．
把图画一下看起来简单．就是反复用抽屉原则.

其实很简单,只要证明有一点发出两条同色线.即有存在同色三角形.
因为是证明题,要严密.只能分两种情况来讲
v1有线发出.和v1没线发出或不够线发出(必有V2有同色线发出.)
图论中通常反复设研究为第一点V1.所以看起来不太清楚.
只要同构便是同一关系,好处在于不必被很多没用的信息打扰.
echooooo的图,我看不懂.图论用点和线表示逻辑关系.G=(V,E)
点用v1,v,2,....线用e1,e2,e3....也可用(v1,v2)表示线即两点的
相邻关系.,建议你重画一下便知了(要染色),我实在不会用电脑画图..

我又看了你的图,点表示人.那么线表示??如是语言,则每点至多发出三条线..
题目是证明至少有三人能讲同一种语言.只要构造出一个总是存在的
同色三角形.即可.不必去考虑其他的点(人)的情况.在图论中两点间可画
两条以上线.(不一定要直线)来表示两种以上的相邻关系.如此题,e=(v1,v2),e'=(v1,v2)
e(边)表示语言,即两人会讲两种相同的语言.故通常图论证明是不会一一举例的.
说明的.这也是图论的优点
我用通俗的话讲一下:
1)如v1同V2......V9都有(8个可重复)共同语言.因V1至多会三种语言.由抽屉原则
故V1至少同两人以上会同一语言.设此两人为V2,V3,显然V1,V2,V3三人会同一语言.
2)如V1不能同V2....V9都有共同语言.假设同V2没共同语言.因为每三人至少有两人会
同一语言,故V3一定与V1或V2有至少一个共同语言.同理V4,V5,V6,V7,V8,V9也分别至少与V1,或V2
有一种共同语言.这样V3,V4,V5,V6,V7,V8,V9同V1或V2分别有七个共同语言(可能重复).
由抽屉原则,V1,V2两人中必有一人同V3,V4,V5,V6,V7,V8,V9,共同讲4个以上共同语言.(可能重复)
假设为V1.因V1至多会讲三种语言,有抽屉原则,上述4个语言必有两个是重复(为同种语言)
假设此两个重复的人为V3,V4.也即V1,V3,V4讲同一语言.
命题得证
用抽屉原则把"个"重叠为"种"是关键.当然9人也重要.否则不能用抽屉原则了

[ 本帖最后由 Ted老爸 于 2008-3-6 16:03 编辑 ].

图论/组合都是离散数学的分支.主要研究逻辑关系.对计算机有很大帮助.
个人认为图论较实用,不等式要求构造一些巧妙的过度元素来证明.趣味性可能
更好些..

对的,图论就是用图来帮助我们理顺各逻辑关系的.
有了图方便理解和叙述.(不然讲起来费力).
既然有兴趣.我给你一题玩一下.
有m个新生报到,发现每人都有n人不认识.现要分组:
每组三人.要求,三人全认识,或三人全不认识.
求有多少种分组.(m,n,足够大).
只要有式子有说明,不必化简..

其实初中生也是可以学离散数学的.我也是初中在业余数学学校(前身)学了一些.回家
找书看一下.当时流行图论/数论题.(我不是机算机专业的),现在记得些..

对,认识是相互的.:.

把m人看作m点.如认识就连红线,不认识连黑线.
找一下有多少同色三角形,多少异色三角形.而又有
多少同色角(两条同色边的夹角).用组合记数便可
因为不用抽屉原则,所以人数随意.(不太小即可).

题目要求出至多有多少组合乎要求.即使有人在一种分法下没有入任何组也行的.
我看到过北京小学奥数竞赛有类似题目.这题是我临时想的.因为不想你凑数再递推.
这不是线性的.目的是让你感觉一下图论对逻辑推理的帮助.
如你觉得m,n,整除3才能做,我可以改题.
再提示,同色三角形有三个同色角,而异色三角形有一个同色角(只有两色).每人可发出m-1条线
又有多少同色角???由此推出有多少同色三角形.即有多少组
切记图论只画局部图.这也是我不给你具体数字的目的.有趣吗?.

类似有m点,任三点不共线,能组成有多少三角形.

真的不必太复杂(图论就是帮你简化的)
每点(人)有m-n-1条绿线,n条红线
则有同色角:C(m-n-1)^2+Cn^2(任两条同色边就有一个同色角)
m人就有共:m*(C(m-n-1)^2+Cn^2)
另一方面:
设共有x个组(同色三角形)满足题意:
则有Cm^3-x个异色三角形.
上面已讲,同色三角形有三个同色角,而异色三角形有一个同色角.
共有同色角:3*x+(Cm^3-x)
得m*(C(m-n-1)^2+Cn^2)=3*x+(Cm^3-x)
解得X便可
此题还可有很多变化.但都大同小异.
Ca^b指从a中取b个有的组合.实在想不出如何用电脑表示.

是的，图论和排列组合／抽屉原则都是讨论可能性和必然性．
做排列组合题也不可能用穷举吧．一般也是看局部规律来
推出全部可能，也是说的多，不会有很多符号吧．
我以为图论就是给你一种大家听的懂的话来表示你大脑想的
过程．即使不会图论也是可以思考，如同没学过方程式也能解应用题．
好了，以后有类似看来简单，但无从下手的题目，多半是
图论题．尤其美国，东欧喜欢图论题，有空看看一定有帮助．.